第二章 线性规划(2).ppt

1、线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）单单 纯纯 形形 方方 法法1线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）单纯形方法是单纯形方法是G.B.Danzig于于1947年首先发明的。近年首先发明的。近50年来，一直是求解线性规划的最有效的方法之一，被广泛应用年来，一直是求解线性规划的最有效的方法之一，被广泛应用于各种线性规划问题的求解。本节讨论单纯形法的基本概念、于各种线性规划问题的求解。本节讨论单纯形法的基本概念、原理及算法。原理及算法。2

2、线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）给定线性规划问题（标准形式）给定线性规划问题（标准形式）max z=c c1 1x x1 1 +c+c2 2x x2 2+c cn nx xn n a a1111x x1 1+a+a1212x x2 2+a+a1n1nx xn n =b b1 1 a a2121x x1 1+a+a2222x x2 2+a+a2n2nx xn n =b b2 2s.t.s.t.a am1m1x x1 1+a+am2m2x x2 2+a amnmnx xn n =b bm m x xj j 0 0

3、 （j=1j=1，2 n2 n）3线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）一、线性规划问题的解的概念一、线性规划问题的解的概念 可行解可行解 最优解最优解 基基 基解（基本解）基解（基本解）基可行解基可行解 可行基可行基4线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）Max Z=3X1+5X2 X1 +X3 =4s.t.2X2 +X4 =12 3X1 +2X2 +X5=18 Xi0 5线性规划线性规划线性规划线性规划 Linear Linear

4、ProgrammingProgramming（LPLP）X1X2X3X4X5Z004121800640630094-60454001261260-2120184600-64243060272620036*6线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）123456787线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）二、凸集及其顶点二、凸集及其顶点 凸集凸集 顶点（极点）顶点（极点）凸集凸集凹集凹集8线性规划线性规划线性规划线性规划 Linear Lin

5、ear ProgrammingProgramming（LPLP）三、线性规划基本定理三、线性规划基本定理基本定理基本定理 1 线性规划所有可行解组成的集合线性规划所有可行解组成的集合S=X|AX=b，X 0 是是凸集。凸集。基本定理基本定理 2 X是线性规划问题的是线性规划问题的基本可行解的充要条件基本可行解的充要条件为为是是 X 是凸集是凸集S=X|AX=b，X 0 的极点。的极点。基本定理基本定理 3 给定线性规划问题，给定线性规划问题，A是秩为是秩为 m 的的 mn 矩阵，矩阵，（i）若线性规划问题存在若线性规划问题存在可行解，则必可行解，则必存在存在基可行基可行解解 （ii）若线性规划

6、问题存在有界最优解若线性规划问题存在有界最优解，则必，则必存在有存在有界最优界最优基可行解。基可行解。9线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）单纯形法迭代原理及其思路单纯形法迭代原理及其思路单纯形法的初步讨论单纯形法的初步讨论 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化为化为标准型标准型10线性规划线性规划线性规划线性规划 Linear L

7、inear ProgrammingProgramming（LPLP）此线性规划问题此线性规划问题转化为了一个含有四个变量的转化为了一个含有四个变量的标准形标准形线性线性规划问题，规划问题，X3，X4为松弛变量。为求解上面的为松弛变量。为求解上面的LP问题，问题，我们要考虑满足约束条件我们要考虑满足约束条件s.t.并使并使 Z 取得取得Max的的X1，X2，X3，X4的值，由此分析如下的值，由此分析如下-11线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）确定初始基可行解：确定初始基可行解：通过观察可以发现，松弛变量通过观察可

8、以发现，松弛变量X3和和X4对应的等式对应的等式约束条约束条件中的系数矩阵为单位矩阵可以作为初始件中的系数矩阵为单位矩阵可以作为初始可行基可行基矩阵。因此矩阵。因此取：取：X3，X4为基变量；为基变量；X1，X2为非基变量。则可变为为非基变量。则可变为 Max Z=50X1+30X2 s.t.X3 =120-4X1-3X2 X4=50-2X1 -X2 X1，X2，X3，X40 12线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）典式典式 关于基的关于基的典式典式 1、等式等式约束条件中显含约束条件中显含基可行解基可行解 2、

9、目标函数中不、目标函数中不含含基基变量变量Max Z=50X1+30X2s.t.4X1+3X2+X3 =120 2X1+X2+X4=50 X1，X2，X3，X4 0Max Z=50X1+30X2s.t.X3 =120-4X1-3X2 X4=50-2X1 -X2 X1，X2，X3，X4013线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）在典式中令：在典式中令：X1=X2=0 0，我们得到一个我们得到一个基本可行解基本可行解 X1=（X1，X2，X3，X4）T=（0，0，120，50）T，其对应的目标函数值其对应的目标函数值

10、Z1=50X1+30X2=0Max Z=50X1+30X2s.t.X3 =120-4X1-3X2 X4=50-2X1 -X2 X1，X2，X3，X4014线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）最优性检验：最优性检验：基本可行解基本可行解 X1是最优解吗？是最优解吗？显然不是。应寻找更好的解。显然不是。应寻找更好的解。从问题的数学角度分析，在典式的目标函数中，从问题的数学角度分析，在典式的目标函数中，非基非基变量变量X1，X2前的系数都为正，表明前的系数都为正，表明目标函数值有增加的可能。目标函数值有增加的可能。只要

11、将目标函数中只要将目标函数中系数为正的某系数为正的某非基变量非基变量与某一基变量地与某一基变量地位对换。位对换。15线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）换基迭代：换基迭代：进行进行换基就是要从非基变量中选一个变量换基就是要从非基变量中选一个变量入基入基，再从，再从基变量中选一个变量基变量中选一个变量出基出基。并且换基后仍需满足：。并且换基后仍需满足：1 1、新的解仍是基本新的解仍是基本可行解；可行解；2 2、目标函数值将得到改善。目标函数值将得到改善。16线性规划线性规划线性规划线性规划 Linear Linea

12、r ProgrammingProgramming（LPLP）选择入基变量：选择入基变量：由于在目标函数由于在目标函数Z1=50X1+30X2 中中X1，X2的系数都为正，哪一个入的系数都为正，哪一个入基都可使目标函数值得到改善。对于求目标函数极大化的问题，我基都可使目标函数值得到改善。对于求目标函数极大化的问题，我们希望目标值增加得越快越好，因此系数最大的们希望目标值增加得越快越好，因此系数最大的X1入基。入基。选择出基变量：选择出基变量：X1入基后，其值从零增加并由于入基后，其值从零增加并由于约束条件的原因会引起其他变量的约束条件的原因会引起其他变量的变化。由变化。由典式典式以及变量必须取正

13、值的条件，我们可以得到下列不等以及变量必须取正值的条件，我们可以得到下列不等式关系：式关系：X3 =120-4X1-3X2 0 X4=50-2X1-X2 017线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）因为迭代后因为迭代后X2仍为仍为非基变量非基变量（仍会令其取值为零仍会令其取值为零），则上式可简化为：，则上式可简化为：120-4X1 0 50-2X1 0 由此可以看出，虽然我们希望由此可以看出，虽然我们希望X1入基后取正值，且取值越大目标值增加入基后取正值，且取值越大目标值增加越大，但是，越大，但是，X1又得受到又得

14、受到约束。约束。显然，只有显然，只有取取X1=min（120/4，50/2）=25时，才能使上述不等式成立时，才能使上述不等式成立并且恰使并且恰使基变量基变量X4变为零，这正好满足非基变量必须取变为零，这正好满足非基变量必须取值值零的条件，所零的条件，所以可以可令令X4 出基，出基，方程变为：方程变为：4X1+X3 =120-3X2 2X1 =50-X2 -X4化简后得化简后得新的新的典式典式方程方程：X3 =20-X2 +2X4 X1 =25-0.5X2 -0.5X418线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）代入

15、目标函数可得：代入目标函数可得：Z2=1250+5X2-25X4 令令非基变量非基变量X2 =X4=0，即可得一个新的即可得一个新的基本可行解基本可行解 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=

16、1350-5X3-15X419线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）第三个第三个基本可行解基本可行解 X3=（15，20，0，0）T，其对应其对应的目标函数值的目标函数值Z3=1350。此时松弛变量都是此时松弛变量都是非基变量非基变量（取值为零取值为零），这表明资，这表明资源已用源已用 尽；并且目标函数值尽；并且目标函数值Z3=1350-5X3-15X4中中非非基变量基变量X3，X4的系数全为负值，说明目标函数已无法进的系数全为负值，说明目标函数已无法进一步改善，因此该解已是最优解。一步改善，因此该解已是最优解。2

17、0线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）单纯形法小结：单纯形法小结：单纯形法是这样一种单纯形法是这样一种迭代算法迭代算法如下图如下图X1Z1保持保持单调增单调增保持保持可行可行性性保持保持可行可行性性保持保持可行可行性性保持保持可行可行性性保持保持单调增单调增保持保持单调增单调增保持保持单调增单调增X2X3.XkZ2Z3.Zk当当Zk 中中非基变量非基变量的系数的系数全为负值时，这时的的系数的系数全为负值时，这时的基本可行解基本可行解Xk 即即是线性规划问题的最优解，是线性规划问题的最优解，迭代结束。迭代结束。21

18、线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）单纯形表单纯形表对于给定的线性规划问题：对于给定的线性规划问题：max Z=c c1 1x x1 1 +c+c2 2x x2 2+c cn nx xn n a a1111x x1 1+a+a1212x x2 2+a+a1n1nx xn n b b1 1 a a2121x x1 1+a+a2222x x2 2+a+a2n2nx xn n b b2 2s.t.s.t.a am1m1x x1 1+a+am2m2x x2 2+a amnmnx xn n b bm m x xj j 0

19、0 （j=1j=1，2 n2 n）对此问题添加对此问题添加m个松弛变量后，可得下面线性规划问题并且是个松弛变量后，可得下面线性规划问题并且是典式的形式。典式的形式。22线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）线性规划的典式线性规划的典式max Z=c c1 1x x1 1 +c+c2 2x x2 2+c cn nx xn n a a1111x x1 1+a+a1212x x2 2+a+a1n1nx xn n+x+xn+1 n+1 =b=b1 1 a a2121x x1 1+a+a2222x x2 2+a+a2n2nx

20、 xn n +x xn+2 n+2 =b=b2 2s.t.s.t.a am1m1x x1 1+a+am2m2x x2 2+a amnmnx xn n +x xn+mn+m =b bm m x xj j 0 0 （j=1j=1，2 n2 n，n+1n+1，n+2n+2，n+mn+m）23线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）将上面将上面典式中各变量及系数填写在一张表格中就形成下面的典式中各变量及系数填写在一张表格中就形成下面的单纯形表单纯形表cj c1 c2 cn cn+1 cn+mCB基解 x1 x2 xn xn+

21、1 xn+10000 xn+1xn+2xn+m b1 b2 bm a11 a12 a1n 1 a21 a22 a2n am1 am2 amn 112mj=cj zj c1 c2 cn 0 0j=cj zj 1 2 n n+1 n+m 24线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）上面上面的的单纯形表还可以表示成矩阵的形式单纯形表还可以表示成矩阵的形式基基解解 X XS XSb A I j C 0基基解解 XB XN XS XSb B N I j CB CN 025线性规划线性规划线性规划线性规划 Linear Line

22、ar ProgrammingProgramming（LPLP）由单纯形表进行由单纯形表进行迭代步骤：迭代步骤：1.选择选择 Xj 入基：当入基：当 j 行行中中 c cj j=max =max c ci icci i 00 2.选择选择 Xi 出基：当出基：当 i i =min(bmin(bi i/a/aijij)a)aijij 003.3.换基换基迭代：当确定了迭代：当确定了入基变量入基变量 Xj 、出基变量出基变量 Xi 后，以后，以 aij 作为主元对作为主元对单纯形表进行初等行变换（取单纯形表进行初等行变换（取主主运算），运算），即将即将 aij 所在列除采用初等行变换所在列除采用初等

23、行变换将将 aii 变换为变换为1外的其外的其余元素都余元素都变换为变换为 0 0。注意这种。注意这种变换只能采用初等行变换变换只能采用初等行变换!26线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）最优解检验：最优解检验：1、当迭代进行至某一步时，当迭代进行至某一步时，j 行行中所有中所有检验数均小于等于检验数均小于等于零，则零，则迭代结束。迭代结束。表中当前表中当前所指所指基本可行解即为基本可行解即为最优解。最优解。2、当迭代进行至某一步时，当迭代进行至某一步时，j 行行中所有中所有检验数均小于等于检验数均小于等于零，且

24、此时至少有一个零，且此时至少有一个非基变量所对应的非基变量所对应的检验数检验数rk等于零，则原线性等于零，则原线性规划问题有无穷多个规划问题有无穷多个最优解。最优解。3、当迭代进行至某一步时，当迭代进行至某一步时，j 行行中至少有一个中至少有一个检验数检验数 rk 大于零，且该检验数对应的大于零，且该检验数对应的列中列中a1k，a2k，amk，均均小小于等于于等于零，零，则原线性规划问题则原线性规划问题最优解无界（最优解无界（max Z+）。）。27线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）其中其中 b 0，I 是是

25、mm 单位单位矩阵。矩阵。对上面对上面（I 式式）经过迭代，经过迭代，并设最终的最优基矩阵为并设最终的最优基矩阵为B,不妨设不妨设B 为为A 的首的首m 列，则将（列，则将（I 式式）改写后有）改写后有单纯形方法的矩阵描述：单纯形方法的矩阵描述：设线性规划问题设线性规划问题 max Z=CX max Z=CX+0XS s.t.AX b s.t.AX+I XS=b （I 式式）X 0 X，XS 028线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）max Z=CBXB+CNXN+0XS s.t.BXB+NXN+I XS=b X

26、B，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单纯形方法单纯形方法迭代迭代（I 式）式）（B 式式）29线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）单纯形方法的矩阵描述：单纯形方法的矩阵描述：基基解解 XB XN XS XSb B N I j CB CN 0基基解解 XB XN XS XBB

27、-1b I B-1N B-1 j 0 CN-CB B 1N -CB B-1对应对应I 式式的的单纯形表单纯形表 I 表表对应对应B 式式的的单纯形表单纯形表 B 表表迭代30线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）单纯形表计算步骤举例单纯形表计算步骤举例给定线性规划问题给定线性规划问题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线性规划线性

28、规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）基基XB解解B-1bX1X2X3X4 X31204310X4502101检验数检验数 j 5030002120/450/2X111/201/2250201-2050-2520/125211X2150-1/23/210-5-1532线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）人工变量法：人工变量法：当一般线性规划问题标准化之后，我们或可得到一个显当一般线性规划问题标准化之后，我们或可得到一个显然的然的基本可行解（如基本

29、可行解（如松弛变量作为松弛变量作为基变量的一个基变量的一个初始初始基本可基本可行解），这样我们就可以马上进入行解），这样我们就可以马上进入单纯形表的运算步骤。然单纯形表的运算步骤。然而，并非所有而，并非所有问题标准化之后我们都可得到一个显然的问题标准化之后我们都可得到一个显然的初始初始基本可行解，基本可行解，这时就需要我们首先确定出一个这时就需要我们首先确定出一个基本可行解作基本可行解作为为初始初始基本可行解。通常采用的是人工变量法来确定这样的基本可行解。通常采用的是人工变量法来确定这样的初始初始基本可行解。这种情况下一般有两种方法：基本可行解。这种情况下一般有两种方法：1 1、大大M M法（

30、罚因子法）法（罚因子法）2 2、两阶段法、两阶段法33线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）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 ProgrammingProgr

31、amming（LPLP）大大 M 法求解线性规划问题的具体方法与前面的一法求解线性规划问题的具体方法与前面的一般单纯形法相同，就是将般单纯形法相同，就是将M当作一个充分大的数来处当作一个充分大的数来处理。理。35线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（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-1bX1X2X3X

32、4X5X6X7 X441111000X61-21-10-110X790310001检验数检验数 j36线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）基基XB解解B-1bX1X2X3X4X5X6X7 X441111000X61-21-10-110X790310001检验数检验数 j-3-2M4M10-M0037线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）基基XB解解B-1bX1X2X3X4X5X6X7 X4411110004X61-21-10-1101

33、X7903100013检验数检验数 j-3-2M4M10-M00基基XB解解B-1bX1X2X3X4X5X6X7 X4330211-10X21-21-10-110X7660403-31检验数检验数 j-3+6M01+4M03M-4M038线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）基基XB解解B-1bX1X2X3X4X5X6X7 X4330211-101X21-21-10-110-X7660403-311检验数检验数 j-3+6M01+4M03M-4M0基基XB解解B-1bX1X2X3X4X5X6X7 X400001-1

34、/21/2-1/2X23011/30001/3X11102/301/2-1/21/6检验数检验数 j00301.5-1.5-M0.5-M39线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）基基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/

35、4X33/23/20103/4-3/41/4检验数检验数 j-9/2000-3/43/4-M-1/4-M40线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）采用大采用大 M 法求解线性规划问题时可能出现的几种情况：法求解线性规划问题时可能出现的几种情况：1、当采用单纯形法求解、当采用单纯形法求解 LPM 得到最优解时，基变量得到最优解时，基变量不含不含任何任何人工变量，则所得到的最优解就是原问题的最优解；人工变量，则所得到的最优解就是原问题的最优解；2、当采用单纯形法求解、当采用单纯形法求解 LPM 得到最优解时，基变量至少

36、得到最优解时，基变量至少含有含有一个人工变量且一个人工变量且非零非零，则原问题无可行解；，则原问题无可行解；3、当采用单纯形法求解、当采用单纯形法求解 LPM 得到最优解时，基变量至少得到最优解时，基变量至少含有含有一个人工变量且人工变量都一个人工变量且人工变量都为零为零，则通过变换得到原问题最优，则通过变换得到原问题最优解；解；41线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）2、两阶段法、两阶段法I 阶段问题阶段问题 max z=x6 x7 x1+x2+x3+x4 =4 -2x1+x2 x3 -x5+x6 =1 3x2

37、+x3 +x7 =9 x1，x2，x3，x4，x5，x6，x7 0基基XB解解B-1bX1X2X3X4X5X6X7 X441111000X61-21-10-110X790310001检验数检验数 j42线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）第第I 阶段阶段基基XB解解B-1bX1X2X3X4X5X6X7 X441111000X61-21-10-110X790310001检验数检验数 j-2400-10043线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（L

38、PLP）第第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）第第I 阶段阶段基基XB解解B-1bX1X2X3X4X5X6X7 X4330211-101X21-21-10-110-X7660403-311检验

39、数检验数 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）第第II 阶段阶段基基XB解解B-1bX1X2X3X4X5X6X7 X400001-1/21/2-1/2X23011/30001/3X11102/301/2-1/21/6检验数检验数 j00000-1-100303/246线性规划线性规划线性规划线性规划 Line

40、ar Linear ProgrammingProgramming（LPLP）第第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线性规划线性规划线性规划线性规划 Linear Linear ProgrammingProgramming（LPLP）1.目标函数极小化时，解的最优判别：目标函数极小化时，解的最优判别：j 0

41、2.退化：退化：一个或几个一个或几个基变量基变量等于零，一个简单易行的避免退化等于零，一个简单易行的避免退化的方法是的方法是1974年由勃兰德（年由勃兰德（Bland）提出的提出的Bkand 法法则。则。3.无可行解的判别：无可行解的判别：在采用人工变量求解线性规划问题得到最优解时，在采用人工变量求解线性规划问题得到最优解时，如果基变量中仍含有如果基变量中仍含有非零人工变量非零人工变量，则原问题无可行，则原问题无可行解。解。48作业作业作业作业(第三版第三版第三版第三版)习题：习题：1.1(1)(3)1.3(1)1.4(1)1.6(1)(3)1.8 49练习题练习题练习题练习题用单纯形法求解用

42、单纯形法求解:max Z=2X1-X2 +X3 3X1+X2+X3 60 s.t.X1 -X2+2X3 10 X1+X2-X3 20 X1，X2，X3 050练习题练习题练习题练习题用单纯形法求解用单纯形法求解:max Z=6X1+2 X2+10X3+8X4 5X1+6X2-4X3-4X4 20 s.t.3X1 -3X2+2X3+8X4 25 4X1-2X2+X3+3X4 10 X1，X2，X3，X4 051练习题练习题练习题练习题用单纯形法求解用单纯形法求解:max Z=X1+6X2+4X3 -X1+2X2+2X3 13 s.t.4X1 -4X2+X3 20 X1+2X2+X3 17 X1 1，X2 2，X3 352练习题练习题练习题练习题用大用大M法和两阶段法求解法和两阶段法求解:max Z=X1+2 X2+3X3-X4 X1+2X2+3X3 =15 s.t.2X1 +X2+5X3 =20 X1+2X2+X3+X4=10 X1，X2，X3，X4 053作业作业作业作业(第二版第二版第二版第二版)习题：习题：1.1(1)(3)1.3(1)1.4(1)1.7(1)(3)1.8 54