运筹学课后习题答案

1、精选第一章 线性规划1、 由图可得：最优解为2、用图解法求解线性规划： Min z=2x1+x2 解： 由图可得：最优解x=1.6,y=6.43用图解法求解线性规划： Max z=5x1+6x2 解： 由图可得：最优解Max z=5x1+6x2, Max z= +4用图解法求解线性规划： Maxz = 2x1 +x2 由图可得：最大值 ， 所以max Z = 8.6将线性规划模型化成标准形式： Min z=x1-2x2+3x3 解：令Z=-Z,引进松弛变量x40，引入剩余变量x50，并令x3=x3-x3,其中x30,x30Max z=-x1+2x2-3x3+3x37将线性规划模型化为标准形式

2、Min Z =x1+2x2+3x3 解：令Z = -z，引进松弛变量x40,引进剩余变量x50,得到一下等价的标准形式。 x2=-x2 x3=x3-x3Z = -min Z = -x1-2x2-3x3 Cj33400iCBXBbx1x2x3x4x50X4403451080X5606430120j334004x383/54/511/5040/30x54221/58/50-3/5160/7j3/5-1/50-4/504x320 4/714/35-1/73x11018/2101/75/21j0-3/70-31/35-1/79用单纯形法求解线性规划问题：Max Z =70x1+120x2 解： Max

3、 Z =70x1+120x2 单纯形表如下 Max Z =3908.Cj43000iCBXBbx1x2x3x4x50X330002210015000X4400052.50108000X550010001500Cj-Zj43000Cj43000iCBXBbx1x2x3x4x50X320000210-20X4150002.501-50X150010001Cj-Zj0000-411.解：（1）引入松弛变量X4，X5，X6，将原问题标准化，得max Z=10X1+6X2+4X3 X1+X2+X3+X4=10010 X1+4X2+5X3+X5=6002 X1+2X2+6X3+X6=300X1,X2,X3

4、,X4,X5,X60得到初始单纯形表：Cj1064000CBXBbX1X2X3X4X5X6000X4X5X6100600300110214215610001000110060150Cj-Zj1064000（2）其中1 =C1-Z1=10-（0×1+0×10+0×2）=10，同理求得其他依据max =max10,6,4=10,对应的X1为换入变量，计算得到，min =min100/1,600/10,300/2=60,X5为换出变量，进行旋转运算。（3）重复（2）过程得到如下迭代过程Cj1064000CBXBbX1X2X3X4X5X60100X4X1X64060180

5、0103/52/56/51/21/25100-1/101/101/5001200/3150150Cj-Zj02-10-106100X2X1X6200/3100/31000101005/61/645/3-2/3-2-1/61/60001200/3150150Cj-Zj00-8/3-10/3-2/30j 0，迭代已得到最优解，X*=（100/3，200/3，0，0，0，100）T ，Z* =10×100/3+6×200/3+4×0 =2200/3。12解：（1）引入松弛变量X3，X4，X5将原问题标准化，得max Z=2X1+X25X2+X3=156X1+2X2+ X

6、4=24X1+2X2+ X5=5X1,X2,X3,X4,X50得到初始单纯形表：Cj21000CBXBbX1X2X3X4X5000X3X4X515245061521100010001-45Cj-Zj21000（2）其中1 =C1-Z1=2-（0×1+0×10+0×2）=2，同理求得其他依据max =max2,1,0=2,对应的X1为换入变量，计算得到，min =min-,24/6,5/1=4, X4为换出变量，进行旋转运算。（3）重复（2）过程得到如下迭代过程Cj106400CBXBbX1X2X3X4X5020X3X1X5154101051/32/310001/6

7、-1/60013123/2Cj-Zj01/30-1/30021X3X1X215/217/23/20100011005/41/4-1/4-15/2-1/23/2Cj-Zj000-1/4-1/2j 0，迭代已得到最优解，X*=（7/2，3/2，0，0，0）T ，Z* =2×7/2+3/2 =17/2。13解：引入松弛变量X3、X4，约束条件化成等式，将原问题进行标准化，得：Max Z=2.5X1+X2 3X1+5X2+X3 =15 5X1+2X2 +X4=10 X1,X2,X3,X40（1） 确定初始可行基为单位矩阵I=P3，P4，基变量为X3，X4，X5，非基变量为X1，X2，则有：M

8、ax Z=2.5X1+3X2 X3=15-3X1-5X2s.t X4=10-5X1-2X2 Xi0，j=1，2，3，42.5100 b 0 15 0 10 3 5 1 05 2 0 1522.5100 将题求解过程列成单纯形表格形式，表1 由上述可得，将替换为表2，单纯形迭代过程 2.5100 b0 9 2.5 20 19/5 1 -3/51 2/5 0 1/545/1950000.5由表2可得，将替换为2.5100 b1 2.5 0 1 1 0 000表3 最终单纯形表非基变量检验数=0,=，得到该线性规划另一最优解，=（，0,0）,=5， 该线性规划具有无穷多个解14. 用单纯形法求解线性

9、规划问题：解：（1） 将原问题转化为标准形式，得（2）建立单纯性，并进行迭代运算Cj21000C8 XBbX1X2X3X4X50X315051000X4246101040X55110015Cj-Zj210000X3150510032X1411/601/60240X5105/60-1/616/5Cj-Zj02/30-1/300X390011-62X119/51001/5-1/51X26/5010-1/56/5Cj-Zj000-1/5-4/5 （3）得到最优解X*=(,9 ,0 ,0 )T，Z*=15.用单纯形法求解线性规划问题：解：（1） 将原问题转化为标准形式，得（2）建立单纯性，并进行迭代运

10、算Cj21000C8 XBbX1X2X3X4X50X3211210020X42-21010-0X54-11001-Cj-Zj110001X121-21000X460-32100X560-1101Cj-Zj03-100本例其次个单纯形表中，非基变量X2对应的检验数0，并且对应的变量系数ai，20（i=1，2，3），依据无界解判定定理，该线性规划问题有无界解（或无最优解）。假如从方程角度看，其次个表格还原线性方程也即：令=0，则此时，若进基，则，会和基变量同时增加，同时目标函数值无限增长，所以本题无解。16解：（1）引入松弛变量X3，X4，X5将原问题标准化，得max Z=2X1+4X2+0X3+

11、0X4+0X5X1+2X2+X3=8X1+X4=4X2+X5=3X1,X2,X3,X4,X50（1）得到初始单纯形表：Cj24000CBXBbX1X2X3X4X5000X3X4X58431102011000100014-3Cj-Zj24000（2）重复（1）过程得到如下迭代过程Cj106400CBXBbX1X2X3X4X5004X3X4X224311000110001000124-Cj-Zj2000-4204X1X4X22231000011-10010001Cj-Zj00-2005 = 0，3 < 0，因此有无穷多解，其中一个解为X1=2X2=3max Z = 1617、Max z=3x

12、1+5x2 Max z=3x1+5x2 x1+ x3=4 x1 4标准化并且引入松弛变量 2x2+ x4=12 2x212 3x1+2x2+ x5=183x1+2x218x1，x2，x3，x4，x50 x10 x20Cj35000CbXbbX1X2X3X4X50X3410100/0X4120【2】01060X518320019j350000X34101005X260101/200X56300-11j000-5/20非基变量j0，得到最优解，其中x1=0，x2=6，x3=4.x4=0，x5=6最优解Max Z=3*0+5*6=30其中，有非基变量1=0，所以有无穷多个解18、解：化为标

13、准形式：MaxZ=-5X1-2X2-4X33X1+X2+2X3-X4=46X1+3X2+5X3-X5=10X1,x2,x3,x4,x5>=0增加人工变量x6,x7,得到：MaxZ=-5X1-2X2-4X3-MX6-MX73X1+X2+2X3-X4+X6=46X1+3X2+5X3-X5+X7=10X1,x2,x3,x4,x5>=0大M法求解过程如下：cj-5-2-400-M-MiCBXBbX1X2X3X4X5X6X7-M-MX6X7410361325-100-110014/35/3cj-zj-5+9M-2+4M-4+7M-M-M00-5-MX1X74/32101/312/31-1/3

14、20-11/3-201-1cj-zj0-1/3+M-2/3+M-5/3+2M-M5/3-3M0-50X1X45/31101/21/25/61/201-1/6-1/20-11/61/210/32cj-zj01/21/60-5/6-M5/6-M-5-2X1X22/3210011/31-121/3-11-2-1/31cj-zj00-1/3-1-1/31-M1/3-M最优解为X1*=2/3,X2*=2,X3*=0最优目标函数值minZ=22/319、解：化为标准形式：maxZ=-540x1-450x2-720x33x1+5x2+9x3-x4=709x1+5x2+3x3-x5=30X1,x2,x3,x4

15、,x5>=0增加人工变量x6,x7,得到：maxZ=-540x1-450x2-720x3-Mx6-Mx73x1+5x2+9x3-x4+x6=709x1+5x2+3x3-x5+x7=30X1,x2,x3,x4,x5>=0大M法求解过程如下：cj-540-450-72000-M-MiCBXBbX1X2X3X4X5X6X7-M-MX6X770303(9)5593-100-1100170/330/9cj-zj12M-54010M-45012M-720-M-M00-M-540X6X16010/30110/35/9(8)1/3-101/3-1/910-1/31/92.510cj-zj0-150

16、+10M/38M-540MM/3-600-M/3+60-720-540X3X115/25/6015/12(5/12)10-1/81/241/24-1/81/8-1/24-1/241/8182cj-zj01250135/2-475/12135/2-M75/2-M-720-450X3X220/32-112/501101/61/101/6-3/101/6-1/10-1/63/10-5700-360-180-4500-720075-7515-15-7575-M-1515-M最优解为X*=(0,2,20/3,0,0)最优目标函数值minZ=570020解：先将其化成标准形式，有 max z = 3+ +

17、0+0 + =4 （a） -2+- -=1 （b） 3+ =9 （c） ，0 这种状况可以添加两列单位向量，P7 ，连同约束条件中的向量P4构成单位矩阵 P4 P6 P7 1 0 0 0 1 0 0 0 1P6，P7是人为添加上去的，它相当于在上述问题的约束条件（b）中添加变量，约束条件（c）中添加变量，这两个变量相应称为人工变量。由于约束条件（b）（c）在添加人工变量前已是等式，为使这些等式得到满足，因此在最优解中人工变量取值必需为零。为此，令目标函数中人工变量的系数为任意大的负数，用“-M”代表。添加人工变量后数学模型变为 max z = 3+ +0+0MM+ =4 -2+- -+ =1

18、3+ +=9 ，0 得到初始可行解，并列出初始单纯形表。在单纯形法迭代运算中，M可当作一个数学符号一起参与运算。检验数中含M符号的，当M的系数为正时，该检验数为正；当M的系数为负时，该检验数为负。求解过程见下表 cj -3 0 1 0 0 -M -MCB 基 b X1 X2 X3 X4 X5 X6 X70 4M 1M 91 1 1 1 0 0 0-2 1 -1 0 -1 1 00 3 1 0 0 0 1cjzj-2M-3 4M 1 0 -M 0 00 30 1M 6 3 0 2 1 1 -1 0-2 1 -1 0 -1 1 06 0 4 0 3 -3 1cjzj6M-3 0 4M+1 0 3M

19、 -4M 00 00 33 10 0 0 1 -1/2 -1/2 -1/20 1 1/3 0 0 0 1/3 1 0 2/3 0 1/2 -1/2 1/6cjzj0 0 3 0 3/2 -M-3/2 -M+1/20 00 5/21 3/20 0 0 1 -1/2 1/2 -1/2-1/2 1 0 0 -1/4 1/4 1/43/2 0 1 0 3/4 -3/4 1/4cjzj-9/2 0 0 0 -3/4 -M+3/4 -M-1/4最优解为（0，5/2，3/2）21、解：将原问题转化为标准型 Maxz=3x1+2x2 2x1+x2+x3=2 s.t. 3x1+4x2-x4=12 Xi0，i=1

20、,2,3,4然后添加人工变量x5，将原线性规划问题变为 Maxz=3x1+2x2-Mx5 2x1+x2+x3=2s.t. 3x1+4x2-x4+x5=12 Xi0，i=1,2,3,4,5取基变量为x3,x5,建立单纯形表，迭代过程如下：Cj3200-Mi Cb Xb BX1X2X3X4X50X32211002-MX512340-113Cj-zj3+3M2+4M0-M0Cj3200-Mi Cb Xb BX1X2X3X4X50X2221100-MX54-50-4-11Cj-zj3-5M0-4M-M0在单纯形表中，非基变量的检验值都是小于0，而人工变量仍不为0，则该线性规划无最优解。22、解：假设甲

21、、乙俩种产品产量分别为x1、x2，产品售后的最大利润为z，则依据题意可建立以下线性规划模型：Max=70x1+120x2 9x1+4x2360s.t. 4x1+6x2200 3x1+10x2300 Xi0，i=1,223 .24.27. 设生产四种产品分别为X1,X2,X3X4,则应满足的目标函数为max=2X1+3X2+X3+X4 满足的约束条件为 0.5X1+3X2+X3+0.5X41800 2X1+X2+X3+ X42800 0.5X1+0.5X2+X3+X41800 3X1+X2+2X3+3X41800 X1 1000 X2600 X3500 X440028. 设X1=A出售的数量，X

22、2=A在其次车间加工后的出售数量， X3=B的出售数量，X4=B在第三车间加工后的出售数量， X5=第一车间所用的原料数量 目标函数为maxZ=8X1+9.5X2+7X3+8X42.75X5 满足的约束条件为 X5100000 3X2+2X4+1.5X5 200000 X1+X23X5=0 X3+ X4 2X5=0 X1,X2,X3,X40 29,解: 现在我们对本问题定义三种不同形式的决策变量，从而从不同的途径来构建模型.（1）设工厂第季度生产产品吨首先，考虑约束条件：第一季度末工厂需交货20吨，故应有x1>=20；第一季度末交货后积余（x1-20）吨；其次季度末工厂需交货20吨，故应

23、有x1-20+x2>=20；类似地，应有；第四季度末供货后工厂不能积压产品，故应有；又考虑到工厂每个季度的生产力量，故应有. 其次，考虑目标函数：第一季度工厂的生产费用为15.0，其次季度工厂生产的费用包括生产费用14及积压产品的存贮费；类似地，第三季度费用为，第四季度费用为. 工厂一年的费用即为这四个季度费用之和. 整理后，得下列线性规划模型： min s.t. ，.（2）设第季度工厂生产的产品为吨，第季度初存贮的产品为吨（明显，）.由于每季度初的存贮量为上季度存贮量、生产量之和与上季度的需求量之差，又考虑到第四季度末存贮量为零，故有：， ， ；同时，每季度的生产量不能超过生产力量：；

24、而工厂四个季度的总费用由每季的生产费用与存贮费用组成，于是得线性规划：min s.t. ， 2，3，4.（3） 设第季度生产而用于第季度末交货的产品数量为吨.依据合同要求，必需有： ， ， ， .又每季度生产而用于当季和以后各季交货的产品数不行能超过该季工厂的生产力量，故应有： ， ， ， .第季度生产的用于第季度交货的每吨产品的费用，于是，有线性规划模型：min z = s.t. 1，4；1，4，.30,解 设为#型飞机被派遣去#工厂执行任务的架数.甲方的目标是期望大事“至少摧毁一个工厂”的概率最大. 这相当于期望大事“不摧毁任何工厂”的概率最小. 我们有：它不是线性的，为此将上式改写为 于

25、是，模型的目标函数为 关于燃料的约束条件为： 经过整理，即为 .飞机数量约束： ，综上所述，本问题的线性规划模型为： max z = s.t. ， 1，2；1，2，3.其次章 线性规划1. 对偶问题和对偶变量的经济意义是什么？从经济学的角度来说,对偶变量反映的是对应的原变量的边际效应,即每增加一单位的原变量使目标函数变化的值,当原变量在目标函数取得最优解时没有用完的状况下,原变量的增加不会转变目标函数的值,此时原变量的边际效应为0,即对偶变量为0,这就是强对偶理论。2. 简述对偶单纯形法的计算步骤。它与单纯形法的异同之处是什么？计算步骤见书P-42  单纯形法 对

26、偶单纯形法 原理保证原问题是可行解的状况下向对偶问题可行的方向迭代保证对偶问题是可行解的状况下向原问题可行的方向迭代最优解推断看非基变量的检验数是否都小于等于零看对偶单纯形表的B-1b是否都大于等于零  迭代原则最大最小比值原则最大：检验数最大的那个非基变量为换入变量；最小：B-1b/aik最小的那个对应的基变量为换出变量最小最小比值原则最小：B-1b列数字最小（负数）的那个对应的基变量为换出变量；最小：(cj-zi)/alj最小的那个对应的非基变量为换入变量3. 什么是资源的影子价格？他和相应的市场价格之间有什么区分？对偶变量yi的意义代表在资源最优利用条件下对

27、第i种资源的估价，这是依据资源在生产作用中做出的贡献而得到的估价，称为影子价格。市场价格是指实际发生的市场交易价格，它是计量财务支出和收入的直接依据；机会成本或支付意愿就是经济分析中的影子价格。4. 如何依据原问题和对偶问题之间的对应关系，找出两个问题变量之间、解及检验数之间的关系？（1）对偶(min型)变量的最优解等于原问题松弛变量检验数的确定值（2）对偶问题最优解的剩余变量解值等于原问题对应变量的检验数的确定值（3）由于原问题和对偶问题是相互对偶的，因此对偶问题的检验数与原问题的解也有类似上述关系。（4）更一般地讲，不管原问题是否标准，在最优解的单纯型表中，都有原问题虚变量(松弛或剩余)&

28、#160;的检验数对应其对偶问题实变量 (对偶变量)的最优解，原问题实变量(决策变量) 的检验数对应其对偶问题虚变量 (松弛或剩余变量)的最优解。5. (1) min w=30y1+80y2 (2) max w=30y1+80y2+50y3 y1+4y22 y1-y2+4y32 3y1+2y22 3y1+5y2+2y38 3y1+4y2-4 -3y1+4y2-4y3=-4 y1,y20 y10,y2无限制，y30 6. 解：max z=-4x=-2x2-6x3 -2x1-4x2-8x3+x4=-24 s.t. -4x1-x2-4x3+x5=-8 xj0,j=1,2

29、,3,4,5 cj-4-2-600cBxBbx1x2x3x4x50x4-24-2-4-8100x5-8-4-1-401cj-zj-4-2-6-2x261/211/2-1/400x5-2-7/20-7/2-1/41cj-zj-30-5-1/20-4x14/71011/14-2/7-2x240/7010-2/71/7cj-zj00-2-2/7-6/7所以：x*=(4/7,40/7,0,0,0), z*=96/7.7. max z=x1+2x2+3x3+4x4x1+2x2+2x3+3x4+x5=20 2x1+x2+3x3+2x4+x6=20 xj0,j=1,2,3,4,5,6对偶问题：min w=2

30、0y1+20y2y1+2y21 y1+y2-y3=12y1+y22 2y1+y2-y4=22y1+3y23 2y1+3y2-y5=3 3y1+2y24 3y1+2y2-y6=4 y1,y20 yi0,i=1,.,6已知对偶问题最优解为：y1*=6/5,y2*=1/5.代入，得：y3=3/5,y4=3/5,y5=0,y6=0 Y*XS=(y1,y2)(x5,x6)T=0 X*YS=(x1,x2,x3,x4)T(y3,y4,y5,y6)=0so：x5=x6=0,x1=x2=0代入得,x3=x4=4,So:最优解x*=(0,0,4,4).8. 设甲、乙、丙3种产品数量分别为x1,x2,x3，总利润为

31、z max z=4x1+x2+5x3 x1+2x2+3x345 6x1+3x2+5x3+x4=45 3x1+4x2+5x330 3x1+4x2+5x3+x5=30 x1,x2,x30 xi0,i=1,.,5cj-4-2-600icxibx1x2x3x4x50x4456351090x5303450116cj-zj415005X363/54/5101/5100X4153-101-15cj-zj1-300-14x151-1/301/3-1/35x33011-1/52/5cj-zj0-8/30-1/3-2/3所以最优解为x*=(5,0,3) z*=20+15=35即甲生产5件，乙不生产，丙生产3件。(

32、2) p=c-cBB-1P=(c1,1,5,0,0)-(c1,5) 1 -1/3 0 1/3 -1/3 0 1 1 -1/5 2/5=(c1,1,5,0,0)-(c1,5-c1/3,5,c1/3-1,-c1/3+2)=(0,c1/3-4,0,1-c1/3,c1/3-2) c1/3-40 1-c1/30 so:3c16 c1/3-20So:当年的利润在3，6时，最优解不变(3)设丁为x6,C6=5/2,P6=(3,2)T= P6=B-1P6= 1/3 -1/3 3 1/3 -1/5 2/5 2 1/5C6=C6-CBB-1P6=5/2-(4,5) 1/3 1/5 =1/6>0连续迭代cj4

33、15005/2icxibx1x2x3x4x5X64x151-1/301/3-1/31/3155x33011-1/52/51/515cj-zj0-8/30-1/3-2/31/65/2X615055-1214x101-2-5/3-2/3-10cj-zj0-7/2-5/3-1/3-10So:最优解x*=(0,0,0,15) Z*=37.5即值得支配生产，最优方案为甲、乙、丙不生产，丁生产15件（4） 由（1）知对偶价格为2/3>0.5.所以应购买45/5*5-30=15,应购进15单位的B（5）1500cxBbx1x2x3x4i0X345351090X43045006cj-zj155X293/

34、511/500X4-1510-11cj-zj-20-105X364/5101/50X4-151011cj-zj-300-1SO:X*=(0,0,6) Z*=30即乙不生产，丙生产6件9. 解：（1）设分别为产品甲、乙、丙的产量，其模型为 ；得此问题的最终单纯形表如下：（表 34） 表3410640006200/3015/65/31/6010100/3101/62/31/600100004012200/310620/310/32/30008/310/32/30 可得，； （2）； （3）； （4）； （5）该产品值得支配生产； （6）。10. (1) 由题意已知原线性规划问题目标函数为Max（因j0为最优），且c4、c5为0（松弛变量目标函数系数为0）。依据知：，得：依据，得：则原线性规划问题的数