最優化——單純形法

一般性線性規劃標準型為對象總結其基本步驟
$$\begin{array}{ll}\max & z\\ \text{?s.t.?}& P_1{x}_1+P_2{x}_2+?+P_n{x}_n=b???(1)\\ & c_1{x}_1+c_2{x}_2+?+c_n{x}_n=z???(2)\\ & x_j\ge 0,?1\le j\le n\end{array}$$

步驟一：求廣義基本可行解

已知一個可逆方陣 $B=\left(P_{j(1)},P_{j(2)},?,P_{j(m)}\right)$ 滿足
$$B^{?1}b\ge 0$$
其中 $1\le j(i)\le n,?1\le i\le m,$ 即 $B$ 是線性規劃標準型 的可行基陣

由$B$可以把線性約束(1)$P_1{x}_1+P_2{x}_2+?+P_n{x}_n=b$改寫為
$$\begin{array}{l}?\left(P_{j(1)},?,P_{j(m)}\right)?\begin{array}{c}{x}_{j(1)}\\ ?\\ x_{j(m)}\end{array}?+P_{j(m+1)}{x}_{j(m+1)}+?+P_{j(n)}{x}_{j(n)}=b\\ ??\begin{array}{c}{x}_{j(1)}\\ ?\\ x_{j(m)}\end{array}?+\left(B^{?1}{P}_{j(m+1)}\right)x_{j(m+1)}+?+\left(B^{?1}{P}_{j(n)}\right)x_{j(n)}=B^{?1}b\end{array}$$
可以得到一個基本可行解$X=(x_1...x_n{)}^T$的表達式：

$X_B=?\begin{array}{c}{x}_{j(1)}\\ ?\\ x_{j(m)}\end{array}?,(x_{j(m+1)}...x_{j(n)})=0$

對應線性約束的表達式變為如下:
$$X_B+{\hat{P}}_{j(m+1)}{x}_{j(m+1)}+?+{\hat{P}}_{j(n)}{x}_{j(n)}={\hat{P}}_{n+1}???（3）$$
其中${\hat{P}}_j=B^{?1}{P}_j=?\begin{array}{c}{\hat{p}}_{1j}\\ ?\\ {\hat{p}}_{mj}\end{array}?,?1\le j\le n,{\hat{P}}_{n+1}=B^{?1}b$

步驟二：求檢驗數

記 $C_B={\left(c_{j(1)},?,c_{j(m)}\right)}^T,$

用$C_B$左乘(3) 得 $C_B^T{X}_B+C_B^T{\hat{P}}_{j(m+1)}{x}_{j(m+1)}+?+C_B^T{\hat{P}}_{j(n)}{x}_{j(n)}=C_B^T{\hat{P}}_{n+1}???(4)$

目標函數(2)用$C_B$可以寫成： $C_B^T{X}_B+c_{j(m+1)}{x}_{j(m+1)}+?+c_{j(n)}{x}_{j(n)}=z???(5)$

用(5)-(4)得：
$\begin{array}{c}z?C_B^T{\hat{P}}_{n+1}=\left(c_{j(m+1)}?C_B^T{\hat{P}}_{j(m+1)}\right)x_{j(m+1)}+?+\left(c_{j(n)}?C_B^T{\hat{P}}_{j(n)}\right)x_{j(n)}???(6)\\ z?\hat{z}={\sigma }_{j(m+1)}{x}_{j(m+1)}+?+{\sigma }_{j(n)}{x}_{j(n)}???(7)\end{array}$
$C_B^T{\hat{P}}_{n+1}$就是第一步中$X$所求得的一個可行基本解的目標函數值$\hat{z}$，這個可以把$X_B=?\begin{array}{c}{x}_{j(1)}\\ ?\\ x_{j(m)}\end{array}?,(x_{j(m+1)}...x_{j(n)})=0$帶入(4)和(5)就可以看出來。

步驟三：得到單純形表

其中 $\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$

稱 ${\sigma }_1,?,{\sigma }_n$ 為檢驗數，可看出基變量檢驗數等于0

總結

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

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