运筹学单纯形法.pptx

《运筹学单纯形法.pptx》由会员分享，可在线阅读，更多相关《运筹学单纯形法.pptx（95页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、3.1 3.1 线性规划问题的标准形式线性规划问题的标准形式目标函数目标函数约束条件约束条件(1)线性规划模型一般形式线性规划模型一般形式第1页/共95页价值系数价值系数决策变量决策变量技术系数技术系数右端常数右端常数(2)线性规划模型标准形式线性规划模型标准形式第2页/共95页简记形式简记形式(3)线性规划模型其它形式线性规划模型其它形式第3页/共95页矩阵形式矩阵形式价值向量价值向量决策向量决策向量系数矩阵系数矩阵右端向量右端向量第4页/共95页价值向量价值向量决策向量决策向量右端向量右端向量向量形式向量形式列向量列向量第5页/共95页对于各种非标准形式的线性规划问题，我们总可对于各种非标

2、准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式以通过以下变换，将其转化为标准形式:(4)一般型向标准型的转化一般型向标准型的转化l目标函数目标函数l目标函数为极小化目标函数为极小化l约束条件约束条件l分两种情况：大于和小于分两种情况：大于和小于l决策变量决策变量l可能存在小于零的情况可能存在小于零的情况第6页/共95页1.1.极小化目标函数的问题：极小化目标函数的问题：设目标函数为设目标函数为 Min f=c1x1+c2x2+cnxn 则则可可以以令令z z -f-f ，该该极极小小化化问问题题与与下下面面的的极大化问题有相同的最优解，即极大化问题有相同的最优解，即 Max

3、z=-c1x1-c2x2-cnxn 但但必必须须注注意意，尽尽管管以以上上两两个个问问题题的的最最优优解解相相同同，但但他他们们最最优优解解的的目目标标函函数数值值却却相相差差一一个个符号，即符号，即 Min f -Max z第7页/共95页2 2、约束条件不是等式的问题：、约束条件不是等式的问题：设约束条件为设约束条件为 ai1 x1+ai2 x2+ain xn bi 可可以以引引进进一一个个新新的的变变量量s s ，使使它它等等于于约约束束右右边与左边之差边与左边之差 s=bi (ai1 x1+ai2 x2+ain xn)显然，显然，s s 也具有非负约束，即也具有非负约束，即s s00，

4、这时新的约束条件成为这时新的约束条件成为 ai1 x1+ai2 x2+ain xn+s=bi 变量变量 s s 称为称为松弛变量松弛变量第8页/共95页lMax Z=40X1+50X2 X1+2X2 30 s.t 3X1+2X2 60 引入松弛变量X3、X4、X5 2X2 24 X1,X2 0 0lMax Z=40X1+50X2+0 X3+0 X4+0 X5 X1+2X2+X3 30 s.t 3X1+2X2+X4 60 2X2+X5 24 X1,X5 0 0第9页/共95页当约束条件为当约束条件为 ai1 x1+ai2 x2+ain xn bi 时，类似地令时，类似地令 s=(ai1 x1+a

5、i2 x2+ain xn)-bi 显然，显然，s 也具有非负约束，即也具有非负约束，即s0，这时新的，这时新的约束条件成为约束条件成为 ai1 x1+ai2 x2+ain xn-s=bi变量变量s s称为称为剩余变量剩余变量第10页/共95页Max Z=2X1+5X2+6X3+8X4 4X1+6X2+X3+2X4 12 s.t X1+X2+7X3+5X4 14 2X2+X3+3X4 8 X1,X4 0 0引入剩余变量：X5、X6、X7Max Z=2X1+5X2+6X3+8X4 4X1+6X2+X3+2X4-X5 12 s.t X1+X2+7X3+5X4 -X6 14 2X2+X3+3X4 -X

6、7 8 X1,X7 0 0第11页/共95页3.决策变量决策变量如果某个变量的约束条件为如果某个变量的约束条件为或者或者可令可令或者或者代入原问题代入原问题如果某个变量为自由变量，则可令如果某个变量为自由变量，则可令且且第12页/共95页 X1+X2 5s.t -6 X1 10 X2 0 0令 X1=X1+6-6+6 X1+6 10+6 0 X1 16 X1+X2 11s.t X1 16 X1,X2 0 0第13页/共95页 3X1+2X2 8 s.t X1-4X2 14 X2 0,0,X1 无限制 令X1=X1-X1 3 X1-3 X1 +2X2 8 s.t X1-X1 -4X2 14 X1

7、,X1,X2 0 0第14页/共95页例：将线性规划模型例：将线性规划模型 Min Z=-X1+2X2-3X3 X1+X2+X3 7 s.t X1-X2+X3 2 X1，X2 0，X3无限制无限制 化为标准型化为标准型第15页/共95页解：解：令令X3=X4-X5 加松弛变量加松弛变量X6加剩余变量加剩余变量X7 令令Z=-ZMax Z=X1-2X2+3X4-3X5 X1+X2+X4-X5+X6=7X1-X2+X4-X5-X7=2X1,X2,X4,X7 0s.t第16页/共95页3.2 3.2 线性规划问题的解线性规划问题的解(1)解的基本概念解的基本概念定义定义 在线性规划问题中，约束方程组

8、在线性规划问题中，约束方程组(2)(2)的系的系数矩阵数矩阵A(A(假定假定 )的任意一个的任意一个 阶的非奇阶的非奇异异(可逆可逆)的子方阵的子方阵B(B(即即 )，称为线性规划，称为线性规划问题的一个问题的一个基阵基阵或或基基。第17页/共95页基阵基阵非基阵非基阵基基向向量量非非基基向向量量基变量基变量非基变量非基变量第18页/共95页令令则则定义定义 在约束方程组在约束方程组(2)中，对于中，对于一个选定的基一个选定的基B，令所有的非基变，令所有的非基变量为零得到的解，称为相应于基量为零得到的解，称为相应于基B的基本解。的基本解。第19页/共95页定义定义 在基本解中，若该基本解满足非

9、负约束，在基本解中，若该基本解满足非负约束，即即 ，则称此基本解为，则称此基本解为基本基本可行解可行解，简称，简称基可行解基可行解；对应的基；对应的基B称为称为可行基可行基。定义定义 在线性规划问题的一个基本可行解中，如在线性规划问题的一个基本可行解中，如果所有的基变量都取正值，则称它为果所有的基变量都取正值，则称它为非退化解非退化解，如果所有的基本可行解都是非退化解。称该问题如果所有的基本可行解都是非退化解。称该问题为为非退化的线性规划问题非退化的线性规划问题；若基本可行解中，有；若基本可行解中，有基变量为零，则称为基变量为零，则称为退化解退化解，该问题称为，该问题称为退化的退化的线性规划问

10、题线性规划问题。基本解中最多有基本解中最多有m个非零分量。个非零分量。基本解的数目不超过基本解的数目不超过 个。个。第20页/共95页非非非非可可可可行行行行解解解解解的集合：解的集合：解的集合：解的集合：可可可可行行行行解解解解基基基基本本本本解解解解最最最最优优优优解解解解基基基基本本本本可可可可行行行行解解解解解空间解空间第21页/共95页例例 现有线性规划问题现有线性规划问题试求其基本解、基本可行解并判断是否为退化试求其基本解、基本可行解并判断是否为退化解。解。第22页/共95页解解:(1)首先将原问题转化为标准型首先将原问题转化为标准型 引入松弛变量引入松弛变量x3和和x4(2)求基

11、本解求基本解由上式得由上式得第23页/共95页可能的基阵可能的基阵 由于所有由于所有|B|0,所所以有以有6个基阵和个基阵和6个基本解。个基本解。第24页/共95页对于基阵对于基阵令令则则对于基阵对于基阵令令则则为基本可行解，为基本可行解，B13为可行基为可行基为基本可行解，为基本可行解，B12为可行基为可行基第25页/共95页对于基阵对于基阵令令则则对于基阵对于基阵令令则则第26页/共95页对于基阵对于基阵令令则则对于基阵对于基阵令令则则为基本可行解，为基本可行解，B24为可行基为可行基为基本可行解，为基本可行解，B34为可行基为可行基第27页/共95页0ABCDE1 1 基本解为边界约束方

12、程的交点；基本解为边界约束方程的交点；2 2 基对应于可行解可行域极点；基对应于可行解可行域极点；3 3 相邻基本解的脚标有一个相同。相邻基本解的脚标有一个相同。第28页/共95页例例2 现有线性规划问题现有线性规划问题试求其基本解、基本可行解并判断是否为退化试求其基本解、基本可行解并判断是否为退化解。解。第29页/共95页解解:(1)首先将原问题转化为标准型首先将原问题转化为标准型 引入松弛变量引入松弛变量x3和和x4(2)求基本解求基本解由上式得由上式得第30页/共95页可能的基阵可能的基阵 由于所有由于所有|B|0，所以有所以有6个基阵和个基阵和6个基本解。个基本解。第31页/共95页对

13、于基阵对于基阵令令则则对于基阵对于基阵令令则则为基本可行解，为基本可行解，B12为可行基为可行基为基本可行解，为基本可行解，B13为可行基为可行基,为退化解为退化解第32页/共95页对于基阵对于基阵令令则则对于基阵对于基阵令令则则为基本可行解，为基本可行解，B23为可行基为可行基,为退化解为退化解第33页/共95页对于基阵对于基阵令令则则对于基阵对于基阵令令则则为基本可行解，为基本可行解，B24为可行基为可行基为基本可行解，为基本可行解，B34为可行基为可行基,为退化解为退化解第34页/共95页0ABC第35页/共95页(2)解的基本性质解的基本性质判别可行解为基可行解的准则判别可行解为基可行

14、解的准则定理定理1 线性规划问题的可行解是基可行解的充要线性规划问题的可行解是基可行解的充要条件是它的非零变量所对应的列向量线性无关条件是它的非零变量所对应的列向量线性无关.线性规划问题的基本定理线性规划问题的基本定理:定理定理2和定理和定理3定理定理2 线性规划问题有可行解线性规划问题有可行解,则它必有基可行解则它必有基可行解.定理定理3 若线性规划问题有最优解若线性规划问题有最优解,则一定存在一个则一定存在一个基可行解是它的最优解基可行解是它的最优解.第36页/共95页定理定理2 线性规划问题有可行解线性规划问题有可行解,则它必有基可行解则它必有基可行解.证证:设设 为线性规划问题的一个可

15、行解为线性规划问题的一个可行解.若若 ,则它是一个基可行解则它是一个基可行解,定理成定理成立立;若若 ,则令则令 的前的前k个分量为非个分量为非零分量：零分量：若上述分量所对应的列向量若上述分量所对应的列向量 线性无关线性无关,则它是一个基可行解则它是一个基可行解,定理成立定理成立;若若 线性相关，线性相关，从从 出发，出发，必可找到线性规划问题的一个基可行解。必可找到线性规划问题的一个基可行解。第37页/共95页由于由于 线性相关，则存在线性相关，则存在一组不全为零的数一组不全为零的数 ，使得使得假定假定令令若若令令(若若令令)(*)由由(*)可知可知即即与与 相比，相比，的非零分量减少的非

16、零分量减少1个，若对应的个，若对应的k-1个列向量线性无关，则即为基可行解；否则继续个列向量线性无关，则即为基可行解；否则继续上述步骤，直至剩下的非零变量对应的列向量线性无上述步骤，直至剩下的非零变量对应的列向量线性无关。关。第38页/共95页几点结论几点结论v若线性规划问题有可行解若线性规划问题有可行解,则可行域是一个凸多边形或则可行域是一个凸多边形或凸多面体凸多面体(凸集凸集),且仅有有限个顶点且仅有有限个顶点(极点极点);v线性规划问题的每一个基可行解都对应于可行域上的线性规划问题的每一个基可行解都对应于可行域上的一个顶点一个顶点(极点极点);v若线性规划问题有最优解若线性规划问题有最优

17、解,则最优解必可在基可行解则最优解必可在基可行解(极点极点)上达到上达到;v线性规划问题的基可行解线性规划问题的基可行解(极点极点)的个数是有限的的个数是有限的,不会不会超过超过 个个.上述结论说明上述结论说明:线性规划的最优解可通过有限次运算在基可行解中获得线性规划的最优解可通过有限次运算在基可行解中获得.第39页/共95页3.3 3.3 单纯形法单纯形法l例例1 1Max Z=40X1+50X2 X1+2X2+X3 =30 3X1+2X2 +X4 =60 2X2 +X5=24 X1 X5 0 0(1)单纯形法的引入单纯形法的引入第40页/共95页解：解：(1)(1)、确定初始可行解、确定初

18、始可行解B=(P3 P4 P5)=IZ =0 +40X1+50X2X3=30-(X1+2X2 )X4=60-(3X1+2X2)X5=24 -2 X2令X1=X2=0X(1)=(0,0,30,60,24)TZ(1)=0第41页/共95页(2)(2)、判定解是否最优、判定解是否最优Z=0+40X1+50X2当当 X1 从从 0 或或 X2 从从 0 Z 从从 0 X X(1)(1)不是最优解不是最优解第42页/共95页(3)(3)、由一个基可行解、由一个基可行解另一个基可行解。另一个基可行解。50 40 选 X2 从 0，X1=0X3 =30-2X2 0 0 X2 30/2 X4 =60-2X2

19、0 0 X2 60/2 X5=24-2 X2 0 0 X2 24/2 X2=min(30/2,60/2,24/2)=12X2：进基变量进基变量，X5：出基变量出基变量。第43页/共95页B B2 2=(P3 P4 P2)Z=0+40 X1+50 X2 X3 +2X2 =30-X1 X4+2X2 =60-3X1 2X2 =24-X5 第44页/共95页 1/2，代入代入 式，式，Z=600 +40X1 -25X5X3 =6 -X1 +X5 X4 =36-3X1 +X5 X2=12 -1/2X5令令 X1=X5=0 X(2)=(0,12,6,36,0)T Z(2)=600第45页/共95页(2)(

20、2)判断判断 400 X(2)不是最优解不是最优解。(3)选选X1从从0，X5=0 X3=6-X1 0 0 X4=36-3X1 0 0 X2=12 0 0 X1=min(6/1,36/3,1)=6X1进基，进基，X3出基。出基。第46页/共95页B3=(P1 P4 P2)Z=840-40X3+15X5X1=6 -X3+X5 X4=18+3X3-2X5X2=12 -1/2X5令令X3=X5=0 X(3)=(6,12,0,18,0)TZ(3)=840第47页/共95页(2)150 X(3)不是不是(3)选选X5从从0，X3=0 X1=6 +X5 0 X4=18 -2X5 0 X2=12-1/2 X

21、5 0 X5=min(18/2,12/1/2)=9X5进基，进基，X4出基。出基。第48页/共95页B4=(P1 P5 P2)Z=975-35/2X3-15/2X4X1=15+1/2X3-1/2X4X5=9 +3/2X3-1/2X4X2=15/2-3/4X3+1/4X4令令X3=X4=0 X(4)=(15,15/2,0,0,9)T Z(4)=975第49页/共95页0(0,0)X2X1A DCB(0,12)(6,12)(15,7.5)X(4)X(1)X(2)X(3)Z=40X1+50X2第50页/共95页单纯形法小结：单纯形法小结：单纯形法是这样一种迭代算法单纯形法是这样一种迭代算法如下图如下

22、图 当当Zk中中非基变量非基变量的系数的系数全为负值时，这时的基本可的系数的系数全为负值时，这时的基本可行解行解Xk即是线性规划问题的最优解，即是线性规划问题的最优解，迭代结束。迭代结束。X1Z1保持单调增保持单调增保持可行性保持可行性保持可行性保持可行性保持可行性保持可行性保持可行性保持可行性保持单调增保持单调增保持单调增保持单调增保持单调增保持单调增X2X3.XkZ2Z3.Zk 当当Zk 中中非基变量非基变量的系数的系数全为负值时，这时的的系数的系数全为负值时，这时的基本可行解基本可行解Xk 即是线性规划问题的最优解，即是线性规划问题的最优解，迭代结束。迭代结束。第51页/共95页(2)线

23、性规划的典则形式线性规划的典则形式标准型标准型第52页/共95页第53页/共95页 上式称为线性规划问题对应于基上式称为线性规划问题对应于基B的的典则形式典则形式，简称，简称典式典式。1.约束方程组的系数矩阵中含有一个单位矩阵，并以其约束方程组的系数矩阵中含有一个单位矩阵，并以其为基；为基；2.目标函数中不含基变量，只有非基变量。目标函数中不含基变量，只有非基变量。检检验验数数第54页/共95页(3)最优性判别定理最优性判别定理在线性规划问题的典式中，设在线性规划问题的典式中，设 X(0)=(x1,x2,xm,0,0)为对应于基为对应于基B 的一个基可行解，若有的一个基可行解，若有 j 0(j

24、=m+1,m+2,n)则则X(0)是线性规划问题的是线性规划问题的最优解最优解，基，基B为为最优基最优基。证：设证：设X为线性规划问题的一个可行解，必有为线性规划问题的一个可行解，必有 X 0，当，当 j 0，则则 X 0 Z*=CX(0)=Z(0)Z(0)+X=CX 故故X(0)为线性规划问题的最优解为线性规划问题的最优解。第55页/共95页在线性规划问题的典式中，设在线性规划问题的典式中，设 X(0)=(x1,x2,xm,0,0)为对应于基为对应于基B 的一个基可行解，若有的一个基可行解，若有 j 0(j=m+1,m+2,n)且且 j+k =0 则则线性规划问题有无穷多个最优解。线性规划问

25、题有无穷多个最优解。无穷多最优解判别定理无穷多最优解判别定理在线性规划问题的典式中，设在线性规划问题的典式中，设X(0)为对应于基为对应于基B 的一个的一个基可行解，若某一非基变量基可行解，若某一非基变量xj+k的检验数的检验数 j+k 0 且对应的列向量且对应的列向量 Pm+k=(a1,m+k,a2,m+k,am,m+k)0 则则线性规划问题具有无界解，即无有限最优解。线性规划问题具有无界解，即无有限最优解。无界解判别定理无界解判别定理第56页/共95页(4)基可行解改进定理基可行解改进定理在线性规划问题的典式中，设在线性规划问题的典式中，设 X(0)=(x1,x2,xm,0,0)为对应于基

26、为对应于基B 的一个基可行解，若满足以下条件：的一个基可行解，若满足以下条件：1)某个非基变量的检验数某个非基变量的检验数 k 0(m+1 k n);2)aik(i=1,2,m)不全小于或等于零，即至少有一个不全小于或等于零，即至少有一个 aik 0(1 k m);3)bi 0(I=1,2,m),即即X(0)为非退化的基可行解。为非退化的基可行解。则从则从X(0)出发，一定能找到一个新的基可行解出发，一定能找到一个新的基可行解X(1)，使得，使得 CX(1)CX(0)。第57页/共95页(5)单纯形表单纯形表 将线性规划问题典式中将线性规划问题典式中各变量及系数填写在一张各变量及系数填写在一张

27、表格中表格中，该表即为，该表即为单纯形表单纯形表。cj c1 c2 cn cn+1 cn+2 cn+m解解 CB基基 x1 x2 xn xn+1 xn+2 xn+m0000 xn+1xn+2xn+m a11 a12 a1n 1 a21 a22 a2n 1 am1 am2 amn 1b1 b2 bm 1 2 m j=cj zj 1 2 n n+1 n+2 n+m 第58页/共95页单单纯纯形形方方法法的的矩矩阵阵表表示示BNIbCBCN00IB-1NB-1B-1b0CN-CB B-1N-CB B-1CBB-1b第59页/共95页对应对应I 式式的的单纯形表单纯形表 I 表表(初始单纯形表初始单纯

28、形表)对应对应B 式式的的单纯形表单纯形表 B 表表迭代迭代IB-1NB-1B-1b0CN-CB B-1N-CB B-1CBB-1bBNIbCBCN00价值系数价值系数cjCBCN0解解基系数基系数基基XBXNXSCBXBIB-1NB-1B-1b检验数检验数j0CN-CB B-1N-CB B-1CBB-1b当当CN-CBB-1N0时，即为时，即为最优单纯形表最优单纯形表价值系数价值系数cjCBCN0解解基系数基系数基基XBXNXS0XBBNIb检验数检验数jCBCN00第60页/共95页(1)、确定初始基域初始基本可行解、确定初始基域初始基本可行解,列出初始单列出初始单纯形表纯形表(3)、若有

29、、若有 j 0，Pj 全全 0，停止，停止，没有有限最优解；没有有限最优解；否则转否则转(4)(2)、对应于非基变量检验数、对应于非基变量检验数 j全小于全小于零零。若是，停止，得到最优解；若是，停止，得到最优解；若否，转若否，转(3)。(6)(6)单纯形法的迭代步骤单纯形法的迭代步骤第61页/共95页=min aim+k 0 =0 =biaim+kbrarm+k定定Xr为出基变量，为出基变量，arm+k为为主元。主元。由最小由最小比值法求：比值法求：Max j=m+kXm+k 进基变量进基变量 j 0 0(4)、第62页/共95页转转(2)(2)a1m+k 0a2m+k 0ar,m+k 1a

30、mm+k 0初等行变换初等行变换Pm+k=(5)、以、以arm+k为中心，换基迭代为中心，换基迭代从步骤从步骤(2)-(5)(2)-(5)的每一个循环，称为一次的每一个循环，称为一次单纯形迭代单纯形迭代.第63页/共95页单纯形表计算步骤举例单纯形表计算步骤举例给定线性规划问题给定线性规划问题例例1 Max z=50X1+30X2 4X1+3X2 120 s.t 2X1+X2 50 X1，X2 0Max z=50X1+30X2 4X1+3X2+X3 =120s.t 2X1+X2 +X4=50 X1，X2，X3，X4 0第64页/共95页单纯形表计算步骤举例单纯形表计算步骤举例给定线性规划问题给

31、定线性规划问题Max z=50X1+30X2s.t.4X1+3X2+X3 =120 2X1+X2 +X4=50 X1，X2，X3，X4 0cj503000B-1bcBxBx1x2x3x40X343101200 x4210150j5030000120/450/2()x15011/21/22501-220050-252050()x23020011-21510-1/23/20-5-1512501350第65页/共95页cj503000B-1bcBxBx1x2x3x40 x34310120120/40 x4(2)1015050/2j50300000 x30(1)1-2202050 x111/201/2

32、2550j050-25125030 x2011-22050 x110-1/25/215j00-5-151350初始单纯形表初始单纯形表最优单纯形表最优单纯形表B-1唯一最优解唯一最优解最优值最优值第66页/共95页例例2 第67页/共95页cj4080000 B-1bcBxBx1x2x3x4x50 x31210030150 x43201060300 x5020012412j40800000cj4080000 B-1bcBxBx1x2x3x4x50 x31010-1660 x43001-1361280 x201001/212j40000-40960第68页/共95页cj4080000 B-1bc

33、BxBx1x2x3x4x540 x11010-160 x400-31218980 x201001/21224j00-40001200cj4080000 B-1bcBxBx1x2x3x4x540 x110-1/21/20150 x500-3/21/21980 x2013/4-1/4015/2j00-40001200达到最优状态时，若存在非基变量检验数为零，则为达到最优状态时，若存在非基变量检验数为零，则为有无穷多最优解有无穷多最优解第69页/共95页例例3 第70页/共95页cj2100B-1bcBxBx1x2x3x40 x31110550 x41-10100j210000 x3021-155/

34、22x11-1010j030-201x2011/2-1/25/22x1101/21/25/2j00-3/2-1/215/2可以为零可以为零第71页/共95页例例4 例例5 无法获得初始基无法获得初始基和初始基可行解和初始基可行解第72页/共95页3.4 3.4 求初始基的人工变量法求初始基的人工变量法求解线性规划问题的单纯形法第一步就是要找到一个初求解线性规划问题的单纯形法第一步就是要找到一个初始可行基并求出初始基可行解，以它作为迭代的起点。始可行基并求出初始基可行解，以它作为迭代的起点。获得初始可行基及初始基可行解的途径主要有：获得初始可行基及初始基可行解的途径主要有：(1)试算法；试算法；

35、(2)人工变量法。人工变量法。在约束方程组中的每一个没有单位向量的约束方程中人在约束方程组中的每一个没有单位向量的约束方程中人为加入一个变量，使系数矩阵中凑成一个单位方阵，以为加入一个变量，使系数矩阵中凑成一个单位方阵，以形成一个初始可行基阵。形成一个初始可行基阵。第73页/共95页约束条件约束条件：a11x1+a12x2+a1nxn+xn+1=b1 a21x1+a22x2+a2nxn+xn+2=b2 .am1x1+am2x2+amnxn+xn+m=bm x1，x2，xn ,xn+1,xn+m 0s.t人工变量人工变量人工基人工基第74页/共95页等价否？等价否？第75页/共95页大大M法法两

36、阶段法两阶段法第76页/共95页大大M法与二阶段法的一些说明法与二阶段法的一些说明n由于人工变量在原问题的解中是不能存在的，应尽快被由于人工变量在原问题的解中是不能存在的，应尽快被迭代出去，因此人工变量在目标函数中对应的价值系数迭代出去，因此人工变量在目标函数中对应的价值系数应具有惩罚性，称为罚系数。应具有惩罚性，称为罚系数。q大大M法实质上与原单纯形法一样，法实质上与原单纯形法一样，M可看成一个很大可看成一个很大的常数的常数q人工变量被迭代出去后就不会再成为基变量人工变量被迭代出去后就不会再成为基变量q当检验数都满足最优条件，但基变量中仍有人工变量，当检验数都满足最优条件，但基变量中仍有人工

37、变量，说明原线性规划问题无可行解说明原线性规划问题无可行解q大大M法手算很不方便，因此提出了二阶段法法手算很不方便，因此提出了二阶段法n计算机中常用大计算机中常用大M法法n二阶段法手算可能容易二阶段法手算可能容易第77页/共95页二阶段法的求解过程二阶段法的求解过程n第一阶段的任务是将人工变量尽快迭代出去，从而找到第一阶段的任务是将人工变量尽快迭代出去，从而找到一个没有人工变量的基本可行解一个没有人工变量的基本可行解n第二阶段以第一阶段得到的基本可行解为初始解，采用第二阶段以第一阶段得到的基本可行解为初始解，采用原单纯形法求解原单纯形法求解n若第一阶段结束时，人工变量仍在基变量中，则原问题若第

38、一阶段结束时，人工变量仍在基变量中，则原问题无（可行）解无（可行）解n为了简化计算，在第一阶段重新定义价值系数如下：为了简化计算，在第一阶段重新定义价值系数如下：第78页/共95页例例6 大大M法法第79页/共95页cj3-1-100-M-M B-1bcBxBx1x2x3x4x5x6x70 x41-2110001111-Mx6-4120-11033/2-Mx7-201000111j-6M+3M-13M-10-M00-4Mcj3-1-100-M-M B-1bcBxBx1x2x3x4x5x6x70 x43-20100-110-Mx60100-11-211-1x3-20100011j1M-100-M

39、0-3M+1-M-1第80页/共95页cj3-1-100-M-M B-1bcBxBx1x2x3x4x5x6x70 x43001-22-5124-1x20100-11-21-1x3-20100011j1000-1-M+1-M-1-2cj3-1-100-M-M B-1bcBxBx1x2x3x4x5x6x73x11001/3-2/32/3-5/34-1x20100-11-21-1x30012/3-4/34/3-7/39j000-1/3-1/3-M+1/3-M+2/32最最优优解解人工变量被迭代出去后就不会再成为基变量人工变量被迭代出去后就不会再成为基变量第81页/共95页例例4 第82页/共95页c

40、j2400-M B-1bcBxBx1x2x3x4x5-Mx521-101840 x4-210102j2+2M4+M-M00-8Mcj2400-M B-1bcBxBx1x2x3x4x52x111/2-1/201/2480 x402-111105j0310-M-18cj2400-M B-1bcBxBx1x2x3x4x52x110-1/4-1/41/43/24x201-1/21/21/25j005/2-3/2-M-5/226未达到最优状态，但无法继续改进，即未达到最优状态，但无法继续改进，即无有限最优解无有限最优解第83页/共95页例例5 cj320-MB-1bcBxBx1x2x3x4-Mx4-1-

41、1-111j-M+3-M+2-M0-M已达到最优状态，但基变量中的人工变量未退出，故已达到最优状态，但基变量中的人工变量未退出，故无可行解无可行解第84页/共95页例例6 (2)两阶段法两阶段法第85页/共95页第一阶段第一阶段cj00000-1-1 B-1bcBxBx1x2x3x4x5x6x70 x41-2110001111-1x6-4120-11033/2-1x7-201000111j-6130-100-4第86页/共95页cj00000-1-1 B-1bcBxBx1x2x3x4x5x6x70 x43-20100-110-1x60100-11-2110 x3-20100011j0100-1

42、0-3-1cj00000-1-1 B-1bcBxBx1x2x3x4x5x6x70 x43001-22-5120 x20100-11-210 x3-20100011j00000-1-10获得初始可行解获得初始可行解第87页/共95页cj3-1-100B-1bcBxBx1x2x3x4x50 x43001-2124-1x20100-11-1x3-201001j1000-1-2cj3-1-100B-1bcBxBx1x2x3x4x53x11001/3-2/34-1x20100-11-1x30012/3-4/39j000-1/3-1/32第二阶段第二阶段获获得得最最优优解解第88页/共95页例例4 第89

43、页/共95页第一阶段第一阶段cj0000-1 B-1bcBxBx1x2x3x4x5-1x521-101840 x4-210102j21-100-8cj0000-1 B-1bcBxBx1x2x3x4x50 x111/2-1/201/240 x402-11110j0000-10获得原问题的一个初始可行解获得原问题的一个初始可行解第90页/共95页第二阶段第二阶段cj2400B-1bcBxBx1x2x3x42x111/2-1/20480 x402-11105j03008cj2400B-1bcBxBx1x2x3x42x110-1/4-1/43/24x201-1/21/25j005/2-3/226未达到最优状态，但无法继续改进，即未达到最优状态，但无法继续改进，即无有限最优解无有限最优解第91页/共95页例例5 cj000-1B-1bcBxBx1x2x3x4-1x4-1-1-111j-1-1-10-1第一阶段第一阶段已达到最优状态，但目标函数值不为零，故已达到最优状态，但目标函数值不为零，故无可行解无可行解第92页/共95页单纯形法详细计算步骤单纯形法详细计算步骤第93页/共95页第三章习题第三章习题1468(选选2)10(选选2)11第94页/共95页感谢您的观看！第95页/共95页