《5线性规划问题单纯形法.ppt》由会员分享，可在线阅读，更多相关《5线性规划问题单纯形法.ppt（47页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第五章第五章第五章第五章单纯形法单纯形法与单纯形表与单纯形表1线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）图解法的启示图解法的启示1)线性规划问题解的可能情况线性规划问题解的可能情况 a.唯一最优解唯一最优解 b.无穷多最优解无穷多最优解 c.无解（没有有界最优解，无可行解）无解（没有有界最优解，无可行解）2)若线性规划问题的可行域非空，则可行域是一个若线性规划问题的可行域非空，则可行域是一个凸集；凸集；3)若线性规划问题的最优解存在，则一定可以在可若线性规划问题的最优解存在，则一定可以在可行域的凸集的某个顶点上达到。行
2、域的凸集的某个顶点上达到。2线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）单纯形法单纯形法 单纯形方法是单纯形方法是G.B.Danzig于于1947年首先发明的。近年首先发明的。近50年年来，一直是求解线性规划的最有效的方法之一，被广泛应用于来，一直是求解线性规划的最有效的方法之一，被广泛应用于各种线性规划问题的求解。本节讨论单纯形法的基本概念、原各种线性规划问题的求解。本节讨论单纯形法的基本概念、原理及算法。理及算法。3线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgrammi
3、ng（LPLP）单纯形法单纯形法给定线性规划问题（标准形式）给定线性规划问题（标准形式）max z=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn =b1 a21x1+a22x2+a2nxn=b2 s.t.am1x1+am2x2+amnxn =bm xj 0 （j=1，2 n）4线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）单纯形法单纯形法一、线性规划问题的解的概念一、线性规划问题的解的概念 可行解可行解 最优解最优解 基基 基解（基本解）基解（基本解）基可行解基可行解 可行基可行基5线性规划线性规划线性
4、规划线性规划 Linear Linear ProgrammingProgramming（LPLP）单纯形法单纯形法二、凸集及其顶点二、凸集及其顶点 凸集凸集 顶点（极点）顶点（极点）凸集凸集凹集凹集6线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）12345678基解（基解（可行可行）基解（基解（不可行不可行）7线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）单纯形法单纯形法三、线性规划基本定理三、线性规划基本定理基本定理基本定理 1 线性规划所有可行解组
5、成的集合线性规划所有可行解组成的集合S=X|AX=b，X 0 是是凸集凸集。基本定理基本定理 2 X是线性规划问题的是线性规划问题的基本可行解的充要条件基本可行解的充要条件为为是是 X 是凸集是凸集S=X|AX=b，X 0 的的极点极点。基本定理基本定理 3 给定线性规划问题，给定线性规划问题，A是秩为是秩为 m 的的 mn 矩阵，矩阵，（i）若线性规划问题存在若线性规划问题存在可行解，则必可行解，则必存在存在基本可行基本可行解解 （ii）若线性规划问题存在有界最优解若线性规划问题存在有界最优解，则必，则必存在有界存在有界最优最优基本可行解。基本可行解。8线性规划线性规划线性规划线性规划 Li
6、near Linear ProgrammingProgramming（LPLP）单纯形法单纯形法单纯形法迭代原理及其思路单纯形法迭代原理及其思路单纯形法的初步讨论单纯形法的初步讨论例例1.8 求解求解LP问题问题 化为化为标准型标准型Max Z=50X1+30X2s.t.4X1+3X2 120 2X1+X2 50 X1，X2 0Max Z=50X1+30X2s.t.4X1+3X2+X3 =120 2X1+X2+X4=50 X1，X2，X3，X4 0（1.18）9线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）单纯形法单纯形法
7、 此线性规划问题此线性规划问题转化为了一个含有四个变量的转化为了一个含有四个变量的标准形标准形线性线性规划问题，规划问题，X3，X4为松弛变量。为求解上面的为松弛变量。为求解上面的LP问题，我们要问题，我们要考虑满足约束条件考虑满足约束条件s.t.并使并使 Z 取得取得Max的的X1，X2，X3，X4的值，的值，由此分析如下由此分析如下-10线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）单纯形法单纯形法确定初始基可行解：确定初始基可行解：通过观察可以发现，松弛变量通过观察可以发现，松弛变量X3和和X4对应的等式对应的等式约
8、束条约束条件中的系数矩阵为单位矩阵可以作为件中的系数矩阵为单位矩阵可以作为初始初始可行基可行基矩阵矩阵。因此。因此取取 X3，X4为基变量；为基变量；X1，X2为非基变量。则（为非基变量。则（1.181.18）可变为）可变为：Max Z=50X1+30X2 s.t.X3 =120-4X1-3X2 X4=50-2X1 -X2 （1.191.19）X1，X2，X3，X4011线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）单纯形法单纯形法典式典式（1.191.19）或）或（1.181.18）称为关于基的称为关于基的典式典式 1、
9、等式等式约束条件中显含约束条件中显含基可行解基可行解 2、目标函数中不、目标函数中不含含基基变量变量Max Z=50X1+30X2s.t.4X1+3X2+X3 =120 2X1+X2+X4=50 (1.18)X1，X2，X3，X4 0Max Z=50X1+30X2s.t.X3 =120-4X1-3X2 X4=50-2X1 -X2 （1.19）X1，X2，X3，X4012线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）单纯形法单纯形法 在典式在典式（1.19）中令：中令：X1=X2=0，我们得到一个我们得到一个基本可行解基本可
10、行解 X1=（X1，X2，X3，X4）T=（0，0，120，50）T，其对应的目标函数值其对应的目标函数值 Z1=50X1+30X2=013线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）单纯形法单纯形法最优性检验：最优性检验：基本可行解基本可行解 X1 是最优解吗？显然不是。应寻找更好的解。是最优解吗？显然不是。应寻找更好的解。从问题的数学角度分析，在典式从问题的数学角度分析，在典式（1.191.19）的目标函数中，的目标函数中，非基非基变量变量X1，X2前的系数都为正，而此时的前的系数都为正，而此时的X1，X2均取零值，
11、表明均取零值，表明只要增加其值，则只要增加其值，则目标函数值有增加的可能。因此，将目标函目标函数值有增加的可能。因此，将目标函数中数中系数为正的某一系数为正的某一非基变量非基变量与某一与某一基变量基变量地位地位对换对换。14线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）单纯形法单纯形法换基迭代：换基迭代：进行进行换基就是要从非基变量中选一个变量换基就是要从非基变量中选一个变量入基入基，再从基变，再从基变量中选一个变量量中选一个变量出基出基。并且换基后仍需满足：。并且换基后仍需满足：1)新的解仍是基本新的解仍是基本可行解；可
12、行解；2)目标函数值将得到改善。目标函数值将得到改善。15线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）单纯形法单纯形法选择入基变量：选择入基变量：由于在目标函数由于在目标函数 Z1=50X1+30X2 中中X1，X2的的系数都为正，哪一个入基都可使目标函数值得到改善。对于求系数都为正，哪一个入基都可使目标函数值得到改善。对于求目标函数极大化的问题，我们希望目标值增加得越快越好，因目标函数极大化的问题，我们希望目标值增加得越快越好，因此系数最大的此系数最大的X1入基。入基。选择出基变量：选择出基变量：X1入基后，其值从零增
13、加并由于入基后，其值从零增加并由于约束条件的约束条件的原因会引起其他变量的变化。由原因会引起其他变量的变化。由典式典式（1.19）以及变量必须取）以及变量必须取正值（可行）的条件，我们可以得到下列不等式关系：正值（可行）的条件，我们可以得到下列不等式关系：X3 =120-4X1-3X2 0 X4=50-2X1-X2 016线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）单纯形法单纯形法 因为迭代后因为迭代后X2仍为仍为非基变量（非基变量（仍会令其取值为零仍会令其取值为零），则上），则上式可简化为：式可简化为：120-4X1
14、0，且且 50-2X1 0，由此可以看出，虽然我们希望由此可以看出，虽然我们希望X1入基后取正值，取值越大入基后取正值，取值越大目标值增加越大，但是目标值增加越大，但是 X1又得受到以上又得受到以上约束（保证其可行）。约束（保证其可行）。显然，当显然，当取取 X1=min（120/4，50/2）=25时，才能使上述时，才能使上述不等式成立，且此时恰使不等式成立，且此时恰使基变量基变量X4变为零，这正好满足非基变变为零，这正好满足非基变量必须取量必须取值值零的条件，所以可零的条件，所以可令令X4 出基，这样，新的基变量变出基，这样，新的基变量变为为X3，X1，而，而 X2，X4 成了非基变量，成
15、了非基变量，则则17线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）单纯形法单纯形法约束约束方程变为：方程变为：4X1+X3 =120-3X2 2X1 =50-X2 -X4化简后得：化简后得：新的新的典式典式方程方程 X3 =20-X2 +2X4 X1 =25-0.5X2 -0.5X418线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）单纯形法单纯形法代入目标函数可得：代入目标函数可得：Z2=1250+5X2-25X4 令令非基变量非基变量X2 =X4=0
16、，即可得一个新的即可得一个新的基本可行解基本可行解 X2=（25，0，20，0）T，其对应的目标函数值其对应的目标函数值Z2=1250，并并完成了第一次完成了第一次迭代。迭代。由于由于目标函数目标函数 Z2=1250+5X2-25X4中中X2的的系数仍为正，该解系数仍为正，该解X2仍不是最优解。重复上述仍不是最优解。重复上述迭代过程得到：迭代过程得到：X2入基，入基，X3出基，则新的出基，则新的典式典式方程变为：方程变为：X1 =15+0.5X3-1.5X4 X2 =20-X3+2X4 Z3=1350-5X3-15X419线性规划线性规划线性规划线性规划 Linear Linear Progr
17、ammingProgramming（LPLP）单纯形法单纯形法第三个第三个基本可行解基本可行解 X3=（15，20，0，0）T，其对应的目标其对应的目标函数值函数值 Z3=1350。此时松弛变量此时松弛变量 都是都是非基变量（取值为非基变量（取值为零），这表明资源已用零），这表明资源已用尽；并且目标函数值尽；并且目标函数值 Z3 =1350-5X3-15X4中中非基变量非基变量X3，X4的系数全为负值，说明目标函数已无的系数全为负值，说明目标函数已无法进一步改善，因此该解已是最优解。法进一步改善，因此该解已是最优解。20线性规划线性规划线性规划线性规划 Linear Linear Progra
18、mmingProgramming（LPLP）单纯形法小结：单纯形法小结：单纯形法是这样一种单纯形法是这样一种迭代算法迭代算法如下图如下图当当 Zk 中中非基变量非基变量的系数的系数全为负值时，这时的的系数的系数全为负值时，这时的基本可行基本可行解解 Xk 即是即是 线性规划问题的最优解，线性规划问题的最优解，迭代结束。迭代结束。X1Z1保持保持单调增单调增保持保持可行可行性性保持保持可行可行性性保持保持可行可行性性保持保持可行可行性性保持保持单调增单调增保持保持单调增单调增保持保持单调增单调增X2X3.XkZ2Z3.Zk 当当 Zk 中中非基变量非基变量的系数的系数全为负值时，这时的的系数的系
19、数全为负值时，这时的基本基本可行解可行解 Xk 即即是线性规划问题的最优解，是线性规划问题的最优解，迭代结束。迭代结束。21线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）单纯形表单纯形表对于给定的线性规划问题：对于给定的线性规划问题：max Z=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2s.t.am1x1+am2x2+amnxn bm xj 0 （j=1，2 n）对此问题添加对此问题添加m个松弛变量后，可得下面线性规划问题并个松弛变量后，可得下面线性规划
20、问题并且是典式的形式。且是典式的形式。22线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）单纯形表单纯形表线性规划的典式线性规划的典式max Z=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn+xn+1 =b1 a21x1+a22x2+a2nxn +xn+2 =b2s.t.am1x1+am2x2+amnxn +xn+m =bm xj 0 （j=1，2 n，n+1，n+2，n+m）23线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）单纯形表
21、：单纯形表：将上面将上面典式中各变量及系数填写在一张表格中就形成下面典式中各变量及系数填写在一张表格中就形成下面的的单纯形表单纯形表cj c1 c2 cn cn+1 cn+2 cn+m CB基基解解 x1 x2 xn xn+1 xn+2 xn+m0000 xn+1xn+2xn+m b1 b2 bm a11 a12 a1n 1 a21 a22 a2n 1 am1 am2 amn 1 1 2 m j=cj zj c1 c2 cn 0 0 0 j=cj zj 1 2 n n+1 n+2 n+m 24线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgrammi
22、ng（LPLP）单纯形表：单纯形表：上面上面的的单纯形表还可以表示成矩阵的形式单纯形表还可以表示成矩阵的形式基基解解 X XS XSb A I j C 0基基解解 XB XN XS XSb B N I j CB CN 0或或25线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）单纯形法单纯形法由单纯形表进行由单纯形表进行迭代步骤：迭代步骤：1)选择选择 Xj 入基：当入基：当 j 行行中中 j=max i i 0 2)选择选择 Xi 出基：当出基：当 i=min bi/aij aij 0 3)换基换基迭代：当确定了迭代：当确定
23、了入基变量入基变量 Xj 、出基变量出基变量 Xi 后，以后，以 aij 作为主元对作为主元对单纯形表进行单纯形表进行取取主主运算运算，取取主主运算运算即即采用初等采用初等行行变换变换将主元将主元 aij 所在列，除所在列，除将将 aii 变变换为换为1而而外，该列中的其余元素外，该列中的其余元素都都变换为变换为 0 0。注意这种。注意这种变变换只能采用初等行变换换只能采用初等行变换!26线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）单纯形法单纯形法最优解检验：最优解检验：1)1)当迭代进行至某一步时，当迭代进行至某一步时
24、，j 行行中所有中所有检验数均小于等于零，检验数均小于等于零，则则迭代结束。迭代结束。表中当前表中当前所指所指基本可行解即为基本可行解即为最优解最优解。2)2)当迭代进行至某一步时，当迭代进行至某一步时，j 行行中所有中所有检验数均小于等于零，检验数均小于等于零，且此时至少有一个且此时至少有一个非基变量所对应的非基变量所对应的检验数检验数 k 等于零，则等于零，则原线性规划问题有原线性规划问题有无穷多个无穷多个最优解最优解。3)3)当迭代进行至某一步时，当迭代进行至某一步时，j 行行中至少有一个中至少有一个检验数检验数 k 大大于零，且该检验数对应的于零，且该检验数对应的列中列中a1k，a2k
25、，amk，均均小小于于等于零等于零，则原线性规划问题，则原线性规划问题最优解无界最优解无界（max Z+）。）。27线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）单纯形方法的矩阵描述：单纯形方法的矩阵描述：设线性规划问题设线性规划问题 max Z=CX max Z=CX+0XS s.t.AX b s.t.AX+I XS=b （I 式式）X 0 X，XS 0其中其中 b 0，I 是是 m m 单位单位矩阵。矩阵。对上面对上面（I 式式）经过迭代，经过迭代，并设最终的最优基矩阵为并设最终的最优基矩阵为B（不妨不妨设设B 为为A
26、 的首的首m 列，则将（列，则将（I 式式）改写后有）改写后有28线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）单纯形方法的矩阵描述：单纯形方法的矩阵描述：max Z=CBXB+CNXN+0XS s.t.BXB+NXN+I XS=b XB，XN，XS 0 max Z=CB B-1+（CN-CB B-1）XN-CB B-1XS s.t.XB+B-1NXN+B-1XS=B-1b XB，XN，XS 0 B 式中式中最优最优目标函数值目标函数值Z*=CB B-1，检验数检验数 CN-CB B-1 0，-CB B-1 0单纯形方法单
27、纯形方法迭代迭代（I 式式）（B 式式）29线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）单纯形方法的矩阵描述：单纯形方法的矩阵描述：基基解解 XB XN XS XSb B N I j CB CN 0基基解解 XB XN XS XBB-1b I B-1N B-1 j 0 CN-CB B 1N -CB B-1对应对应I 式式的的单纯形表单纯形表 I 表表对应对应B 式式的的单纯形表单纯形表 B 表表迭代迭代30线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP
28、）单纯形表计算步骤举例单纯形表计算步骤举例给定线性规划问题给定线性规划问题max z=50X1+30X2s.t.4X1+3X2 120 2X1+X2 50 X1，X2 0max z=50X1+30X2s.t.4X1+3X2+X3 =120 2X1+X2 +X4=50 X1，X2，X3，X4 031线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）单纯形表计算步骤举例单纯形表计算步骤举例max z=50X1+30X2s.t.4X1+3X2+X3 =120 2X1+X2 +X4=50 X1，X2，X3，X4 0基基XB解解B-1b
29、X1X2X3X4 X31204310X4502101检验数检验数 j 5030002120/450/2X111/201/2250201-2050-2520/125211X2150-1/23/210-5-1532线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）单纯形法的进一步讨论单纯形法的进一步讨论人工变量法：人工变量法：当一般线性规划问题标准化之后，我们或可得到一个显然当一般线性规划问题标准化之后，我们或可得到一个显然的的基本可行解（如基本可行解（如松弛变量作为松弛变量作为基变量的一个基变量的一个初始初始基本可行解）基本可行
30、解），这样我们就可以马上进入，这样我们就可以马上进入单纯形表的运算步骤。然而，并非单纯形表的运算步骤。然而，并非所有所有问题标准化之后我们都可得到一个显然的问题标准化之后我们都可得到一个显然的初始初始基本可行解，基本可行解，这时就需要我们首先确定出一个这时就需要我们首先确定出一个基本可行解作为基本可行解作为初始初始基本可行基本可行解。通常采用的是人工变量法来确定这样的解。通常采用的是人工变量法来确定这样的初始初始基本可行解。基本可行解。这种情况下一般有两种方法：这种情况下一般有两种方法：1)1)大大M M法（罚因子法）法（罚因子法）2)2)两阶段法两阶段法33线性规划线性规划线性规划线性规划
31、Linear Linear ProgrammingProgramming（LPLP）单纯形法的进一步讨论单纯形法的进一步讨论1、大、大 M 法（罚因子法）法（罚因子法）max z=-3X1+X3 x1+x2+x3 4 -2x1+x2 x3 1 3x2+x3=9 x1，x2，x3 0LPM max z=-3x1+x3+0 x4+0 x5 Mx6 Mx7 x1+x2+x3+x4 =4 -2x1+x2 x3 -x5+x6 =1 3x2+x3 +x7 =9 x1，x2，x3，x4，x5，x6，x7 034线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgram
32、ming（LPLP）1、大、大 M 法法LPM max z=-3x1+x3+0 x4+0 x5 Mx6 Mx7 x1+x2+x3+x4 =4 -2x1+x2 x3 -x5+x6 =1 3x2+x3 +x7 =9 x1，x2，x3，x4，x5，x6，x7 0基基XB解解B-1bX1X2X3X4X5X6X7 X441111000X61-21-10-110X790310001检验数检验数 j-30100-M-M35线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）1、大、大 M 法法基基XB解解B-1bX1X2X3X4X5X6X7
33、X441111000X61-21-10-110X790310001检验数检验数 j-3-2MM1-M0-M0-M基基XB解解B-1bX1X2X3X4X5X6X7 X441111000X61-21-10-110X790310001检验数检验数 j-3-2M4M10-M0036线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）1、大、大 M 法法基基XB解解B-1bX1X2X3X4X5X6X7 X4411110004X61-21-10-1101X7903100013检验数检验数 j-3-2M4M10-M00基基XB解解B-1bX1
34、X2X3X4X5X6X7 X4330211-10X21-21-10-110X7660403-31检验数检验数 j-3+6M01+4M03M-4M037线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）1、大、大 M 法法基基XB解解B-1bX1X2X3X4X5X6X7 X4330211-101X21-21-10-110-X7660403-311检验数检验数 j-3+6M01+4M03M-4M0基基XB解解B-1bX1X2X3X4X5X6X7 X400001-1/21/2-1/2X23011/30001/3X11102/301/
35、2-1/21/6检验数检验数 j00301.5-1.5-M0.5-M38线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）1、大、大 M 法法基基XB解解B-1bX1X2X3X4X5X6X7 X400001-1/21/2-1/2-X23011/30001/39X11102/301/2-1/21/63/2检验数检验数 j00301.5-1.5-M0.5-M基基XB解解B-1bX1X2X3X4X5X6X7 X400001-1/21/2-1/2X25/2-1/2100-1/41/41/4X33/23/20103/4-3/41/4检验
36、数检验数 j-9/2000-3/43/4-M-1/4-M39线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）采用大采用大 M 法求解线性规划问题时可能出现的几种情况：法求解线性规划问题时可能出现的几种情况：1)当采用单纯形法求解当采用单纯形法求解 LPM 得到最优解时，基变量得到最优解时，基变量不含不含任何任何人工变量，则所得到的最优解就是原问题的最优解；人工变量，则所得到的最优解就是原问题的最优解；2)当采用单纯形法求解当采用单纯形法求解 LPM 得到最优解时，基变量至少得到最优解时，基变量至少含有含有一个人工变量且一个人
37、工变量且非零非零，则原问题无可行解；，则原问题无可行解；3)当采用单纯形法求解当采用单纯形法求解 LPM 得到最优解时，基变量至少得到最优解时，基变量至少含有含有一个人工变量且人工变量都一个人工变量且人工变量都为零为零，则通过变换得到原问题，则通过变换得到原问题最优解；最优解；40线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）2、两阶段法、两阶段法max z=-3X1+X3 x1+x2+x3 4 -2x1+x2 x3 1 3x2+x3=9 x1，x2，x3 0I阶段问题阶段问题 max z=x6 x7 x1+x2+x3+x
38、4 =4 -2x1+x2 x3 -x5+x6 =1 3x2+x3 +x7 =9 x1，x2，x3，x4，x5，x6，x7 041线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）2、两阶段法、两阶段法I 阶段问题阶段问题 max z=x6 x7 x1+x2+x3+x4 =4 -2x1+x2 x3 -x5+x6 =1 3x2+x3 +x7 =9 x1，x2，x3，x4，x5，x6，x7 0基基XB解解B-1bX1X2X3X4X5X6X7 X441111000X61-21-10-110X790310001检验数检验数 j00000
39、-1-142线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）2、两阶段法、两阶段法第第I 阶段阶段基基XB解解B-1bX1X2X3X4X5X6X7 X441111000X61-21-10-110X790310001检验数检验数 j00000-1-1基基XB解解B-1bX1X2X3X4X5X6X7 X441111000X61-21-10-110X790310001检验数检验数 j-2400-10043线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）2、两阶段
40、法、两阶段法第第I 阶段阶段基基XB解解B-1bX1X2X3X4X5X6X7 X4411110004X61-21-10-1101X7903100013检验数检验数 j-2400-100基基XB解解B-1bX1X2X3X4X5X6X7 X4330211-10X21-21-10-110X7660403-31检验数检验数 j60403-4044线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）2、两阶段法、两阶段法第第I 阶段阶段基基XB解解B-1bX1X2X3X4X5X6X7 X4330211-101X21-21-10-110-X
41、7660403-311检验数检验数 j60403-40基基XB解解B-1bX1X2X3X4X5X6X7 X400001-1/21/2-1/2X23011/30001/3X11102/301/2-1/21/6检验数检验数 j00000-1-145线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）2、两阶段法、两阶段法第第II 阶段阶段基基XB解解B-1bX1X2X3X4X5X6X7 X400001-1/21/2-1/2X23011/30001/3X11102/301/2-1/21/6检验数检验数 j00000-1-1基基XB解解
42、B-1bX1X2X3X4X5 X400001-1/2X23011/300X11102/301/2检验数检验数 j00303/2-3010046线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）2、两阶段法、两阶段法第第II 阶段阶段基基XB解解B-1bX1X2X3X4X5 X400001-1/2-X23011/3009X11102/301/23/2检验数检验数 j00303/2基基XB解解B-1bX1X2X3X4X5 X400001-1/2X25/2-1/2100-1/4X33/23/20103/4检验数检验数 j-9/2000-3/447