线性规划课件.ppt

《线性规划课件.ppt》由会员分享，可在线阅读，更多相关《线性规划课件.ppt（101页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关于线性规划关于线性规划现在学习的是第1页，共101页2 2决决策策变变量量：x1,.,xn表示要寻求的方案，每一组值就是一个方案；约束条件：线性等式或不等式约束条件：线性等式或不等式目标函数：目标函数：Z=Z=(x x1 1 x xn n)线性式，求线性式，求Z Z极大或极小极大或极小线性规划模型特点现在学习的是第2页，共101页3 3 一般式一般式min z=c1x1+c2x2+cnxnai1x1+ai2x2+ainxn=b=bi i,i=1,i=1,p,pai1x1+ai2x2+ainxn bi ,i=p+1,mxj j 0,0,j=1,qxj 符号无限制符号无限制，j=q+1,ns.t

2、.目标函数目标函数（LP）现在学习的是第3页，共101页4 4比例性：决策变量变化引起目标的改变量与决策变量改变量成正比例性：决策变量变化引起目标的改变量与决策变量改变量成正比比可加性：每个决策变量对目标和约束的影响独立于其它变量可加性：每个决策变量对目标和约束的影响独立于其它变量连续性：每个决策变量取连续值连续性：每个决策变量取连续值确定性：线性规划中的参数确定性：线性规划中的参数aij,bi,ci为确定值为确定值 隐含的假设现在学习的是第4页，共101页5 5 矩阵形式说明：矩阵形式说明：A A1 1 A A2 2 A An n a11 a12 a1n A=A=a21 a22 a2n am

3、1 am2 amn x1 x=x2 xn b1 b=b2 bm c1 c=c2 cn约束矩阵约束矩阵决决策策向向量量右右端端向向量量价价值值向向量量现在学习的是第5页，共101页6 6 LP问题的规范型：问题的规范型：LP问题的标准型：问题的标准型：LP问题的三种形式是等价的：问题的三种形式是等价的：min z=cTxAx bx 0 0 s.t.min z=cTxAx=bx 0 0 s.t.LP问题的规范型问题的规范型LP问题的标准型问题的标准型LP问题的一般型问题的一般型现在学习的是第6页，共101页7 7LP问题的规范型问题的规范型LP问题的一般型问题的一般型现在学习的是第7页，共101页

4、8 8LP问题的标准型问题的标准型LP问题的一般型问题的一般型现在学习的是第8页，共101页9 9 例：将线性规划问题化成标准型：例：将线性规划问题化成标准型：现在学习的是第9页，共101页1010解的概念：满足所有约束条件的一组x1,x2，xn的值称作线性规划的可行解，所有可行解构成的集合称作可行域。使目标函数取得最大或最小值的可行解称为线性规划问题的最优解；对应的目标函数的取值称为最优值。求解线性规划问题就是求其最优解和相应的最优值。图解法？对于只有两个变量的线性规划问题，可以用在平面上作图的方法求解，这种方法称为图解法。特点：图解法简单、直观，便于初学者了解线性规划基本原理和几何意义。2

5、.2可行区域与基本可行解可行区域与基本可行解现在学习的是第10页，共101页1111step1.画直角坐标系；线性规划问题图解法的步骤 对每个约束（包括非负约束）条件，先取等式得到一条直线（平面）并在坐标图中画出该直线，然后取一已知点来判断该点的坐标是否满足该约束条件，若满足，则可行域与已知点在所画直线的同侧，否则可行域在直线的另一侧。若所有的约束均已画出，则可在坐标系中画出可行域。step2.依次做每条约束线，找出可行域;若不存在可行域,则该问题无界；step3.做目标函数线，根据目标类型平移,直到该线即将离开可行域时与该线接触的最后一点即为一最优解;若该线可无限制地在可行域内移动,则该问题

6、无界。现在学习的是第11页，共101页1212例例1、maxZ=-X1+X2 2 X1-X2 -2X1-2X2 2X1+X2 5 X1,X2 0 0 1.1.图解法图解法现在学习的是第12页，共101页1313解：解：(1)、确定可行域、确定可行域 X1 0 0 X1=0=0(纵纵)X2 0 0 X2=0=0(横横)2 X1-X2=-2 ()(0,2)(-1,0)0123X2BCX1-2X2=2 ()(0,-1)(2,0)42 X2 X1 1-X-X2 2 =-2=-2X X1 1-2X-2X2 2 =2=2X1+X2=5 ()(0,5)(5,0)X X1 1+X+X2 2 =5=5(1,4)

7、(1,4)-X-X1 1+X+X2 2 =3=3-X-X1 1+X+X2 2 =0=0在该点取到最在该点取到最大值大值3 3A1A2A3A4OZ=-X1+X2,Z=0 2 3 1解：解：(1)、确定可行域、确定可行域 X1 0 0 X1=0=0(纵纵)X2 0 0 X2=0=0(横横)0123X2现在学习的是第13页，共101页1414 2 3 10123X2A1BC42 X2 X1 1-X-X2 2 =-2=-2X X1 1-2X-2X2 2 =2=2X X1 1+X+X2 2 =5=5(1,4)(1,4)若目标函数改为若目标函数改为min Z=4X1-2X2 2 X1-X2 -2X1-2X

8、2 2X1+X2 5 X1,X2 0 0A2A3A4O现在学习的是第14页，共101页1515最优解：最优解：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 0 1 1)min Z=4X1-2X2=-4 现在学习的是第15页，共101页1616 2 3 10123X2A1BC42 X2 X1 1-X-X2 2 =-2=-2X X1 1-2X-2X2 2 =2=2X X1 1+X+X2 2 =5=5(1,4)(1,4)A2A3A4O可行域：由约束平面围

9、起来的凸多边形区域，可行域内的每一个点代表一 个可行解。最优解：总是在可行域的边界上，一般由可行域的顶点表示。有效与无效(紧与松)约束：与最优解相关的约束为有效(紧)约束。图解法的观察【1】现在学习的是第16页，共101页1717无界无界无有限最优解无有限最优解例例2、maxZ=2X1+4X2 2X1+X2 8 8-2X1+X2 2X1,X2 0 0Z=02X1+X2=8-2X1+X2=28246X240X1现在学习的是第17页，共101页1818例例3、maxZ=3X1+2X2-X1-X2 1 1X1,X2 0 0无解无解无可行解无可行解-1X2-1X10-X-X1 1-X-X2 2 =1=

10、1现在学习的是第18页，共101页1919如果可行域为空集，线性规划问题无可行解；如果目标函数线可以无限制地在可行域内向改善的方向移动，线性规划问题无界；线性规划问题可能存在无穷多个最优解。图解法的观察（2）唯一最优解唯一最优解 无穷多最优解无穷多最优解 无有限最优解无有限最优解 无可行解无可行解有最优解有最优解无最优解无最优解总结总结现在学习的是第19页，共101页2020两个变量的两个变量的LP问题的解：问题的解：(1)、可行域为凸多边形。、可行域为凸多边形。(2)、若有最优解，定可在可行域的顶点得到。、若有最优解，定可在可行域的顶点得到。X(1)X(2)凸多边形凸多边形凹多边形凹多边形X

11、(1)X(2)现在学习的是第20页，共101页21212.可行区域的几何结构min Z=CTX AX=b X 0 0A A mn 满秩满秩 X=(x1 xn)T D=D=XRXRn n|AX=b,X AX=b,X 0 0现在学习的是第21页，共101页2222凸集没有凹陷部分，该集合内任取凸集没有凹陷部分，该集合内任取两点连线上的任何点都应该在集合内。两点连线上的任何点都应该在集合内。定义定义1：xSy凸集凸集：S S是是n维欧氏空间的一个集合维欧氏空间的一个集合,如果对任意如果对任意 x,y S,0 1,有有 x+(1-)y S。现在学习的是第22页，共101页2323定理定理1 1 D=X

12、Rn|AX=b,X 0是凸集。是凸集。现在学习的是第23页，共101页2424定义定义2：给定给定bRR1 1,及非零向量及非零向量a aT TRRn n称集合称集合H=XRH=XRn n|a|aT TX=bX=b 是是R Rn n中的一个超平面中的一个超平面.H H+=XR=XRn n|a|aT TX X b b H H-=XR=XRn n|a|aT TX X b b H H+，H H-和超平面和超平面H H都是凸集都是凸集.H H+和和H H-是由超平面是由超平面H H产生的两个闭的半空间产生的两个闭的半空间.结论：线性规划的可行域是凸集。结论：线性规划的可行域是凸集。现在学习的是第24页

13、，共101页2525定义定义3 3：凸集：凸集凸集凸集S的顶点的顶点X：S是是一个一个凸集，凸集，XSS，对任意对任意X(1),X(2)SS，X X(1)(1)X X(2)(2),和任意的和任意的 ，0 0 11,都有都有 X X(1)+(1-)X(2).定义定义4 4：现在学习的是第25页，共101页2626a11 a1m a1m+1 a1na21 a2m a2m+1 a2n am1 amm amm+1 amnBN(m n)r(A)=m,至少有一个至少有一个m阶子式不为阶子式不为03 3、基本可行解及线性规划的基本原理、基本可行解及线性规划的基本原理现在学习的是第26页，共101页2727定

14、义定义5：基：基(基阵基阵)秩为秩为m m的约束矩阵的约束矩阵 A Amnmn的的一个一个m阶子阶子矩阵矩阵B是可逆矩阵，则方阵是可逆矩阵，则方阵B称为对应称为对应LP问题的一个基。问题的一个基。A=(A1 Am Am+1 An)=(BN)基向量基向量 非基向量非基向量X=(X1 Xm Xm+1 Xn)T=(XBT，XNT)T 基变量基变量 非基变量非基变量 XBT XNT现在学习的是第27页，共101页2828AX=b的求解的求解A=(B N)X=(XBT，XNT)T XB XN(B N)=bBXB+NXN=bBXB=b-NXNXB=B-1 b-B-1N XN现在学习的是第28页，共101页

15、2929定义定义5：基本解：基本解对应于基对应于基B，X=为为AX=b的一个解。的一个解。B-1 b 0 基本可行解基本可行解基基B，基本解，基本解X=若若B-1 b 0 0，称基，称基B B为可行基。为可行基。B-1 b 0 基本解中最多有基本解中最多有m m个非零分量。个非零分量。基本解的数目不超过基本解的数目不超过Cnm=个。个。n!m!(n-m)!（续）（续）现在学习的是第29页，共101页3030 X1+2X2+X3=30=30 3X1+2X2 +X4=60 2X2 +X5=24 X1 X5 0 01 2 1 0 03 2 0 1 00 2 0 0 1A1 A2 A3 A4 A5A=

16、例：例：Max Z=40X1+50X2 现在学习的是第30页，共101页3131X1X2X3X4X5X=b=306024基基 B=(A3 A4 A5)=I 可逆可逆 非基非基 N=(A1 A2)X3=30-(X1+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 现在学习的是第31页，共101页3232令令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|

17、B1|=60,可逆可逆现在学习的是第32页，共101页3333X1=12-(1/3 X4-1/3 X5)X2=12-(1/2 X5)X3=-6-(-1/3 X4-2/3 X5)令令X4=X5=0 X=(12,12,-6,0,0)T不是可行解不是可行解1=(A1 A2 A3)不是可行基。不是可行基。可以直接验证可以直接验证B-1 b 是否大于等于零。是否大于等于零。现在学习的是第33页，共101页3434定理定理3：LP问题的可问题的可行解行解X是基本是基本可行解可行解X的非的非0分量对应分量对应的系数列向量线的系数列向量线性无关性无关证明证明：()显然。显然。不妨设前不妨设前k个分量非零。若个

18、分量非零。若A1,Ak 线性线性无关，无关，则必有则必有km。若若k=m,构成基构成基，则则X就是基本可行解；就是基本可行解；若若km,可以在其余可以在其余n-k列向量中再找出列向量中再找出m-k个，构成个，构成m个线形个线形无关的列向量构成基，无关的列向量构成基，X就是该基对应的基本可行解。就是该基对应的基本可行解。现在学习的是第34页，共101页3535可行域可行域D中点中点X是顶点是顶点X是基本可行解是基本可行解定理定理4：现在学习的是第35页，共101页3636标准形式的标准形式的LP问题有可行解问题有可行解该该LP问题一定问题一定有基本可行解有基本可行解定理定理5：现在学习的是第36

19、页，共101页3737标准形式的标准形式的LP问题问题有有限的最优值有有限的最优值该该LP问题一定有基问题一定有基本可行解是最优解本可行解是最优解定理定理6:现在学习的是第37页，共101页3838若若(LP)(LP)问题有可行解，则可行解集问题有可行解，则可行解集(可行域可行域)是凸集是凸集(可能有界，可能有界，也可能无界也可能无界)，有有限个顶点。，有有限个顶点。LP问题解的性质 (LP)问题的基本可行解问题的基本可行解 可行域的顶点。可行域的顶点。若若(LP)问题有最优解，必可以在基本可行解问题有最优解，必可以在基本可行解(顶点顶点)达到。达到。现在学习的是第38页，共101页3939可

20、可行行解解基基本本解解基本可行解个数有限，当约束条件为基本可行解个数有限，当约束条件为m个，个，n个变量个变量时，基本可行解个数不超过时，基本可行解个数不超过:Cnm=n!m!(n-m)!(m 40 选选X2从从0，X1=0X3 =30-2X2 0 0，X2 30/2 X4 =60-2X2 0 0，X2 60/2 X5=24-2X2 0 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 0现在学习

21、的是第42页，共101页4343B B2 2=(A3 A4 A2)min W=-40X1-50X2 X1+2X2+X3 =30 3X1+2X2 +X4 =60 2X2 +X5=24 X1 X5 0 0min W=-600-40X1+25X5 X1 +X3 -X5=6 3X1 +X4-X5=36 X2 +1/2X5=12 X1 X5 0 0 1/2，代入代入式，式，令令X1=X5=0 X(2)=(0,12,6,36,0)T W(2)=-600现在学习的是第43页，共101页4444(2)(2)判断：判断：min W=-600-40X1+25X5 400，X(2)不是不是最优解。最优解。(3)(3

22、)选选X1从从0，X5=0 X3=6-X1 0 0 X4=36-3X1 0 0 X2=12 0 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 0现在学习的是第44页，共101页4545B3=(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-40X1

23、+25X5 X1 +X3 -X5=6 3X1 +X4-X5=36 X2 +1/2X5=12 X1 X5 0 0代入代入式，式，-3*-3*现在学习的是第45页，共101页4646(2)(2)判断：判断：minW=-840+40X3-15X5 150 X(3)不是最优解不是最优解(3)(3)选选X5从从0，X3=0 X1=6 +X5 0 0 X4=18 -2X5 0 0 X2=12-1/2 X5 0 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

24、现在学习的是第46页，共101页4747B4=(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/2)，-(1/4)判断：判断：minW=-975+35/2X3+15/2X4 ，maxZ=975达到最优。达到最优。现在

25、学习的是第47页，共101页4848例例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 0(-z)+40X1+50X2 =0=0 X1+2X2+X3 =30 3X1+2X2 +X4 =60 2X2 +X5=24 X1 X5 0 0X2 30/2 X2 60/2 X2 24/2回顾现在学习的是第48页，共101页4949例例1 x1 x2 x3 x4 x5-z-600 4

26、0 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=-600 X1 +X3 -X5=6 3X1 +X4 -X5=36 X2 +(1/2)X5=12 X1 X5 0 0X1 6/1 X1 36/3现在学习的是第49页，共101页5050例例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(-z)-40X3 +15X5=-840=-840 X1 +X3 -X5=6 -3X3+X4 +

27、2X5=18 X2 +1/2 X5=12 X1 X5 0 0X5 18/2 X5 12/1/2现在学习的是第50页，共101页5151例例1(-z)-35/2X3-15/2X4 =-975=-975 X1 -1/2X3+1/2X4 =15 -3/2X3+1/2X4+X5 =9 X2+3/4X3-1/4X4 =15/2 X1 X5 0 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/2 1 0 1 3/4 -1/4 0 X(4)=(15,15/2,0,0,9)T maxZ=975ma

28、xZ=975现在学习的是第51页，共101页52520(0,0)X X2 2X X1 1A A D DC CB B(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思考：线性规划问题的求解方法现在学习的是第52页，共101页单纯形法的理论基础（略）单纯形法的理论基础（略）现在学习的是第53页，共101页5454为了叙述方便，我们不妨假设（为了叙述方便，我们不妨假设（LPLP）问题

29、为如下形式：）问题为如下形式：或或典则方程组（典典则方程组（典式）式）非基变量检验非基变量检验数数现在学习的是第54页，共101页5555单纯形表单纯形表 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 P Pm m P Pm+1 m+1 P Pm+k m+k P Pn n现在学习的是第55页，共101页5656此时，此时，B=(P

30、1 P2 Pm)I对应的基本可行解为对应的基本可行解为定理定理1 1：对解：对解X(1)，若检验数，若检验数 j(j=1,n)全部全部 0,则则X(1)为为最优解。最优解。现在学习的是第56页，共101页5757定理定理2 2：对：对X(1)，若有某个非基变量，若有某个非基变量Xk k00且相应的且相应的Pk=(a1k ,amk)T 0，则原问题无有限最优解。则原问题无有限最优解。现在学习的是第57页，共101页5858换基迭代公式：换基迭代公式：(1)、决定进基变量：决定进基变量：maxmax j=k 0,则则Xk 为为进基进基变量变量(2)、决定离基变量：决定离基变量：bi-aikXk 0

31、 0(i=1,2,m)，Xk biaik(aik 0 0=min aik 0 =0 =biaikbrark则第则第r r个基变量（个基变量（X XBr）为换出变量为换出变量。现在学习的是第58页，共101页5959定理定理3：在非退化情况下，经单纯形法得到的：在非退化情况下，经单纯形法得到的X(2)=(b1-a1k ,bm-amk ,0,0)T是基本可行解，且是基本可行解，且Z(2)0 =0 =biaikbrark注：现在学习的是第59页，共101页6060单纯形法基本步骤(1)、定初始基，初始基本可行解，典式，、定初始基，初始基本可行解，典式，检验数检验数(3)、若有若有 k 0 0，Pk全

32、全 0，停，停，没有有限最优解；没有有限最优解；否则转否则转(4)(2)、对应于非基变量检验数、对应于非基变量检验数 j全全 0。若是，停，得到最优解；若是，停，得到最优解；若否，转若否，转(3)。现在学习的是第60页，共101页6161=min aik 0 =0 =biaikbrark定第定第r r个基变量（个基变量（X XBr）为为离基离基变量，变量，a ark为为主元。主元。由最小由最小比值法求：比值法求：k kmaxmax j j|j=1,|j=1,n,n 0 0,kXk X Xk k为为进基变量进基变量 j00(4)、现在学习的是第61页，共101页6262转转(2)(2)k 0 a

33、1k 0ark 1amk 0初等行变换初等行变换Pk=(5)、以、以a ark为中心，换基迭代为中心，换基迭代现在学习的是第62页，共101页6363在单纯形表上解决下述问题 maxZ=40X1+50X2 X1+2X2+X3 =30 3X1+2X2 +X4 =60 2X2 +X5=24 X1 X5 0 0Min ZMin Z=-40X=-40X1 1-50X-50X2 2现在学习的是第63页，共101页6464 X1 X2 X3 X4 X5Z 0 40 50 0 0 0 0 40 50 0 0 0 X3 30 1 2 1 0 0 15 30 1 2 1 0 0 15X4 6060 3 3 2

34、0 1 0 302 0 1 0 30X5 24 0 (2)0 0 1 12 24 0 (2)0 0 1 12 -600 40 0 0 0 -25 -600 40 0 0 0 -25X3 6 (1)0 1 0 -1 66 (1)0 1 0 -1 6X4 36 3 0 0 1 -1 1236 3 0 0 1 -1 12X2 12 0 1 0 0 1/2 12 0 1 0 0 1/2 -840 0 0 -40 0 15 -840 0 0 -40 0 15X1 6 1 0 1 0 -16 1 0 1 0 -1X4 18 0 0 -3 1 (2)9 18 0 0 -3 1 (2)9X2 12 0 1 0

35、 0 1/2 24 12 0 1 0 0 1/2 24现在学习的是第64页，共101页6565 z -975 0 0 -35/2 -15/2 0-975 0 0 -35/2 -15/2 0 X1 15 1 0 -1/2 1/2 0 15 1 0 -1/2 1/2 0 X5 9 0 0 -3/2 1/2 1 9 0 0 -3/2 1/2 1 X2 15/2 0 1 3/4 -1/4 0 15/2 0 1 3/4 -1/4 0本问题的最优解本问题的最优解 X=(15,15/2,0,0,9)T Z=975现在学习的是第65页，共101页6666几点说明：几点说明：(1)(1)、例、例 minZ=-m

36、inZ=-X1-2X2X1 4X2 3X1+2X2 8 X1,X2 0 0 X1 +X3 =4 X2 +X4 =3X1+2X2 +X5=8 X1，X5 0 0现在学习的是第66页，共101页6767 X1 X2 X3 X4 X5Z 0 1 2 0 0 00 1 2 0 0 0X3 4 1 0 1 0 0 4 1 0 1 0 0X4 3 0 (1)0 1 03 0 (1)0 1 0X5 8 1 2 0 0 1 8 1 2 0 0 1Z -6 1 0 0 -2 0 -6 1 0 0 -2 0X3 4 1 0 1 0 0 4 1 0 1 0 0 X2 3 0 1 0 1 0 3 0 1 0 1 0

37、X5 2 2 (1)0 0 -2 1 (1)0 0 -2 1 (接下表接下表)现在学习的是第67页，共101页6868 X1 X2 X3 X4 X5 Z -8 0 0 0 0 -18 0 0 0 0 -1X3 2 0 0 1 (2)-1 2 0 0 1 (2)-1X2 3 0 1 0 1 03 0 1 0 1 0X1 2 1 0 0 -2 1 2 1 0 0 -2 1Z -8 0 0 0 0 -1 -8 0 0 0 0 -1X4 1 0 0 1/2 1 -1/2 1 0 0 1/2 1 -1/2 X2 2 0 1 -1/2 0 1/2 2 0 1 -1/2 0 1/2 X1 4 4 1 0 1

38、 0 0 1 0 1 0 0 非基变量检验数为非基变量检验数为0 0现在学习的是第68页，共101页6969X X(1)(1)=(2,3)Z Z(1)(1)=-8=-8 X X(2)(2)=(4,2)Z Z(2)(2)=-8=-8无穷多解无穷多解全部解：全部解：X X=+(1-)(0 1)2 4 3 2现在学习的是第69页，共101页7070(2)(2)、3X1+4X2 64X1+X2 23X1+2X2 3X1,X2 0 0Min Z=-10XMin Z=-10X1 1-12X-12X2 2 X1 X2 X3 X4 X5Z 0 10 12 0 0 0X3 6 3 (4)1 0 0X4 2 4

39、1 0 1 0X5 3 3 2 0 0 1现在学习的是第70页，共101页7171 X1 X2 X3 X4 X5 z 0 10 12 0 0 0 0 10 12 0 0 0 i i X3 6 3 (4)1 0 0 3/2 6 3 (4)1 0 0 3/2 X4 2 4 1 0 1 0 2/12 4 1 0 1 0 2/1 X5 3 3 2 0 0 1 3/2 3 3 2 0 0 1 3/2 z -18 1 0 -3 0 0 -18 1 0 -3 0 0 i i X2 3/2 3/4 1 1/4 0 0 23/2 3/4 1 1/4 0 0 2 X4 1/2 13/4 0 -1/4 1 0 2/

40、131/2 13/4 0 -1/4 1 0 2/13 X5 0 0 (3/2)0 -1/2 0 1 0(3/2)0 -1/2 0 1 0 z -18 0 0 -8/3 0 -2/3 18 0 0 -8/3 0 -2/3 X2 3/2 0 1 1/2 0 -1/23/2 0 1 1/2 0 -1/2 X4 1/2 0 0 5/6 1 -13/6 1/2 0 0 5/6 1 -13/6 X1 0 1 0 -1/3 0 2/30 1 0 -1/3 0 2/3现在学习的是第71页，共101页7272退化解退化解X X*=(0,3/2,0,1/2,0)TZ Zminmin=-18现在学习的是第72页，共

41、101页7373 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)(3)例：例：minZ=-4X1-X2-X1+X2 2 X1-4X2 4 X1-2X2 8X1,X2 0现在学习的是第73页，共101页7474Z -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 12 1 0 0 -1 2X2 2 0 1 0 -1/2 1/2 现在学

42、习的是第74页，共101页7575本问题无界。本问题无界。X1X2OZ=0Z=-4X1-X2 X1-2X2 8-X1+X2 2 X1-4X2 4 现在学习的是第75页，共101页7676一、两阶段法：一、两阶段法：原问题原问题 minZ=Cj xj j=1n xj 0j=1n aij xj=bi 0(i=1,2,m)作辅助问题作辅助问题minW=yi i=1m xj，yi 0j=1n aij xj+yi=bi(i=1,2,m)2.4 初始解初始解现在学习的是第76页，共101页7777第第1阶段阶段 最优基最优基B*min =*(1)、*0(2)、*=0 yi 0(i=1,2,m)B*基变量无

43、人工变量基变量无人工变量 B*基变量含人工变量基变量含人工变量yr 单纯形表中，单纯形表中，yr+ark yk+arj xj=0 ()k Jj JJ：非基变量下标集合：非基变量下标集合,判定原问题无可行解。判定原问题无可行解。现在学习的是第77页，共101页78781)arj 全全=0 ()式多余方程式多余方程2)arj 有有 0 元，设为元，设为ars 0 以以ars为主元，换基迭代，最后得到为主元，换基迭代，最后得到现在学习的是第78页，共101页7979maxZ=-X1+2X2 X1+X2 2-X1+X2 1 X2 3 3X1 X2 0例例1 1：minZ=X1-2X2 minW=X6+

44、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第一阶段：求第一阶段：求现在学习的是第79页，共101页8080 0 0 0 0 0 -1 -1 0 0 0 0 0 -1 -1 X1 X2 X3 X4 X5 X6 X7 W 3 3 0 2 -1 -1 0 -1 -1 0 0 0 0 0 X6 2 1 1 -1 0 0 1 0 2 1 1 -1 0 0 1 0 X7 1 -1 1 -1 (1)0 -1 0 0 1(1)0 -1 0 0 1 X5 3 0 1 0

45、 0 1 0 0 3 0 1 0 0 1 0 0 W 1 1 +2 +2 0 -1 1 0 -1 1 0 0 -2 X6 1 (2)0 -1 1 0 1 -1 1 (2)0 -1 1 0 1 -1 X2 1 -1 1 -1 1 0 -1 0 0 1 1 0 -1 0 0 1 X5 2 1 0 0 1 1 0 -1 2 1 0 0 1 1 0 -1 W 0 0 0 0 0 0 0 0 0 0 0 -1 -1 X1 1/2 1 0 -1/2 1/2 0 1/2 -1/2 1/2 1 0 -1/2 1/2 0 1/2 -1/2 X2 3/2 0 3/2 0 1 -1/2 -1/2 0 1/2 1/2

46、1 -1/2 -1/2 0 1/2 1/2 X5 3/2 0 0 1/2 1/2 1 -1/2 -1/2 3/2 0 0 1/2 1/2 1 -1/2 -1/2 现在学习的是第80页，共101页8181 -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/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

47、 2 1 0 0 1 1 X2 3 0 1 0 0 1 X3 1 -1 0 1 0 1第二阶段第二阶段现在学习的是第81页，共101页8282例例2：maxZ=2X1+X2 5X1+10X2 82X1+2X2 1X1，X2 0minZ=-2X1-X2 第第(1)(1)阶段：阶段：minW=X55X1+10X2-X3+X5=82X1+2X2+X4=1X1 X5 0现在学习的是第82页，共101页8383 0 0 0 0 -1 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

48、 0X5 3 -5 0 -1 -5 1X2 1/2 1 1 0 1/2 0现在学习的是第83页，共101页8484X2X1O5X1+10X2 82X1+2X2 1X1，X2 05X1+10X2 810X1+10X2 5X1，X2 0现在学习的是第84页，共101页8585例例3 3、求、求minZ=+4X1+3X3 1/2X1+X2+1/2X3-2/3X4=23/2X1 +3/4X3 =33X1-6X2 +4X4 =0X1,X2,X3,X4 0满足满足现在学习的是第85页，共101页8686 0 0 0 0 -1 -1 -1 X1 X2 X3 X4 y1 y2 y3 W 5 5 -5 5/4

49、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 -1/2 X1 0 1 -2 0 4/3 0 0 1/3第第 一一 阶阶 段段 一一二二现在学习的是第86页，共101页8787 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

50、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第第二二阶阶段段现在学习的是第87页，共101页8888例例4 4、求、求minZ=4X1+3X31/2X1+X2+1/2X3-2/3X4=23/2X1-1/2X3=33X1-6X2+4X4=0X1,X2,X3,X4 0满足满足现在学习的是第88页，共101页8989 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