大学精品课件：第二章 线性规划与单纯形法（第6节）.ppt

1、第第1页页单纯形法的基本思想：从可行域中某个基可行解（单纯形法的基本思想：从可行域中某个基可行解（一个顶点）开始，转换到另一个使问题目标函数值一个顶点）开始，转换到另一个使问题目标函数值更优的基可行解（顶点），当目标函数值达到最优更优的基可行解（顶点），当目标函数值达到最优时，问题就得到了最优解。时，问题就得到了最优解。第第2页页1.确定初始基可行解确定初始基可行解（1）确定换入变量）确定换入变量（2）确定换出变量）确定换出变量2.最优性检验与解的判别最优性检验与解的判别3.基变换：从一个基可行解到另一个基可行解的过程。基变换：从一个基可行解到另一个基可行解的过程。（3）转换）转换第第3页页1

2、.线性规划问题中能够直接观察到一个初始可行基。线性规划问题中能够直接观察到一个初始可行基。2.线性规划问题中所有约束条件均为线性规划问题中所有约束条件均为 形式的不等形式的不等式。式。加上松弛变量将其变为标准型后，就出现一个初加上松弛变量将其变为标准型后，就出现一个初始可行基。始可行基。第第4页页 0,.,.max12211112121112211nmnmnmmnnnnxxbxaxaxabxaxaxatsxcxcxcz第第5页页 0,.,.,.max1122111112121112211mnnnmmnnmnmmnnnnnxxxxbxxaxaxabxxaxaxatsxcxcxcz注意：松弛变量在

3、目标函数中的系数为注意：松弛变量在目标函数中的系数为 0。第第6页页此时出现一个初始可行基，该初始可行基为此时出现一个初始可行基，该初始可行基为单位矩单位矩阵阵，基变量全部由，基变量全部由剩余变量剩余变量组成。组成。第第7页页3.线性规划问题中所有约束条件均为线性规划问题中所有约束条件均为 形式的不等形式的不等式。式。减去剩余变量将其变为标准型后，再分别在每个减去剩余变量将其变为标准型后，再分别在每个约束条件等式左边加上一个人工变量，凑出一个约束条件等式左边加上一个人工变量，凑出一个初始可行基。初始可行基。第第8页页 0,.,.,.max1122111112121112211mnnnmmnnm

4、nmmnnnnnxxxxbxxaxaxabxxaxaxatsxcxcxcz引入剩余变量化为标准型，但无法直接得到初始可引入剩余变量化为标准型，但无法直接得到初始可行基：行基：注意：剩余变量在目标函数中的系数为注意：剩余变量在目标函数中的系数为 0。第第9页页 0,.,.,.max112211111121211112211mnnnmmmnmnnmnmmmnnnnmmnmnnnxxxxbxxxaxaxabxxxaxaxatsxMxMxcxcxcz可再引入可再引入 m 个新变量凑出初始可行基：个新变量凑出初始可行基：这些新变量无实际含义，完全是为了凑出初始可行这些新变量无实际含义，完全是为了凑出初始

5、可行基以便于运算，称为人工变量。基以便于运算，称为人工变量。注意：人工变量在目标函数中的系数不为注意：人工变量在目标函数中的系数不为 0。第第10页页此时出现一个初始可行基，该初始可行基为此时出现一个初始可行基，该初始可行基为单位矩单位矩阵阵，基变量全部由，基变量全部由人工变量人工变量组成。组成。第第11页页 0,.,.max12211112121112211nmnmnmmnnnnxxbxaxaxabxaxaxatsxcxcxcz4.当约束条件不等式为当约束条件不等式为=时，也无法直接得出一个时，也无法直接得出一个初始可行基，也可采取引入人工变量的方法凑出一初始可行基，也可采取引入人工变量的方

6、法凑出一个初始可行基：个初始可行基：第第12页页 0,.,.,.max11221111121211112211mnnnmmnnmnmmnnnmnnnnxxxxbxxaxaxabxxaxaxatsMxMxxcxcxcz可引入人工变量凑出初始可行基：可引入人工变量凑出初始可行基：第第13页页此时出现一个初始可行基，该初始可行基为此时出现一个初始可行基，该初始可行基为单位矩单位矩阵阵，基变量全部由，基变量全部由人工变量人工变量组成。组成。第第14页页5.当约束条件中有当约束条件中有、=时，要直接凑出初始可行时，要直接凑出初始可行基：基：（1）的不等式直接加上一个松弛变量；的不等式直接加上一个松弛变量

7、；（2）的不等式减去一个剩余变量，再加上一个人的不等式减去一个剩余变量，再加上一个人工变量；工变量；（3）等式直接加上一个人工变量。）等式直接加上一个人工变量。第第15页页 0,.,.1331312212111111nnnnnnnxxbxaxabxaxabxaxa 0,.,.13431312322121111111nnnnnnnnnnnxxbxxaxabxxxaxabxxaxa松弛变量松弛变量剩余变量剩余变量人工变量人工变量第第16页页此时出现一个初始可行基，该初始可行基为此时出现一个初始可行基，该初始可行基为单位矩单位矩阵阵，基变量全部由，基变量全部由剩余变量剩余变量和和人工变量人工变量共同

8、组成。共同组成。第第17页页总总 结结当凑出初始可行基时，该初始可行基均为当凑出初始可行基时，该初始可行基均为单位矩阵单位矩阵。第第18页页 njjjxczMax1 mnmnmmmmnnmmnnmmbxaxaxbxaxaxbxaxax.11,2211,221111,11njxj,.,1,0 第第19页页 nmjjjmiiixcxczMax11 mibxaxtsinmjjiji,.,1,.1 njxj,.,1,0 第第20页页 nmjjjmiiixcxczMax11 mixabxtsnmjjijii,.,1,.1 njxj,.,1,0 （1）（2）第第21页页将（将（2）代入（）代入（1）：）：

9、nmjjjminmjjijiixcxabcz111)(nmjjjmiminmjjijiiixcxacbc1111 minmjjmiijinmjjjiixacxcbc1111 minmjjmiijijiixaccbc111)(第第22页页 minmjjmiijijiixaccbcz111)(非基变量非基变量将非基变量将非基变量 xj 变为基变量而产变为基变量而产生的目标函数增加值生的目标函数增加值当前基可行解的目标函数值当前基可行解的目标函数值第第23页页 minmjjmiijijiixaccbcz111)(变量变量 xj 所对应的目标函数系数所对应的目标函数系数基变量基变量 xi 所对应的目标

10、函数系数所对应的目标函数系数变量变量 xj 所对应的约束条件系数所对应的约束条件系数约束条件右端常数约束条件右端常数第第24页页 minmjjmiijijiixaccbcz111)(0zj nmjjjxzz10 称称j 为检验数为检验数。第第25页页 miijijjacc1 变量变量 xj 所对应的目标函数系数所对应的目标函数系数基变量基变量 xi 所对应的目标函数系数所对应的目标函数系数变量变量 xj 所对应的约束条件系数所对应的约束条件系数第第26页页检验数主要是针对非基变量而言的。检验数主要是针对非基变量而言的。基变量的检验数为基变量的检验数为 0。某个非基变量的检验数的含义表示该非基变

11、量变某个非基变量的检验数的含义表示该非基变量变为基变量后，而引起的问题目标函数增加值。为基变量后，而引起的问题目标函数增加值。第第27页页例例max z=2x1+3x2 0,12 4 16 482 .212121xxxxxxts第第28页页2132 maxxxz TX)0(12,16,8,0,0 0,12 4 16 48 2.543215241321xxxxxxxxxxxxts基变量：基变量：x3、x4、x5第第29页页 2041 00021 3402 00032 第第30页页 0001 00003 0010 00004 0100 00005 第第31页页1.唯一最优解判别定理唯一最优解判别定

12、理若若 为对应于基为对应于基 B 的一个的一个 基可行解，且对于一切基可行解，且对于一切 j=m+1,n，有，有j 0，并且对于并且对于i=1,2,m，有，有ai,m+k0，则，则线性规划问题具线性规划问题具有无界解。有无界解。TmbbbX 0,.,0,.,21)0(第第35页页证：证：令非基变量：令非基变量：njjjxczMax1 mnmnkmkmmmmmmnnkmkmmmnnkmkmmmbxaxaxaxbxaxaxaxbxaxaxax.,11,22,211,2211,111,11njxj,.,1,0 ),.,.,(111nkmkmkmmxxxxx )0,.,0,0,.,0(0 其其中中第第

13、36页页TkmmmkmababX)0,.,.,0,.,(,11)1(从而得到一新解从而得到一新解 X(1)：0 所以新解所以新解 X(1)中各分量均为非负值，且随着中各分量均为非负值，且随着增增加，各分量会无限增大，故为无界解加，各分量会无限增大，故为无界解。0,.,2,1 kmmkmkmaaa且且第第37页页方法：从基可行解的可行基中取出一个列向量，再方法：从基可行解的可行基中取出一个列向量，再换入另外一个列向量，使换入的列向量同原来的向换入另外一个列向量，使换入的列向量同原来的向量仍然线性无关，从而得到一个新的可行基。量仍然线性无关，从而得到一个新的可行基。基变换：从一个基可行解到另一个基

14、可行解的过程。基变换：从一个基可行解到另一个基可行解的过程。第第38页页2132 maxxxz 0,12 4 16 48 2.543215241321xxxxxxxxxxxxts换入到可行基中去换入到可行基中去从可行基中换出来从可行基中换出来 100第第39页页2132 maxxxz 0,12 4 16 48 2.543215241321xxxxxxxxxxxxts换入变量换入变量换出变量换出变量必须为非基变量必须为非基变量必须为基变量必须为基变量第第40页页2132 maxxxz 0,12 4 16 48 2.543215241321xxxxxxxxxxxxts变为非单位向量变为非单位向量

15、100变为单位向量变为单位向量该过程称为旋转运算该过程称为旋转运算第第41页页换入变量的确定换入变量的确定换出变量的确定换出变量的确定旋转运算旋转运算基变换基变换第第42页页0 j jjj )0(max1.换入变量的确定换入变量的确定选择检验数为正的非基变量作为换入变量选择检验数为正的非基变量作为换入变量多个检验数为正时，选择检验数最大的非基变量换入多个检验数为正时，选择检验数最大的非基变量换入注：检验数最大的非基变量有多个时，可任选一个。注：检验数最大的非基变量有多个时，可任选一个。第第43页页2.换出变量的确定换出变量的确定 njjjxczMax1 mnmntmtmmmmmmnntmtmm

16、mnntmtmmmbxaxaxaxbxaxaxaxbxaxaxax.,11,22,211,2211,111,11njxj,.,1,0 第第44页页非基变量非基变量 x m+t 为换入变量为换入变量 njjjxczMax1 mnmntmtmmmmmmnntmtmmmnntmtmmmbxaxaxaxbxaxaxaxbxaxaxax.,11,22,211,2211,111,11njxj,.,1,0 换入变量换入变量第第45页页),.,(1mtmPPP 线性相关线性相关 tmmtmtmaaP,1.10 .01).(1mPPtmP 线性表示。线性表示。),.,(1mPP可以用可以用第第46页页 1001

17、,1tmmtmtmaaP0,1,不不全全为为，tmimiitmitmaPaP P1Pm第第47页页01,miitmitmPaP（1）miitmitmPaP1,第第48页页bPbmiii 1TmbbX)0,.,0,.,(1)0(（2）问题的基可行解为：问题的基可行解为：故代入各约束条件可得：故代入各约束条件可得：第第49页页（2）+（1）：）：(0)bPaPPbmiitmitmmiii )(1,1 bPPabtmmiitmii 1,)(（3）第第50页页TtmmmtmababX)0,.,.,0,.,(,11)1(由式（由式（3）可知：）可知：为问题新产生的解，但不能保证新产生的解是可为问题新产生

18、的解，但不能保证新产生的解是可行解，更不能保证是基可行解。行解，更不能保证是基可行解。x1xmxm+t基变量基变量非基变量非基变量第第51页页下面来讨论选择下面来讨论选择 值才能使得值才能使得新产生的解新产生的解 X(1)为基可行解为基可行解 Ttmmmtmabab)0,.,.,0,.,(,11 x1xmxm+t基变量基变量非基变量非基变量第第52页页要使得新产生的解为基可行解，必须满足：要使得新产生的解为基可行解，必须满足：基变量基变量(x1,xm)中要有一个中要有一个 xl 被换出，变被换出，变为非基变量，即其对应的分量值变为为非基变量，即其对应的分量值变为 0，同时还，同时还要保证其他变

19、量的值都要大于要保证其他变量的值都要大于 0。第第53页页换入的变量换入的变量 xm+t 所对应的系数列向量所对应的系数列向量Pm+t线性无关线性无关(P1,Pl-1,Pl,Pl+1,Pm)Pm+t第第54页页合理选择合理选择 的值，可使得：的值，可使得：某一个分量为某一个分量为 0，而其它分量均大于，而其它分量均大于 0。Ttmmmtmabab)0,.,.,0,.,(,11 第第55页页tmlltmitmiiiabaab ,0min 最小比值规则最小比值规则按下述规则确定的按下述规则确定的 值可满足上述要求：值可满足上述要求：从而使从而使成为一组可行解。成为一组可行解。Ttmmmtmabab

20、)0,.,.,0,.,(,11 第第56页页TtmlltmmtmlltmtmllabaabbaabbX)0,.,.,0,.,.,0,(,m,1,1)1(得到一新可行解得到一新可行解 X(1)：第第 l 个分量个分量第第 m+t 个分量个分量x l 为换入变量为换入变量第第57页页 tmiabtmimilimiliaabbxtmlltmitmllii ,0,)1(第第58页页下面来验证得的新可行解下面来验证得的新可行解 X(1)为基可行解。为基可行解。),.,.,(111mltmlPPPPP 线性无关线性无关第第 l 个分量个分量第第59页页反证法：反证法：),.,.,(111mllPPPP 线

21、性无关线性无关),.,.,(111mltmlPPPPP 线性相关线性相关假设假设),.,.,(111mllPPPP tmP 线性表示线性表示第第60页页mmlllltmPPPPP .111111),.,.,(111mllPPPP tmP 线性表示线性表示因为因为可由可由故故第第61页页mtmmltmlltmlltmltmtmPaPaPaPaPaP ,1,1,1,11,1.又又 tmmtmtmtmaaaP,2,1 0011P 0102P 100mP故故第第62页页mmlllltmPPPPP ,.,.111111mtmmltmlltmlltmltmtmPaPaPaPaPaP ,1,1,1,11,1

22、.多了此项多了此项第第63页页0)(,1,ltmljmljjjtmjPaPa 两式相减可得：两式相减可得：0,tmla是一组不全为是一组不全为 0 的数的数),.,.,(,1,1,1,11,1mtmmltmltmlltmltmaaaaa 第第64页页),.,(1mPP线性相关线性相关由此可知，假设错误。由此可知，假设错误。),.,.,(111mltmlPPPPP 线性无关线性无关X(1)为基可行解。为基可行解。由此可得由此可得但但),.,(1mPP是线性无关的。是线性无关的。第第65页页tmlltmitmiiiabaab ,0min 换入变量：换入变量：xm+t换出变量：换出变量：xltmjj

23、 )0(max注：最小比值有多个时（此时会出现非基变量注：最小比值有多个时（此时会出现非基变量=0的情况，的情况，即退化现象），可任选一个（通常选择下标较小的那个即退化现象），可任选一个（通常选择下标较小的那个基变量基变量 x l 换出）。换出）。第第66页页例例max z=2x1+3x2 0,12 4 16 482 .212121xxxxxxts第第67页页2132 xxz TX)0(12,16,8,0,0 0,12 4 16 48 2.543215241321xxxxxxxxxxxxts基变量：基变量：x3、x4、x5第第68页页 2041 00021 3041 00032 3)3,2ma

24、x()0(max jj x2 换入换入3)412,28min(0min,tmitmiiiaab x5 换出换出第第69页页3.旋转运算旋转运算换入变量：换入变量：xk换出变量：换出变量：xlkjj )0(maxkllkikiiiabaab,0min k=m+1,nl=1,m第第70页页 mklkkkkaaaaP21 0100lP第第 l 个分量个分量换入变量换入变量 xk 的系数列向量：的系数列向量：换出变量换出变量 xl 的系数列向量：的系数列向量：第第 l 个分量个分量第第71页页将将 xk 换入，将换入，将 xl 换出，也就是将换出，也就是将 xk 的列向量的列向量 Pk 转转变为变为

25、xl 的列向量的列向量 Pl 的形式：的形式：mklkkkkaaaaP21 0100第第 l 个分量个分量第第72页页 mlmnmkmmnllkmlnkmnkmmlbbbaaaaaaaaabxxxxxx11,1,111,111 1 0 0 0 1 0 0 0 1 换换出出 变变量量换入换入 变量变量约束条件系数矩阵约束条件系数矩阵 A 如下所示：如下所示：主主 元元 素素x1xlxm换出换出 变量变量第第73页页 mlklmnmkmmlknllkmllknkmnkmmlbabbaaaaaaaaaaabxxxxxx 1 0 0 1 0 1 0 0 0 1 11,1,111,111（1）将第）将第

26、 l 行除以行除以 al k：第第74页页 lklmkmlkllklklknlmkmnlkmlmkmmlkmklknllkmllklknlknlkmlkmlkknkmmlabababababaaaaaaaaaaaaaaaaaaaaaaaaabxxxxxx 0 -1 -0 1 0 1 0 0 -0 -1 11 1,1,1,111,11,1111（2）将第）将第 l 行乘以行乘以-ai k 加到各行：加到各行：第第75页页TlkllklmkmlklklllklklllklkabababababababababX)0 ,.,.,0 ,0 ,.,(,11,1111)1(（3）从而得到一个新的基可行解）

27、从而得到一个新的基可行解 X(1)：第第76页页 0,124 16 482 .32 max21212121xxxxxxtsxxz例：例：解：解：max z=2 x1+3 x2+0 x3+0 x4+0 x5 0,12 4 16 48 2.543215241321xxxxxxxxxxxxts第第77页页基变量：基变量：x3、x4、x5TX)12,16,8 ,0 ,0()0(2041)0 0 0(21 3402)0 0 0(32 换入变量：换入变量：x23412,28min 换出变量：换出变量：x5第第78页页 21 61 8 1 0 0 4 0 0 1 0 0 4 0 0 1 2 1 54321bxxxxx换入换入 变量变量换出换出 变量变量主主 元元 素素换出换出 变量变量第第79页页 3 61 2 4/1 0 0 1 0 0 1 0 0 4 2/1 0 1 0 1 54321bxxxxxTX)0 ,61 ,2 ,3 ,0()1(