最优化——单纯形法，单纯形表的求取 -ag凯发k8国际

一般性线性规划标准型为对象总结其基本步骤
$$\begin{array}{ll}\max & z\\ \text{ s.t. }& p^1{x}^1{p}^2{x}^2\cdots p^n{x}^n=b---(1)\\ & c^1{x}^1{c}^2{x}^2\cdots c^n{x}^n=z---(2)\\ & x^j\ge 0,\forall 1\le j\le n\end{array}$$

步骤一：求广义基本可行解

已知一个可逆方阵 $b=\left(p^{j(1)},p^{j(2)},\cdots ,p^{j(m)}\right)$ 满足
$$b^{-1}b\ge 0$$
其中 $1\le j(i)\le n,\forall 1\le i\le m,$ 即 $b$ 是线性规划标准型 的可行基阵

由$b$可以把线性约束(1)$p^1{x}^1{p}^2{x}^2\cdots p^n{x}^n=b$改写为
$$\begin{array}{l}\iff \left(p^{j(1)},\cdots ,p^{j(m)}\right)\left(\begin{array}{c}{x}^{j(1)}\\ ⋮\\ x^{j(m)}\end{array}\right)p^{j(m1)}{x}^{j(m1)}\cdots p^{j(n)}{x}^{j(n)}=b\\ \iff \left(\begin{array}{c}{x}^{j(1)}\\ ⋮\\ x^{j(m)}\end{array}\right)\left(b^{-1}{p}^{j(m1)}\right)x^{j(m1)}\cdots \left(b^{-1}{p}^{j(n)}\right)x^{j(n)}=b^{-1}b\end{array}$$
可以得到一个基本可行解$x=(x^1...x^n{)}^t$的表达式：

$x^b=\left(\begin{array}{c}{x}^{j(1)}\\ ⋮\\ x^{j(m)}\end{array}\right),(x^{j(m1)}...x^{j(n)})=0$

对应线性约束的表达式变为如下:
$$x^b{\hat{p}}^{j(m1)}{x}^{j(m1)}\cdots {\hat{p}}^{j(n)}{x}^{j(n)}={\hat{p}}^{n1}---（3）$$
其中${\hat{p}}^j=b^{-1}{p}^j=\left(\begin{array}{c}{\hat{p}}^{1j}\\ ⋮\\ {\hat{p}}^{mj}\end{array}\right),\forall 1\le j\le n,{\hat{p}}^{n1}=b^{-1}b$

步骤二：求检验数

记 $c^b={\left(c^{j(1)},\cdots ,c^{j(m)}\right)}^t,$

用$c^b$左乘(3) 得 $c^b{x}^b{c}^b{\hat{p}}^{j(m1)}{x}^{j(m1)}\cdots c^b{\hat{p}}^{j(n)}{x}^{j(n)}=c^b{\hat{p}}^{n1}---(4)$

目标函数(2)用$c^b$可以写成： $c^b{x}^b{c}^{j(m1)}{x}^{j(m1)}\cdots c^{j(n)}{x}^{j(n)}=z---(5)$

用(5)-(4)得：
$\begin{array}{c}z-c^b{\hat{p}}^{n1}=\left(c^{j(m1)}-c^b{\hat{p}}^{j(m1)}\right)x^{j(m1)}\cdots \left(c^{j(n)}-c^b{\hat{p}}^{j(n)}\right)x^{j(n)}---(6)\\ z-\hat{z}={\sigma }^{j(m1)}{x}^{j(m1)}\cdots {\sigma }^{j(n)}{x}^{j(n)}---(7)\end{array}$
$c^b{\hat{p}}^{n1}$就是第一步中$x$所求得的一个可行基本解的目标函数值$\hat{z}$，这个可以把$x^b=\left(\begin{array}{c}{x}^{j(1)}\\ ⋮\\ x^{j(m)}\end{array}\right),(x^{j(m1)}...x^{j(n)})=0$带入(4)和(5)就可以看出来。

步骤三：得到单纯形表

其中 $\left({\hat{p}}^{j(1)},\cdots ,{\hat{p}}^{j(m)}\right)=i^m,\hat{z}=c^b{\hat{p}}^{n1}=c^b{b}^{-1}b$

${\sigma }^j=c^j-c^b{\hat{p}}^j=c^j-c^b{b}^{-1}{p}^j,\forall 1\le j\le n$

称 ${\sigma }^1,\cdots ,{\sigma }^n$ 为检验数，可看出基变量检验数等于0

总结

以上是ag凯发k8国际为你收集整理的最优化——单纯形法，单纯形表的求取的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得ag凯发k8国际网站内容还不错，欢迎将ag凯发k8国际推荐给好友。