运筹学03单纯形法

《运筹学03单纯形法》由会员分享，可在线阅读，更多相关《运筹学03单纯形法（95页珍藏版）》请在装配图网上搜索。

1、单击此处编辑母版标题样式,,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,,,*,第三章 单纯形法,3.1 线性规划问题的标准形式,,3.2 线性规划问题的解,,3.3 单纯形法,,3.4 求初始基的人工变量法,,1,,3.1 线性规划问题的标准形式,目标函数,约束条件,(1) 线性规划模型一般形式,,2,,价值系数,决策变量,技术系数,右端常数,(2) 线性规划模型标准形式,,3,,简记形式,(3) 线性规划模型其它形式,,4,,矩阵形式,价值向量,决策向量,系数矩阵,右端向量,,5,,价值向量,决策向量,右端向量,向量形式,列向量,,6,,对于各种非标准形式的线性规划

2、问题，我们总可以通过以下变换，将其转化为标准形式:,(4) 一般型向标准型的转化,目标函数,,目标函数为极小化,,约束条件,,分两种情况：大于和小于,,决策变量,,可能存在小于零的情况,,7,,1.极小化目标函数的问题：,,设目标函数为,,,Min f = c,1,x,1,+ c,2,x,2,+ … + c,n,x,n,,,,则可以令,z,＝,-f,，该极小化问题与下面的极大化问题有相同的最优解，即,,,Max z = -c,1,x,1,- c,2,x,2,- … - c,n,x,n,,,,但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即,,,Min

3、f ＝ - Max z,,8,,2、约束条件不是等式的问题：,,设约束条件为,a,i1,x,1,+,a,i2,x,2,+ … +,a,in,x,n,,≤,b,i,,可以引进一个新的变量,s,，使它等于约束右边与左边之差,,,s,=,b,i,– (,a,i1,x,1,,+,a,i2,x,2,,+ … +,a,in,x,n,,),,显然，,s,也具有非负约束，即,s,≥0，,,这时新的约束条件成为,,,a,i1,x,1,+,a,i2,x,2,+ … +,a,in,x,n,+,s,=,b,i,,变量,s,称为,松弛变量,,9,,Max Z=40X,1,+ 50X,2,,X,1,+2X,2,≤ 30

4、,,s.t 3X,1,+2X,2,≤ 60,引入,松弛变量,X,3,、,X,4,、,X,5,,2X,2,≤ 24,,,X,1,,,,X,2,0,,,Max Z=40X,1,+ 50X,2,+0 X,3,+0,,X,4,+0 X,5,,X,1,+2X,2,+ X,3,,＝,,30,,s.t 3X,1,+2X,2,,+ X,4,,＝,,60,,2X,2,,+ X,5,＝,24,,,X,1,,…,,,X,5,0,,10,,当约束条件为,,,a,i1,x,1,+,a,i2,x,2,+,…,+,a,in,x,n,,≥,b,i,,,时，类似地令,,,s,= (,a,i1,x,1,+

5、,a,i2,x,2,+ … +,a,in,x,n,)-,b,i,,,显然，,s,也具有非负约束，即,s,≥0，这时新的约束条件成为,,,a,i1,x,1,+,a,i2,x,2,+ … +,a,in,x,n,-,s,=,b,i,,变量,s,称为,剩余变量,,11,,Max Z=2X,1,+ 5X,2,+6X,3,+8X,4,,4,X,1,+6X,2,+ X,3,+2X,4,≥ 12,,s.t X,1,+ X,2,+7X,3,+5X,4,≥ 14,,2X,2,+ X,3,+3X,4,≥ 8,,,X,1,,,,…,,X,4,0,,引入,剩余变量,：,X,5,、X,6,、X,7

6、,,Max Z=2X,1,+ 5X,2,+6X,3,+8X,4,,,4,X,1,+6X,2,+ X,3,+2X,4,- X,5,,＝,12,,s.t X,1,+ X,2,+7X,3,+5X,4,- X,6,＝,14,,2X,2,+ X,3,+3X,4,- X,7,＝,8,,,X,1,,,,…,,X,7,0,,12,,3. 决策变量,,如果某个变量的约束条件为,,或者,可令,或者,代入原问题,如果某个变量为自由变量，则可令,且,,13,,X,1,+X,2, 5,,s.t -6,,X,1, 10,,X,2,0,,,令,X,1,',,= X,1,+6,,

7、,-6+6 ,X,1,+6,, 10+6,,,0,,X,1,',,,16,,,,X,1,',,+X,2, 11,,s.t X,1,',,16,,X,1,' , X,2,0,,14,,,3,X,1,+2X,2, 8,,s.t X,1,-4X,2,,14,,X,2,0,,X,1,无限制,,,令,X,1,= X,1,'- X,1,'',,,3,X,1,' -3 X,1," +2X,2, 8,,s.t X,1,',,- X,1," - 4X,2,,,14,,X,1,' , X,1," ,X,2,0,,15,,例：将线性规划模型,,Min

8、 Z = -X,1,+2X,2,-3X,3,,X,1,+X,2,+X,3, 7,,s.t X,1,-X,2,+X,3,2,,X,1,，X,2,0,，,X,3,无限制,,化为标准型,,16,,解：① 令,X,3,=X,4,-,,X,5,② 加松弛变量,X,6,③加剩余变量,X,7,,④ 令,Z'= -Z,Max Z'= X,1,-2X,2,+3X,4,-3X,5,X,1,+X,2,+X,4,-X,5,+X,6,=7,,X,1,-X,2,+X,4,-X,5,-X,7,=2,,X,1,,,,X,2,,,,X,4,,,…,, X,7,0,s.t,,17,,3.2 线性规划问

9、题的解,(1) 解的基本概念,定义 在线性规划问题中，约束方程组(2)的系数矩阵A(假定 )的任意一个 阶的非奇异(可逆)的子方阵B(即 )，称为线性规划问题的一个,基阵,或,基,。,,18,,基阵,非基阵,基,,向,,量,非,,基,,向,,量,基变量,非基变量,,19,,令,则,定义 在约束方程组(2) 中，对于一个选定的基B，令所有的非基变量为零得到的解，称为相应于基B的基本解。,,20,,定义 在基本解中，若该基本解满足非负约束，即 ，则称此基本解为,基本可行解,，简称,基可行解,；对应的基B称为,可行基,。

10、,定义 在线性规划问题的一个基本可行解中，如果所有的基变量都取正值，则称它为,非退化解,，如果所有的基本可行解都是非退化解。称该问题为,非退化的线性规划问题,；若基本可行解中，有基变量为零，则称为,退化解,，该问题称为,退化的线性规划问题,。,基本解中最多有,m,个非零分量。,基本解的数目不超过,个。,,21,,非可行解,解的集合：,可行解,基本解,最优解,基本可行解,解空间,,22,,例 现有线性规划问题,试求其基本解、基本可行解并判断是否为退化解。,,23,,解,: (1),首先将原问题转化为标准型,,引入松弛变量,x,3,和,x,4,(2) 求基本解,,由上式得,,24,,可能的

11、基阵,由于所有|B|,≠,0,所以有6个基阵和6个基本解。,,25,,对于基阵,令,则,对于基阵,令,则,为基本可行解，B,13,为可行基,为基本可行解，B,12,为可行基,,26,,对于基阵,令,则,对于基阵,令,则,,27,,对于基阵,令,则,对于基阵,令,则,为基本可行解，B,24,为可行基,为基本可行解，B,34,为可行基,,28,,0,A,B,C,D,E,1 基本解为边界约束方程的交点；,,2 基对应于可行解可行域极点；,,3 相邻基本解的脚标有一个相同。,,29,,例2 现有线性规划问题,试求其基本解、基本可行解并判断是否为退化解。,,30,,解,: (1),首先将原问题转化为标

12、准型,,引入松弛变量,x,3,和,x,4,(2) 求基本解,,由上式得,,31,,可能的基阵,由于所有|B|,≠,0，所以有6个基阵和6个基本解。,,32,,对于基阵,令,则,对于基阵,令,则,为基本可行解，B,12,为可行基,为基本可行解，B,13,为可行基,为退化解,,33,,对于基阵,令,则,对于基阵,令,则,为基本可行解，B,23,为可行基,为退化解,,34,,对于基阵,令,则,对于基阵,令,则,为基本可行解，B,24,为可行基,为基本可行解，B,34,为可行基,为退化解,,35,,0,A,B,C,,36,,(2) 解的基本性质,判别可行解为基可行解的准则,定理1 线性规划问题的可行

13、解是基可行解的充要条件是它的非零变量所对应的列向量线性无关.,线性规划问题的基本定理:定理2和定理3,定理2 线性规划问题有可行解,则它必有基可行解.,定理3 若线性规划问题有最优解,则一定存在一个基可行解是它的最优解.,,37,,定理2 线性规划问题有可行解,则它必有基可行解.,证:设 为线性规划问题的一个可行解.,,若 ,则它是一个基可行解,定理成立;,,若 ,则令 的前,k,个分量为非零分量：,若上述分量所对应的列向量,,线性无关,则它是一个基可行解,定理成立;,,若

14、 线性相关，从 出发，,,必可找到线性规划问题的一个基可行解。,,38,,由于 线性相关，则存在一组不全为零的数 ， 使得,假定,令,若,令,(若,令,),(*),由(*)可知,即,与 相比， 的非零分量减少1个，若对应的,k-1,个列向量线性无关，则即为基可行解；否则继续上述步骤，直至剩下的非零变量对应的列向量线性无关。,,39,,几点结论,若线性规划问题有可行解,,,则可行域是一个凸多边形或凸多面体,(,凸集,),,且仅有有限个顶点,(,极点,);,,线性规

15、划问题的每一个基可行解都对应于可行域上的一个顶点,(,极点,);,,若线性规划问题有最优解,,,则最优解必可在基可行解,(,极点,),上达到,;,,线性规划问题的基可行解,(,极点,),的个数是有限的,,,不会超过 个,.,上述结论说明:,,线性规划的最优解可通过有限次运算在基可行解中获得,.,,40,,3.3 单纯形法,例,1,,,,Max Z=40X,1,+50X,2,,X,1,+2X,2,+X,3,=30,,3X,1,+2X,2,+X,4,=60,,2X,2,+X,5,=24,,X,1,… X,5,0,(1)单纯形法的引入,,41,,解：(1)、确定初始可行解,B = ( P

16、,3,P,4,P,5,) = I,Z = 0 + 40X,1,+ 50X,2,,X,3,= 30 - ( X,1,+ 2X,2,),,X,4,= 60 - ( 3X,1,+ 2X,2,),,X,5,= 24 - 2 X,2,令,X,1,=,,X,2,=0,X,(1),=(0, 0, 30, 60, 24),T,,Z,(1),=0,,42,,(2)、判定解是否最优,Z=0+40X,1,+50X,2,,当,X,1,从,0,↗ 或,X,2,从,0,↗,,Z,从,0,↗,∴,X,(1),不是最优解,,43,,(3)、由一个基可行解→另一个基可行解。,∵,50,>,4

17、0,选,X,2,从,0,↗，,X,1,=0,X,3,= 30 - 2X,2,0,X,2,,30,/,2,,,X,4,= 60 - 2X,2,0,X,2,,60,/,2,,,X,5,= 24 - 2 X,2,0,X,2,,24,/,2,,,X,2,= min (,30,/,2,,,60,/,2,,,24,/,2,) =12,,X,2,：,进基变量,，,,X,5,：,出基变量,。,,44,,B,2,=( P,3,P,4,P,2,),Z= 0 + 40 X,1,+ 50 X,2,④,,X,3,+ 2X,2,= 30 - X,1,①,,X,4,+ 2X,2,= 60 - 3X,1,,②,,

18、2X,2,= 24 - X,5,③,,45,,③ ×,1,/,2,，,③ 代入 ④ 式， ①－③，②－③,Z = 600 + 40X,1,- 25X,5,,X,3,= 6 - X,1,+ X,5,,X,4,=,,36 - 3X,1,+ X,5,,X,2,= 12 -,1,/,2,X,5,令,X,1,= X,5,= 0 X,(2),= ( 0, 12, 6, 36, 0 ),T,,Z,(2),= 600,,46,,(2),',,判断,∵,40,>0,∴,X,(2),不是最优解。,(3),',选,X,1,从,0,↗，,X,5,=0,X,3

19、,= 6- X,1,0,,,X,4,=,,36-3X,1,0,,,X,2,=12,0,,X,1,=min(,6,/,1,,,36,/,3,, 1 ) =6,,X,1,进基，,,X,3,出基。,,47,,B,3,=(P,1,P,4,P,2,),Z=840-40X,3,+15X,5,,X,1,=6 - X,3,+ X,5,,X,4,=,,18+3X,3,- 2X,5,,X,2,=12 -,1,/,2,X,5,令,X,3,=X,5,=0,,X,(3),=(6, 12, 0, 18, 0),T,,Z,(3),=840,,48,,(2),",∵,15,>0,∴,X

20、,(3),不是,(3),",选,X,5,从,0,↗，,X,3,=0,X,1,=6 +X,5,0,,,X,4,=,,18 -2X,5,0,,,X,2,=12-,1,/,2,X,5,,0,,,X,5,=min(,18,/,2,,,12,/,1/2,) =9,,X,5,进基，,,X,4,出基。,,49,,B,4,=(P,1,P,5,P,2,),Z=975-,35,/,2,X,3,-,15,/,2,X,4,,X,1,= 15 +,1,/,2,X,3,-,1,/,2,X,4,,X,5,=,,9 +,3,/,2,X,3,-,1,/,2,X,4,,X,2,=,15,/,2,-,3,

21、/,4,X,3,+,1,/,4,X,4,,令,X,3,=X,4,=0,,X,(4),=(15,,15,/,2,, 0, 0 ,9 ),T,Z,(4),=975,,50,,0,(0,0),X,2,X,1,A,,D,C,B,(0,12),(6,12),(15,7.5),X,(4),X,(1),X,(2),X,(3),Z=40X,1,+50X,2,,51,,单纯形法小结：,,,单纯形法是这样一种迭代算法——如下图…,,当,Z,k,中,非基变量的系数的系数全为负值时，这时的基本可行解,X,k,即是线性规划问题的最优解，,迭代结束。,,X,1,Z,1,保持单调增,保持可行性,保持可行性,保持可行性,保持

22、可行性,保持单调增,保持单调增,保持单调增,X,2,X,3,...,X,k,Z,2,Z,3,...,Z,k,,当,Z,k,中,非基变量的系数的系数全为负值时，这时的基本可行解,X,k,,即是线性规划问题的最优解，,迭代结束。,,52,,(2) 线性规划的典则形式,标准型,,53,,,54,,上式称为线性规划问题对应于基B的,典则形式,，简称,典式,。,,约束方程组的系数矩阵中含有一个单位矩阵，并以其为基；,,目标函数中不含基变量，只有非基变量。,检,,验,,数,,55,,(3) 最优性判别定理,在线性规划问题的典式中，设,,,X,(0),=(,x,1,,x,2,,…,x,m,,0,…,0,),

23、,为对应于基B 的一个基可行解，若有,,,,j,,0 ( j,=,m+1 , m+2 ,,… , n,),,则,X,(0),是线性规划问题的,最优解,，基,B,为,最优基,。,证：设X为线性规划问题的一个可行解，必有,,,X  0 ，当 ,j, 0， 则 X,, 0,,Z*=C,X,(0),= Z,(0),,Z,(0),+,,X =CX,,故,X,(0),为线性规划问题的最优解,。,,56,,在线性规划问题的典式中，设,X,(0),=(x,1,,x,2,,…,x,m,,0,…,0),,为对应于基B 的一个基可行解，若有,,,,j,, 0 (,j = m+1 , m+2 ,

24、,… , n,,),且,,j+k,= 0,,,则,线性规划问题有无穷多个最优解。,无穷多最优解判别定理,在线性规划问题的典式中，设X,(0),为对应于基B 的一个基可行解，若某一非基变量,x,j+k,的检验数,,,j+k,> 0,,,且对应的列向量,,P’,m+k,=(a,1,m+k,,a,2,m+k,,,…,,a,m,m+k,), 0,,则,线性规划问题具有无界解，即无有限最优解。,无界解判别定理,,57,,(4) 基可行解改进定理,在线性规划问题的典式中，设,,,X,(0),=(x,1,,x,2,,…,x,m,,0,…,0),,为对应于基B 的一个基可行解，若满足以下条件：,,某个非

25、基变量的检验数,,,k,> 0 ( m+1 k ,n,),;,,a,ik,,( i = 1,2,,…,,m,),不全小于或等于零，即至少有一个,a,ik,,> 0 ( 1  k ,m,),;,,b,i,’> 0( I = 1 , 2,,…,,m,),,,即,X,(0),为非退化的基可行解。,,则从,X,(0),出发，一定能找到一个新的基可行解,X,(1),，,使得,CX,(1),> CX,(0),,。,,58,,(5) 单纯形表,将线性规划问题典式中,各变量及系数填写在一张表格中,，该表即为,单纯形表,。,c,j,,,,c,1,c,2,… c,n,c,n+1,c,n+2,

26、… c,n+m,解,,C,B,基,x,1,x,2,… x,n,x,n+1,x,n+2,… x,n+m,,,0,,0,,0,,0,x,n+1,,x,n+2,,…,,x,n+m,a,11,a,12,… a,1n,1,,a,21,a,22,… a,2n,1,,… … … … …,,a,m1,a,m2,… a,mn,1,b,1,,,b,2,,…,,,b,m,,1,,,2,,…,,,m,,j,= c,j,– z,j,,,,1,,,2,…,,,n,,n+1,,,

27、n+2,…,,n+m,,,,59,,单纯形方法的矩阵表示,B,N,I,b,C,B,C,N,0,0,I,B,-1,N,B,-1,B,-1,b,0,C,N,-C,B,B,-1,N,-C,B,B,-1,C,B,B,-1,b,,60,,对应,I,式,的,单纯形表——,,I,表(初始单纯形表),对应,B,式,的,单纯形表——,B,表,迭代,I,B,-1,N,B,-1,B,-1,b,0,C,N,-C,B,B,-1,N,-C,B,B,-1,C,B,B,-1,b,B,N,I,b,C,B,C,N,0,0,价值系数,c,j,,C,B,C,N,0,解,θ,基系数,基,X,B,X,N,X,S,,,C,B,X,B,I

28、,B,-1,N,B,-1,B,-1,b,,检验数,σ,j,,0,C,N,-C,B,B,-1,N,-C,B,B,-1,C,B,B,-1,b,,当,C,N,-C,B,B,-1,N≤0,时，即为,最优单纯形表,价值系数,c,j,,C,B,C,N,0,解,θ,基系数,基,X,B,X,N,X,S,,,0,X,B,B,N,I,b,,检验数,σ,j,,C,B,C,N,0,0,,,61,,(1)、确定初始基域初始基本可行解,列出初始单纯形表,(3)、若有,,j,>,0，P,j,全,,,0，,停止，,,没有有限最优解； 否则转 (4),(2)、对应于非基变量检验数,,j,全小于,零,。,,,若是，停止，得

29、到最优解；,,若否，转(3)。,(6),单纯形法的迭代步骤,,62,,θ=,min,a,im+k,>,0 =,,b,i,,a,im+k,,b,r,,a,rm+k,定,X,r,为出基变量，,a,rm+k,为主元。,由最小,θ,比值法求：,Max,,j,=,,m+k,→,X,m+k,进基变量,,j,,,0,(4)、,,63,,转(2),a,1m+k,0,,a,2m+k,0,,,a,r,m+k,1,,,a,mm+k,0,初等行变换,P,m+k,=,…,…,…,…,(5)、以,a,rm+k,为中心，换基迭代,从步骤(2)-(5)的每一个循环，称为一次,单纯形迭代,.,,64,,单纯形表计算步

30、骤举例,,给定线性规划问题,例,1,Max z = 50X,1,+ 30X,2,,4X,1,+3X,2,≤,,120,,s.t,2X,1,+ X,2,,≤,50,,X,1,，X,2,,≥,0,Max z = 50X,1,+ 30X,2,,4X,1,+ 3X,2,+ X,3,=,,120,,s.t 2X,1,+ X,2,+ X,4,= 50,,X,1,， X,2,，X,3,，X,4,,≥,0,,65,,单纯形表计算步骤举例,,给定线性规划问题,Max z = 50X,1,+ 30X,2,,s.t. 4X,1,+ 3X,2,+ X,3,=,,120,,2X,

31、1,+ X,2,+ X,4,= 50,,X,1,， X,2,，X,3,，X,4,≥ 0,c,j,,50,30,0,0,B,-1,b,θ,c,B,x,B,x,1,x,2,x,3,x,4,,,0,X,3,4,3,1,0,120,,0,x,4,2,1,0,1,50,,Σ,j,,50,30,0,0,0,,120/4,50/2,( ),x,1,50,1,1/2,1/2,25,0,1,-2,20,0,5,0,-25,20,50,( ),,,,,,x,2,30,20,0,1,1,-2,15,1,0,-1/2,3/2,0,-5,-15,1250,1350,,66,,c,j,,50,30,0,

32、0,B,-1,b,θ,c,B,x,B,x,1,x,2,x,3,x,4,,,0,x,3,4,3,1,0,120,120/4,0,x,4,(,2,),1,0,1,50,50/2,σ,j,,50,30,0,0,0,,0,x,3,0,(,1,),1,-2,20,20,50,x,1,1,1/2,0,1/2,25,50,σ,j,,0,5,0,-25,1250,,30,x,2,0,1,1,-2,20,,50,x,1,1,0,-1/2,5/2,15,,σ,j,,0,0,-5,-15,1350,,初始单纯形表,最优单纯形表,B,-1,唯一最优解,最优值,,67,,例2,,68,,c,j,,40,80,0,0,0

33、,B,-1,b,θ,c,B,x,B,x,1,x,2,x,3,x,4,x,5,,,0,x,3,1,2,1,0,0,30,15,0,x,4,3,2,0,1,0,60,30,0,x,5,0,2,0,0,1,24,12,σ,j,,40,80,0,0,0,0,,c,j,,40,80,0,0,0,B,-1,b,θ,c,B,x,B,x,1,x,2,x,3,x,4,x,5,,,0,x,3,1,0,1,0,-1,6,6,0,x,4,3,0,0,1,-1,36,12,80,x,2,0,1,0,0,1/2,12,,σ,j,,40,0,0,0,-40,960,,,69,,c,j,,40,80,0,0,0,B,-1,b

34、,θ,c,B,x,B,x,1,x,2,x,3,x,4,x,5,,,40,x,1,1,0,1,0,-1,6,,0,x,4,0,0,-3,1,2,18,9,80,x,2,0,1,0,0,1/2,12,24,σ,j,,0,0,-40,0,0,1200,,c,j,,40,80,0,0,0,B,-1,b,θ,c,B,x,B,x,1,x,2,x,3,x,4,x,5,,,40,x,1,1,0,-1/2,1/2,0,15,,0,x,5,0,0,-3/2,1/2,1,9,,80,x,2,0,1,3/4,-1/4,0,15/2,,σ,j,,0,0,-40,0,0,1200,,,,达到最优状态时，若存在非基变量检验

35、数为零，则为,有无穷多最优解,,70,,例3,,71,,c,j,,2,1,0,0,B,-1,b,θ,c,B,x,B,x,1,x,2,x,3,x,4,,,0,x,3,1,1,1,0,5,5,0,x,4,1,-1,0,1,0,0,σ,j,,2,1,0,0,0,,0,x,3,0,2,1,-1,5,5/2,2,x,1,1,-1,0,1,0,,σ,j,,0,3,0,-2,0,,1,x,2,0,1,1/2,-1/2,5/2,,2,x,1,1,0,1/2,1/2,5/2,,σ,j,,0,0,-3/2,-1/2,15/2,,Θ,可以为零,,72,,例4,例5,无法获得初始基和初始基可行解,,73,,3.4 求

36、初始基的人工变量法,求解线性规划问题的单纯形法第一步就是要找到一个初始可行基并求出初始基可行解，以它作为迭代的起点。,,获得初始可行基及初始基可行解的途径主要有：,,(1) 试算法；,,(2) 人工变量法。,,在约束方程组中的每一个没有单位向量的约束方程中人为加入一个变量，使系数矩阵中凑成一个单位方阵，以形成一个初始可行基阵。,,74,,约束条件,：,,a,11,x,1,+,a,12,x,2,+,…,+,a,1n,x,n,+x,n+1,=,b,1,,a,21,x,1,+,a,22,x,2,+,…,+,a,2n,x,n,+x,n+2,,=,b,2,,,.,,.,,.,,a,m1,x,1,+ a,

37、m2,x,2,+ … + a,mn,x,n,+x,n+m,,=,b,m,,,,,x,1,，x,2,，… ，x,n,,,x,n+1,,,…,,,x,n+m,,≥ 0,s.t,人工变量,人工基,,75,,等价否？,,,76,,大M法,两阶段法,,77,,大M法与二阶段法的一些说明,,由于人工变量在原问题的解中是不能存在的，应尽快被迭代出去，因此人工变量在目标函数中对应的价值系数应具有惩罚性，称为罚系数。,,大M法实质上与原单纯形法一样，,M,可看成一个很大的常数,,人工变量被迭代出去后就不会再成为基变量,,当检验数都满足最优条件，但基变量中仍有人工变量，说明原线性规划问题无可行解,,大M法手算很不

38、方便，因此提出了二阶段法,,计算机中常用大M法,,二阶段法手算可能容易,,78,,二阶段法的求解过程,第一阶段的任务是将人工变量尽快迭代出去，从而找到一个没有人工变量的基本可行解,,第二阶段以第一阶段得到的基本可行解为初始解，采用原单纯形法求解,,若第一阶段结束时，人工变量仍在基变量中，则原问题无（可行）解,,为了简化计算，在第一阶段重新定义价值系数如下：,,,79,,例6,大M法,,80,,c,j,,3,-1,-1,0,0,-M,-M,B,-1,b,θ,c,B,x,B,x,1,x,2,x,3,x,4,x,5,x,6,x,7,,,0,x,4,1,-2,1,1,0,0,0,11,11,-M,x,

39、6,-4,1,2,0,-1,1,0,3,3/2,-M,x,7,-2,0,1,0,0,0,1,1,1,σ,j,,-6M+3,M-1,3M-1,0,-M,0,0,-4M,,c,j,,3,-1,-1,0,0,-M,-M,B,-1,b,θ,c,B,x,B,x,1,x,2,x,3,x,4,x,5,x,6,x,7,,,0,x,4,3,-2,0,1,0,0,-1,10,,-M,x,6,0,1,0,0,-1,1,-2,1,1,-1,x,3,-2,0,1,0,0,0,1,1,,σ,j,,1,M-1,0,0,-M,0,-3M+1,-M-1,,,81,,c,j,,3,-1,-1,0,0,-M,-M,B,-1,b,θ

40、,c,B,x,B,x,1,x,2,x,3,x,4,x,5,x,6,x,7,,,0,x,4,3,0,0,1,-2,2,-5,12,4,-1,x,2,0,1,0,0,-1,1,-2,1,,-1,x,3,-2,0,1,0,0,0,1,1,,σ,j,,1,0,0,0,-1,-M+1,-M-1,-2,,c,j,,3,-1,-1,0,0,-M,-M,B,-1,b,θ,c,B,x,B,x,1,x,2,x,3,x,4,x,5,x,6,x,7,,,3,x,1,1,0,0,1/3,-2/3,2/3,-5/3,4,,-1,x,2,0,1,0,0,-1,1,-2,1,,-1,x,3,0,0,1,2/3,-4/3,4/

41、3,-7/3,9,,σ,j,,0,0,0,-1/3,-1/3,-M+1/3,-M+2/3,2,,最优解,人工变量被迭代出去后就不会再成为基变量,,,,82,,例4,,83,,c,j,,2,4,0,0,-M,B,-1,b,θ,c,B,x,B,x,1,x,2,x,3,x,4,x,5,,,-M,x,5,2,1,-1,0,1,8,4,0,x,4,-2,1,0,1,0,2,,σ,j,,2+2M,4+M,-M,0,0,-8M,,c,j,,2,4,0,0,-M,B,-1,b,θ,c,B,x,B,x,1,x,2,x,3,x,4,x,5,,,2,x,1,1,1/2,-1/2,0,1/2,4,8,0,x,4,0,

42、2,-1,1,1,10,5,σ,j,,0,3,1,0,-M-1,8,,c,j,,2,4,0,0,-M,B,-1,b,θ,c,B,x,B,x,1,x,2,x,3,x,4,x,5,,,2,x,1,1,0,-1/4,-1/4,1/4,3/2,,4,x,2,0,1,-1/2,1/2,1/2,5,,σ,j,,0,0,5/2,-3/2,-M-5/2,26,,未达到最优状态，但无法继续改进，即,无有限最优解,,84,,例5,c,j,,3,2,0,-M,B,-1,b,θ,c,B,x,B,x,1,x,2,x,3,x,4,,,-M,x,4,-1,-1,-1,1,1,,σ,j,,-M+3,-M+2,-M,0,-M,

43、,已达到最优状态，但基变量中的人工变量未退出，故,无可行解,,85,,例6,(2) 两阶段法,,86,,第一阶段,c,j,,0,0,0,0,0,-1,-1,B,-1,b,θ,c,B,x,B,x,1,x,2,x,3,x,4,x,5,x,6,x,7,,,0,x,4,1,-2,1,1,0,0,0,11,11,-1,x,6,-4,1,2,0,-1,1,0,3,3/2,-1,x,7,-2,0,1,0,0,0,1,1,1,σ,j,,-6,1,3,0,-1,0,0,-4,,,87,,c,j,,0,0,0,0,0,-1,-1,B,-1,b,θ,c,B,x,B,x,1,x,2,x,3,x,4,x,5,x,6,x

44、,7,,,0,x,4,3,-2,0,1,0,0,-1,10,,-1,x,6,0,1,0,0,-1,1,-2,1,1,0,x,3,-2,0,1,0,0,0,1,1,,σ,j,,0,1,0,0,-1,0,-3,-1,,c,j,,0,0,0,0,0,-1,-1,B,-1,b,θ,c,B,x,B,x,1,x,2,x,3,x,4,x,5,x,6,x,7,,,0,x,4,3,0,0,1,-2,2,-5,12,,0,x,2,0,1,0,0,-1,1,-2,1,,0,x,3,-2,0,1,0,0,0,1,1,,σ,j,,0,0,0,0,0,-1,-1,0,,获得初始可行解,,88,,c,j,,3,-1,-1,

45、0,0,,,B,-1,b,θ,c,B,x,B,x,1,x,2,x,3,x,4,x,5,,,,,0,x,4,3,0,0,1,-2,,,12,4,-1,x,2,0,1,0,0,-1,,,1,,-1,x,3,-2,0,1,0,0,,,1,,σ,j,,1,0,0,0,-1,,,-2,,c,j,,3,-1,-1,0,0,,,B,-1,b,θ,c,B,x,B,x,1,x,2,x,3,x,4,x,5,,,,,3,x,1,1,0,0,1/3,-2/3,,,4,,-1,x,2,0,1,0,0,-1,,,1,,-1,x,3,0,0,1,2/3,-4/3,,,9,,σ,j,,0,0,0,-1/3,-1/3,,,2,

46、,第二阶段,获得最优解,,89,,例4,,90,,第一阶段,c,j,,0,0,0,0,-1,B,-1,b,θ,c,B,x,B,x,1,x,2,x,3,x,4,x,5,,,-1,x,5,2,1,-1,0,1,8,4,0,x,4,-2,1,0,1,0,2,,σ,j,,2,1,-1,0,0,-8,,c,j,,0,0,0,0,-1,B,-1,b,θ,c,B,x,B,x,1,x,2,x,3,x,4,x,5,,,0,x,1,1,1/2,-1/2,0,1/2,4,,0,x,4,0,2,-1,1,1,10,,σ,j,,0,0,0,0,-1,0,,获得原问题的一个初始可行解,,91,,第二阶段,c,j,,2,4

47、,0,0,,B,-1,b,θ,c,B,x,B,x,1,x,2,x,3,x,4,,,,2,x,1,1,1/2,-1/2,0,,4,8,0,x,4,0,2,-1,1,,10,5,σ,j,,0,3,0,0,,8,,c,j,,2,4,0,0,,B,-1,b,θ,c,B,x,B,x,1,x,2,x,3,x,4,,,,2,x,1,1,0,-1/4,-1/4,,3/2,,4,x,2,0,1,-1/2,1/2,,5,,σ,j,,0,0,5/2,-3/2,,26,,未达到最优状态，但无法继续改进，即,无有限最优解,,92,,例5,c,j,,0,0,0,-1,B,-1,b,θ,c,B,x,B,x,1,x,2,x,3,x,4,,,-1,x,4,-1,-1,-1,1,1,,σ,j,,-1,-1,-1,0,-1,,第一阶段,已达到最优状态，但目标函数值不为零，故,无可行解,,93,,,,单纯形法详细计算步骤,,94,,第三章习题,,1,,4,,6,,8(选2),,10 (选2),,11,,95,,