线性规划及单纯形法(3)课件.ppt

第一章第一章 线性规划及单纯形法线性规划及单纯形法线性规划及单纯形法(3)课件1.2 1.2 线性规划问题解的基本理论线性规划问题解的基本理论线性规划问题解的基本理论线性规划问题解的基本理论 线性规划及单纯形法(3)课件一、LP问题的各种解 可行解、最优解（最优值）可行解、最优解（最优值）求解求解LPLP问题问题: :求出问题的最优解和最优值求出问题的最优解和最优值线性规划及单纯形法(3)课件1、、可可行行解解：满满足足约约束束条条件件和和非非负负条条件件的的决决策策变量的一组取值变量的一组取值2、最优解、最优解:  使目标函数达到最优值的可行解使目标函数达到最优值的可行解3、最优值、最优值：最优解对应目标函数的取值最优解对应目标函数的取值线性规划及单纯形法(3)课件对于线性规划标准型对于线性规划标准型Max    Z=c1x1+c2x2+…..+cnxns.t.    a11x1+a12x2+….+a1nxn=b1         a21x1+a22x2+….+a2nxn=b2              ………………….         am1x1+am2x2+….+amnxn=bm         x1,x2….xn   0其中：其中：bi   0(i=1,2,….m)线性规划及单纯形法(3)课件即：即：s.t.s.t.可行解可行解可行解可行解: : : :满足满足满足满足AX=b, X>=0AX=b, X>=0AX=b, X>=0AX=b, X>=0的解的解的解的解X X X X称为线性规划问题的称为线性规划问题的称为线性规划问题的称为线性规划问题的可行解。

可行解最优解：使最优解：使最优解：使最优解：使Z=CXZ=CXZ=CXZ=CX达到最大值的可行解称为最优解达到最大值的可行解称为最优解达到最大值的可行解称为最优解达到最大值的可行解称为最优解线性规划及单纯形法(3)课件二、与线性规划问题解有关的基本概念二、与线性规划问题解有关的基本概念1.基基：设设A是是约约束束方方程程组组m×n的的系系数数矩矩阵阵，， A的的秩秩R(A)＝＝m，，B是是A中中m×m阶阶非非奇奇异异子子式式, 即即|B|≠0, 则则称称B是是LP问问题题的一个基的一个基          基向量、基变量、非基变量、基本解？基向量、基变量、非基变量、基本解？线性规划及单纯形法(3)课件基向量基向量：矩阵B=（P1，P2….Pm) ，其列向量Pj称为对应基B的基向量基变量和非基变量基变量和非基变量：与基向量 Pj 相对应的变量xj就称为基变量，其余的就称为非基变量不妨设：线性规划及单纯形法(3)课件例例1-1 线性规划及单纯形法(3)课件将该将该LP化为标准型化为标准型线性规划及单纯形法(3)课件线性规划及单纯形法(3)课件 1 2 1 0 01 2 1 0 0A A A A = = = = （（（（P1 ,P2 ,P3 ,P4 ,P5P1 ,P2 ,P3 ,P4 ,P5P1 ,P2 ,P3 ,P4 ,P5P1 ,P2 ,P3 ,P4 ,P5））））= = = = 4 0 0 1 04 0 0 1 0 0 4 0 0 1 0 4 0 0 1 A A A A矩阵包含以下矩阵包含以下1010个个3×33×3的子矩阵：的子矩阵： B B B B1 1 1 1= =（（p p p p1 1 1 1 ，，，，p p p p2 2 2 2 ，，，，p p p p3 3 3 3 ）） B B B B2 2 2 2= =（（p p p p1 1 1 1 ，，，，p p p p2 2 2 2 ，，，，p p p p4 4 4 4）） B B B B3 3 3 3= =（（p p p p1 1 1 1 ，，，，p p p p2 2 2 2 ，，，，p p p p5 5 5 5）） B B B B4 4 4 4= =（（p p p p1 1 1 1 ，，，，p p p p3 3 3 3 ，，，，p p p p4 4 4 4）） B B B B5 5 5 5= =（（p p p p1 1 1 1 ，，，，p p p p3 3 3 3 ，，，，p p p p5 5 5 5）） B B B B6 6 6 6= =（（p p p p1 1 1 1 ，，，，p p p p4 4 4 4 ，，，，p p p p5 5 5 5）） B B B B7 7 7 7= =（（p p p p2 2 2 2 ，，，，p p p p3 3 3 3 ，，，，p p p p4 4 4 4）） B B B B8 8 8 8= =（（p p p p2 2 2 2 ，，，，p p p p3 3 3 3 ，，，，p p p p5 5 5 5）） B B B B9 9 9 9= =（（p p p p2 2 2 2 ，，，，p p p p4 4 4 4 ，，，，p p p p5 5 5 5）） B B B B10101010= =（（p p p p3 3 3 3 ，，，，p p p p4 4 4 4 ，，，，p p p p5 5 5 5））    线性规划及单纯形法(3)课件 经经计计算算可可知知：：对对应应A A系系数数矩矩阵阵可可找找出出8 8个个基（除基（除B B4 4 、、B B8 8 以外都是以外都是基）。

基）  线性规划及单纯形法(3)课件线性规划及单纯形法(3)课件对应的基变量是对应的基变量是 x3  x4  x5线性规划及单纯形法(3)课件基本解基本解：对于某一特定的基对于某一特定的基B B，，令非基变量等于令非基变量等于零，则可由约束方程组零，则可由约束方程组 AXAX＝b b求得一个解，这样的解称为基本解思考：基本解与可行解的区别？思考：基本解与可行解的区别？线性规划及单纯形法(3)课件对应于每一个基，可以得到对应于每一个基，可以得到8 8个基本解：个基本解： x x(1)(1) = (4,3,-2,0,0) = (4,3,-2,0,0)T T （对应（对应B B1 1）） x x(2)(2) = (2,3,0,8,0) = (2,3,0,8,0)T T （对应（对应B B2 2）） x x(3)(3) = (4,2,0,0,4) = (4,2,0,0,4)T T （对应（对应B B3 3）） x x(5)(5) = (4,0,4,0,12) = (4,0,4,0,12)T T （对应（对应B B5 5）） x x(6)(6)= (8,0,0,-16,12)= (8,0,0,-16,12)T T（对应（对应B B6 6）） x x(7)(7)= (0,3,2,16,0)= (0,3,2,16,0)T T （对应（对应B B7 7）） x x(9)(9)= (0,4,0,16,-4)= (0,4,0,16,-4)T T （对应（对应B B9 9）） x x(10)(10) = (0,0,8,16,12) = (0,0,8,16,12)T T （对应（对应B B1010）） 线性规划及单纯形法(3)课件n n结合图形法分析X(2)(2,3)X(1)(4,3)X(3)(4,2)X(6)(8,0)X(10)(0,0)6 —5 —4 —3 —2 —1 —0     x2|||||||||123456789x1X(7)(0,3)X(9)(0,0)X(5)(4,0)线性规划及单纯形法(3)课件基本可行解：基本可行解：基本解不一定都是可行的。

满足非负限制的基本解，称为基本可行解基本可行解可行基：可行基：与基本可行解对应的基，称为可行基可行解、基本解、基本可行解的关系？可行解、基本解、基本可行解的关系？线性规划及单纯形法(3)课件解的集合：解的集合：非非可可行行解解可可行行解解线性规划及单纯形法(3)课件解的集合：解的集合：基基本本解解线性规划及单纯形法(3)课件解的集合：解的集合：可可行行解解基基本本解解基基基基本本本本可可可可行行行行解解解解线性规划及单纯形法(3)课件解的集合：解的集合：可可行行解解基基本本解解最最最最优优优优解解解解基基基基本本本本可可可可行行行行解解解解线性规划及单纯形法(3)课件作作作作业业业业：：：：找找找找出出出出下下下下列列列列线线线线性性性性规规规规划划划划问问问问题题题题的的的的基基基基本本本本解解解解、、、、基基基基本本本本可可可可行解和可行基行解和可行基行解和可行基行解和可行基 Max Max Max Max z z z z = 1500 = 1500 = 1500 = 1500 x x x x1 1 1 1 + 2500 + 2500 + 2500 + 2500 x x x x2 2 2 2 s.t. 3 s.t. 3 s.t. 3 s.t. 3 x x x x1 1 1 1 + 2 + 2 + 2 + 2 x x x x2 2 2 2 ≤≤≤≤ 65 65 65 65 2 2 2 2 x x x x1 1 1 1 + + + + x x x x2 2 2 2 ≤≤≤≤ 40 40 40 40 3 3 3 3 x x x x2 2 2 2 ≤ ≤ ≤ ≤ 75757575 x x x x1 1 1 1 , x, x, x, x2 2 2 2 ≥ 0 ≥ 0 ≥ 0 ≥ 0 注注注注意意意意，，，，线线线线性性性性规规规规划划划划的的的的基基基基本本本本解解解解、、、、基基基基本本本本可可可可行行行行解解解解和和和和可可可可行行行行基只与线性规划问题标准形式的约束条件有关。

基只与线性规划问题标准形式的约束条件有关基只与线性规划问题标准形式的约束条件有关基只与线性规划问题标准形式的约束条件有关线性规划及单纯形法(3)课件 3 2 1 0 0 3 2 1 0 0 3 2 1 0 0 3 2 1 0 0A A A A = = = = （（（（P1 ,P2 ,P3 ,P4 ,P5P1 ,P2 ,P3 ,P4 ,P5P1 ,P2 ,P3 ,P4 ,P5P1 ,P2 ,P3 ,P4 ,P5））））= 2 1 0 1 0= 2 1 0 1 0= 2 1 0 1 0= 2 1 0 1 0 0 3 0 0 1 0 3 0 0 1 0 3 0 0 1 0 3 0 0 1 A A A A矩阵包含以下矩阵包含以下矩阵包含以下矩阵包含以下10101010个个个个3×33×33×33×3的子矩阵：的子矩阵：的子矩阵：的子矩阵： B B B B1 1 1 1= = = =（（（（p p p p1 1 1 1 ，，，，p p p p2 2 2 2 ，，，，p p p p3 3 3 3 ）））） B B B B2 2 2 2= = = =（（（（p p p p1 1 1 1 ，，，，p p p p2 2 2 2 ，，，，p p p p4 4 4 4）））） B B B B3 3 3 3= = = =（（（（p p p p1 1 1 1 ，，，，p p p p2 2 2 2 ，，，，p p p p5 5 5 5）））） B B B B4 4 4 4= = = =（（（（p p p p1 1 1 1 ，，，，p p p p3 3 3 3 ，，，，p p p p4 4 4 4）））） B B B B5 5 5 5= = = =（（（（p p p p1 1 1 1 ，，，，p p p p3 3 3 3 ，，，，p p p p5 5 5 5）））） B B B B6 6 6 6= = = =（（（（p p p p1 1 1 1 ，，，，p p p p4 4 4 4 ，，，，p p p p5 5 5 5）））） B B B B7 7 7 7= = = =（（（（p p p p2 2 2 2 ，，，，p p p p3 3 3 3 ，，，，p p p p4 4 4 4）））） B B B B8 8 8 8= = = =（（（（p p p p2 2 2 2 ，，，，p p p p3 3 3 3 ，，，，p p p p5 5 5 5）））） B B B B9 9 9 9= = = =（（（（p p p p2 2 2 2 ，，，，p p p p4 4 4 4 ，，，，p p p p5 5 5 5）））） B B B B10101010= = = =（（（（p p p p3 3 3 3 ，，，，p p p p4 4 4 4 ，，，，p p p p5 5 5 5））））    线性规划及单纯形法(3)课件 其其其其中中中中   B B B B4 4 4 4   = = = = 0 0 0 0，，，，因因因因而而而而B B B B4 4 4 4不不不不是是是是该该该该线线线线性性性性规规规规划划划划问问问问题题题题的的的的基基基基。

其余均为非奇异方阵，因此该问题共有其余均为非奇异方阵，因此该问题共有其余均为非奇异方阵，因此该问题共有其余均为非奇异方阵，因此该问题共有9 9 9 9个基 对对对对于于于于基基基基B B B B3 3 3 3= = = =（（（（p p p p1 1 1 1 ，，，，p p p p2 2 2 2 ，，，，p p p p5 5 5 5）））），，，，令令令令非非非非基基基基变变变变量量量量x x x x3 3 3 3 = = = = 0 0 0 0，，，， x x x x4 4 4 4 = = = = 0 0 0 0，，，，即即即即在在在在等等等等式式式式约约约约束束束束中中中中令令令令x x x x3 3 3 3 = = = = 0 0 0 0，，，，x x x x4 4 4 4 = = = = 0 0 0 0，，，，解解解解线线线线性方程组：性方程组：性方程组：性方程组： 3 3 3 3 x x x x1 1 1 1 + 2 + 2 + 2 + 2 x x x x2 2 2 2 = 65= 65= 65= 65 2 2 2 2 x x x x1 1 1 1 + + + + x x x x2 2 2 2 = 40= 40= 40= 40 3 3 3 3 x x x x2 2 2 2 + + + + x x x x5 5 5 5 = 75= 75= 75= 75 得到得到得到得到x x x x1 1 1 1 =15=15=15=15，，，，x x x x2 2 2 2 = 10= 10= 10= 10，，，，x x x x5 5 5 5 = 45= 45= 45= 45，对应的基本解：，对应的基本解：，对应的基本解：，对应的基本解： x x x x（（（（3 3 3 3））））=(=(=(=(x x x x1 1 1 1 ，，，，x x x x2 2 2 2 ，，，，x x x x3 3 3 3 ，，，，x x x x4 4 4 4 ，，，，x x x x5 5 5 5) ) ) )T T T T=(15=(15=(15=(15，，，，10101010，，，，0 0 0 0，，，，0 0 0 0，，，，45)45)45)45)T T T T。

由由由由于于于于每每每每一一一一个个个个分分分分量量量量都都都都是是是是大大大大于于于于或或或或等等等等于于于于0 0 0 0的的的的，，，，因因因因此此此此它它它它是是是是一一一一个个个个基基基基本本本本可可可可行行行行解解解解于于于于是是是是对对对对应应应应的的的的基基基基B B B B3 3 3 3是是是是一一一一个个个个可行基线性规划及单纯形法(3)课件 类似可得到类似可得到类似可得到类似可得到 x x x x(2)(2)(2)(2) = (5,25,0,5,0) = (5,25,0,5,0) = (5,25,0,5,0) = (5,25,0,5,0)T T T T （对应（对应（对应（对应B B B B2 2 2 2）））） x x x x(7)(7)(7)(7) = (20,0,5,0,75) = (20,0,5,0,75) = (20,0,5,0,75) = (20,0,5,0,75)T T T T （对应（对应（对应（对应B B B B5 5 5 5）））） x x x x(8)(8)(8)(8) = (0,25,15,15,0) = (0,25,15,15,0) = (0,25,15,15,0) = (0,25,15,15,0)T T T T （对应（对应（对应（对应B B B B7 7 7 7）））） x x x x(9)(9)(9)(9) = (0,0,65,40,75) = (0,0,65,40,75) = (0,0,65,40,75) = (0,0,65,40,75)T T T T （对应（对应（对应（对应B B B B10101010）））） 是基本可行解是基本可行解是基本可行解是基本可行解; ; ; ; 因此，可行基有五个，分别是因此，可行基有五个，分别是因此，可行基有五个，分别是因此，可行基有五个，分别是B B B B2 2 2 2 B B B B3 3 3 3 B B B B5 5 5 5 B B B B7 7 7 7 B B B B10101010。

x x x x(3)(3)(3)(3)= (0,32.5,0,7.5,-22.5)= (0,32.5,0,7.5,-22.5)= (0,32.5,0,7.5,-22.5)= (0,32.5,0,7.5,-22.5)T T T T（对应（对应（对应（对应B B B B9 9 9 9）））） x x x x(4)(4)(4)(4)= (65/3,0,0,-10/3,75)= (65/3,0,0,-10/3,75)= (65/3,0,0,-10/3,75)= (65/3,0,0,-10/3,75)T T T T （对应（对应（对应（对应B B B B6 6 6 6）））） x x x x(5)(5)(5)(5)= (7.5,25,-7.5,0,0)= (7.5,25,-7.5,0,0)= (7.5,25,-7.5,0,0)= (7.5,25,-7.5,0,0)T T T T （对应（对应（对应（对应B B B B1 1 1 1）））） x x x x(6)(6)(6)(6) = (0,40,-15,0,-45) = (0,40,-15,0,-45) = (0,40,-15,0,-45) = (0,40,-15,0,-45)T T T T （对应（对应（对应（对应B B B B8 8 8 8）））） 是基本解。

是基本解是基本解是基本解线性规划及单纯形法(3)课件三、与三、与线性规划解的性质有关的线性规划解的性质有关的 基本概念（凸集、顶点）基本概念（凸集、顶点）线性规划及单纯形法(3)课件       1、、 凸凸集集——设设K是是n维维欧欧氏氏空空间间的的一一个个点点集集，，若若任任意意两两点点X（（1））∈∈K，，X（（2））∈∈K的连线上的一切点：的连线上的一切点：         αX（（1））+（（1-α））X（（2）） ∈∈ K          （（0<α<1），则称），则称K为为凸集凸集        线性规划及单纯形法(3)课件凸集凸集非凸集非凸集线性规划及单纯形法(3)课件2、 凸凸组组合合 设设X（（1））,X（（2））, … ,X（（k））是是n维维欧欧氏氏空空间间中中的的K个个点点,若若存存在在k个个数数μ1, μ2 , … ,μk ,满足满足0≤μi≤1,  i=1,2, …,k；且；且                  ，，   则称则称X=μ1X（（1））+μ2X（（2））+…+μkX(k)为为           X（（1））, ，，X（（2）） ，，…，，X（（k））的的凸组合凸组合。

           线性规划及单纯形法(3)课件          3、、 顶点顶点   设设K是凸集，是凸集，X K；若；若X不能用不能用      X（（1））   K，，X（（2））   K 的线性组合表示，即的线性组合表示，即         X≠αX（（1））+（（1-α））X（（2））    （（0<α<1））     则称则称X为为K的一个的一个顶点顶点（也称极点或角点）（也称极点或角点）线性规划及单纯形法(3)课件多边形上的点是顶点多边形上的点是顶点圆周上的点都是顶点圆周上的点都是顶点线性规划及单纯形法(3)课件四、线性规划问题解的性质定理四、线性规划问题解的性质定理：：  定定理理1-1 若若线线性性规规划划问问题题存存在在可可行行域域，，则则其其可可行行域域（（即即可可行行解解集集））                                  是是凸凸集 定理定理1-2 线性规划几何理论基本定理线性规划几何理论基本定理若若                                                  ，，则则X是是D的的一一个个顶顶点点的的充充分分必必要要条条件件是是X为为线线性性规划的基本可行解。

规划的基本可行解线性规划及单纯形法(3)课件定定理理1-3 若若可可行行域域非非空空有有界界，，则则线线性性规规划划问问题题的的目目标标函函数数一一定定可可以以在在可可行行域域的的顶顶点点上上达达到最优值到最优值定定理理1-4 若若目目标标函函数数在在k个个点点处处达达到到最最优优值值（（k≥2））,则则在在这这些些顶顶点点的的凸凸组组合合上上也也达达到到最优值线性规划及单纯形法(3)课件上述上述4个定理的一些有意义的启示：个定理的一些有意义的启示： J LP的的可可行行域域一一定定是是凸凸集集，，但但是是凸凸集集不不一一定定成成为为LP的的可可行行域域，，而而非非凸凸集集一一定定不会是不会是LP的可行域的可行域       J线线性性规规划划的的基基本本可可行行解解与与可可行行域域的的顶顶点点是一一对应的是一一对应的 线性规划及单纯形法(3)课件J  在在可可行行域域中中寻寻找找LP的的最最优优解解可可以以转转化化为为只只在在可可行行域域的的顶顶点点中中找找，，从从而而把把一一个无限的问题转化为一个有限的问题个无限的问题转化为一个有限的问题J 若若已已知知一一个个LP有有两两个个或或两两个个以以上上最最优解，那麽就一定有无穷多个最优解。

优解，那麽就一定有无穷多个最优解线性规划及单纯形法(3)课件1-5 1-5 单纯形法单纯形法线性规划及单纯形法(3)课件单纯形方法基本思路：单纯形方法基本思路：•从可行域中某个基本可行解（一个顶点）开从可行域中某个基本可行解（一个顶点）开始（称为初始基本可行解）始（称为初始基本可行解）•如可能，从可行域中求出具有更优目标函数如可能，从可行域中求出具有更优目标函数值的另一个基本可行解（另一个顶点），以值的另一个基本可行解（另一个顶点），以改进初始解改进初始解•继续寻找更优的基础可行解，进一步改进目继续寻找更优的基础可行解，进一步改进目标函数值当某一个基础可行解不能再改善标函数值当某一个基础可行解不能再改善时，该解就是最优解时，该解就是最优解线性规划及单纯形法(3)课件求解线性规划问题的基本思路求解线性规划问题的基本思路1、构造初始可行基；2、求出一个基本可行解（顶点）3、最优性检验：判断是否最优解；4、基变化，转2要保证目标函数值比原来更优从线性规划解的性质可知求解从线性规划解的性质可知求解线性规划问题的基本思路线性规划问题的基本思路线性规划及单纯形法(3)课件 为书写规范和便于计算，对单纯形法的计算设计了单纯形表。

每一次迭代对应一张单纯形表，含初始基本可行解的单纯形表称为初始单纯形表，含最优解的单纯形表称为最终单纯形表本节介绍用单纯形表计算线性规划问题的步骤线性规划及单纯形法(3)课件 在第一次找可行基时，首先寻找单位矩阵，称之为初始可行基，其相应的基本可行解叫初始基本可行解如果找不到单位矩阵作为初始可行基，我们将构造一个单位矩阵，具体做法在以后详细讲述 线性规划及单纯形法(3)课件单纯形表方法的解题步骤：单纯形表方法的解题步骤：对于线性规划的标准型对于线性规划的标准型1 1、找出初始可行基，建立初始单纯型表：、找出初始可行基，建立初始单纯型表：Cjc1c2… … cnbθθCBXBx1x2… … xnc1x1　 　 　 　 　 b1　c2x2　 　 　 　 　 b2　： ： 　 　 　 　 　 ： 　cmxm　 　 　 　 　 bm　σσj j　 　 　 　 　Z线性规划及单纯形法(3)课件2 2、判别、判别( (最优性检验）最优性检验）•若检验数若检验数σσj j全小于等于零，则基全小于等于零，则基B B所对应所对应的基础可行解的基础可行解X X就是最优解，终止就是最优解，终止。

•若存在若存在σσj j大于零，则转入下一步大于零，则转入下一步（注：检验数（注：检验数 ）） j=1,2j=1,2j=1,2j=1,2…………n n n n线性规划及单纯形法(3)课件3 3、换基迭代、换基迭代•确定进基变量确定进基变量X Xk k 即：即： Ơk k== max( max( Ơj j | |Ơj j > 0 )> 0 )对应的变量对应的变量•确定出基变量确定出基变量Xl即：即：θθl =min=min ( ( | > 0 ) > 0 )对应的变量对应的变量 最最小比原则小比原则•对单纯形表进行对单纯形表进行初等行变换初等行变换得到新的单纯形得到新的单纯形表。

表线性规划及单纯形法(3)课件经过上述有限次的换基迭代，就可得到经过上述有限次的换基迭代，就可得到原问题的最优解，或判定无最优解原问题的最优解，或判定无最优解线性规划及单纯形法(3)课件例例1-1 线性规划及单纯形法(3)课件将该将该LP化为标准型化为标准型线性规划及单纯形法(3)课件表格单纯形法：表格单纯形法：        初始单纯形表的建立初始单纯形表的建立 (1)表格结构：表格结构：  b                 2       3       0       0       0                x1        x2      x3      x4      x5CB            XB 0            x3                1       2       1       0       0               8 0            x4                4       0       0       1       0              16  0            x5                0       4       0       0       1               12      δj                 2       3       0       0       0    Cj线性规划及单纯形法(3)课件 C Cj j 2 3 0 0 0 2 3 0 0 0 b b    i i C CB B X XB B x x x x1 1 1 1 x x x x2 2 2 2 x x x x3 3 3 3 x x x x4 4 4 4 x x x x5 5 5 5 0 0 0 0 0 0 X X3 3 X X4 4 X X5 5 1 2 1 0 0 1 2 1 0 0 4 0 0 1 0 4 0 0 1 0 0 0 4 0 0 1 0 0 1 8 8 16 16 12 128/28/2 - -12/412/4 δ δj j 2 3 0 0 0 2 3 0 0 0 Z =0 Z =0 0 0 0 0 3 3 X X3 3 X X4 4 X X2 2 1 0 1 0 -1/2 0 1 0 -1/2 4 0 0 1 0 4 0 0 1 0 0 1 0 0 1/4 0 1 0 0 1/4 2 2 16 16 3 3 2/1 2/1 16/4 16/4 δ δj j 2 0 0 0 -3/4 2 0 0 0 -3/4 Z=9 Z=9 2 2 0 0 3 3 X X1 1 X X4 4 X X2 2 1 0 1 0 -1/2 1 0 1 0 -1/2 0 0 -4 1 0 0 -4 1 2 0 1 0 0 1/4 0 1 0 0 1/4 2 2 8 8 3 3- -8/28/23/(1/4)3/(1/4) δ δj j 0 0 -2 0 1/4 0 0 -2 0 1/4 Z =13 Z =13线性规划及单纯形法(3)课件 2 3 0 0 0 2 3 0 0 0 b b    i i C CB B X XB B x x x x1 1 1 1 x x x x2 2 2 2 x x x x3 3 3 3 x x x x4 4 4 4 x x x x5 5 5 5 2 2 0 0 3 3 X X1 1 X X5 5 X X2 2 1 0 0 1/4 0 1 0 0 1/4 0 0 0 -2 1/2 1 0 0 -2 1/2 1 0 1 1/2 -1/8 0 0 1 1/2 -1/8 0 4 4 4 4 2 2 δ δj j 0 0 -3/2 -1/8 0 0 0 -3/2 -1/8 0 Z =14 Z =14从最优表可知从最优表可知:该该LP的最优解是的最优解是X*=(4,2,0,0,4)T         相应的目标函数最优值是相应的目标函数最优值是Zmax=14线性规划及单纯形法(3)课件练习练习1：：           max S = 50x1 + 30x2                                                         s.t.     4x1+3x2   120                    2x1+  x2   50                     x1,x2   0线性规划及单纯形法(3)课件列出初始单纯形表列出初始单纯形表初始基础可行解为：初始基础可行解为： X（（0））=(0, 0,120,50)t线性规划及单纯形法(3)课件X X1 1 进基变量进基变量, ,X X4 4出基变量出基变量, ,主元主元（（2 2））线性规划及单纯形法(3)课件进行初等行变换：进行初等行变换：得到新的基础可行解得到新的基础可行解X(1)=(25, 0,20,0)t,线性规划及单纯形法(3)课件计算检验数计算检验数线性规划及单纯形法(3)课件X X2 2 进基变量进基变量, ,X X3 3出基变量出基变量, ,主元主元（（1 1））线性规划及单纯形法(3)课件进行初等行变换：进行初等行变换：得到基础可行解得到基础可行解X(2)=(15,20,0,0)t线性规划及单纯形法(3)课件由于检验数全都小于等于由于检验数全都小于等于0 0，因此，因此该解为最优解。

该解为最优解线性规划及单纯形法(3)课件线性规划及单纯形法(3)课件X X(0)(0)=(0, 0,120,50)=(0, 0,120,50)t t相当于相当于O(0,0)O(0,0)线性规划及单纯形法(3)课件X X(1)(1)=(25, 0,20,0)=(25, 0,20,0)t t相当于相当于1 1(25,0)(25,0)线性规划及单纯形法(3)课件X(2)=(15,20,0,0)t相当于相当于2 2(15,20)(15,20)线性规划及单纯形法(3)课件线性规划及单纯形法(3)课件线性规划及单纯形法(3)课件线性规划及单纯形法(3)课件线性规划及单纯形法(3)课件线性规划及单纯形法(3)课件练习2：教材p31 4(2)、2(1)线性规划及单纯形法(3)课件例例2 2：： 求解线性规划问题：求解线性规划问题： min S = x min S = x1 1 - x- x2 2 s.t. -x s.t. -x1 1+ x+ x2 2   2 2 2x 2x1 1- x- x2 2   2 2 x x1 1 , , x x2 2   0 0解：化标准型：解：化标准型： max S max S  = -x = -x1 1+x+x2 2 s.t. -x s.t. -x1 1+ x+ x2 2 +x +x3 3 = 2 = 2 2x 2x1 1 - x- x2 2 +x+x4 4 = 2= 2 x x1 1 , , x x2 2 , , x x3 3 , , x x4 4   0 0线性规划及单纯形法(3)课件列出初始单纯形表：列出初始单纯形表：线性规划及单纯形法(3)课件计算检验数，确定进基变量、出基变计算检验数，确定进基变量、出基变量，找到主元：量，找到主元：线性规划及单纯形法(3)课件进行初等行变换：进行初等行变换：线性规划及单纯形法(3)课件再计算检验数：再计算检验数：线性规划及单纯形法(3)课件因为检验数全小于等于零，得最优解：因为检验数全小于等于零，得最优解：X=X=（（0 0，，2 2，，0 0，，4 4）） S S =2 S = -2=2 S = -2线性规划及单纯形法(3)课件注意：虽然所有检验数全小于等于零，注意：虽然所有检验数全小于等于零，但非基变量但非基变量x x1 1对应的检验数对应的检验数=0=0，若以，若以x x1 1进基，进基，x x4 4出基出基, ,其最优值不变。

其最优值不变线性规划及单纯形法(3)课件进行初等行变换进行初等行变换线性规划及单纯形法(3)课件计算检验数：计算检验数：线性规划及单纯形法(3)课件因为检验数全小于等于零，得另一个最因为检验数全小于等于零，得另一个最优解：优解：X=X=（（4 4，，6 6，，0 0，，0 0））S S =2 S = -=2 S = -2 2线性规划及单纯形法(3)课件根据解的性质：根据解的性质：最优解最优解 X X（（1 1））==（（0 0，，2 2，，0 0，，4 4））t t，， X X(2) (2) ==（（4 4，，6 6，，0 0，，0 0））t t连线上的点仍是最优解：连线上的点仍是最优解： X= X=  X X（（1 1）） +(1- +(1-  ) ) X X（（2 2）） (0 (0       1) 1)因此，本题有无穷多组最优解。

因此，本题有无穷多组最优解线性规划及单纯形法(3)课件例例3 3  求解线性规划问题：求解线性规划问题： max S= 2x max S= 2x1 1+x+x2 2 s.t. x s.t. x1 1 - x- x2 2   -5 -5 2x 2x1 1 - 5x- 5x2 2   10 10 x x1 1 , , x x2 2   0 0解：解：化标准型：化标准型： max S max S = 2x= 2x1 1 + x+ x2 2 s.t. -x s.t. -x1 1+ x+ x2 2 +x +x3 3 = 5 = 5 2x 2x1 1 - 5x- 5x2 2 +x+x4 4 = 10= 10 x x1 1 , , x x2 2 , , x x3 3 , , x x4 4   0 0线性规划及单纯形法(3)课件列出初始单纯形表：列出初始单纯形表：线性规划及单纯形法(3)课件计算检验数，确定进基变量、出基变量，计算检验数，确定进基变量、出基变量，找到主元：找到主元：线性规划及单纯形法(3)课件进行初等行变换进行初等行变换线性规划及单纯形法(3)课件再计算检验数，确定进基变量为再计算检验数，确定进基变量为x2：：线性规划及单纯形法(3)课件由于进由于进基变量基变量X X2 2所对应的系数全都小于所对应的系数全都小于0 0，，所以原问题无最优解所以原问题无最优解. .线性规划及单纯形法(3)课件课堂作业：课堂作业： 单纯形法求解线性规划问题单纯形法求解线性规划问题(1) min S = x(1) min S = x1 1 - 3x- 3x2 2 + + 2x2x3 3 + 4x+ 4x4 4 s.t. 2x s.t. 2x1 1+ 4x+ 4x3 3 +x+x4 4 = 6 = 6 -x -x1 1+x+x2 2 + + 3x3x3 3 = 5 = 5 x x1 1 , , x x2 2 , , x x3 3 , , x x4 4   0 0(2) max z = x(2) max z = x1 1 + x + x2 2 s.t. -2x s.t. -2x1 1 + x + x2 2 ≤ 4 ≤ 4 x x1 1 - x - x2 2 ≤ 2 ≤ 2 x x1 1 , x , x2 2   0 0(3) (3) 教材教材p31 2p31 2（（3 3））线性规划及单纯形法(3)课件课堂作业：课堂作业： 单纯形法求解线性规划问题单纯形法求解线性规划问题（（1 1））min S = xmin S = x1 1 - 3x- 3x2 2 + + 2x2x3 3 + 4x+ 4x4 4 s.t. 2x s.t. 2x1 1+ 4x+ 4x3 3 +x+x4 4 = 6 = 6 -x -x1 1+x+x2 2 + + 3x3x3 3 = 5 = 5 x x1 1 , , x x2 2 , , x x3 3 , , x x4 4   0 0解：解：化问题为标准型化问题为标准型max Smax S  = -x = -x1 1 + 3x+ 3x2 2 - 2x- 2x3 3 - 4x- 4x4 4 s.t. 2x s.t. 2x1 1+ 4x+ 4x3 3 +x+x4 4 = 6 = 6 -x -x1 1+x+x2 2 + + 3x3x3 3 = 5 = 5 x x1 1 , , x x2 2 , , x x3 3 , , x x4 4   0 0线性规划及单纯形法(3)课件线性规划及单纯形法(3)课件因为检验数全小于等于零，得唯一最优解：因为检验数全小于等于零，得唯一最优解：X*=X*=（（3 3，，8 8，，0 0，，0 0））T T , S*= -21. , S*= -21.线性规划及单纯形法(3)课件（（2 2））max Z = xmax Z = x1 1 +x+x2 2 s.t. -2x s.t. -2x1 1+ x+ x2 2 ≤ 4 ≤ 4 x x1 1 - x- x2 2 ≤ 2≤ 2 x x1 1 , , x x2 2   0 0解：化问题为标准型解：化问题为标准型max z = xmax z = x1 1 + x+ x2 2 +0x+0x3 3 -+0x-+0x4 4 s.t. -2x s.t. -2x1 1+ x+ x2 2+ x+ x3 3 = 4= 4 x x1 1 - x- x2 2 + + x x4 4 = 2 = 2 x x1 1 , , x x2 2 , , x x3 3 , , x x4 4   0 0线性规划及单纯形法(3)课件线性规划及单纯形法(3)课件仍然有检验数大于零，因此还不是最仍然有检验数大于零，因此还不是最优解。

此时，继续找进基变量优解此时，继续找进基变量X X2 2，但，但是没有出基变量，这说明本题为无界是没有出基变量，这说明本题为无界解线性规划及单纯形法(3)课件或或或或 也也是是无无界界解解线性规划及单纯形法(3)课件（（3 3））max z = 3xmax z = 3x1 1 + 6x+ 6x2 2 s.t. x s.t. x1 1 - 2x- 2x2 2   -2 -2 x x1 1 + 2x+ 2x2 2   6 6 x x1 1 , , x x2 2   0 0解：解：化问题为标准型化问题为标准型max z = 3xmax z = 3x1 1 + 6x+ 6x2 2 +0x+0x3 3 +0x+0x4 4 s.t. -x s.t. -x1 1+ 2x+ 2x2 2 +x +x3 3 = 2 = 2 x x1 1+2x+2x2 2 + + x x4 4 = 6 = 6 x x1 1 , , x x2 2 , , x x3 3 , , x x4 4   0 0线性规划及单纯形法(3)课件线性规划及单纯形法(3)课件因为检验数全小于等于零，得最优解：因为检验数全小于等于零，得最优解：X X (1)(1) = =（（2/32/3，，8/38/3，，0 0，，0 0））T T , z*= 18. , z*= 18.又因为非基变量又因为非基变量x x3 3对应的检验数等于对应的检验数等于0,0,所以有无穷多最优解。

所以有无穷多最优解线性规划及单纯形法(3)课件线性规划及单纯形法(3)课件对应该最优表得到另外一个最优解：对应该最优表得到另外一个最优解：X X (2)(2) = =（（6 6，，0 0，，8 8，，0 0））T T , z*= 18. , z*= 18.于是于是X X(1) (1) 与与x x(2)(2) 的凸组合的凸组合x*x*仍是最仍是最优解：优解： X X* * = =   X X（（1 1）） +(1- +(1-  ) X) X（（2 2）） (0 (0       1) 1)线性规划及单纯形法(3)课件二、无初始可行基求最优解二、无初始可行基求最优解人工变量法人工变量法约束方程系数矩阵约束方程系数矩阵A A中不包含单位矩阵中不包含单位矩阵时，往往采用添加人工变量的方法来人时，往往采用添加人工变量的方法来人为的构造一个单位矩阵作基。

为的构造一个单位矩阵作基线性规划及单纯形法(3)课件————大大MM法法由于人工变量是另外添加的，因此最后由于人工变量是另外添加的，因此最后得到的最优解中人工变量取值必须为得到的最优解中人工变量取值必须为0 0为此，令目标函数中人工变量的系数为为此，令目标函数中人工变量的系数为 “-M”“-M”（其中（其中MM为为一个任意大的正数）一个任意大的正数）线性规划及单纯形法(3)课件例例1 1 用大用大MM法求下列问题法求下列问题 min z = -3x min z = -3x1 1 + x + x2 2 + x+ x3 3 s.t. X s.t. X1 1-2x-2x2 2 + x+ x3 3   11 11 -4x -4x1 1+ x+ x2 2 + 2x+ 2x3 3   3 3 - 2x - 2x1 1 + x+ x3 3 = 1 = 1 x x1 1,x ,x2 2 , , x x3 3   0 0线性规划及单纯形法(3)课件解：将问题化成标准形式，并加解：将问题化成标准形式，并加入人工变量入人工变量max z’ =  3x1 - x2 - x3 - M x6 - M x7          s.t.     X1-2x2 + x3         + x4 = 11                -4x1+ x2 + 2x3 –x5 + x6 = 3              - 2x1              + x3            + x7 = 1              x1,x2 , x3 , x4 , x5, x6 , x7   0                     MM是任意大的正数是任意大的正数线性规划及单纯形法(3)课件列出初始单纯形表：CjCj3 3-1-1-1-10 00 0-M-M-M-Mb b C CB BX XB BX X1 1X X2 2X X3 3X X4 4X X5 5X X6 6X X7 70 0X X4 41 1-2-21 11 10 00 00 01111-M-MX X6 6-4-41 12 20 0-1-11 10 03 3-M-MX X7 7-2-20 01 10 00 00 01 11 1 j j 线性规划及单纯形法(3)课件计算检验数，计算检验数，  3 3=3M-1=3M-1最大最大,X,X3 3为进基变量为进基变量CjCj3 3-1-1-1-10 00 0-M-M-M-Mb b C CB BX XB BX X1 1X X2 2X X3 3X X4 4X X5 5X X6 6X X7 70 0X X4 41 1-2-21 11 10 00 00 01111-M-MX X6 6-4-41 12 20 0-1-11 10 03 3-M-MX X7 7-2-20 01 10 00 00 01 11 1 j j3-6M 3-6M M-1 M-1 3M-3M-1 1 0 0 -M -M 0 0 0 0 线性规划及单纯形法(3)课件最小比值：最小比值：X7为出基变量，主元为为出基变量，主元为（（1））CjCj3 3-1-1-1-10 00 0-M-M-M-Mb b C CB BX XB BX X1 1X X2 2X X3 3X X4 4X X5 5X X6 6X X7 70 0X X4 41 1-2-21 11 10 00 00 011111111-M-MX X6 6-4-41 12 20 0-1-11 10 03 33/23/2-M-MX X7 7-2-20 0(1)(1)0 00 00 01 11 11 1 j j3-3-6M 6M M-1 M-1 3M-3M-1 1 0 0 -M -M 0 0 0 0 线性规划及单纯形法(3)课件进行初等行变换，得到新的单纯形表进行初等行变换，得到新的单纯形表CjCj3 3-1-1-1-10 00 0-M-M-M-Mb b C CB BX XB BX X1 1X X2 2X X3 3X X4 4X X5 5X X6 6X X7 70 0X X4 43 3-2-20 01 10 00 0-1-11010 -M-MX X6 60 01 10 00 0-1-11 1-2-21 1 -1-1X X3 3-2-20 0(1)(1)0 00 00 01 11 1  j j 线性规划及单纯形法(3)课件计算检验数，确定进基变量，出基变量计算检验数，确定进基变量，出基变量CjCj3 3-1-1-1-10 00 0-M-M-M-Mb b C CB BX XB BX X1 1X X2 2X X3 3X X4 4X X5 5X X6 6X X7 70 0X X4 43 3-2-20 01 10 00 0-1-11010- - -M-MX X6 60 0(1)(1)0 00 0-1-11 1-2-21 11 1 -1-1X X3 3-2-20 01 10 00 00 01 11 1- -  j j1 1 M-M-1 1 0 0 0 0 -M -M 0 0 1-1-3M 3M 线性规划及单纯形法(3)课件进行初等行变换，得到新的单纯形表进行初等行变换，得到新的单纯形表CjCj3 3-1-1-1-10 00 0-M-M-M-Mb b C CB BX XB BX X1 1X X2 2X X3 3X X4 4X X5 5X X6 6X X7 70 0X X4 43 30 00 01 1-2-22 2-5-51212 -1-1X X2 20 0 1 1 0 00 0-1-11 1-2-21 1 -1-1X X3 3-2-20 0 1 1 0 00 00 01 11 1  j j 线性规划及单纯形法(3)课件CjCj3 3-1-1-1-10 00 0-M-M-M-Mb b C CB BX XB BX X1 1X X2 2X X3 3X X4 4X X5 5X X6 6X X7 70 0X X4 4(3 (3) )0 00 01 1-2-22 2-5-512124 4 -1-1X X2 20 0 1 1 0 00 0-1-11 1-2-21 1- - -1-1X X3 3-2-20 0 1 1 0 00 00 01 11 1- -  j j1 1 0 0 0 0 0 0 -1 -1 1-1-M M -M -M-1 -1 重新计算检验数，确定进基变量，出基变量重新计算检验数，确定进基变量，出基变量线性规划及单纯形法(3)课件CjCj3 3-1-1-1-10 00 0-M-M-M-Mb b C CB BX XB BX X1 1X X2 2X X3 3X X4 4X X5 5X X6 6X X7 73 3X X1 11 10 00 01/31/3- -2/32/32/32/3-5/3-5/34 4 -1-1X X2 20 0 1 1 0 00 0-1-11 1-2-21 1 -1-1X X3 30 00 0 1 1 2/32/3- -4/34/34/34/3-7/3-7/39 9  j j0 0 0 0 0 0 - -1/3 1/3 - -1/3 1/3 1/31/3-M -M 2/32/3-M -M Z’=2 Z’=2 进行初等行变换，得到新的单纯形表，并计算检验数进行初等行变换，得到新的单纯形表，并计算检验数进行初等行变换，得到新的单纯形表，并计算检验数进行初等行变换，得到新的单纯形表，并计算检验数得到最优解得到最优解X*=(4,1,9,0,0,0,0)t,最优值为最优值为z’=2，，Z=-2线性规划及单纯形法(3)课件练习：练习： 用大用大MM法求下列问题法求下列问题               max  S = 6x1 +4x2                                                         s.t.     2x1+3x2   100                    4x1+2x2   120                      x1 = 14                      x2   22                       x1,x2   0线性规划及单纯形法(3)课件解：将问题化成标准形式解：将问题化成标准形式max S =  6x1 + 4x2                                                 s.t. 2x1+3x2 +x3                    = 100        4x1+2x2             +x4             = 120             x1                            = 14                     x2              - x5 = 22                    x1,x2 , x3,x4 ，，x5   0线性规划及单纯形法(3)课件解：引入人工变量解：引入人工变量, x, x6 6   0 0，， x x7 7   0 0max  S =   6x1 + 4x2 -Mx6 -Mx7   s.t. 2x1+3x2 +x3                          = 100        4x1+2x2          +x4                     = 120             x1                        +x6      = 14                     x2          - x5       +x7 = 22              x1,x2 , x3,x4 , x5 , x6  ,x7   0线性规划及单纯形法(3)课件列出初始单纯形表：CjCj6 64 40 00 00 0-M-M-M-Mb b C CB BX XB BX X1 1X X2 2X X3 3X X4 4X X5 5X X6 6X X7 70 0X X3 32 23 31 10 00 00 00 0100100 0 0X X4 44 42 20 01 10 00 00 0120120 -M-MX X6 61 10 00 00 00 01 10 01414 -M-MX X7 70 01 10 00 0-1-10 01 12222  j j S S线性规划及单纯形法(3)课件计算检验数，计算检验数，  1 1=6+M=6+M最大最大,X,X1 1为进基变量为进基变量CjCj6 64 40 00 00 0-M-M-M-Mb b C CB BX XB BX X1 1X X2 2X X3 3X X4 4X X5 5X X6 6X X7 70 0X X3 32 23 31 10 00 00 00 0100100 0 0X X4 44 42 20 01 10 00 00 0120120 -M-MX X6 6(1)(1)0 00 00 00 01 10 01414 -M-MX X7 70 01 10 00 0-1-10 01 12222    j j6+6+MM4+4+MM0 00 0-M-M0 00 0S S线性规划及单纯形法(3)课件最小比值：最小比值：X X6 6为出基变量为出基变量, ,主元为（主元为（1 1））CjCj6 64 40 00 00 0-M-M-M-Mb b C CB BX XB BX X1 1X X2 2X X3 3X X4 4X X5 5X X6 6X X7 70 0X X3 32 23 31 10 00 00 00 010010050 50 0 0X X4 44 42 20 01 10 00 00 012012030 30 -M-MX X6 6(1)(1)0 00 00 00 01 10 014141414 -M-MX X7 70 01 10 00 0-1-10 01 12222- -  j j6+6+MM4+4+MM0 00 0-M-M0 00 0S S线性规划及单纯形法(3)课件进行初等行变幻，得到新的单纯形表进行初等行变幻，得到新的单纯形表CjCj6 64 40 00 00 0-M-M-M-Mb b C CB BX XB BX X1 1X X2 2X X3 3X X4 4X X5 5X X6 6X X7 70 0X X3 30 03 31 10 00 0-2-20 07272 0 0X X4 40 02 20 01 10 0-4-40 06464 6 6X X1 1 1 1 0 00 00 00 01 10 01414 -M-MX X7 70 01 10 00 0-1-10 01 12222  j j S S线性规划及单纯形法(3)课件计算检验数，确定进基变量为计算检验数，确定进基变量为X X2 2，，出基变量出基变量为为X X7 7，主元（，主元（1 1））CjCj6 64 40 00 00 0-M-M-M-Mb b C CB BX XB BX X1 1X X2 2X X3 3X X4 4X X5 5X X6 6X X7 70 0X X3 30 03 31 10 00 0-2-20 0727224 24 0 0X X4 40 02 20 01 10 0-4-40 0646432 32 6 6X X1 1 1 1 0 00 00 00 01 10 01414- - -M-MX X7 70 0(1)(1)0 00 0-1-10 01 1222222 22  j j0 0 4+4+M M 0 0 0 0 -M -M -M-M-6-60 0 S S线性规划及单纯形法(3)课件进行初等行变换，得到新的单纯形表进行初等行变换，得到新的单纯形表进行初等行变换，得到新的单纯形表进行初等行变换，得到新的单纯形表CjCj6 64 40 00 00 0-M-M-M-Mb b C CB BX XB BX X1 1X X2 2X X3 3X X4 4X X5 5X X6 6X X7 70 0X X3 30 00 01 10 03 3-2-2-3-36 6 0 0X X4 40 00 00 01 12 2-4-4-2-22020 6 6X X1 1 1 1 0 00 00 00 01 10 01414 4 4X X2 20 0 1 1 0 00 0-1-10 01 12222  j j S S线性规划及单纯形法(3)课件计算检验数，计算检验数， 确定进基变量为确定进基变量为X X5 5，出基变，出基变量为量为X X3 3，主元（，主元（3 3））CjCj6 64 40 00 00 0-M-M-M-Mb b C CB BX XB BX X1 1X X2 2X X3 3X X4 4X X5 5X X6 6X X7 70 0X X3 30 00 01 10 0(3 (3) )-2-2-3-36 62 2 0 0X X4 40 00 00 01 12 2-4-4-2-2202010 10 6 6X X1 1 1 1 0 00 00 00 01 10 01414- - 4 4X X2 20 0 1 1 0 00 0-1-10 01 12222- -  j j0 0 0 0 0 0 0 0 4 4 -M-M-6 -6 -M-M-4 -4 S S线性规划及单纯形法(3)课件 进行初等行变换，进行初等行变换，进行初等行变换，进行初等行变换，得到新的单纯形表，计算检验数得到新的单纯形表，计算检验数得到新的单纯形表，计算检验数得到新的单纯形表，计算检验数C C6 64 40 00 00 0-M-M-M-Mb b C CB BX XB BX X1 1X X2 2X X3 3X X4 4X X5 5X X6 6X X7 70 0X X5 50 00 01/31/30 01 1-2/3-2/3-1-12 2 0 0X X4 40 00 0- -2/32/31 10 0-8/3-8/30 01616 6 6X X1 1 1 1 0 00 00 00 01 10 01414 4 4X X2 20 0 1 1 1/31/30 00 0-2/3-2/30 02424  0 0 0 0 - -4/3 4/3 0 0 0 0 -10/3-10/3-M -M -M -M 180 180 X X X X* * * *====（（（（14141414，，，，24242424，，，，0 0 0 0，，，，16161616，，，，2 2 2 2，，，，0 0 0 0，，，，0 0 0 0））））t t t t为最优解，最优为最优解，最优为最优解，最优为最优解，最优值值值值S= 180S= 180S= 180S= 180线性规划及单纯形法(3)课件例例2 2 用大用大MM法求下列问题法求下列问题 max S = x max S = x1 1 +x +x2 2 s.t. x s.t. x1 1-x-x2 2   0 0 3x 3x1 1-x-x2 2   -3 -3 x x1 1,x ,x2 2   0 0线性规划及单纯形法(3)课件解：将问题化成标准形式解：将问题化成标准形式             max S =   x1  +x2                                                         s.t. -x1 +x2 +x3      = 0              -3x1  -x2            -x4= 3                 x1,x2 , x3 , x4   0线性规划及单纯形法(3)课件解：引入人工变量解：引入人工变量, x, x5 5   0 0 max S = x max S = x1 1 +x+x2 2 - Mx- Mx5 5 s.t. -xs.t. -x1 1+x+x2 2 +x+x3 3 = 0 = 0 -3x -3x1 1+x+x2 2 -x-x4 4 +x+x5 5 = 3= 3 x x1 1,x ,x2 2 , , x x3 3,x ,x4 4 , , x x5 5   0 0 线性规划及单纯形法(3)课件列出初始单纯形表列出初始单纯形表线性规划及单纯形法(3)课件计算检验数计算检验数：：线性规划及单纯形法(3)课件检验数最大的对应检验数最大的对应X2，，为进基变量为进基变量线性规划及单纯形法(3)课件最小比值：出基变量为最小比值：出基变量为X3，，主元主元（（1））线性规划及单纯形法(3)课件进行初等行变换，得到新的单纯形表进行初等行变换，得到新的单纯形表线性规划及单纯形法(3)课件计算检验数全小于零，此时计算检验数全小于零，此时 X= X= X= X=（（（（0 0 0 0，，，，0 0 0 0，，，，0 0 0 0，，，，0 0 0 0，，，，3 3 3 3））））t t t t ，，，，但人工变量不但人工变量不等于零，因此原问题无可行解。

等于零，因此原问题无可行解线性规划及单纯形法(3)课件。