运筹学03-单纯形法.ppt

第三章第三章 单纯形法单纯形法3.1 3.1 线性规划问题的标准形式线性规划问题的标准形式3.2 3.2 线性规划问题的解线性规划问题的解3.3 3.3 单纯形法单纯形法3.4 3.4 求初始基的人工变量法求初始基的人工变量法3.1 线性规划问题的标准形式目标函数目标函数约束条件约束条件(1) 线性规划模型一般形式线性规划模型一般形式价值系数价值系数决策变量决策变量技术系数技术系数右端常数右端常数(2) 线性规划模型标准形式线性规划模型标准形式简记形式简记形式(3) 线性规划模型其它形式线性规划模型其它形式矩阵形式矩阵形式价值向量价值向量决策向量决策向量系数矩阵系数矩阵右端向量右端向量价值向量价值向量决策向量决策向量右端向量右端向量向量形式向量形式列向量列向量对于各种非标准形式的线性规划问题，我们总可对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式以通过以下变换，将其转化为标准形式: :(4) 一般型向标准型的转化一般型向标准型的转化l目标函数目标函数l目标函数为极小化目标函数为极小化l约束条件约束条件l分两种情况：大于和小于分两种情况：大于和小于l决策变量决策变量l可能存在小于零的情况可能存在小于零的情况1.1.极小化目标函数的问题：极小化目标函数的问题： 设目标函数为设目标函数为 Min f = c1x1 + c2x2 + … + cnxn 则则可可以以令令z z ＝＝-f-f ，，该该极极小小化化问问题题与与下下面面的的极大化问题有相同的最优解，即极大化问题有相同的最优解，即 Max z = -c1x1 - c2x2 - … - cnxn 但但必必须须注注意意，，尽尽管管以以上上两两个个问问题题的的最最优优解解相相同同，，但但他他们们最最优优解解的的目目标标函函数数值值却却相相差差一一个个符号，即符号，即 Min f ＝＝ - Max z2 2、、约束条件不是等式的问题：约束条件不是等式的问题： 设约束条件为设约束条件为 ai1 x1+ai2 x2+ … +ain xn ≤ bi 可可以以引引进进一一个个新新的的变变量量s s ，，使使它它等等于于约约束束右右边与左边之差边与左边之差 s = bi – (ai1 x1 + ai2 x2 + … + ain xn ) 显然，显然，s s 也具有非负约束，即也具有非负约束，即s s≥0≥0，， 这时新的约束条件成为这时新的约束条件成为 ai1 x1+ai2 x2+ … +ain xn+s = bi 变量变量 s s 称为称为松弛变量松弛变量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当约束条件为当约束条件为 ai1 x1+ai2 x2+ … +ain xn ≥ bi 时，类似地令时，类似地令 s = (ai1 x1+ai2 x2+ … +ain xn)- bi 显然，显然，s 也具有非负约束，即也具有非负约束，即s≥0，，这时新的约这时新的约束条件成为束条件成为 ai1 x1+ai2 x2+ … +ain xn-s = bi变量变量s s称为称为剩余变量剩余变量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 - X7 ＝＝8 X1 , …, X7  0 03. 决策变量决策变量如果某个变量的约束条件为如果某个变量的约束条件为或者或者可令可令或者或者代入原问题代入原问题如果某个变量为自由变量，则可令如果某个变量为自由变量，则可令且且 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 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' , X1" ,X2  0 0例：将线性规划模型例：将线性规划模型 Min Z = -X1+2X2 -3X3 X1+X2 +X3  7 s.t X1 -X2 +X3  2 X1，，X2 0，，X3无限制无限制 化为标准型化为标准型解：解：①① 令令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3.2 3.2 线性规划问题的解线性规划问题的解(1) 解的基本概念解的基本概念定义定义 性规划问题中，约束方程组性规划问题中，约束方程组(2)(2)的系的系数矩阵数矩阵A(A(假定假定 ) )的任意一个的任意一个 阶的非奇阶的非奇异异( (可逆可逆) )的子方阵的子方阵B(B(即即 ) )，称为线性规划，称为线性规划问题的一个问题的一个基阵基阵或或基基。

基阵基阵非基阵非基阵基基向向量量非非基基向向量量基变量基变量非基变量非基变量令令则则定义定义 在约束方程组在约束方程组(2) 中，对于中，对于一个选定的基一个选定的基B，，令所有的非基变令所有的非基变量为零得到的解，称为相应于基量为零得到的解，称为相应于基B的基本解的基本解定义定义 在基本解中，若该基本解满足非负约束，在基本解中，若该基本解满足非负约束，即即 ，则称此基本解为，则称此基本解为基本可行解基本可行解，简，简称称基可行解基可行解；对应的基；对应的基B称为称为可行基可行基定义定义 性规划问题的一个基本可行解中，如果性规划问题的一个基本可行解中，如果所有的基变量都取正值，则称它为所有的基变量都取正值，则称它为非退化解非退化解，如，如果所有的基本可行解都是非退化解称该问题为果所有的基本可行解都是非退化解称该问题为非退化的线性规划问题非退化的线性规划问题；若；若基本可行解中，有基基本可行解中，有基变量为零，则称为变量为零，则称为退化解退化解，该问题称为，该问题称为退化的线退化的线性规划问题性规划问题基本解中最多有基本解中最多有m个非零分量。

个非零分量基本解的数目不超过基本解的数目不超过 个非非非非可可可可行行行行解解解解解的集合：解的集合：解的集合：解的集合：可可可可行行行行解解解解基基基基本本本本解解解解最最最最优优优优解解解解基基基基本本本本可可可可行行行行解解解解解空间解空间例例 现有线性规划问题现有线性规划问题试求其基本解、基本可行解并判断是否为退化试求其基本解、基本可行解并判断是否为退化解解解: (1)首先将原问题转化为标准型首先将原问题转化为标准型 引入松弛变量引入松弛变量x3和和x4(2) 求基本解求基本解由上式得由上式得可能的基阵可能的基阵 由于所有由于所有|B|≠≠ 0,所所以有以有6个基阵和个基阵和6个基本解个基本解对于基阵对于基阵令令则则对于基阵对于基阵令令则则为为基本可行解，基本可行解，B13为可行基为可行基为为基本可行解，基本可行解，B12为可行基为可行基对于基阵对于基阵令令则则对于基阵对于基阵令令则则对于基阵对于基阵令令则则对于基阵对于基阵令令则则为为基本可行解，基本可行解，B24为可行基为可行基为为基本可行解，基本可行解，B34为可行基为可行基0ABCDE1 1 基本解为边界约束方程的交点；基本解为边界约束方程的交点；2 2 基对应于可行解可行域极点；基对应于可行解可行域极点；3 3 相邻基本解的脚标有一个相同。

相邻基本解的脚标有一个相同例例2 现有线性规划问题现有线性规划问题试求其基本解、基本可行解并判断是否为退化试求其基本解、基本可行解并判断是否为退化解解解: (1)首先将原问题转化为标准型首先将原问题转化为标准型 引入松弛变量引入松弛变量x3和和x4(2) 求基本解求基本解由上式得由上式得可能的基阵可能的基阵 由于所有由于所有|B|≠≠ 0，，所以有所以有6个基阵和个基阵和6个基本解个基本解对于基阵对于基阵令令则则对于基阵对于基阵令令则则为为基本可行解，基本可行解，B12为可行基为可行基为为基本可行解，基本可行解，B13为可行基为可行基,为退化解为退化解对于基阵对于基阵令令则则对于基阵对于基阵令令则则为为基本可行解，基本可行解，B23为可行基为可行基,为退化解为退化解对于基阵对于基阵令令则则对于基阵对于基阵令令则则为为基本可行解，基本可行解，B24为可行基为可行基为为基本可行解，基本可行解，B34为可行基为可行基,为退化解为退化解0ABC(2) 解的基本性质解的基本性质判别可行解为基可行解的准则判别可行解为基可行解的准则定理定理1 线性规划问题的可行解是基可行解的充要线性规划问题的可行解是基可行解的充要条件是它的非零变量所对应的列向量线性无关条件是它的非零变量所对应的列向量线性无关. 线性规划问题的基本定理线性规划问题的基本定理:定理定理2和定理和定理3定理定理2 线性规划问题有可行解线性规划问题有可行解,则它必有基可行解则它必有基可行解.定理定理3 若线性规划问题有最优解若线性规划问题有最优解,则一定存在一个则一定存在一个基可行解是它的最优解基可行解是它的最优解.定理定理2 线性规划问题有可行解线性规划问题有可行解,则它必有基可行解则它必有基可行解.证证:设设 为线性规划问题的一个可行解为线性规划问题的一个可行解. 若若 ,则它是一个基可行解则它是一个基可行解,定理成立定理成立; 若若 ,则令则令 的前的前k个分量为非零分量：个分量为非零分量：若若上述分量所对应的列向量上述分量所对应的列向量 线性无关线性无关,则它是一个基可行解则它是一个基可行解,定理成立定理成立;若若 线性相关，从线性相关，从 出发，出发，必可找到线性规划问题的一个基可行解。

必可找到线性规划问题的一个基可行解由于由于 线性相关，则存在一组不全为线性相关，则存在一组不全为零的数零的数 ，， 使得使得假定假定令令若若令令(若若令令)(*)由由(*)可可知知即即与与 相比，相比， 的非零分量减少的非零分量减少1个，若对应的个，若对应的k-1个个列向量线性无关，则即为基可行解；否则继续上述步列向量线性无关，则即为基可行解；否则继续上述步骤，直至剩下的非零变量对应的列向量线性无关骤，直至剩下的非零变量对应的列向量线性无关几点结论几点结论v若线性规划问题有可行解若线性规划问题有可行解,则可行域是一个凸多边形则可行域是一个凸多边形或凸多面体或凸多面体(凸集凸集),且仅有有限个顶点且仅有有限个顶点(极点极点);v线性规划问题的每一个基可行解都对应于可行域上的线性规划问题的每一个基可行解都对应于可行域上的一个顶点一个顶点(极点极点);v若线性规划问题有最优解若线性规划问题有最优解,则最优解必可在基可行解则最优解必可在基可行解(极点极点)上达到上达到;v线性规划问题的基可行解线性规划问题的基可行解(极点极点)的个数是有限的的个数是有限的,不不会超过会超过 个个.上述结论说明上述结论说明:线性规划的最优解可通过有限次运算在基可行解中获得线性规划的最优解可通过有限次运算在基可行解中获得.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)单纯形法的引入单纯形法的引入解：解：(1)(1)、确定初始可行解、确定初始可行解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(2)(2)、判定解是否最优、判定解是否最优Z=0+40X1+50X2当当 X1 从从 0↗ ↗ 或或 X2 从从 0↗ ↗Z 从从 0↗ ↗∴ ∴ X X(1) (1) 不是最优解不是最优解(3)(3)、由一个基可行解、由一个基可行解→→另一个基可行解。

另一个基可行解∵ ∵ 50 > > 40 选选 X2 从从 0↗↗，，X1 =0X3 = 30 - 2X2  0 0 X2   30/2 X4 = 60 - 2X2  0 0 X2   60/2 X5 = 24 - 2 X2  0 0 X2   24/2 X2 = min ( 30/2 , 60/2 , 24/2 ) =12X2 ：：进基变量进基变量，， X5 ：：出基变量出基变量B B2 2=( P3 P4 P2 )Z= 0 + 40 X1 + 50 X2 ④④X3 + 2X2 = 30 - X1 ①① X4 + 2X2 = 60 - 3X1 ②② 2X2 = 24 - X5 ③③③③ × 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(2)(2)' 判断判断∵∵ 40>0 ∴∴ 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出基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(2)" ∵∵ 15>0 ∴∴ 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出基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0(0,0)X2X1A DCB(0,12)(6,12)(15,7.5)X(4)X(1)X(2)X(3)Z=40X1+50X2单纯形法小结：单纯形法小结： 单纯形法是这样一种迭代算法单纯形法是这样一种迭代算法——如下图如下图… 当当Zk中中非基变量非基变量的系数的系数全为负值时，这时的基本可的系数的系数全为负值时，这时的基本可行解行解Xk即是线性规划问题的最优解，即是线性规划问题的最优解，迭代结束。

迭代结束X1Z1保持单调增保持单调增保持可行性保持可行性保持可行性保持可行性保持可行性保持可行性保持可行性保持可行性保持单调增保持单调增保持单调增保持单调增保持单调增保持单调增X2X3...XkZ2Z3...Zk 当当Zk 中中非基变量非基变量的系数的系数全为负值时，这时的基的系数的系数全为负值时，这时的基本可行解本可行解Xk 即即是线性规划问题的最优解，是线性规划问题的最优解，迭代结束迭代结束(2) 线性规划的典则形式线性规划的典则形式标准型标准型 上式称为线性规划问题对应于基上式称为线性规划问题对应于基B的的典则形式典则形式，简称，简称典式典式1.约束方程组的系数矩阵中含有一个单位矩阵，并以其约束方程组的系数矩阵中含有一个单位矩阵，并以其为基；为基；2.目标函数中不含基变量，只有非基变量目标函数中不含基变量，只有非基变量检检验验数数(3) 最优性判别定理最优性判别定理性规划问题的典式中，设性规划问题的典式中，设 X(0)=(x1,x2,…,xm,0,…,0)为对应于基为对应于基B 的的一个基可行解，若有一个基可行解，若有  j   0 ( j = 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)为为线性规划问题的最优解线性规划问题的最优解性规划问题的典式中，设性规划问题的典式中，设 X(0)=(x1,x2,…,xm,0,…,0)为对应于基为对应于基B 的的一个基可行解，若有一个基可行解，若有  j   0 ( j = m+1 , m+2 , … , n ) 且且  j+k = 0 则则线性规划问题有无穷多个最优解线性规划问题有无穷多个最优解无穷多最优解判别定理无穷多最优解判别定理性规划问题的典式中，设性规划问题的典式中，设X(0) 为对应于基为对应于基B 的的一个一个基可行解，若某一非基变量基可行解，若某一非基变量xj+k的检验数的检验数  j+k > 0 且对应的列向量且对应的列向量 P’m+k=(a1,m+k,a2,m+k,…,am,m+k)   0 则则线性规划问题具有无界解，即无有限最优解。

线性规划问题具有无界解，即无有限最优解无界解判别定理无界解判别定理(4) 基可行解改进定理基可行解改进定理性规划问题的典式中，设性规划问题的典式中，设 X(0)=(x1,x2,…,xm,0,…,0)为对应于基为对应于基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) (5) 单纯形表单纯形表 将线性规划问题典式中将线性规划问题典式中各变量及系数填写在一张各变量及系数填写在一张表格中表格中，该表即为，该表即为单纯形表单纯形表cj  c1 c2 … cn cn+1 cn+2 … cn+m解解 CB基基 x1 x2 … xn xn+1 xn+2 … xn+m0000xn+1xn+2…xn+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 单单纯纯形形方方法法的的矩矩阵阵表表示示BNIbCBCN00IB-1NB-1B-1b0CN -CB B-1N-CB B-1CBB-1b对应对应I 式式的的单纯形表单纯形表—— I 表表(初始单纯形表初始单纯形表)对应对应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-1N≤0时，即为时，即为最优单纯形表最优单纯形表价值系数价值系数cjCBCN0解解θ基系数基系数基基XBXNXS0XBBNIb检验数检验数σjCBCN00(1)、确定初始基域初始基本可行解、确定初始基域初始基本可行解,列出初始单列出初始单纯形表纯形表(3)、若有、若有 j > 0，，Pj 全全   0，，停止，停止， 没有有限最优解；没有有限最优解； 否则转否则转 (4)(2)、对应于非基变量检验数、对应于非基变量检验数 j全全小于小于零零。

若是，停止，得到最优解；若是，停止，得到最优解； 若否，转若否，转(3)6) (6) 单纯形法的迭代步骤单纯形法的迭代步骤θ= θ= min aim+k > >0 =0 =biaim+kbrarm+k定定Xr为出基变量，为出基变量，arm+k为为主元由最小由最小θθ比值法求：比值法求：Max  j =  m+k→Xm+k 进基变量进基变量 j   0 0(4)、、转转(2) (2) a1m+k 0a2m+k 0ar,m+k 1amm+k 0初等行变换初等行变换Pm+k =…………(5)、以、以arm+k为中心，换基迭代为中心，换基迭代从从步骤步骤(2)-(5)(2)-(5)的每一个循环，称为一次的每一个循环，称为一次单纯形迭代单纯形迭代. .单纯形表计算步骤举例单纯形表计算步骤举例　　给定线性规划问题　　给定线性规划问题例例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单纯形表计算步骤举例单纯形表计算步骤举例　　给定线性规划问题　　给定线性规划问题Max z = 50X1 + 30X2s.t. 4X1+ 3X2 + X3 = 120 2X1+ X2 + X4 = 50 X1，， X2 ，，X3 ，，X4 ≥ 0cj503000B-1bθcBxBx1x2x3x40X343101200x4210150Σj5030000120/450/2( )x15011/21/22501-220050-252050( )x23020011-21510-1/23/20-5-1512501350cj503000B-1bθcBxBx1x2x3x40x34310120120/40x4(2)1015050/2σj50300000x30(1)1-2202050x111/201/22550σj050-25125030x2011-22050x110-1/25/215σj00-5-151350初始单纯形表初始单纯形表最优单纯形表最优单纯形表B-1唯一最优解唯一最优解最优值最优值例例2 cj4080000 B-1bθcBxBx1x2x3x4x50x31210030150x43201060300x5020012412σj40800000cj4080000 B-1bθcBxBx1x2x3x4x50x31010-1660x43001-1361280x201001/212σj40000-40960cj4080000 B-1bθcBxBx1x2x3x4x540x11010-160x400-31218980x201001/21224σj00-40001200cj4080000 B-1bθcBxBx1x2x3x4x540x110-1/21/20150x500-3/21/21980x2013/4-1/4015/2σj00-40001200达到最优状态时，若存在非基变量检验数为零，则为达到最优状态时，若存在非基变量检验数为零，则为有无穷多最优解有无穷多最优解例例3 cj2100B-1bθcBxBx1x2x3x40x31110550x41-10100σj210000x3021-155/22x11-1010σj030-201x2011/2-1/25/22x1101/21/25/2σj00-3/2-1/215/2Θ可以为零可以为零例例4 例例5 无法获得初始基无法获得初始基和初始基可行解和初始基可行解3.4 3.4 求初始基的人工变量法求初始基的人工变量法求解线性规划问题的单纯形法第一步就是要找到一个初求解线性规划问题的单纯形法第一步就是要找到一个初始可行基并求出初始基可行解始可行基并求出初始基可行解，，以它作为迭代的起点。

以它作为迭代的起点获得初始可行基及初始基可行解的途径主要有：获得初始可行基及初始基可行解的途径主要有：(1) 试算法；试算法；(2) 人工变量法人工变量法在约束方程组中的每一个没有单位向量的约束方程中人在约束方程组中的每一个没有单位向量的约束方程中人为加入一个变量，使系数矩阵中凑成一个单位方阵，以为加入一个变量，使系数矩阵中凑成一个单位方阵，以形成一个初始可行基阵形成一个初始可行基阵约束条件约束条件：： 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人工变量人工变量人工基人工基等价否？等价否？大大M法法两阶段法两阶段法大大M法与二阶段法的一些说明法与二阶段法的一些说明n由于人工变量在原问题的解中是不能存在的，应尽快被由于人工变量在原问题的解中是不能存在的，应尽快被迭代出去，因此人工变量在目标函数中对应的价值系数迭代出去，因此人工变量在目标函数中对应的价值系数应具有惩罚性，称为罚系数。

应具有惩罚性，称为罚系数q大大M法实质上与原单纯形法一样，法实质上与原单纯形法一样，M可看成一个很大可看成一个很大的常数的常数q人工变量被迭代出去后就不会再成为基变量人工变量被迭代出去后就不会再成为基变量q当检验数都满足最优条件，但基变量中仍有人工变量，当检验数都满足最优条件，但基变量中仍有人工变量，说明原线性规划问题无可行解说明原线性规划问题无可行解q大大M法手算很不方便，因此提出了二阶段法法手算很不方便，因此提出了二阶段法n计算机中常用大计算机中常用大M法法n二阶段法手算可能容易二阶段法手算可能容易二阶段法的求解过程二阶段法的求解过程n第一阶段的任务是将人工变量尽快迭代出去，从而找到第一阶段的任务是将人工变量尽快迭代出去，从而找到一个没有人工变量的基本可行解一个没有人工变量的基本可行解n第二阶段以第一阶段得到的基本可行解为初始解，采用第二阶段以第一阶段得到的基本可行解为初始解，采用原单纯形法求解原单纯形法求解n若第一阶段结束时，人工变量仍在基变量中，则原问题若第一阶段结束时，人工变量仍在基变量中，则原问题无（可行）解无（可行）解n为了简化计算，在第一阶段重新定义价值系数如下：为了简化计算，在第一阶段重新定义价值系数如下：例例6 大大M法法cj3-1-100-M-M B-1bθcBxBx1x2x3x4x5x6x70x41-2110001111-Mx6-4120-11033/2-Mx7-201000111σj-6M+3M-13M-10-M00-4Mcj3-1-100-M-M B-1bθcBxBx1x2x3x4x5x6x70x43-20100-110-Mx60100-11-211-1x3-20100011σj1M-100-M0-3M+1 -M-1cj3-1-100-M-M B-1bθcBxBx1x2x3x4x5x6x70x43001-22-5124-1x20100-11-21-1x3-20100011σj1000-1-M+1 -M-1-2cj3-1-100-M-M B-1bθcBxBx1x2x3x4x5x6x73x11001/3-2/32/3-5/34-1x20100-11-21-1x30012/3-4/34/3-7/39σj000-1/3-1/3-M+1/3 -M+2/32最最优优解解人工变量被迭代出去后就不会再成为基变量人工变量被迭代出去后就不会再成为基变量例例4 cj2400-M B-1bθcBxBx1x2x3x4x5-Mx521-101840x4-210102σj2+2M4+M-M00-8Mcj2400-M B-1bθcBxBx1x2x3x4x52x111/2-1/201/2480x402-111105σj0310-M-18cj2400-M B-1bθcBxBx1x2x3x4x52x110-1/4-1/41/43/24x201-1/21/21/25σj005/2-3/2-M-5/226未达到最优状态，但无法继续改进，即未达到最优状态，但无法继续改进，即无有限最优解无有限最优解例例5 cj320-MB-1bθcBxBx1x2x3x4-Mx4-1-1-111σj-M+3-M+2-M0-M已达到最优状态，但基变量中的人工变量未退出，故已达到最优状态，但基变量中的人工变量未退出，故无可行解无可行解例例6 (2) 两阶段法两阶段法第一阶段第一阶段cj00000-1-1 B-1bθcBxBx1x2x3x4x5x6x70x41-2110001111-1x6-4120-11033/2-1x7-201000111σj-6130-100-4cj00000-1-1 B-1bθcBxBx1x2x3x4x5x6x70x43-20100-110-1x60100-11-2110x3-20100011σj0100-10-3-1cj00000-1-1 B-1bθcBxBx1x2x3x4x5x6x70x43001-22-5120x20100-11-210x3-20100011σj00000-1-10获得初始可行解获得初始可行解cj3-1-100B-1bθcBxBx1x2x3x4x50x43001-2124-1x20100-11-1x3-201001σj1000-1-2cj3-1-100B-1bθcBxBx1x2x3x4x53x11001/3-2/34-1x20100-11-1x30012/3-4/39σj000-1/3-1/32第二阶段第二阶段获获得得最最优优解解例例4 第一阶段第一阶段cj0000-1 B-1bθcBxBx1x2x3x4x5-1x521-101840x4-210102σj21-100-8cj0000-1 B-1bθcBxBx1x2x3x4x50x111/2-1/201/240x402-11110σj0000-10获得原问题的一个初始可行解获得原问题的一个初始可行解第二阶段第二阶段cj2400B-1bθcBxBx1x2x3x42x111/2-1/20480x402-11105σj03008cj2400B-1bθcBxBx1x2x3x42x110-1/4-1/43/24x201-1/21/25σj005/2-3/226未达到最优状态，但无法继续改进，即未达到最优状态，但无法继续改进，即无有限最优解无有限最优解例例5 cj000-1B-1bθcBxBx1x2x3x4-1x4-1-1-111σj-1-1-10-1第一阶段第一阶段已达到最优状态，但目标函数值不为零，故已达到最优状态，但目标函数值不为零，故无可行解无可行解单纯形法详细计算步骤单纯形法详细计算步骤第三章习题第三章习题1468(选选2)10 (选选2)11。