运筹学基础及应用第四版胡运权主编课后练习答案

1、文档编码 : CB3O4E3Q4X7 HU1A5T1A8P3 ZV7O2Y5U8U10习题一P46 运筹学基础及应用习题解答1.1 a 4x 12x 24x24 3 2 1 0 1 2 4x 13 6x 206x 2x 11的全部x 1,x2,此时目标函数值4 x 1该问题有无穷多最优解,即中意6x26且2z3；b x 23 2 0 1 4 x1用图解法找不到中意全部约束条件的公共范畴,所以该问题无可行解；1.2 a约束方程组的系数矩阵0 x3基解x 5x6是否基可行解目标函数值123630A814020300001基x 2x 1x4p 1p2p3016-7 6000否10 3p 1是p2p4

2、0700100p 1p2p5030070是3 21 / 24 p 1p2p6,010 ,07,7T400021否3 44p 1p3p4005800否2p 1p3p5003080是2p 1p3p6101003否0 2p 1p4p5是003500p 1p4p65002015否最优解x4400,；b 约束方程组的系数矩阵p 1A1 223,411x 1x2基解x4是否基可行解目标函数值212基x3p2否114002p 1p3x20,20110是43555p 1p4否11100365p2p3是12002p2p4否010252p 3p4是0110T最优解,0；551.3 a 1 图解法2 / 24 x

3、24 3 2 1 最优解即为3x10 91 x2 ,133 z1x4x2的解,最大值355x12x 28222单纯形法 第一在各约束条件上添加放松变量,将问题转化为标准形式maxz10 x 15x20 x 30 x4s . t.3x 14 x2x 395x 12 x2x48x 1x 20就P 3, P 4组成一个基；令得基可行解x0 , 0 , ,9 8,由此列出初始单纯形表500cj10cB基bx 1x2x3x40 x3934100 x485201cjzj1050012；min8,98 553cj10500cB基bx 1x2x3x40 x32 10141355510 x 1812015553

4、 / 24 cjzj,min210810220,31422新的单纯形表为cj,基1050 x 10 x23,x30,x40；最大值z*35cBbx 1x2x3x45x2301532141410 x 111012cjzj77005251414120,说明已找到问题最优解1,22b 1 图解法6x 12x 224x212 x 1x 259 6 3 最优解即为6x 10 3 6 7,9 ,最大值zx 12x224 5的解x317x 1x 22222 单纯形法 第一在各约束条件上添加放松变量,将问题转化为标准形式maxz2x 1x 20 x 30 x 40 x 5st . . 65x 2x 315x

5、12x 2x 424x 1x 2x 554 / 24 就3P ,P ,5P 组成一个基；令x 1x20得基可行解x0,0,15,24,5,由此列出初始单纯形表cj2 1 0 0 0cB基b1xx23xx4x50 x315 0 5 1 0 0 0 x424 6 2 0 1 0 0 x55 1 1 0 0 1 cjzj2 1 0 0 012；min,24 5 ,6 14cj基b2 1 0 0 0cB1xx23xx4x50 x315 0 5 1 0 0 x41 1 30 10 2 4 60 x51 0 2 30 11 6cjzjmin0 1 30 10330,15,24,32522新的单纯形表为cj

6、基b152 1 0 0 05cB1xx23xx4x0 x30 0 1 5154225 / 24 2 ,zx471 0 0 11,17,x 315,x40,x 50；最大2420 x530 1 0 13242cjj0 0 0 1142120,说明已找到问题最优解x 1x222值* z1721.6 a 在 约 束 条 件 中 添 加 松 弛 变 量 或 剩 余 变 量 , 且 令x2 x 2x 2x 20 ,x 20, x 3x3,z z该问题转化为maxz 3x 1 x 2x 22x 30 x40 x 5s .2x13x 23x 24 x 3x4124x 1x 2 x 22 x 3x 583x

7、1 2, x 2 x 2, x 2 x 3 ,x3x 36x 1,x4,x50其约束系数矩阵为2334100 xP 7 ,P 8Mx6Mx7A411201311300在 A 中人为地添加两列单位向量2334100040 x 54112011031130001令maxz 3x 1 x 2x 22 x 3得初始单纯形表cj基b311200MMcBx 1x 2 x 2 x 3x4x5x6x 70Mx41223341000 x68411-20-110Mx 76311-300016 / 24 cjzj37M1125 M0M00 x 30, x 30,zzb 在约束条件中添加放松变量或剩余变量,且令x 3

8、 x 3 x 3该问题转化为maxz23x125x2 x 3x 30 x40 x5x12x x 3x 3x 46st . . x 1x223 x 33 x 3x 516x 1x5x5x1033x1,x 2, x 3,x,x 4,x 503其约束系数矩阵为1211100P 7,P 8x40 x5Mx6Mx7A213301115500在 A 中人为地添加两列单位向量121110121330100 3011550001令maxz3 x 15 x2 x 3x得初始单纯形表cjzj基b3 -5 1 -1 0 0 -M McBx 1x2x3x3x4x5x6x7Mx6 61 2 1 -1 -1 0 1 00

9、 x5 162 1 3 -3 0 1 0 0Mx 7 101 1 5 -5 0 0 0 1cj32M 53M 1+6M -1-6 M -M 0 0 01.7 a解 1：大 M 法在上述线性规划问题中分别减去剩余变量0 xx4,x 6,x8,再加上人工变量x5,x 7,x9,得maxz2x 1x 22x30 x4Mx56Mx70 x 8Mx97 / 24 s t , ,x 1x 2x 3x 4x 5,602x 1x 3x 6x 722x 2x 3x 8x 90 x x 2,x 3,x 4,x x 6,x x 8x 9其中 M 是一个任意大的正数；据此可列出单纯形表cj2120M0M0Mibc基b

10、x 1x 2x34x 4x5x6x7x8x96Mx 56111110000Mx 722010011000Mx 90021000011cjzj2M3 M12MM0M0M04Mx 56103 / 211001/ 21/ 2Mx 7220100110021x 20011/ 200001/ 21/ 25 M30M0M113 Mcjzj2M0M2222223/ 4Mx 53401013/ 23/ 21/ 21/ 22x 322010011001x 21110001/ 2 1/ 21/ 21/ 2cjzj4M500M03 M35M3M21 13M2222x 13 / 41001/ 41/ 43 / 83/

11、 81/ 81/ 82x 37 / 20011/ 21/ 21/ 41/ 41/ 41/ 41x 27 / 40101/ 41/ 41/ 81/ 83/ 83 / 8cjzj0005 / 4M53/ 83M99M4888由单纯形表运算结果可以看出,40 且ia0i1,2,3,所以该线性规划问题有无界解解 2：两阶段法；现 在 上 述 线 性 规 划 问 题 的 约 束 条 件 中 分 别 减 去 剩 余 变 量x 4,x6,x 8,再 加 上 人 工 变 量x 5,x7,x 9,得第一阶段的数学模型8 / 24 据此可列出单纯形表cj000010101ibc基bx 1x 2x3x 4x5x6x

12、7x8x96 04 23/ 41x 561111100001x 722010011001x 90021000011cjzj1311010101x 56103 / 211001/ 21/ 21x 722010011000 x 20011/ 200001/ 21/ 2cjzj105/ 2101013221x 53400113/ 23/ 21/ 21/ 20 x 322010011000 x 21110001/ 2 1/ 21/ 21/ 2cjzj0000101012x 13 / 41001/ 41/ 43 / 83/ 81/ 81/ 82x 37 / 20011/ 21/ 21/ 41/ 41/

13、41/ 41x 27 / 40101/ 41/ 41/ 81/ 83/ 83 / 8cjzj000010101第一阶段求得的最优解X*3 7 7 , ,4 4 2,0,0,0,0,0,0T,目标函数的最优值*0 ；因人工变量x5x 7x90,所以X*3 7 7 , ,4 4 2,0,0,0,0,0,0T是原线性规划问题的基可行解； 于是可以进行其次阶段运算；将第一阶段的最终表中的人工变量取消,并填入原问题的目标函数的系数,进行其次阶段的运算,见下表；bccjzj2x120000i基bx 1x 3x4x6x82x 123 / 41001/ 43/ 81/ 82x 37 / 20011/ 21/

14、41/ 41x 27 / 40101/ 41/ 83 / 89 / 24 cjzj000 且0405 / 43/ 89 / 8由表中运算结果可以看出,4iai1,2,3,所以原线性规划问题有无界解；b解 1：大 M 法在上述线性规划问题中分别减去剩余变量Mx6x4,x 6,x8,再加上人工变量x5,x 7,x9,得minz2x 13x2x 30 x 40 x 5Mx7x 14x 22x 3x 4x 68s t , ,3 x 12x 2x 5x 76x x 1 2,x 3,x 4,x x 5 6,x x 7 8,x 90其中 M 是一个任意大的正数；据此可列出单纯形表cj2120M0M0Mibc

15、基bx 1x 2x3x 4x5x6x72 38 4 / 5Mx 681421010Mx 763200101cjzj24M36M12MMM003x 221/ 411 / 21/ 401/ 40Mx 725 / 2011/ 211 / 21cjzj55M0M131 MM3M3042242243x 29 / 5013 / 53 /101 /103 / 101/ 102x 14 / 5102 / 51/ 52 / 51/ 52 / 5cjzj0001/ 21/ 2M1/ 2M1 / 2由单纯形表运算结果可以看出,最优解X*4 9 ,5 5,0,0,0,0,0T,目标函数的最优解值* z24397；X

16、存在非基变量检验数30 ,故该线性规划问题有无穷多最优解；55解 2：两阶段法；10 / 24 现在上述线性规划问题的约束条件中分别减去剩余变量x4,x5,再加上人工变量x6,x 7,得第一阶段的数学模型minx6x 7x 14x 22x 3x 4x 68s t , ,3 x 12x 2x 5x 76x x 2,x 3,x 4,x x 6,x x 8,x 90据此可列出单纯形表cj0000011ibc基bx 1x 2x 3x4x5x6x 721x 6814210101x 76320010130cjzj46211008x 221/ 411 / 21/ 401/ 401x 725 / 2011 /

17、 211/ 214 / 50cjzj5/ 2011/ 213 / 20 x 29 / 5013/ 53 / 101 / 103 /101 /100 x 14 / 5102 / 51/ 52 / 51/ 52 / 5cjzj0000011第一阶段求得的最优解X*4 9 ,5 5,0,0,0,0,0T,目标函数的最优值*0 ；因人工变量x6x70,所以4 9 ,5 5,0,0,0,0,0T是原线性规划问题的基可行解；于是可以进行其次阶段运算；将第一阶段的最终表中的人工变量取消,并填入原问题的目标函数的系数,进行其次阶段的运算,见下表；bccjzj23100i基bx 1x 2x 3x 4x 511

18、/ 24 3x 29 / 5013/ 54 9 ,5 53 / 101/ 102x 14 / 5102 / 51/ 52 / 5cjzj0001/ 21 / 2由单纯形表运算结果可以看出,最优解X*,0,0,0,0,0T,目标函数的最优解值* z24397；由于存在非基变量检验数0 ,故该线性规划问题有无穷多最优355解；1.8 表 1-23 x4zj6x 1x 2x3x4x524-210 x 5113201cj31200表 1-24 x 1zj3x 1x 2x3x4x5121120 x 51051121cj0753201.10 5jx283354000 x 1x 2x3x4x5x623101

19、3000 x5143430523100 x629353042301czj8313045300 x 1x 2x3x4x5x65x2231013004x 314154150121515012 / 24 0jx689154115000215451czj1115017154505jx25041x 1x 2x3x4x5x6010154184110410016415414414x 36241100241124115413x 18941czj000454124411141最终一个表为所求；习题二 P76 2.1 写出对偶问题a minz2x 12 x24 x33对偶问题为：max w12y 13y25y3s

20、 .2x 13x 24 x32s .yy 12y2y32x 1x 23 x3y43y1y24y32x 14x 23 x354y 13y 23y34x 1,x20 ,x 3无约束0 ,y 2,0y3无约束b max z5x 16x 23 x350对偶问题为：minw5y 13y28 y350 x 12x22x 3y 1y 24y 3s .x 1x15x2x 33s .y 12y 15y27y364x 17 x23 x382y1y23y33无约束,x20,x无约束,y20,y332.2 a错误；原问题存在可行解,对偶问题可能存在可行解,也可能无可行解；b错误；线性规划的对偶问题无可行解,就原问题可

21、能无可行解,也可能为无界解；c错误；d正确；2.6 对偶单纯形法a minzx 14x 112x218x33x 33s .x 12x 22x35,x 2,x30解：先将问题改写为求目标函数极大化,并化为标准形式13 / 24 max z ix 14x 1212x218x 30 x40 x5s .x02x3x3x4x 532x35i,1,5列单纯形表,用对偶单纯形法求解,步骤如下cj基b04T121800cBx 1x 2x3x4x50j10310 x430 x 5502201czj4121800012x4310310 x251011022cjzj40606c18x 311101033x 23 2

22、112110133200zj226j最优解为x,1,3 2, 目标值z39；b minz5x 1x22x24x33x 12x 34s .6x 13 x25x 310 x 1,x 2,x30解：先将问题改写为求目标函数极大化,并化为标准形式max z 35x 12x24x340 x40 x5s .xx 1x 22x3xx546x 13x25x 3100i,1,5i列单纯形表,用对偶单纯形法求解cj5240014 / 24 cB基b0 x 1x 2x38x4x50jx4431210635010 x 510czj5240002x 42 3101 3113x210215 30133cjzj102 30

23、23c4x32301312x2031052zj10020j最优解为x0,2T, 目标值z；2.8 将该问题化为标准形式：maxz2x12x2x30 x40 x 5s .x 1x2x3x46x 1x2x 54xi0i,15用单纯形表求解cj基b21100cBx 1x2x3x4x 50jx 4611110120010 x54czj211006cB基bx 1x2-x3x4x 52j1x6111100 x 51 003111czj0312015 / 24 由于j0,所以已找到最优解X*6 , 0 , ,0,0 10,目标函数值*z12a 令目标函数cjmaxz（21）x 1（ -1+2）x 2（1+

24、）x 32-10,从而111令230 ,将1反映到最终单纯形表中211 1 0 0cB基bx 1x2x 3x 4x52j1x 461 1 1 1 00 x51003111czj0-3-1-1-12-10cj表中解为最优的条件：-3-10,-1-10,2令130,将2反映到最终单纯形表中212100cB基bx1x2x3x4x52jx161 1 1 1 00 x51003111czj02-3-120cj表中解为最优的条件：2-30, 从而233 令120,将3反映到最终单纯形表中211300cB基bx1x2x3x4x52jx161 1 1 1 00 x51003111czj0-33-120表中解为

25、最优的条件：3-10, 从而3116 / 24 b 令线性规划问题为maxz2x 1x 2x3354s . t.x 1x 2x 36x 12x24x i0i,11先分析的变化bB1b101110,从而161101使问题最优基不变的条件是bb61012同理有10620,从而2102,所以将约束条件减去剩余变量后的方c 由于x,6,0,0,0 10代入x 12x36程x 12x 3x62直接反映到最终单纯形表中cj2 -1 1 0 0 0 cB基b1xx23x4x5xx62 1x6 1 1 1 1 0 0 0 5x10 0 3 1 1 1 0 0 6x-2 1 0 -2 0 0 1 cjzj0 -

26、3 -1 -2 0 0 对表中系数矩阵进行初等变换,得cj基b2 -1 1 0 0 0 cB1xx23x4x5xx62 1x6 111 1 0 0 0 5x10 1 1 1 0 0 3 0 6x-8 0 -1 -3 -1 0 1 17 / 24 cjzj0 -3 -1 -2 0 0 cj2 -1 1 0 0 0 cB基b1xx23x4x5xx62 1x1031 230 230 130 5x2230 830 231 130 6x830 131 130 13cjzj0 80 50 1333因此增加约束条件后,新的最优解为x 110,x 38,x 522,最优值为28 33332.12 a 线性规划

27、问题maxzx 13x1x2x24x 345635x 3s .3x 14x2,5x3030 x 1,xx 32单纯形法求解cB基bx 1x2x3x4x 50jx 44 5635100 x53 034501czj314000jx 41 5310114x 3634110555czj31100455531x5110113334x 33011125518 / 24 cjzj0201355最优解为x1,x2,x35 , 0 , 3,目标值z27；a 设产品 A 的利润为 3,线性规划问题变为maxz3x1x24x36x 13x25x 345s .3x 14x25x 330 x 1,x2,x 30单纯形法

28、求解基bx 1x22x311x4x 53都小于等于0,解得39；x44 563510 x 53 034501cjzj31400 x41 5310113x634101555cjzj3110045551x511011333x 330111255cjzj02303355为保持最优方案不变,应使3,1 3,3155355b 线性规划问题变为maxzx 13x 1x24x33x 44563x5x38x42s . t.3x 14x2,5x3x2x430 x 1,x 2x 3,04单纯形法求解cB基bx 1x2x3x4x 5x 60 x 54 56358100 x63 034520119 / 24 cjzj

29、314300不值得0jx 41 53106114x 36342 5011555czj31107 5045553j1x511021 31334x 33014121555czj0201135550jx4511011 6122664x35213101 15851515czj129007 3017101530此时最优解为x1,x2,x3,00 , 5,目标值z20,小于原最优值,因此该种产品生产 ；c 设购买材料数量为yy ,就规划问题变为maxz3x1x24x 30.4y6x13x 25x 345s .3x 14x25x 330 x 1,x2,x 3,y0单纯形法求解cB基bx 1x2x3yx 4x

30、 510jx 56350104 50 x63 03451012czj3140050jx 41 53101114x 363411105555czj3110204555531x511011333320 / 24 4 x 3 30 1 1 2 1 25 5 5c j z j 0 2 0 1 1 35 5 50 y 1 5 3 1 0 1 1 14 3x 9 6 3 11 0 05 5 5c j z j 3 9 0 0 2 25 5 5 5此时最优解为 x 1 , x 2 , x 3 , y ,0 ,0 ,9 15,目标值 z 30,大于原最优值,因此 应当购进原材料扩大生产 ,以购材料 15 单位为

31、宜；运筹学基础及应用第四版胡运权主编课后练习答案（35 章）第三章3.1 表 3.36 产地B1 B2 B3 B4 产量销地A1 9 8 12 13 18 A2 10 10 12 14 24 A3 8 9 11 12 6 A4 10 10 11 12 12 销量6 14 35 5 用 vogel 法求解得B B1 B2 B3 B4 A A1 61424 4 A2 A3 0 A4 11 用位势法检验,把上表中有数字的地方换成运价B B1 B2 B3 B4 Ui A 21 / 24 A1 8 8 12 13 8 A2 8 A3 11 7 A4 1 0 11 12 7 Vj 4 5 令 v1=1 就 u1+v2=8 所以 u3=7 u1+v4=13 v3=4 u2+v3=12 u4=7 u3+v1=8 v5=8 u3+v3=11 u2=8 u4+v3=11 v2=0 u4+v4=12 得检验数表B B1 B2 B3 B4 A A1 02 0 1 A2 1 A3 2 2 0 A4 3 表中全部的数字均大于等于零,故所求方案为最优方案3.3 解：（a）用运价代替表 3.39 中有数字的地方,求出位势和检验数B B1 B2 B3 B4 Ui A A1 1 9 11 12-k A2 12 k 11 A3 2 k-11 -2 k-1 1 Vj 1 令 v1=1 就 u1+v2=1