運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用課后習(xí)題答案

1、x243210123x1習(xí)題一P46 (a)運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用 習(xí)題解答該問題有無窮多最優(yōu)解，即滿足 4x+ 6x= 6且0 £ x£ 1 的所有 (x , x)，此時(shí)目標(biāo)函數(shù)值z = 3 。(b)122212x232014x1用圖解法找不到滿足所有約束條件的公共范圍，所以該問題無可行解。(a)(1) 圖解法x243210123x1ì3x+ 4x= 9æ3 ö35最優(yōu)解即為í12的解 x = ç1,÷ ，最大值 z =î5x + 2x= 8è2 ø212(2) 單純形法首先在各約束條件上

2、添加松弛變量，將問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式max z = 10x1+ 5x2+ 0x3+ 0x4ì3x + 4x+ x= 9s.t.í123î5x + 2x+ x= 8124則 P , P 組成一個基。令 x = x= 034()12c®j10500c基Bbx1x2x3x4c- z10500jj得基可行解 x = 0,0,9,8 ，由此列出初始單純形表o> s0x3934100x485201。q = minæ 8 , 9 ö = 8 ç÷c®j10500c基Bbx1x2x3x40x3x1215850

3、3;14 ùêú1ë 5 û- 351012501512è 53 ø5c- zjj010- 2o> 0 ， q = minæ 21 , 8 ö = 3ç÷2新的單純形表為è 142 ø2c®j10500c基Bbx1x2x3x45x210x132101514- 310-171427c- zjj00- 514- 2514o ,s12< 0 ，表明已找到問題最優(yōu)解x1= 1,x2= 3 ,x23= 0 , x4= 0 。最大值 z * = 352(b

4、)(1) 圖解法x2129630369x1ì6x+ 2x= 24æ 73 ö17最優(yōu)解即為í12的解 x = ç,÷ ，最大值 z =îx + x= 512è 22 ø2(2) 單純形法首先在各約束條件上添加松弛變量，將問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式max z = 2x1ì5x+ x+ 0x23+ x= 15+ 0x4+ 0x5s.t.ï6x + 2+23íxx= 24ï124îx + x+ x= 5125則 P ， P ， P345組成一個基。令 x = x= 01

5、2得基可行解 x = (0,0,15,24,5 )，由此列出初始單純形表c®j21000c基Bbx1x2x3x4x500x3x4150510024620100x5511001c- z21000jjo> s。q = min æ -, 24 , 5 ö = 4çø12è61 ÷c®j21000c基Bbx1x2x3x4x505100x031511301602x440x510é 2êc- zjj0ë 3 û13ùú0- 1610-1302è

6、8;o> 0 ，q = min æ 15 , 24, 3 ö = 32ç 5÷2新的單純形表為001100010000c®j21000c B基bx1x2x3x4x5020x3x4x51527232-54141- 15c- zjj-414-2123212715<o ,s120 ，表明已找到問題最優(yōu)解x117= 1 ， x=22， x=， x324= 0 ， x5= 0 。最大354000x1x2x3x4x5x65x2 3128 30x- 4 30051 300- 2 31514 300x6cj- zj值 z* =2x1x2x3x4x5

7、c- zjj3-1200表 1-23x4624- 210x51-13201x1x2x3x4x5x1x5cj表 1-24312-11 2010511 21- zj0- 75- 3 2029 35 304- 2 301-1 304- 5 300111 1500-17 15- 4 505x250 4101015 418 41-10 414x362 41001- 6 415 414 413x89 41100- 2 41-12 4115 41x1x2x3x4x5x61c- zjj000- 45 41- 24 41-11 41最后一個表為所求。習(xí)題二P76(a) 錯誤。原問題存在可行解，對偶問題可能存在可

8、行解，也可能無可行解。(b) 錯誤。線性規(guī)劃的對偶問題無可行解，則原問題可能無可行解，也可能為無界解。(c)錯誤。(d)正確。將該問題化為標(biāo)準(zhǔn)形式：max z = 2x - x12+ x+ 0x34+ 0x5x1x2x3x4x5x65x2 3101 328 30040x3x6cj- zj14 15-4 1501- 2 151 5089 1541 1500- 2 15- 4 5ìx + x+ x+ x= 6ï 1234s.t. í - x + 2x+ x= 4ï1( 25)îx ³ 0 i = 1,5i用單純形表求解c®j2-

9、1100c B00基bx1x2x3x4x5x11114x5640-12001cj- zj2-1100q = 62x6111100x51003111c基Bbx1x2x3x4x51c- zjj0- 3-1- 20由于s< 0 ，所以已找到最優(yōu)解 X * = (6,0,0,0,10)，目標(biāo)函數(shù)值 z* = 12j(a) 令目標(biāo)函數(shù)maxz =（2 + l）x +（-1+l ）x +（1+l ）x112233(1) 令l2= l = 0 ，將l 反映到最終單純形表中13c®j2+l1-1100c基Bbx1x2x3x4x52 + l10x4x6101011311115c- zjj0 -

10、3 - l-1- l - 2 - l01110表中解為最優(yōu)的條件：- 3 - l1£ 0 ， - 1 - l1£ 0 ， - 2 - l1£ 0 ，從而l1³ -1(2)令l= l13= 0 ，將l2反映到最終單純形表中c®j2- 1 + l1002c基Bbx1x2x3x4x520x1x5610101311111cj- zj0 l- 3- 12- 200表中解為最優(yōu)的條件： l2- 3 £ 0 ， 從而l£ 32(3) 令l = lc®j2- 11 + l003c基Bbx1x2x3x4x512= 0 ，將l3反映到

11、最終單純形表中1c- zjj0- 3l3- 1- 202x611110x510031110表中解為最優(yōu)的條件： l- 1 £ 0 ， 從而l£ 133(b) 令線性規(guī)劃問題為max z = 2x - x+ x123ìx + x+ x£ 6 + l4ï 123ls.t.í - x + 2x£ 4 +ïx 1 ³ 0(i 2 1,3)5î=i(1) 先分析的變化ø1æ10öælöæl öDb* = B-1Db = ç11

12、÷ç1 ÷ = ç l1 ÷èøè0 øèèæ 6 + lö使問題最優(yōu)基不變的條件是b*+ Db* = ç1 ÷ ³ 0 ，從而l³ -6ø10 + l11æ6ö(2) 同理有³ 0 ，從而l³ -10èøç10 + l÷22(c) 由于 x*= (6,0,0,0,10) 代入- x1+ 2x3= -6 < 2 ，所以將約束條件減去剩余變量后的方程- xc j ®2-11000c基Bbx1x2x3x4x5x62x10x50x6c- zjj1+ 2x- x36= 2 直接反映到最終單純形表中611110010031110-210-20010-3-1-200c®j2-11000c基Bbx1x2x3x4x5x6對表中系數(shù)矩陣進(jìn)行初等變換，