單純形法

基本可行解的表示式（教材中稱為典式） ：基變量只出現在一個等式的等式約束

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-UHbJsxlP-1607322076772)(最優化—線性規劃.assets/image-20201207112757323.png)]

在選擇保留進基變量所在行的過程中不用考慮進基變量的系數不是正數的行 ,選擇進基變量系數非負的行保留進基變量

思路：①假設已知一個基本可行解??②選擇能夠使目標函數改進的進基變量??③判斷目前的基本可行解是否最優

對于最優規劃
$$\begin{array}{rl}& \max z\\ & \begin{array}{ll}\text{?s.t.?}& P_1{x}_1+P_2{x}_2+?+P_n{x}_n=b\\ & c_1{x}_1+c_2{x}_2+?+c_n{x}_n=z\\ & x_j\ge 0,?1\le j\le n\end{array}\end{array}$$
變換成單純形表（即變換出基變量）：
$$\begin{array}{rl}& \begin{array}{ccccccc}\text{?BV?}& x_1& ?& x_k& ?& x_n& \text{?RHS?}\\ x_{j(1)}& {\hat{p}}_{11}& ?& {\hat{p}}_{1k}& ?& {\hat{p}}_{1n}& {\hat{p}}_{1n+1}\\ ?& ?& ?& ?& ?& ?& ?\\ x_{j(m)}& {\hat{p}}_{m1}& ?& {\hat{p}}_{mk}& ?& {\hat{p}}_{mn}& {\hat{p}}_{mn+1}\\ & {\sigma }_1& ?& {\sigma }_k& ?& {\sigma }_n& z?\hat{z}\end{array}\\ & \text{?其中?}\left({\hat{P}}_{j(1)},?,{\hat{P}}_{j(m)}\right)=I_m,\hat{z}=C_B^T{\hat{P}}_{n+1}=C_B^T{B}^{?1}b\\ & {\sigma }_j=c_j?C_B^T{\hat{P}}_j=c_j?C_B^T{B}^{?1}{P}_j,?1\le j\le n\\ & \text{?稱?}{\sigma }_1,?,{\sigma }_n\text{?為檢驗數，可看出基變量檢驗數等于0?}\end{array}$$
②選擇對應單純形表中檢驗數大于0的變量進基，可使得目標函數改進。

③如果單純形表中檢驗數全都不大于0，那么對應的基本可行解就是最優解。

退化問題：

? 退化問題：基本可行解對應的基變量中存在0元素。本質是多個可行基陣對應于一個基本可行解

? 退化問題的解決：只要設法避免回到已經搜索過的基陣，就可以保證單純形法在有限步內停止。

檢驗數與退化問題：

? 1. 對于求max的線性規劃問題 ，如果所有檢驗數均滿足小于等于0, 而且某非基變量的檢驗數也等于0，則說明優化問題有無窮多最優解。

?

總結

以上是生活随笔為你收集整理的最优化——单纯形法学习心得的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。