线性规划精品课件

1、关于线性规划第一张，PPT共一百零一页，创作于2022年6月2决策变量：x1, ., xn表示要寻求的方案，每一组值就是一个方案；约束条件：线性等式或不等式目标函数：Z=(x1 xn) 线性式，求Z极大或极小线性规划模型特点第二张，PPT共一百零一页，创作于2022年6月3 一般式min z=c1x1+ c2x2+cnxnai1x1+ ai2x2+ ainxn =bi ,i=1,pai1x1+ ai2x2+ ainxn bi , i=p+1,mxj 0 , j=1,qxj 符号无限制， j=q+1,ns.t.目标函数（LP）第三张，PPT共一百零一页，创作于2022年6月4比例性：决策变量变化

2、引起目标的改变量与决策变量改变量成正比可加性：每个决策变量对目标和约束的影响独立于其它变量连续性：每个决策变量取连续值确定性：线性规划中的参数aij , bi , ci为确定值 隐含的假设第四张，PPT共一百零一页，创作于2022年6月5 矩阵形式说明： A1 A2 An a11 a12 a1n A= a21 a22 a2n am1 am2 amn x1 x= x2 xn b1 b= b2 bm c1 c= c2 cn约束矩阵决策向量右端向量价值向量第五张，PPT共一百零一页，创作于2022年6月6 LP问题的规范型： LP问题的标准型：LP问题的三种形式是等价的：min z=cTxAx bx

3、 0 s.t.min z=cTxAx=bx 0 s.t.LP问题的规范型LP问题的标准型LP问题的一般型第六张，PPT共一百零一页，创作于2022年6月7LP问题的规范型LP问题的一般型第七张，PPT共一百零一页，创作于2022年6月8LP问题的标准型LP问题的一般型第八张，PPT共一百零一页，创作于2022年6月9 例：将线性规划问题化成标准型：第九张，PPT共一百零一页，创作于2022年6月10解的概念：满足所有约束条件的一组x1, x2， xn的值称作线性规划的可行解，所有可行解构成的集合称作可行域。使目标函数取得最大或最小值的可行解称为线性规划问题的最优解；对应的目标函数的取值称为最优

4、值。求解线性规划问题就是求其最优解和相应的最优值。图解法？对于只有两个变量的线性规划问题，可以用在平面上作图的方法求解，这种方法称为图解法。 特点：图解法简单、直观，便于初学者了解线性规划基本原理和几何意义。2.2可行区域与基本可行解第十张，PPT共一百零一页，创作于2022年6月11step1.画直角坐标系； 线性规划问题图解法的步骤 对每个约束（包括非负约束）条件，先取等式得到一条直线（平面）并在坐标图中画出该直线，然后取一已知点来判断该点的坐标是否满足该约束条件，若满足，则可行域与已知点在所画直线的同侧，否则可行域在直线的另一侧。若所有的约束均已画出，则可在坐标系中画出可行域。step2

5、.依次做每条约束线，找出可行域;若不存在可行域,则该问题无界；step3.做目标函数线，根据目标类型平移,直到该线即将离开可行域时与该线接触的最后一点即为一最优解; 若该线可无限制地在可行域内移动,则该问题无界。第十一张，PPT共一百零一页，创作于2022年6月12例1、maxZ=-X1+ X2 2 X1-X2 -2X1-2X2 2X1+X2 5 X1 , X2 0 1.图解法第十二张，PPT共一百零一页，创作于2022年6月13解：(1)、确定可行域 X1 0 X1 =0 (纵) X2 0 X2=0 (横) 2 X1-X2 =-2 () (0,2) (-1,0)0123X2BCX1-2X2

6、=2 ()(0,-1) (2,0) 42 X1-X2 =-2X1-2X2 =2X1+X2 =5 ()(0,5) (5,0) X1+X2 =5(1,4)- X1+X2 =3- X1+X2 =0在该点取到最大值3A1A2A3A4OZ=-X1+ X2, Z=0 2 3 1解：(1)、确定可行域 X1 0 X1 =0 (纵) X2 0 X2=0 (横) 0123X2第十三张，PPT共一百零一页，创作于2022年6月14 2 3 10123X2A1BC42 X1-X2 =-2X1-2X2 =2X1+X2 =5(1,4)若目标函数改为min Z=4X1-2X2 2 X1-X2 -2X1-2X2 2X1+X

7、2 5 X1 , X2 0A2A3A4O第十四张，PPT共一百零一页，创作于2022年6月15最优解：A1A2线段上所有的点，最优值为-4X(1)=(0, 2)T , X(2)=(1,4)TX= X(1)+(1-) X(2) (0 1)X1 =1- X2=2+4 (1- )=4-2 (0 1)min Z=4X1-2X2 =-4 第十五张，PPT共一百零一页，创作于2022年6月16 2 3 10123X2A1BC42 X1-X2 =-2X1-2X2 =2X1+X2 =5(1,4)A2A3A4O可行域：由约束平面围起来的凸多边形区域，可行域内的每一个点代表一 个可行解。最优解：总是在可行域的边界

8、上，一般由可行域的顶点表示。有效与无效(紧与松)约束：与最优解相关的约束为有效(紧)约束。图解法的观察【1】第十六张，PPT共一百零一页，创作于2022年6月17无界无有限最优解例2、 maxZ=2X1+ 4X2 2X1+X2 8-2X1+X2 2X1 , X2 0Z=02X1+ X2=8-2X1+ X2=28246X240X1第十七张，PPT共一百零一页，创作于2022年6月18例3、 maxZ=3X1+2X2 -X1 -X2 1X1 , X2 0无解无可行解-1X2-1X10-X1-X2 =1第十八张，PPT共一百零一页，创作于2022年6月19如果可行域为空集，线性规划问题无可行解；如果

9、目标函数线可以无限制地在可行域内向改善的方向移动，线性规划问题无界；线性规划问题可能存在无穷多个最优解。图解法的观察（2） 唯一最优解 无穷多最优解 无有限最优解 无可行解有最优解无最优解总结第十九张，PPT共一百零一页，创作于2022年6月20两个变量的LP问题的解：(1)、可行域为凸多边形。(2)、若有最优解，定可在可行域的顶点得到。X(1)X(2)凸多边形凹多边形X(1)X(2)第二十张，PPT共一百零一页，创作于2022年6月212.可行区域的几何结构min Z=CTX AX =b X0A mn 满秩 X = (x1 xn)T D=XRn| AX =b, X0第二十一张，PPT共一百零

10、一页，创作于2022年6月22凸集没有凹陷部分，该集合内任取两点连线上的任何点都应该在集合内。 定义1：xSy凸集：S是n维欧氏空间的一个集合,如果对任意 x, yS, 0 1, 有x + (1 - ) y S。第二十二张，PPT共一百零一页，创作于2022年6月23定理1 D=XRn| AX =b, X0是凸集。第二十三张，PPT共一百零一页，创作于2022年6月24定义2： 给定bR1,及非零向量aTRn称集合H =XRn| aTX =b是Rn中的一个超平面.H+ =XRn| aTX bH- =XRn| aTX bH+，H-和超平面H都是凸集.H+和H-是由超平面H产生的两个闭的半空间.结

11、论：线性规划的可行域是凸集。第二十四张，PPT共一百零一页，创作于2022年6月25定义3：凸集凸集S的顶点X：S是一个凸集，XS，对任意X(1), X(2)S，X(1) X(2) ,和任意的 ，01,都有 X X(1)+(1-) X(2) .定义4：第二十五张，PPT共一百零一页，创作于2022年6月26a11 a1m a1m+1 a1na21 a2m a2m+1 a2n am1 amm amm+1 amnBN(m n) r(A)=m , 至少有一个m阶子式不为03、基本可行解及线性规划的基本原理第二十六张，PPT共一百零一页，创作于2022年6月27定义5：基(基阵) 秩为m的约束矩阵 A

12、mn的一个m阶子矩阵B是可逆矩阵，则方阵B称为对应LP问题的一个基。A= (A1 Am Am+1 An )=(BN) 基向量 非基向量X= (X1 Xm Xm+1 Xn )T=(XBT ，XNT)T 基变量 非基变量 XBT XNT第二十七张，PPT共一百零一页，创作于2022年6月28AX=b的求解A=(B N)X=(XBT ，XNT)T XB XN(B N) = bBXB +NXN=bBXB =b-NXNXB = B-1 b - B-1N XN第二十八张，PPT共一百零一页，创作于2022年6月29定义5：基本解对应于基B，X=为AX=b的一个解。B-1 b 0 基本可行解基B，基本解X=

13、若B-1 b0，称基B为可行基。 B-1 b 0 基本解中最多有m个非零分量。 基本解的数目不超过Cnm = 个。n!m!(n-m)!（续）第二十九张，PPT共一百零一页，创作于2022年6月30 X1+2X2 +X3 =30 3X1+2X2 +X4 =60 2X2 +X5=24 X1 X5 01 2 1 0 03 2 0 1 00 2 0 0 1A1 A2 A3 A4 A5A=例：Max Z=40X1 +50X2 第三十张，PPT共一百零一页，创作于2022年6月31X1X2X3X4X5X=b=306024基 B=(A3 A4 A5)=I 可逆 非基 N=(A1 A2)X3=30-( X1+

14、2 X2)X4=60-(3X1+2 X2)X5 =24 -2 X21 2 1 0 03 2 0 1 00 2 0 0 1A1 A2 A3 A4 A5A=Z=40X1 +50X2 第三十一张，PPT共一百零一页，创作于2022年6月32令X1 = X2 =0, X3=30, X4=60, X5=24X= = = XN 0 XB B-1 b 00306024 1 2 1又：1 =(A1 A2 A3 )= 3 2 0 0 2 0|B1|=60, 可逆第三十二张，PPT共一百零一页，创作于2022年6月33X1=12-(1/3 X4 -1/3 X5)X2=12-(1/2 X5 )X3 =-6-(- 1

15、/3 X4 -2/3 X5 )令X4=X5=0 X=(12, 12, -6, 0, 0)T不是可行解1 =(A1 A2 A3 )不是可行基。可以直接验证B-1 b 是否大于等于零。 第三十三张，PPT共一百零一页，创作于2022年6月34定理3：LP问题的可行解X是基本可行解X的非0分量对应的系数列向量线性无关证明：( )显然。 不妨设前k个分量非零。若A1 , , Ak 线性无关，则必有km。 若k=m,构成基，则X就是基本可行解；若km,可以在其余n-k列向量中再找出m-k个，构成m个线形无关的列向量构成基， X就是该基对应的基本可行解。第三十四张，PPT共一百零一页，创作于2022年6月

16、35可行域D中点X是顶点X是基本可行解定理4：第三十五张，PPT共一百零一页，创作于2022年6月36标准形式的LP问题有可行解该LP问题一定有基本可行解定理5：第三十六张，PPT共一百零一页，创作于2022年6月37标准形式的LP问题有有限的最优值该LP问题一定有基本可行解是最优解定理6:第三十七张，PPT共一百零一页，创作于2022年6月38若(LP)问题有可行解，则可行解集(可行域)是凸集(可能有界，也可能无界)，有有限个顶点。LP问题解的性质 (LP)问题的基本可行解 可行域的顶点。 若(LP)问题有最优解，必可以在基本可行解(顶点)达到。第三十八张，PPT共一百零一页，创作于2022

17、年6月39可行解基本解基本可行解个数有限，当约束条件为m个，n个变量时，基本可行解个数不超过:Cnm = n!m!(n-m)!(m 40 选X2从0，X1 =0X3 =30-2X2 0， X2 30/2 X4 =60-2X2 0， X2 60/2 X5 =24-2X2 0 ，X2 24/2 X2=min(30/2 , 60/2 , 24/2 ) =12X2进基变量， X5出基变量。min W=-40X1 -50X2 X1 +2X2 +X3 =30 3X1 +2X2 +X4 =60 2X2 +X5 =24 X1 X5 0第四十二张，PPT共一百零一页，创作于2022年6月43B2=(A3 A4

18、A2)min W=-40X1 -50X2 X1 +2X2 +X3 =30 3X1 +2X2 +X4 =60 2X2 +X5 =24 X1 X5 0min W=-600-40X1 +25X5 X1 +X3 -X5 =6 3X1 +X4 - X5 =36 X2 +1/2X5 =12 X1 X5 0 1/2 ，代入式， ，令X1 =X5 =0 X(2) =(0, 12, 6, 36, 0)T W(2) =-600第四十三张，PPT共一百零一页，创作于2022年6月44(2) 判断： min W=-600-40X1 +25X5 400， X(2)不是最优解。(3) 选X1从0， X5 =0 X3= 6

19、- X1 0 X4= 36-3X1 0 X2=12 0 X1=min( 6/1 , 36/3 ) =6X1进基， X3出基。min W=-600-40X1 +25X5 X1 +X3 -X5 =6 3X1 +X4 - X5 =36 X2 +1/2X5 =12 X1 X5 0第四十四张，PPT共一百零一页，创作于2022年6月45B3 =(A1 A4 A2 )minW=-840+40X3-15X5X1 +X3 -X5 =6 -3X3 + X4 +2X5 =18 X2 +1/2X5 =12令X3 =X5 =0 ,X(3) =(6, 12, 0, 18, 0)TW(3) =-840min W=-600

20、-40X1 +25X5 X1 +X3 -X5 =6 3X1 +X4 - X5 =36 X2 +1/2X5 =12 X1 X5 0代入式， -3*第四十五张，PPT共一百零一页，创作于2022年6月46(2) 判断：minW=-840+40X3-15X5 150 X(3)不是最优解(3) 选X5从0， X3 =0 X1=6 +X5 0 X4= 18 -2X5 0 X2=12-1/2 X5 0 X5=min( 18/2 , 12/1/2 ) =9X5进基， X4出基。minW=-840+40X3-15X5X1 +X3 -X5 =6 -3X3 + X4 +2X5 =18 X2 +1/2 X5 =12

21、第四十六张，PPT共一百零一页，创作于2022年6月47B4=(A1 A5 A2 )minW=-975+35/2X3 + 15/2X4X1 -1/2X3 + 1/2X4 = 15 -3/2X3 +1/2X4 + X5= 9 X2+3/4X3 - 1/4X4 = 15/2 令X3 =X4 =0 ,X(4) =(15, 15/2 , 0, 0 ,9 )T W(4)=-975minW=-840+40X3-15X5 X1 +X3 -X5 =6 -3X3 + X4 +2X5 =18 X2 +1/2 X5 =12 1/2 ， 代入式， +(1/2) ， -(1/4) 判断：minW=-975+35/2X3

22、 + 15/2X4 ，maxZ=975达到最优。第四十七张，PPT共一百零一页，创作于2022年6月48例1 x1 x2 x3 x4 x5-z0 40 50 0 0 0 x3x4x5306024 1 2 1 0 0 3 2 0 1 0 0 2 0 0 1maxZ=40X1 +50X2 X1 +2X2 +X3 =30 3X1 +2X2 +X4 =60 2X2 +X5 =24 X1 X5 0(-z)+40X1 +50X2 =0 X1 +2X2 +X3 =30 3X1 +2X2 +X4 =60 2X2 +X5 =24 X1 X5 0X2 30/2 X2 60/2 X2 24/2回顾第四十八张，PPT

23、共一百零一页，创作于2022年6月49例1 x1 x2 x3 x4 x5-z-600 40 0 0 0 -25 x3x4x263612 1 0 1 0 -1 3 0 0 1 -1 0 1 0 0 1/2(-z)+40X1 -25X5 =-600 X1 +X3 -X5 =6 3X1 +X4 -X5 =36 X2 +(1/2) X5 =12 X1 X5 0X1 6/1 X1 36/3第四十九张，PPT共一百零一页，创作于2022年6月50例1 x1 x2 x3 x4 x5-z-840 0 0 -40 0 15x1x4x261812 1 0 1 0 -1 0 0 -3 1 2 0 1 0 0 1/2

24、(-z) -40X3 +15X5 =-840 X1 +X3 -X5 =6 -3X3 +X4 +2X5 =18 X2 +1/2 X5 =12 X1 X5 0X5 18/2 X5 12/1/2第五十张，PPT共一百零一页，创作于2022年6月51例1(-z)-35/2X3 -15/2X4 =-975 X1 -1/2X3 +1/2X4 =15 -3/2X3 +1/2X4 +X5 =9 X2 +3/4X3 -1/4X4 =15/2 X1 X5 0 x1 x2 x3 x4 x5-z-975 0 0 -35/2 -15/2 0 x1x5x215915/2 1 0 -1/2 1/2 0 0 0 -3/2 1

25、/2 1 0 1 3/4 -1/4 0 X(4) =(15, 15/2 , 0, 0 ,9 )T maxZ=975第五十一张，PPT共一百零一页，创作于2022年6月520(0,0)X2X1A DCB(0,12)(6,12)(15,7.5)X(1) =(0, 0, 30, 60, 24 )T ；Z(1) =0X(2) =(0, 12, 6, 36, 0)T ； Z(2) =600X(3) =(6, 12, 0, 18, 0 )T ；Z(3) =840 X(4) =(15, 7.5, 0, 0, 9 )T ；Z(4) =975思考：线性规划问题的求解方法第五十二张，PPT共一百零一页，创作于20

26、22年6月单纯形法的理论基础（略）第五十三张，PPT共一百零一页，创作于2022年6月54为了叙述方便，我们不妨假设（LP）问题为如下形式：或典则方程组（典式）非基变量检验数第五十四张，PPT共一百零一页，创作于2022年6月55单纯形表 X1 X2 Xm Xm+1 Xm+k XnXB Z0 0 0 0 m+1 m+k nX1 b1 1 0 0 a1m+1 a1m+k a1nX2 b2 0 1 0 a2m+1 a2m+k a2nXr br 0 0 0 arm+1 arm+k arnXm bm 0 0 1 amm+1 amm+k ann P1 P2 Pm Pm+1 Pm+k Pn第五十五张，PP

27、T共一百零一页，创作于2022年6月56此时，B=(P1 P2 Pm )I对应的基本可行解为定理1：对解X(1) ，若检验数j ( j=1,n)全部 0,则X(1)为最优解。第五十六张，PPT共一百零一页，创作于2022年6月57定理2：对X(1)，若有某个非基变量Xkk0且相应的Pk =(a1k , ,amk )T 0，则原问题无有限最优解。第五十七张，PPT共一百零一页，创作于2022年6月58换基迭代公式：(1)、决定进基变量：maxj =k 0,则Xk 为进基变量(2)、决定离基变量：bi -aikXk 0 ( i=1 ,2 , m)，Xk biaik(aik0= min aik 0

28、=biaikbrark则第r个基变量（XBr）为换出变量。第五十八张，PPT共一百零一页，创作于2022年6月59定理3：在非退化情况下，经单纯形法得到的X(2) =(b1 - a1k , ,bm - amk ,0, , , ,0)T是基本可行解，且Z(2)0 =biaikbrark注：第五十九张，PPT共一百零一页，创作于2022年6月60单纯形法基本步骤(1)、定初始基，初始基本可行解，典式， 检验数(3)、若有k 0，Pk全 0，停， 没有有限最优解； 否则转(4)(2)、对应于非基变量检验数j全 0。 若是，停，得到最优解； 若否，转(3)。第六十张，PPT共一百零一页，创作于2022

29、年6月61= min aik 0 =biaikbrark定第r个基变量（XBr）为离基变量，ark为主元。由最小比值法求：kmaxj|j=1,n0 ,kXk Xk为进基变量j0(4)、第六十一张，PPT共一百零一页，创作于2022年6月62转(2) k 0 a1k 0ark 1amk 0初等行变换Pk =(5)、以ark为中心，换基迭代第六十二张，PPT共一百零一页，创作于2022年6月63在单纯形表上解决下述问题 maxZ=40X1 +50X2 X1 +2X2 +X3 =30 3X1 +2X2 +X4 =60 2X2 +X5 =24 X1 X5 0Min Z=-40X1-50X2第六十三张，

30、PPT共一百零一页，创作于2022年6月64 X1 X2 X3 X4 X5Z 0 40 50 0 0 0 X3 30 1 2 1 0 0 15X4 60 3 2 0 1 0 30X5 24 0 (2) 0 0 1 12 -600 40 0 0 0 -25X3 6 (1) 0 1 0 -1 6X4 36 3 0 0 1 -1 12X2 12 0 1 0 0 1/2 -840 0 0 -40 0 15X1 6 1 0 1 0 -1X4 18 0 0 -3 1 (2) 9X2 12 0 1 0 0 1/2 24第六十四张，PPT共一百零一页，创作于2022年6月65 z -975 0 0 -35/2

31、 -15/2 0 X1 15 1 0 -1/2 1/2 0 X5 9 0 0 -3/2 1/2 1 X2 15/2 0 1 3/4 -1/4 0本问题的最优解 X=(15, 15/2, 0, 0, 9)T Z=975第六十五张，PPT共一百零一页，创作于2022年6月66几点说明：(1)、例 minZ=-X1 -2X2X1 4X2 3X1+2X2 8 X1 , X2 0 X1 +X3 = 4 X2 +X4 = 3X1+2X2 +X5= 8 X1 ， ，X5 0第六十六张，PPT共一百零一页，创作于2022年6月67 X1 X2 X3 X4 X5Z 0 1 2 0 0 0X3 4 1 0 1 0

32、 0X4 3 0 (1) 0 1 0X5 8 1 2 0 0 1Z -6 1 0 0 -2 0X3 4 1 0 1 0 0 X2 3 0 1 0 1 0 X5 2 (1) 0 0 -2 1 (接下表)第六十七张，PPT共一百零一页，创作于2022年6月68 X1 X2 X3 X4 X5 Z -8 0 0 0 0 -1X3 2 0 0 1 (2) -1X2 3 0 1 0 1 0X1 2 1 0 0 -2 1Z -8 0 0 0 0 -1X4 1 0 0 1/2 1 -1/2 X2 2 0 1 -1/2 0 1/2 X1 4 1 0 1 0 0 非基变量检验数为0第六十八张，PPT共一百零一页，

33、创作于2022年6月69X(1)= (2,3) Z(1)=-8 X(2)= (4,2) Z(2)=-8无穷多解全部解：X= + (1-) (0 1)2 4 3 2第六十九张，PPT共一百零一页，创作于2022年6月70(2)、3X1+4X2 64X1+ X2 23X1 +2X2 3X1 , X2 0Min Z=-10X1-12X2 X1 X2 X3 X4 X5Z 0 10 12 0 0 0X3 6 3 (4) 1 0 0X4 2 4 1 0 1 0X5 3 3 2 0 0 1第七十张，PPT共一百零一页，创作于2022年6月71 X1 X2 X3 X4 X5 z 0 10 12 0 0 0 i

34、 X3 6 3 (4) 1 0 0 3/2 X4 2 4 1 0 1 0 2/1 X5 3 3 2 0 0 1 3/2 z -18 1 0 -3 0 0 i X2 3/2 3/4 1 1/4 0 0 2 X4 1/2 13/4 0 -1/4 1 0 2/13 X5 0 (3/2) 0 -1/2 0 1 0 z -18 0 0 -8/3 0 -2/3 X2 3/2 0 1 1/2 0 -1/2 X4 1/2 0 0 5/6 1 -13/6 X1 0 1 0 -1/3 0 2/3第七十一张，PPT共一百零一页，创作于2022年6月72退化解X *=(0, 3/2, 0, 1/2, 0)TZmin=

35、-18第七十二张，PPT共一百零一页，创作于2022年6月73 X1 X2 X3 X4 X5Z 0 4 1 0 0 0X3 2 -1 1 1 0 0X4 4 (1) -4 0 1 0X5 8 1 -2 0 0 1(3)例：minZ= -4X1 -X2 -X1+ X2 2 X1 -4X2 4 X1 -2X2 8X1 , X2 0第七十三张，PPT共一百零一页，创作于2022年6月74Z -16 0 17 0 -4 0X3 6 0 -3 1 1 0X1 4 1 -4 0 1 0X5 4 0 (2) 0 -1 1z - 50 0 0 0 9/2 -17/2X3 12 0 0 1 -1/2 3/2X1

36、 12 1 0 0 -1 2X2 2 0 1 0 -1/2 1/2 第七十四张，PPT共一百零一页，创作于2022年6月75本问题无界。X1X2OZ=0Z= -4X1 -X2 X1 -2X2 8-X1+ X2 2 X1 -4X2 4 第七十五张，PPT共一百零一页，创作于2022年6月76一、两阶段法：原问题 minZ= Cj xj j=1nxj 0j=1naij xj =bi 0 ( i=1,2, ,m)作辅助问题minW= yi i=1mxj ， yi 0j=1naij xj + yi =bi ( i=1,2, ,m)2.4 初始解第七十六张，PPT共一百零一页，创作于2022年6月77第

37、1阶段 最优基B* min = *(1)、 *0 (2)、 * =0 yi 0( i=1,2, ,m) B* 基变量无人工变量 B* 基变量含人工变量yr 单纯形表中， yr+ark yk +arj xj =0 () k Jj JJ：非基变量下标集合, 判定原问题无可行解。第七十七张，PPT共一百零一页，创作于2022年6月781) arj 全 =0 () 式多余方程2) arj 有0 元，设为ars 0 以ars为主元，换基迭代，最后得到第七十八张，PPT共一百零一页，创作于2022年6月79maxZ= -X1 +2X2 X1 +X2 2-X1 +X2 1 X2 3X1 X2 0例1：min

38、Z= X1 - 2X2 minW=X6 +X7 X1 +X2 -X3 +X6 =2-X1 +X2 -X4 +X7 =1 X2 +X5 =3X1 X7 0 X1 +X2 -X3 =2-X1 +X2 -X4 =1 X2 +X5 =3X1 X5 0第一阶段：求第七十九张，PPT共一百零一页，创作于2022年6月80 0 0 0 0 0 -1 -1 X1 X2 X3 X4 X5 X6 X7 W 3 0 2 -1 -1 0 0 0 X6 2 1 1 -1 0 0 1 0 X7 1 -1 (1) 0 -1 0 0 1 X5 3 0 1 0 0 1 0 0 W 1 +2 0 -1 1 0 0 -2 X6 1

39、 (2) 0 -1 1 0 1 -1 X2 1 -1 1 0 -1 0 0 1 X5 2 1 0 0 1 1 0 -1 W 0 0 0 0 0 0 -1 -1 X1 1/2 1 0 -1/2 1/2 0 1/2 -1/2 X2 3/2 0 1 -1/2 -1/2 0 1/2 1/2 X5 3/2 0 0 1/2 1/2 1 -1/2 -1/2 第八十张，PPT共一百零一页，创作于2022年6月81 -1 2 0 0 0 X1 X2 X3 X4 X5 z -5/2 0 0 1/2 3/2 0 X1 1/2 1 0 -1/2 (1/2) 0 X2 3/2 0 1 -1/2 -1/2 0 X5 3/

40、2 0 0 1/2 1/2 1 z -4 -3 0 2 0 0 X4 1 2 0 -1 1 0 X2 2 1 1 -1 0 0 X5 1 -1 0 (1) 0 1 z - 6 -1 0 0 0 -2 X4 2 1 0 0 1 1 X2 3 0 1 0 0 1 X3 1 -1 0 1 0 1第二阶段第八十一张，PPT共一百零一页，创作于2022年6月82例2：maxZ= 2X1 +X2 5X1 +10X2 82X1 +2X2 1X1 ，X2 0minZ= -2X1 -X2 第(1)阶段：minW= X55X1 +10X2 -X3 +X5 =82X1 +2X2 +X4 =1X1 X5 0第八十二张

41、，PPT共一百零一页，创作于2022年6月83 0 0 0 0 -1 X1 X2 X3 X4 X5 W 8 5 10 -1 0 0X5 8 5 10 -1 0 1X4 1 2 (2) 0 1 0W 3 -5 0 -1 -5 0X5 3 -5 0 -1 -5 1X2 1/2 1 1 0 1/2 0第八十三张，PPT共一百零一页，创作于2022年6月84X2X1O5X1 +10X2 82X1 +2X2 1X1 ，X2 05X1 +10X2 810X1 +10X2 5X1 ，X2 0第八十四张，PPT共一百零一页，创作于2022年6月85例3、求minZ= +4X1 +3X3 1/2X1 +X2+1

42、/2X3-2/3X4 = 23/2X1 +3/4X3 =33X1 -6X2 +4X4 = 0X1 , X2 , X3 , X4 0满足第八十五张，PPT共一百零一页，创作于2022年6月86 0 0 0 0 -1 -1 -1 X1 X2 X3 X4 y1 y2 y3 W 5 5 -5 5/4 10/3 0 0 0 y1 2 1/2 1 1/2 -2/3 1 0 0 y2 3 3/2 0 3/4 0 0 1 0 y3 0 3 -6 0 4 0 0 1 W 5 0 5 5/4 -10/3 0 0 -5/3 y1 2 0 2 1/2 -4/3 1 0 -1/6 y2 3 0 3 3/4 -2 0 1

43、 -1/2 X1 0 1 -2 0 4/3 0 0 1/3第 一 阶 段 一二第八十六张，PPT共一百零一页，创作于2022年6月87 W 0 0 0 0 0 -5/2 0 -5/4 X2 1 0 1 1/4 -2/3 1/2 0 -1/2 y2 0 0 0 0 0 -3/2 1 -1/4 X1 2 1 0 1/2 0 1 0 1/6第一阶段三 -4 0 -3 0 X1 X2 X3 X4 Z 8 0 0 -1 0 X2 1 0 1 1/4 -2/3 X1 2 1 0 1/2 0第二阶段第八十七张，PPT共一百零一页，创作于2022年6月88例4、求minZ=4X1 +3X31/2X1 +X2

44、+1/2X3 -2/3X4 =23/2X1 -1/2X3 =33X1 -6X2 +4X4 =0X1 , X2 , X3 , X4 0满足第八十八张，PPT共一百零一页，创作于2022年6月89 0 0 0 0 -1 -1 -1 X1 X2 X3 X4 y1 y2 y3 W 5 5 - 5 0 10/3 0 0 0 y1 2 1/2 1 1/2 -2/3 1 0 0 y2 3 3/2 0 -1/2 0 0 1 0 y3 0 3 -6 0 4 0 0 1 W 5 0 5 0 -10/3 0 0 -5/3 y1 2 0 2 1/2 -4/3 1 0 -1/6 y2 3 0 3 -1/2 -2 0 1 -1/2 X1 0 1 -2 0 4/3 0 0 1/3第 一 阶 段 一二第八十九张，PPT共一百零一页，创作于2022年6月90第 一 阶 段 W 0 0 0 -5/4 0 -5/2 0 -5/4 X2 1 0 1 1/4 -2/3 1/2 0 -1/12 y2 0 0 0 -5/4 0 -3/2 1 -1/4 X1 2 1 0 1/2 0 1 0 1