運籌學基礎及應用第四版胡運權主編課后練習答案

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,此時目標函數(shù)值4 x 1該問題有無窮多最優(yōu)解,即中意6x26且2z3；b x 23 2 0 1 4 x1用圖解法找不到中意全部約束條件的公共范疇,所以該問題無可行解；1.2 a約束方程組的系數(shù)矩陣0 x3基解x 5x6是否基可行解目標函數(shù)值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否最優(yōu)解x4400,；b 約束方程組的系數(shù)矩陣p 1A1 223,411x 1x2基解x4是否基可行解目標函數(shù)值212基x3p2否114002p 1p3x20,20110是43555p 1p4否11100365p2p3是12002p2p4否010252p 3p4是0110T最優(yōu)解,0；551.3 a 1 圖解法2 / 24 x

3、24 3 2 1 最優(yōu)解即為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,說明已找到問題最優(yōu)解1,22b 1 圖解法6x 12x 224x212 x 1x 259 6 3 最優(yōu)解即為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,說明已找到問題最優(yōu)解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其約束系數(shù)矩陣為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其約束系數(shù)矩陣為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 法在上述線性規(guī)劃問題中分別減去剩余變量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 是一個任意大的正數(shù)；據(jù)此可列出單純形表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,所以該線性規(guī)劃問題有無界解解 2：兩階段法；現(xiàn) 在 上 述 線 性 規(guī) 劃 問 題 的 約 束 條 件 中 分 別 減 去 剩 余 變 量x 4,x6,x 8,再 加 上 人 工 變 量x 5,x7,x 9,得第一階段的數(shù)學模型8 / 24 據(jù)此可列出單純形表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第一階段求得的最優(yōu)解X*3 7 7 , ,4 4 2,0,0,0,0,0,0T,目標函數(shù)的最優(yōu)值*0 ；因人工變量x5x 7x90,所以X*3 7 7 , ,4 4 2,0,0,0,0,0,0T是原線性規(guī)劃問題的基可行解； 于是可以進行其次階段運算；將第一階段的最終表中的人工變量取消,并填入原問題的目標函數(shù)的系數(shù),進行其次階段的運算,見下表；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,所以原線性規(guī)劃問題有無界解；b解 1：大 M 法在上述線性規(guī)劃問題中分別減去剩余變量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 是一個任意大的正數(shù)；據(jù)此可列出單純形表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由單純形表運算結果可以看出,最優(yōu)解X*4 9 ,5 5,0,0,0,0,0T,目標函數(shù)的最優(yōu)解值* z24397；X

16、存在非基變量檢驗數(shù)30 ,故該線性規(guī)劃問題有無窮多最優(yōu)解；55解 2：兩階段法；10 / 24 現(xiàn)在上述線性規(guī)劃問題的約束條件中分別減去剩余變量x4,x5,再加上人工變量x6,x 7,得第一階段的數(shù)學模型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據(jù)此可列出單純形表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第一階段求得的最優(yōu)解X*4 9 ,5 5,0,0,0,0,0T,目標函數(shù)的最優(yōu)值*0 ；因人工變量x6x70,所以4 9 ,5 5,0,0,0,0,0T是原線性規(guī)劃問題的基可行解；于是可以進行其次階段運算；將第一階段的最終表中的人工變量取消,并填入原問題的目標函數(shù)的系數(shù),進行其次階段的運算,見下表；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由單純形表運算結果可以看出,最優(yōu)解X*,0,0,0,0,0T,目標函數(shù)的最優(yōu)解值* z24397；由于存在非基變量檢驗數(shù)0 ,故該線性規(guī)劃問題有無窮多最優(yōu)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錯誤；線性規(guī)劃的對偶問題無可行解,就原問題可

21、能無可行解,也可能為無界解；c錯誤；d正確；2.6 對偶單純形法a minzx 14x 112x218x33x 33s .x 12x 22x35,x 2,x30解：先將問題改寫為求目標函數(shù)極大化,并化為標準形式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最優(yōu)解為x,1,3 2, 目標值z39；b minz5x 1x22x24x33x 12x 34s .6x 13 x25x 310 x 1,x 2,x30解：先將問題改寫為求目標函數(shù)極大化,并化為標準形式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最優(yōu)解為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,所以已找到最優(yōu)解X*6 , 0 , ,0,0 10,目標函數(shù)值*z12a 令目標函數(shù)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表中解為最優(yōu)的條件：-3-10,-1-10,2令130,將2反映到最終單純形表中212100cB基bx1x2x3x4x52jx161 1 1 1 00 x51003111czj02-3-120cj表中解為最優(yōu)的條件：2-30, 從而233 令120,將3反映到最終單純形表中211300cB基bx1x2x3x4x52jx161 1 1 1 00 x51003111czj0-33-120表中解為

25、最優(yōu)的條件：3-10, 從而3116 / 24 b 令線性規(guī)劃問題為maxz2x 1x 2x3354s . t.x 1x 2x 36x 12x24x i0i,11先分析的變化bB1b101110,從而161101使問題最優(yōu)基不變的條件是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 對表中系數(shù)矩陣進行初等變換,得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因此增加約束條件后,新的最優(yōu)解為x 110,x 38,x 522,最優(yōu)值為28 33332.12 a 線性規(guī)劃

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最優(yōu)解為x1,x2,x35 , 0 , 3,目標值z27；a 設產(chǎn)品 A 的利潤為 3,線性規(guī)劃問題變?yōu)閙axz3x1x24x36x 13x25x 345s .3x 14x25x 330 x 1,x2,x 30單純形法

28、求解基bx 1x22x311x4x 53都小于等于0,解得39；x44 563510 x 53 034501cjzj31400 x41 5310113x634101555cjzj3110045551x511011333x 330111255cjzj02303355為保持最優(yōu)方案不變,應使3,1 3,3155355b 線性規(guī)劃問題變?yōu)閙axzx 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此時最優(yōu)解為x1,x2,x3,00 , 5,目標值z20,小于原最優(yōu)值,因此該種產(chǎn)品生產(chǎn) ；c 設購買材料數(shù)量為yy ,就規(guī)劃問題變?yōu)閙axz3x1x24x 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此時最優(yōu)解為 x 1 , x 2 , x 3 , y ,0 ,0 ,9 15,目標值 z 30,大于原最優(yōu)值,因此 應當購進原材料擴大生產(chǎn) ,以購材料 15 單位為

31、宜；運籌學基礎及應用第四版胡運權主編課后練習答案（35 章）第三章3.1 表 3.36 產(chǎn)地B1 B2 B3 B4 產(chǎn)量銷地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 用位勢法檢驗,把上表中有數(shù)字的地方換成運價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 得檢驗數(shù)表B B1 B2 B3 B4 A A1 02 0 1 A2 1 A3 2 2 0 A4 3 表中全部的數(shù)字均大于等于零,故所求方案為最優(yōu)方案3.3 解：（a）用運價代替表 3.39 中有數(shù)字的地方,求出位勢和檢驗數(shù)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