单纯形法(3)

2.5解的判别定理

对于线性规划问题除了有唯一解还有可能出现无穷多最优解、无界解和无可行解等四种情况，因此，需要建立解的判别准则。

(0)'''Tx?(b,b,?,b,0,?,0)定理2 若为对应于基B的一个基可行解，且对12m于一切

j?m?1,...n,,有?j?0，则X(0)为最优解。若对于一切

(0)

j?m?1,...,n，有?j?0,则该线性规划问题有X

为唯一最优解，若有某个

?j?0, j?m?1,...,n，则该线性规划问题有无穷多解，且均为最优解。

(0)'''Tx?(b,b,?,b,0,?,0)定理3 若为一基可行解，有一个?m?k?0，12m并且对i?1,2,...,m,有ai,m?k?0,那么该线性规划问题具有无界解(或称无

最优解)。

证: 构造一个新的解 x(1)，它的分量为

xi(1)?bi'??ai',m?k(??0)(1)xm?k?? xj因ai,m?k'(1)?0;j?m?1,...,n. j?m?k

?0，所以对任意的??0都是可行解，把x(1)代入目标函数内得到

z?z0???m?k

因?m?k?0，故当λ

→+∞，则z→+∞，故该问题目标函数无界。

对于其他的情形：

当要求目标函数极小化时，一种情况是将其化为标准型。如果不化为标准型，只需在上述定理1，2中把?j?0改为?j?0。

11

2.6 单纯形法求解线性规划问题的程序框图 否 用最优性准则检验当前解是否为最优解 σk=max{σj|σj>0} 是 建立初始单纯形表 求B0，x(0),z0 打印x*，z* 选择进基变量xk，进基向量pk ?k?max{?j|? j?0} 停 止 该问题是否为无最优解问 题 是 打印本问题为无最优解 T所有aik?0,(?k?0,pk?(a1k,a2k,?amk)) 否 选择离基变量xl及离基向量 bi'bl''?0?min{'|aik?0}?' aikalk 以aik为主元素，用高斯消元法进行一次迭 '代，过渡到新的可行基B1，求出x（1），z1 12 第三章 表格单纯形法

3.1单纯型表求解

前面我们提到了，若初始可行基及在做基变换时得到的当前可行基，都化成单位矩阵，则可以表格形式用单纯形法来求解线性规划问题。将这种表格称为单纯形表，其功能与增广矩阵类似。

考虑线性规划问题：

maxz?c1x1?c2x2???cnxn?x1?a1,m?1xm?1???a1nxn?b1,?x?a22,m?1xm?1???a2nxn?b2 ????????????????x?amm,m?1xm?1???amnxn?bm?xj?0,j?1,2,...,n.?? 将目标函数改写为

?z?c1x1?c2x2???cnxn?0

为了便于迭代运算，可将上述方程组写成增广矩阵形式

?z x1 x2 ? xm xm?1 ? xn 右端?0?0?????0??110?0c101?0c2???00?1?cma1,m?1a2,m?1?am,m?1cm?1???a1na2n??amncnb1?b2?????bm?0??

采用行初等变换将c1,c2,?,cm变换为零，使其对应的系数矩阵为单位矩阵,

则

?z x1 x2 ? xm xm?1 ? xn b?0?0?????0?1??10?00?01?0??0?1a1,m?1a2,m?1?am,m?1mi?1???a1na2n?amnmi?100?0cm?1??ciai,m?1?cn??ciain 13

??? ???m??cibi???i?1b1b2?bm说明：最后一行为变检验数?j，其中基变量检验数为0，z则该线性规划问题所对应的单纯形表如下表所示 cj c1 ... cm ??cibi

i?1mcm?1 ... cn cB XB c1 c2 x1 x2 b b1 b2 x1 ............... xm xm?1 ...xn ? 10...0 00... a1,m?1 ...a2,m?1 ...a1n ?1 a2n ?2 ... ... ... ... ...... ... cm xm bm 10

am,m?1...amn ?m ?z ?z值 0 ... ?m?1 ... ?n ?bi?bi注：1. ??min?|aij?0??ii?aij?aik2. ?j?cj??ciaij

i?1m3. max??j|?j?0???k

下面我们来介绍利用单纯性表解线性规划问题的步骤如下

(1) 按数学模型确定初始可行基和初始基可行解，建立初始单纯形表。 (2) 计算各非基变量xj的检验数，若所有检验数

?j?cj??ciaij?0,j?1,2,...,n

i?1m则已得到最优解，可停止计算。否则转入下一步。 (3)在?j?0,j?m?1,...,n中，若有某个?k对应xk的系数列向量pk?0，

?0)??k，确定xk为换入变量，按?规则计算

则此问题是无界，停止计算。否则，转入下一步。 (4) 根据max(?jbibl??min(|aik?0)?

aikaik5) 以alk为主元素进行迭代，把xk所对应的列向量

14

pk?(a1k,a2k,...,alk,...,amk)T变换为(0,0,...,1,...,0)T

将xB列中的xl换为xk，得到新的单纯形表。重复(2)～(5)，直到终止。

3.2 用单纯形法求解线性规划问题的举例

例2 线性规划问题的标准形式为：

maxz?3x1?5x2?0x3?0x4?0x5?x1?x3?4?2x?x?1224 s.t???3x1?2x2?x5?18??xi?0,(i?1,2,...,5)用单纯形表解决该问题如下所示：

cj cB 0 0 0 0 5 0 -z 0 5 3 -z x3 x2 x1 XB x3 x4 x5 x3 x2 x5 b 4 12 18 4 6 6 -30 2 6 2 -36 3 x1 1 0 3 1 0 [3] 3 0 0 1 0 5 x2 0 [2] 2 0 1 0 0 0 1 0 0 0 x3 1 0 0 1 0 0 0 1 0 0 0 0 x4 0 1 0 0 0.5 -0.5 -2 1/6 0.5 -1/6 -2 0 x5 0 0 1 0 0 1 0 -1/3 0 1/3 -1 θ - 6 9 4 2

由表格可知，检验数行的元素?j前解为最优解，即为x?0均成立，所以由最优解的判别方法可知，当

?(2,6,2,0,0)T，目标函数值z?36.

通过本题，我们可知用单纯形表解决线性规划问题非常简便快捷，而且非常容

易得出最优解，这也是单纯形表在解决现行规划问题中重要性的表现。

15

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