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

1、第第1页页步骤：步骤：（1）找出初始基可行解；）找出初始基可行解；（2）检验各非基变量的检验数：）检验各非基变量的检验数：如果如果j 0，j=m+1,.,n，则当前解就是最优解，则当前解就是最优解，停止计算：，停止计算：miijijjacc1 第第2页页否则否则，转下步；，转下步；如果如果j 0，j=m+1,.,n 中，若某个非基变量中，若某个非基变量 xj 的系数列向量的系数列向量 Pk 0，则此问题无界，停止计算，否，则此问题无界，停止计算，否则转下步；则转下步；（4）根据）根据max(j 0)=k，来确定，来确定 xk 为换入变量为换入变量（最大检验数有多个时，可任选一个）；（最大检验数

2、有多个时，可任选一个）；第第4页页（5）根据下式来确定）根据下式来确定 x l 为换出变量：为换出变量：lklikikiabaab )0min(最小比值有多个时（下一步迭代会出现非基变量最小比值有多个时（下一步迭代会出现非基变量=0的情况，即退化现象），可任选一个（通常选择下的情况，即退化现象），可任选一个（通常选择下标较小的那个基变量标较小的那个基变量 x l 换出）。换出）。第第5页页（6）以）以 al k 为主元素进行旋转运算，从而得到一个为主元素进行旋转运算，从而得到一个新的基可行解。新的基可行解。（7）重复（重复（2）（6），直到找到问题的最优解。），直到找到问题的最优解。第第6页页

3、cjc1cmcm+1cniCBXBbx1xmxm+1xnc1x1b110a1,m+1a1n1c2x2b200a2,m+1a2n2cmxmbm01am,m+1amnmc j z j00 mimiimacc11,1 miniinacc1,第第7页页max z=2x1+3x2 0,12 4 16 482 .212121xxxxxxts例：例：第第8页页cj23000iCBXBbx1x2x3x4x50 x381210040 x41640010-0 x5120 4 0013c j z j23000解解：（：（1）将模型转化为标准型，得到初始单纯形表）将模型转化为标准型，得到初始单纯形表第第9页页cj23

4、000iCBXBbx1x2x3x4x50 x32 1 010-1/220 x4164001043x2301001/4-c j z j2000-3/4（2）x2 为换入变量，为换入变量，x5 为换出变量，进行旋转运算，为换出变量，进行旋转运算，得到新的单纯形表：得到新的单纯形表：第第10页页cj23000iCBXBbx1x2x3x4x52x121010-1/2-0 x4800-41 2 43x2301001/412c j z j00-201/4（3）x1 为换入变量，为换入变量，x3 为换出变量，进行旋转运算，为换出变量，进行旋转运算，得到新的单纯形表：得到新的单纯形表：第第11页页cj2300

5、0iCBXBbx1x2x3x4x52x141001/400 x5400-21/213x22011/2-1/80c j z j00-3/2-1/80（4）x5 为换入变量，为换入变量，x4 为换出变量，进行旋转运算，为换出变量，进行旋转运算，得到新的单纯形表：得到新的单纯形表：（5）得到问题的最优解：）得到问题的最优解：X=(4,2,0,0,4)T第第12页页1.当约束条件不等式均当约束条件不等式均 时，化成标准型后无法直时，化成标准型后无法直接得到一个初始可行基：接得到一个初始可行基：0,.,.1221111212111nmnmnmmnnxxbxaxaxabxaxaxa第第13页页 0,.,.

6、,.112211111212111mnnnmmnnmnmmnnnxxxxbxxaxaxabxxaxaxa引入剩余变量化为标准型，但无法直接得到初始可引入剩余变量化为标准型，但无法直接得到初始可行基：行基：第第14页页 0,.,.,.1122111111212111mnnnmmmnmnnmnmmmnnnnxxxxbxxxaxaxabxxxaxaxa可再引入可再引入 m 个新变量凑出初始可行基：个新变量凑出初始可行基：这些新变量无实际含义，完全是为了凑出初始可行这些新变量无实际含义，完全是为了凑出初始可行基以便于运算，称为人工变量。基以便于运算，称为人工变量。第第15页页 0,.,.1221111

7、212111nmnmnmmnnxxbxaxaxabxaxaxa2.当约束条件不等式为当约束条件不等式为=时，也无法直接得出一个时，也无法直接得出一个初始可行基，也可采取引入人工变量的方法凑出一初始可行基，也可采取引入人工变量的方法凑出一个初始可行基：个初始可行基：第第16页页 0,.,.,.112211111212111mnnnmmnnmnmmnnnxxxxbxxaxaxabxxaxaxa可引入人工变量凑出初始可行基：可引入人工变量凑出初始可行基：第第17页页3.当约束条件中有当约束条件中有、=时，要直接凑出初始可行时，要直接凑出初始可行基：基：（1）的不等式直接加上一个松弛变量；的不等式直接

8、加上一个松弛变量；（2）的不等式减去一个剩余变量，再加上一个人的不等式减去一个剩余变量，再加上一个人工变量；工变量；（3）等式直接加上一个人工变量。）等式直接加上一个人工变量。第第18页页 0,.,.1331312212111111nnnnnnnxxbxaxabxaxabxaxa 0,.,.13431312322121111111nnnnnnnnnnnxxbxxaxabxxxaxabxxaxa松弛变量松弛变量剩余变量剩余变量人工变量人工变量第第19页页1.大大 M 法法2.两阶段法两阶段法有人工变量引入时的求解方法有人工变量引入时的求解方法第第20页页人工变量为虚拟变量，完全是为了凑出初始可行

9、人工变量为虚拟变量，完全是为了凑出初始可行基而引入，所以在目标函数中人工变量的系数应基而引入，所以在目标函数中人工变量的系数应符合如下规则：符合如下规则：（1）目标函数为极大化：很大的负数（）目标函数为极大化：很大的负数（-M）（2）目标函数为极小化：很大的正数（）目标函数为极小化：很大的正数（M）1.大大 M 法法第第21页页注意：注意：最终单纯形表中，如果基变量中有最终单纯形表中，如果基变量中有非零的人工变量非零的人工变量，则问题无可行解。，则问题无可行解。人工变量目标函数系数设置的原因：人工变量目标函数系数设置的原因：使人工变量在迭代过程中尽快从基变量中被换出。使人工变量在迭代过程中尽快

10、从基变量中被换出。第第22页页 0 ,1 232 411 2 3min32131321321321xxxxxxxxxxxxxxz例：例：第第23页页 0,1 23 2 411 2 003 max76543217316532143217654321xxxxxxxxxxxxxxxxxxxMxMxxxxxxz解：加入解：加入 松弛变量：松弛变量：x4 剩余变量：剩余变量：x5 人工变量：人工变量：x6 和和 x7 得到：得到：第第24页页cj3-1-100-M-MiCBXBbx1x2x3x4x5x6x70 x4111-21100011-Mx63-4120-1103/2-Mx71-20 1 00011

11、c j z j3-6MM-13M-10-M000 x4103-20100-1-Mx610 1 00-11-21-1x31-2010001-c j z j1M-100-M01-3M第第25页页cj3-1-100-M-MiCBXBbx1x2x3x4x5x6x70 x412 3 001-22-54-1x210100-11-2-1x31-2010001-c j z j1000-11-M-1-M3x141001/3-2/32/3-5/3-1x210100-11-2-1x390012/3-4/34/3-7/3c j z j000-1/3-1/31/3-M2/3-M第第26页页问题的最优解：问题的最优解：X

12、=(x1,x2,x3)=(4,1,9)T2.两阶段法两阶段法第一阶段：第一阶段：给原线性规划问题加入人工变量，并构给原线性规划问题加入人工变量，并构造仅含人工变量的目标函数。造仅含人工变量的目标函数。第第27页页 0,.,.max1221111121211121mnnmmnnmnmmnnnmnnnxxbxxaxaxabxxaxaxaxxx 0,.,.max12211112121112211nmnmnmmnnnnxxbxaxaxabxaxaxaxcxcxcz第第28页页然后利用单纯形法求解上述模型，如果最终单纯然后利用单纯形法求解上述模型，如果最终单纯形表中无非零的人工变量，说明原问题存在基可形

13、表中无非零的人工变量，说明原问题存在基可行解，进行第二阶段，否则原问题无可行解，停行解，进行第二阶段，否则原问题无可行解，停止计算。止计算。第第29页页第二阶段：第二阶段：将第一阶段的最终单纯形表除去人工将第一阶段的最终单纯形表除去人工变量；将目标函数行的系数换成原问题的目标函变量；将目标函数行的系数换成原问题的目标函数系数；作为第二阶段计算的初始单纯形表，进数系数；作为第二阶段计算的初始单纯形表，进行计算。行计算。第第30页页 0 ,1 232 411 2 3max32131321321321xxxxxxxxxxxxxxz例：例：解：解：0,1 23 2 411 2 max765432173

14、165321432176xxxxxxxxxxxxxxxxxxxxxz第一阶段第一阶段第第31页页cj00000-1-1iCBXBbx1x2x3x4x5x6x70 x4111-21100011-1x63-4120-1103/2-1x71-20 1 00011c j z j-6130-1000 x4103-20100-1-1x610 1 00-11-210 x31-2010001-c j z j0100-10-3第第32页页cj00000-1-1iCBXBbx1x2x3x4x5x6x70 x4123001-22-50 x210100-11-20 x31-2010001c j z j00000-1-

15、1第二阶段第二阶段第第33页页3x141001/3-2/3-1x210100-1-1x390012/3-4/3c j z j000-1/3-1/3cj3-1-100iCBXBbx1x2x3x4x50 x412 3 001-24-1x210100-1-1x31-20100-c j z j1000-1第第34页页退化问题退化问题用用规则确定换出变量时出现两个以上相同的最小比值规则确定换出变量时出现两个以上相同的最小比值下一次迭代中必有一个或几个基变量等于下一次迭代中必有一个或几个基变量等于0第第35页页当没有出现退化问题时：单纯形法的每次迭代都当没有出现退化问题时：单纯形法的每次迭代都会使目标函数

16、值有所改进，从而在有限次迭代中收会使目标函数值有所改进，从而在有限次迭代中收敛于一个最优解。敛于一个最优解。当退化问题出现时：单纯形法的每次迭代不能保当退化问题出现时：单纯形法的每次迭代不能保证会使目标函数值都有所改进，从而也无法保证在证会使目标函数值都有所改进，从而也无法保证在有限次迭代后收敛于一个最优解。有限次迭代后收敛于一个最优解。从而，退化问题是一个有待证明是否能够收敛的问从而，退化问题是一个有待证明是否能够收敛的问题。题。第第36页页限入循环无法收敛于最优解限入循环无法收敛于最优解从而迭代后的新基可行解不能使目标函数值更优从而迭代后的新基可行解不能使目标函数值更优用用规则确定换出变量

17、时出现两个以上相同的最小比值规则确定换出变量时出现两个以上相同的最小比值下一次迭代中必有一个或几个基变量等于下一次迭代中必有一个或几个基变量等于0每一次迭代的非基变量被换入后，值均为每一次迭代的非基变量被换入后，值均为 0 每次跌代的换出变量均是值为每次跌代的换出变量均是值为 0 的基变量的基变量退化问题可能造成的一种无法收敛于最优解的情况退化问题可能造成的一种无法收敛于最优解的情况第第37页页退化问题出现时，可能会出现上述死循环情况的出退化问题出现时，可能会出现上述死循环情况的出现，使问题无法收敛于最优解，但这种情况出现的现，使问题无法收敛于最优解，但这种情况出现的几率是非常小的。几率是非常

18、小的。退化问题退化问题出现死循环，无法收敛出现死循环，无法收敛（概率较小）（概率较小）没有出现死循环，收敛于最优解没有出现死循环，收敛于最优解（概率较大）（概率较大）第第38页页 0 ,9 3 124 3min3213232132131xxxxxxxxxxxxxz例：例：0,9 3 1 24 003 max7654321732653214321765431xxxxxxxxxxxxxxxxxxxMxMxxxxxz解：解：第第39页页cj-30100-M-MiCBXBbx1x2x3x4x5x6x70 x4411110004-Mx61-2 1-10-1101-Mx7903100013c j z j-

19、3-2M4M10-M000第第40页页cj-30100-M-MiCBXBbx1x2x3x4x5x6x70 x43 3 0211-1010 x21-21-10-110-Mx76 6 0403-311c j z j6M-304M+103M-4M00最小比值有两个相同，无论选择最小比值有两个相同，无论选择 x4 还是还是 x7 作为换出变作为换出变量，均会出现基变量为量，均会出现基变量为 0 的情况，该问题为一个退化的情况，该问题为一个退化问题。问题。第第41页页cj-30100-M-MiCBXBbx1x2x3x4x5x6x7-3x11102/31/31/3-1/3030 x23011/32/3-1

20、/31/30-Mx70000-2 1-110c j z j003-2M+1M+1-1-2M001换出变量换出变量 x7 =0 换入变量换入变量 x5=0选择选择 x4 作为换出变量。作为换出变量。可能出现死循环可能出现死循环第第42页页cj-30100-M-MiCBXBbx1x2x3x4x5x6x7-3x11102/3100-1/33/20 x23011/30001/390 x50000-21-11-c j z j00330-M-M-10换出变量换出变量 x1 0 而不是而不是 x5 换入变量换入变量 x3 0没有出现死循环没有出现死循环第第43页页cj-30100-M-MiCBXBbx1x2

21、x3x4x5x6x71x33/23/2013/200-1/20 x25/2-1/210-1/2001/20 x50000-21-11c j z j-9/200-3/20-M-M+1/23/2从而得到问题最优解，问题并没有限入死循环，从而得到问题最优解，问题并没有限入死循环，问题收敛于最优解。问题收敛于最优解。第第44页页cj-30100-M-MiCBXBbx1x2x3x4x5x6x70 x400001-1/2-1/21/2-0 x23011/30001/39-3x11102/301/2-1/21/63/2c j z j00303/2-M-3/2-M+1/2-32换出变量换出变量 x1 0，而不

22、是，而不是 x4 换入变量换入变量 x3 0没有出现死循环没有出现死循环选择选择 x7 作为换出变量。作为换出变量。第第45页页cj-30100-M-MiCBXBbx1x2x3x4x5x6x70 x400001-1/21/2-1/20 x25/2-1/2100-1/41/41/41x33/23/20103/4-3/41/4c j z j-9/2000-3/4-M+3/4-M-1/43/2从而得到问题最优解，问题并没有限入死循环，从而得到问题最优解，问题并没有限入死循环，问题收敛于最优解。问题收敛于最优解。第第46页页对于退化问题，利用勃兰特规则可以完全避免死循对于退化问题，利用勃兰特规则可以完

23、全避免死循环的出现。环的出现。1974年勃兰特（年勃兰特（Bland）提出的勃兰特规则：）提出的勃兰特规则：（1）选取）选取 cj zj 0 中下标最小的非基变量中下标最小的非基变量xk为换为换入变量：入变量：)0 (min jjzcjk（2）当按）当按 规则计算存在两个和两个以上最小比规则计算存在两个和两个以上最小比值时，选取下标最小的基变量为换出变量值时，选取下标最小的基变量为换出变量。第第47页页添加松弛、人工变量，列出初始单纯形表添加松弛、人工变量，列出初始单纯形表计算非基变量检验数计算非基变量检验数i i所有所有j00基变量中有基变量中有非非零零人工变量人工变量某非基变量某非基变量检

24、验数为零检验数为零唯一最唯一最优解优解无穷多最优解无穷多最优解无可行解无可行解否否否否是是是是是是否否对任一对任一i i 0有有 Pj 0是是无界解无界解否否选择换入变量选择换入变量选择换出变量选择换出变量（注意退化问题）（注意退化问题）旋转运算旋转运算得到一新的基可行解得到一新的基可行解第第48页页习题习题1 如下线性规划问题的最优解为如下线性规划问题的最优解为 X*。0 .max XbAXtsCXz求：求：（1）约束条件不变，目标函数变为）约束条件不变，目标函数变为 z=CX（0）时，）时，最优解是否发生变化。最优解是否发生变化。（2）约束条件不变，目标函数变为）约束条件不变，目标函数变为

25、 z=(+C)X（0）时）时，最优解是否发生变化。，最优解是否发生变化。（3）约束条件变为）约束条件变为 AX=b，目标函数变为，目标函数变为 z=C/X，最优，最优解是否发生变化。解是否发生变化。第第49页页解：解：根据目标函数系统变化对最优解的影响分析可知：根据目标函数系统变化对最优解的影响分析可知：最优解是否改变，只需要判断最终单纯形表中的检最优解是否改变，只需要判断最终单纯形表中的检验数即可。验数即可。（1）01 miijijjacc 由此可知最优解不变。由此可知最优解不变。01 jmiijijjacc 第第50页页（2）即新的检验数可正可负，从而最优解可能会发生变化。即新的检验数可正

26、可负，从而最优解可能会发生变化。01 miijijjacc miijijjacc1)()(miijmiijijaacc11)()()(11 miijimiijjacac )1(1 miijja 第第51页页（3）即基变量没有发生任何变化，基变量值为单纯形表即基变量没有发生任何变化，基变量值为单纯形表的右端常数列，故最优解变为的右端常数列，故最优解变为 X*。01 miijijjacc miijijjacc1)(miijijacc1)(1 01 j 第第52页页习题习题2 线性规划问题模型如下所示线性规划问题模型如下所示0 .max XbAXtsCXz0)(0*XXCC设设 X0 为问题的最优解

27、，若目标函数用为问题的最优解，若目标函数用 C*代替代替 C 后，问题最后，问题最优解变为优解变为 X*，求证，求证第第53页页00*0*CXCXXCXC证：即证证：即证0*00*CXCXXCXC0 0*00*CXCXXCXC0*00*CXCXXCXC证毕。证毕。第第54页页习题习题3 下表是某求极大化线性规划问题计算得到的单纯形表。表下表是某求极大化线性规划问题计算得到的单纯形表。表中无人工变量，中无人工变量，a1、a2、a3、d、c1、c2为待定常数。试说明，这为待定常数。试说明，这些常数取何值时，以下结论成立。些常数取何值时，以下结论成立。（1）表中解为唯一最优解；）表中解为唯一最优解；

28、（2）表中解为最优解，但存在无穷多最优解；）表中解为最优解，但存在无穷多最优解；（3）该线性规划问题具有无界解；）该线性规划问题具有无界解；（4）表中解非最优解，为对解改进，换入变量为）表中解非最优解，为对解改进，换入变量为 x1，换出变量，换出变量为为 x6。CBXBbx1x2x3x4x5x60 x3d4a110a200 x42-1-301-101x63a3-500-41c j z jc1c200-30第第55页页解：解：（1）表中解为唯一最优解：）表中解为唯一最优解：c10，c20（2）表中解为最优解，但存在无穷多最优解：）表中解为最优解，但存在无穷多最优解：c10且且c2=0，或，或c2

29、0（3）该线性规划问题具有无界解：）该线性规划问题具有无界解：c20且且a10（4）表中解非最优解，为对解改进，换入变量为）表中解非最优解，为对解改进，换入变量为 x1，换出变，换出变量为量为 x6：c10，且，且c1c2，3/a3d/4，且，且a30，d0第第56页页习题习题4 求下述线性规划问题目标函数求下述线性规划问题目标函数 z 的上界和下界值。的上界和下界值。0,.max21222212112121112211xxbxaxabxaxatsxcxcz6442,523141011288431222112112121 aaaabbcc，其中：其中：第第57页页习题习题5 已知某线性规划问题

30、的初始单纯形表和用单纯形法跌已知某线性规划问题的初始单纯形表和用单纯形法跌代后得到的表，代后得到的表，x4和和x5为松弛变量。试求未知数为松弛变量。试求未知数 al 的值。的值。XBbx1x2x3x4x5x46bcd10 x51-13e01c j z ja-1200 x1fg2-11/20 x54hi11/21c j z j0-7jkl第第58页页解：因换入变量为解：因换入变量为 x1，换出变量为，换出变量为 x4，故进行旋转运算的，故进行旋转运算的主元素为主元素为 b。XBbx1x2x3x4x5x46/bb/bc/bd/b1/b0 x51-13e01c j z ja-1200 x1fg2-1

31、1/20 x54hi11/21c j z j0-7jklb=2，d=-2，c=4，f=3，g=1，h=0，i=5，e=2，l=0第第59页页下面还要求下面还要求a、j、k 的值。设目标函数系数为的值。设目标函数系数为c1、c2、c3、c4、c5，c4=c5=0a=c1-1=c22=c3-7=c2-2c1j=c3+c1k=-0.5c1c1=3，a=3，j=5，k=-1.5第第60页页习题习题6 已知某线性规划问题的初始单纯形表和用单纯形法跌代已知某线性规划问题的初始单纯形表和用单纯形法跌代后得到的表，后得到的表，x4和和x5不是松弛变量。试求未知数不是松弛变量。试求未知数 al 的值。的值。XB

32、bx1x2x3x4x5x46bcd10 x51-13e01c j z ja-1200 x1fg2-11/20 x54hi11/21c j z j0-7jkl第第61页页解：因换入变量为解：因换入变量为 x1，换出变量为，换出变量为 x4，故进行旋转运算的，故进行旋转运算的主元素为主元素为 b。XBbx1x2x3x4x5x46/bb/bc/bd/b1/b0 x51-13e01c j z ja-1200 x1fg2-11/20 x54hi11/21c j z j0-7jklb=2，d=-2，c=4，f=3，g=1，h=0，i=5，e=2，l=0第第62页页klkljjjaa -下面还要求下面还要求

33、a、j、k 的值。设目标函数系数为的值。设目标函数系数为c1、c2、c3、c4、c5。需借助如下公式：需借助如下公式：xk，xj 为换出变量为换出变量推导过程见书推导过程见书 P28（在第二章中也将介绍此公式的推导）（在第二章中也将介绍此公式的推导）主元素主元素换出变量所对应的系数行向量中的系数换出变量所对应的系数行向量中的系数换入变量的检验数换入变量的检验数第第63页页max z=2x1+3x2 0,12 4 16 482 .212121xxxxxxts例：例：第第64页页cj23000iCBXBbx1x2x3x4x50 x381210040 x41640010-0 x5120 4 0013

34、c j z j230000 x32 1 010-1/220 x4164001043x2301001/4-c j z j2000-3/43402 3443 3400 3400 3410 2112 2100 2110 2100 212/143 klkljjaa -klkljjaa -第第65页页cj23000iCBXBbx1x2x3x4x52x121010-1/2-0 x4800-41 2 43x2301001/412c j z j00-201/42x141001/400 x5400-21/213x22011/2-1/80c j z j00-3/2-1/8041200 41200 41242 41210 412241 klkljjaa -第第66页页XBbx1x2x3x4x5x46 2 4-210 x51-13201c j z ja-1200 x1312-11/20 x540511/21c j z j0-7jk0aa 22a 241a 222a 210a 200下一单纯形表的检验数下一单纯形表的检验数a=3j=5k=3/2