单纯形法(5)

?x1?2x2?x3?x4?11??4x?x?2x?x??3?1235 s.t??2x1?x3?1???xj?0,j?1,2,...,5相应地建立初始单纯形表，这时初始单纯形表中的主体只要将第一阶段中相应的列

换入即可。而目标函数行中数值须重新计算，如下：

cj xB x4 x2 x3 3 -1 -1 0 0 cB 0 -1 -1 3 -1 -1 b 12 1 1 2 4 1 9 -2 x1 [3] 0 -2 1 1 0 0 0 x2 0 1 0 0 0 1 0 0 x3 0 0 1 0 0 0 1 0 x4 1 0 0 0 1/3 0 2/3 -1/3 x5 -2 -1 0 -1 -2/3 -1 -4/3 -1/3 ? 4 \\ \\ ?z x1 x2 x3 ?z 通过一次迭代已得到最优解（?j*T*?0）。最优解x?(4,1,9,0,0)，z?2.

4.3无最优解和无穷多最优解

无最优解与无可行解是两个不同的概念。

无可行解是指原规划不存在可行解，从几何的角度解释是指 线性规划问题的可行域为空集；

无最优解则是指线性规划问题存在可行解，但是可行解的目标函数达不到最优

值，即目标函数在可行域内可以趋于无穷大（或者无穷小）。无最优解也称为无限最优解，或无界解。

无最优解判别定理：

在求解极大化的线性规划问题过程中，若某单纯形表的检验行存在某个大于零

21

的检验数，但是该检验数所对应的非基变量的系数列向量的全部系数都为负数或零，则该线性规划问题无最优解。

无穷多最优解判别原理：

若线性规划问题某个基本可行解所有的非基变量检验数都小于等于零，但其中存在一个检验数等于零，那么该线性规划问题有无穷多最优解。

4.4 退化与循环

如果在一个基本可行解的基变量中至少有一个分量为零，则称此基本可行解是退化的基本可行解。

产生的原因：在单纯形法计算中用最小比值原则确定换出变量时，有时存在两个或两个以上相同的最小比值θ，那么在下次迭代中就会出现一个甚至多个基变量等于零。

退化可能出现以下情况：

① 进行进基、出基变换后，虽然改变了基，但没有改变基本可行解（极点），目标函数当然也不会改进。进行若干次基变换后，才脱离退化基本可行解（极点），进入其他基本可行解（极点）。这种情况会增加迭代次数，使单纯形法收敛的速度减慢。

② 在特殊情况下，退化会出现基的循环，一旦出现这样的情况，单纯形迭代将永远停留在同一极点上，因而无法求得最优解。事实上，已经有人给出了循环的例子.

第五章 单纯形法的矩阵表示

用矩阵描述单纯形法过程的迭代公式，不仅书写简单，而且为修正单纯形法和对偶理论（对偶单纯形法）的介绍提供方便。 线性模型的标准形式为：

maxz?cx

?Ax?b, s.t?

x?0.?假定上述线性规划问题的可行域非空；所有的基本可行解不退化。 若有一个初始可行基B,B为m×m型矩阵，且r(B)?m.即B中含有A中

的m个线性无关的列向量。不失一般性，假定是由A中的前m个列向量组成的，故A有分块矩阵表示形式: A?(B,N)

另外记

x?(xB,xN)T,xB?(x1,x2,...,xm)T,xN?(xm?1,xm?2,...,xn)T

c?(cB,cN)T,cB?(c1,c2,...,cm)T,cN?(cm?1,cm?2,...,cn)T 22

代入上式中可得

?xB?maxz?[cB,cN]??x?N??xB?s.t [B,N]??b? ?xN? xB,xN?0有时也将上式改写成以下形式：

maxz?cBxB?cNxN s.t BxB?NxN?b

xB,xN?0maxz?cBxB?cNxN s.t xB?B?1b?B?1NxN

xB,xN?0 又因为

xB?B-1b-?B-1pjxj.

j?JN所以

z?cBB?1b?(cN?cBB?1N)xN

?cBB?1b??(cj-cBB-1pj)xj.j?JN

因此线性规划问题可表述为如下正则形式：

max z?cBB?1b??(cj-cBB-1pj)xjj?JN?x?B?1b?B?1NxN?B?-1-1s.t ?Bb-Bpjxj??

j?J???xB,xN?0.N

单纯形法中各项准则的矩阵表示为： （1）最优性检验准则

23

非基变量xj的检验数?j 为：?j又令 ?则 ??cj?cBB?1pj,j?JN

?（?m?1,?m?2,?,?n) ,

?cN?cBB?1N ?cN?cBB?1N?0

称σ为检验向量。因此最优性准则用矩阵描述的形式为：

?（2）进基变量选择准则

若?k?maxcj?cBB?1pj,j?JN，则非基变量xk作为进基变量。

j（3）离基变量选择准则

当确定了进基变量为xk后，由式xB?B-1b-?B-1pjxj?B-1b-B-1pkxk

j?JN记B?1b?b',B?1pk?yk,b'及yk均是m维列向量。故由最小比值准则：

?(B?1b)i??1??min??1|(Bpk)i?0??(Bpk)i??(b')i? ?min?|(yk)i?0??(yk)i?(B?1b)lbl' ???1ykl(Bpk)l(B?1b)lbl'令进基变量xk??1，则进基变量为?(Bpk)lykl

pk

,离基变量为p1 ,即第l个基变

量离基，这里的下标l不是变量的自然下标，而是在当前解的基变量中所排序的下标。

下面用矩阵描述单纯形表。 将LP问题写成以下的方程形式：

?0z?BxB?NxN?b,???z?cBxB?cNxN?0, ?x,x?0.?BN表格表示如下：

24

z xB xN 右端项

0 ?1 B cB N cN b 0 将上表中的第二行的（?cBB?1）倍加到第三行上去，再在第二行的等式两端左乘B-1，得到下表

z xB IB xN 右端项

0 ?1 B?1N cN?cBB?1N B?1b ?cBB?1b 0 至此，关于单纯性法的介绍就到这了。事实上，还有改进的单纯形法，限于篇幅，这里不再详细阐述。

总结

通过对单纯形法的认识了解与应用，让我对单纯形法的认识更加深刻，明白了单纯形法在线性规划问题中的重要作用。单纯形法有效地提升了数学规划的应用，很多重大理论诞生之初遭到人们的质疑和反对，但是单纯形法不一样，一诞生就得到人们的青睐，这是因为，单纯形算法的计算简洁明了，计算结果精确有效，它求出的是最优解，超乎很多人的期望和想象力，因此被各个领域频频应用来提高工作效率，节约能量和减少损失，使利润最大化。

参考文献：

[1] 何坚勇 最优化方法 -北京：清华大学出版社，2007.1 [2] 敖特根 单纯形法的产生与发展探析 2011.10 [3] 刘辉 修正单纯形法与单纯形法对比分析 2005.12 [4] 吕林霞 线性规划模型的单纯形法初始可行基选择研究

25

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库单纯形法(5)在线全文阅读。