運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第四版胡運(yùn)權(quán)主編課后練習(xí)答案

1、運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用習(xí)題解答習(xí)題一 P4644x1 2x241，此時(shí)目標(biāo)函數(shù)值該問題有無窮多最優(yōu)解，即滿足4x1 6x2 6且0 x2 一的所有x1 ,x22(b)X2 +用圖解法找不到滿足所有約束條件的公共范圍，所以該問題無可行解。(a)約束方程組的系數(shù)矩陣12 3A 8130基解是否基可行解目標(biāo)函數(shù)值最優(yōu)解x2 115A7,0X1X2X3X4X5X6P1P2P3016石7-6000否P1P2P40100700是10P1P2P50300720是3P1P2P674400021T否P1P3P40052800否P1P3 P50032080是3P1P3P61012003否P1P4P5000350是0P1

2、P4P6540020154否最優(yōu)解 x 0,10,0,7,0,0 T 。(b)約束方程組的系數(shù)矩陣12 3 4A2 2 12基基解是否基可行解目標(biāo)函數(shù)值X1X2X3X4P1P2411200否P1P325011虧0是435P1P41300116否P2P301220是5P2P401202否P3P40011是5T(1)圖解法最優(yōu)解即為3x1 4x2 9的解x 1,-，最大值z(mì) 35 5xi 2x2822(2)單純形法首先在各約束條件上添加松弛變量，將問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式max z 10x1 5x2 0x3 0x4丄3x1 4x2 x3 9st.5x1 2x2 x48則P3，P4組成一個(gè)基。令為X2 0

3、得基可行解x 0,0,9,8，由此列出初始單純形表Cj10500cb基bX1X2X3X40x3934100x485201CjZj105008 98min ,-5 35Cj10500Cb基bX1X2X3X4211430X301555 82110X110555CjZj010221 8320, min ,-14 22新的單純形表為Cj10500cB基bX1X2X3X43535X2012141410X11101277525CjZj0014143*351, 20,表明已找到問題最優(yōu)解X11, X22，X30, X40。最大值 z (b)(1)圖解法2X22412909X,x25172最優(yōu)解即為6x1 2

4、x224的解x 7,-，最大值z(mì)Xi X252 2(2)單純形法首先在各約束條件上添加松弛變量，將問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式max z 2x1 x2 0x3 0x4 Oxs5x2 X315st.6x1 2x2 x4 24Xi X2 xs 5則R，F(xiàn)4，F(xiàn)5組成一個(gè)基。令xi X20得基可行解x 0,0,15,24,5，由此列出初始單純形表Cj21000CB基bX1X2X3X4X50X315051000X4242010110010X55CjZj2100024 512。 min ,46 1Cj21000CB基bX1X2X3X4X5051000X315111002X443602010X51361Cj11Zj

5、03030min15 245，24，Cj21000Cb基bX1X2X3X4X5150015150X32427100112X42420301013X5242CjZj11000421,20，表明已找到問題最優(yōu)解x11，X272，X3值* z仃2新的單純形表為152X40,X50。最大在約束條件中添加松弛變量或剩余變量，且令X2X2X2 X20, X2X3X3, z z該問題轉(zhuǎn)化為max z3x1 x2 x2 2x3 0x4 0x52xi 3x2 3x2 4x3 x4 12II II4x1 x2 x2 2x3 x5 8I11I3x1 x2 x2 3x3 61n1X1,X2, X2, X3,X4, X

6、50其約束系數(shù)矩陣為233 41 0A 411 20 131130 02334100 0411 2 011 03113 000 1令maxz13x1 x2IIX212x3 0x4 0x5 Mx6 Mx7x30, x30 z z得初始單純形表Cj311200MMcb基bX11X2nX21X3X4X5X6X70X41223341000M X68411-20-110M X76311-30001CjZj37M1 125M0M00(b)在約束條件中添加松弛變量或剩余變量，且令x3x3 x；該問題轉(zhuǎn)化為max z3x1 5x2 x3 x30x4 0x51IIx1 2x2 x3 x3 x461II2x1 x

7、2 3x3 3x3 x516st.X1 X2 5X3 5X3101IIX1,X2,X3 , X3,X4 ,X50其約束系數(shù)矩陣為121110A 213301115500在A中人為地添加兩列單位向量P7 ,P8121110102133010011550001令maxz3x15x21X3IIx3 0x4 0x5 Mx6 Mx7得初始單純形表Cj3-51-100-MMCb基bXiX2X3X3X4X5X6X7Mx66121-1 -10 100x516213-30100Mx710115-50001CjZj32M 53M1+6M -1-6M-M 000在上述線性規(guī)劃問題中分別減去剩余變量x4, x6, x

8、8,再加上人工變量x5, x7 ,x9,得Mx5 0x6 Mx7 0x8 Mx9X1X2X3X4X56S,t,2x1X3X6X722x2X3X8X90max z 2x1 x2 2x3 0x4Xl,X2,X3,X4,X5,X6,X7,X8,X9其中M是一個(gè)任意大的正數(shù)。據(jù)此可列出單純形表Cj2120M0M0MCb 基 bX1X2X3X4X5X6X7X8X9iM x5 61111100006M x7 2201001100M x9 00210000110CjZj2 M3M 12 MM0M0M0M x5 6103/211001/ 21/ 24M x7 220100110021 x2 0011/2000

9、01/ 21/ 25M3M 11 3MCjZj2 M0M0M0222 22 2MX53400113/23/21/21/ 23/42X322010011001X21110001/ 21/ 21/21/ 23M 35M3 M1 1 3MCjZj4M 500M022222Xi3/41001/ 41/ 43/83/81/81/ 82X37/20011/ 21/21/41/ 41/ 41/ 41X27/40101/ 41/41/81/83/83/8CjZj0005/4M -3/83 M亠-M4888由單純形表計(jì)算結(jié)果可以看出，4 0且ai4 0(i1,2,3)，所以該線性規(guī)劃問題有無界解解2：兩階段法。

10、現(xiàn)在上述線性規(guī)劃問題的約束條件中分別減去剩余變量x4,x6, x8,再加上人工變量X5,X7,X9,得第一階段的數(shù)學(xué)模型據(jù)此可列出單純形表Cj000010101Cb 基 bX1X2X3X4X5X6X7X8X9i1 X5611111000061 X722010011001 X900210000110CjZj1311010101 X56103/211001/ 21/ 241 x7 220100110020 x20011/200001/ 21/ 2CjZj105/2101012321X53400113/23/21/21/ 23/40 X322010011000x21110001/ 21/ 21/21

11、/ 2CjZj0000101012x-!3/41001/ 41/ 43/83/81/81/ 82X37/20011/ 21/21/41/ 41/ 41/ 41 x27/40101/ 41/41/81/83/83/8CjZj0000101013 7 7第一階段求得的最優(yōu)解X ( , , ,0,0,0,0,0,0) T,目標(biāo)函數(shù)的最優(yōu)值0。4 4 2*3 7 7t因人工變量x5x7x90,所以X (-,-,- ,0,0,0,0,0,0) T是原線性規(guī)劃問題的基可4 4 2行解。于是可以進(jìn)行第二階段運(yùn)算。將第一階段的最終表中的人工變量取消，并填入原問題的目標(biāo)函數(shù)的系數(shù)，進(jìn)行第二階段的運(yùn)算，見下表。C

12、jZj212000 0icb基b%X2X3X4X6X82 %3/41001/43/81/82X37/20011/21/ 41/41 x27/40101/41/83/8CjZj0005/43/89/8由表中計(jì)算結(jié)果可以看出，4 0且ai4 0(i1,2,3)，所以原線性規(guī)劃問題有無界解。(b) 解1:大M法在上述線性規(guī)劃問題中分別減去剩余變量x4, x6, x8,再加上人工變量x5, x7, x9,得min z 2x1 3x2 x3 0x4 0x5 Mx6 Mx7S,t,x1 4x2 2x3 x4X6 83% 2x2 x5 x76Xi,X2,X3,X4,X5,X6,X7,X8,X90其中M是一個(gè)

13、任意大的正數(shù)。據(jù)此可列出單純形表Cj2120M0M0MCb基 bXiX2X3X4X5X6X7iMx6 81210102Mx7 632001013CjZj2 4M3 6M1 2MMM003 x221/411/21/401/408M x725/2011/211/214/555 n”13 1M3M 3CjZj-M0MM04 2242243 x29/5013/53/101 /103/101/102 x14/5102/51/52/51/52/5CjZj0001/21/2M 1/2M 1/24 9由單純形表計(jì)算結(jié)果可以看出，最優(yōu)解X (4,衛(wèi),0,0,0,0,0) T，目標(biāo)函數(shù)的最優(yōu)解值5 5*49z 2

14、 - 3 7oX存在非基變量檢驗(yàn)數(shù)3 0 ,故該線性規(guī)劃問題有無窮多最優(yōu)解。55解2:兩階段法?，F(xiàn)在上述線性規(guī)劃問題的約束條件中分別減去剩余變量x4, x5,再加上人工變量X6, X7,得第一階段的數(shù)學(xué)模型 minX6 X7Xi4x2 2x3X4X68s,t.3為 2x2 x5 x76Xi,X2,X3,X4,X5,X6,X7,X8,X9據(jù)此可列出單純形表Cj0000011Cb 基 bXiX2X3X4X5X6X7i1 X 812101021X7632001013CjZj46211000 x221/411 /21/401/4081 x725/2011/211/214/5CjZj5/2011/213

15、/ 200 X29/5013/53/101/103/101 /100 x,4/5102/51/52/51/52/5CjZj0000011*4 My*第一階段求得的最優(yōu)解X (4,9,0,0,0,0,0) T,目標(biāo)函數(shù)的最優(yōu)值0。5 54 9t因人工變量x6x7 0,所以(一，,0,0,0,0,0) T是原線性規(guī)劃問題的基可行解。于是可5 5以進(jìn)行第二階段運(yùn)算。將第一階段的最終表中的人工變量取消，并填入原問題的目標(biāo)函數(shù)的系數(shù)，進(jìn)行第二階段的運(yùn)算，見下表。CjZj23100iCb基bX1X2X3X4X53 X29/5013/53/101/102 x14/5102/51/52/5CjZj0001/2

16、1/24 9由單純形表計(jì)算結(jié)果可以看出，最優(yōu)解X (4,-,0,0,0,0,0) T，目標(biāo)函數(shù)的最優(yōu)解值5 5z* 2 4 3 9 7。由于存在非基變量檢驗(yàn)數(shù)3 0,故該線性規(guī)劃問題有無窮多最優(yōu)55解。表 1-23XiX2X3X4X5X4624-210X5113201CjZj31200表 1-24X1X2X3X4X5x131211,20X510511/21CjZj075320354000X1X2X3X4X5X65X28/32/3101；3000X514/3430523100X629353042301CjZj13045300X1X2X3X4X5X65X28/32/31013004x3 14/15

17、415012/151500x689/154115002/15451Cj Zj11/150017門54 50X1X2X3X4X5X65x25041010154184110414x3 62410016415414/413x189/41100241124115 41CjZj000454124411f41最后一個(gè)表為所求。習(xí)題二P76寫出對(duì)偶問題minZ 2X-!2X24X3max w 2y13y2 5y3X13x24X32y12y2 y32st.2x1 x2 3x3 y43對(duì)偶問題為：st.3y1y2 4y32X14X23x354y13y2 3y34X1,X20,x3無約束y1 0, y2 0, y

18、3無約束(b)maxz 5x16x23x3minw 5%3y2 8y3X12X22X35y1y2 4y35st.X15x2X3 3對(duì)偶問題為：s.t.2y15y2 7y364X17X23x3 82y1y2 3y33X1無約束,X2 0, X3 0y1無約束，目2 0,y3 0(a) 錯(cuò)誤。原問題存在可行解，對(duì)偶問題可能存在可行解，也可能無可行解。(b) 錯(cuò)誤。線性規(guī)劃的對(duì)偶問題無可行解，則原問題可能無可行解，也可能為無界解。(c) 錯(cuò)誤。(d) 正確。對(duì)偶單純形法min z 4x112x2 18x3x13x3 3st.2x2 2x3 5Xi, X2 , X30解：先將問題改寫為求目標(biāo)函數(shù)極大化

19、，并化為標(biāo)準(zhǔn)形式maxz4X112X218X30X40X5Xi3X3X43st.2x22X3X55Xi 0i 1,5列單純形表，用對(duì)偶單純形法求解，步驟如下Cj4121800cB基 bX1X2X3X4X50x43103100X5502201CjZj41218000x43103105112 x2011022CjZj406061118X3101033311112x2102332CjZj20026T3最優(yōu)解為X 0,1,-，目標(biāo)值z(mì) 39。2(b)min z 5xi 2X2 4X33x1 x2 2x34st.6x1 3x2 5x3 10Xi, X2 , X30解：先將問題改寫為求目標(biāo)函數(shù)極大化，并化

20、為標(biāo)準(zhǔn)形式max z5x1 2x2 4x3 0x4 0x53x1x2 2x3 x44st. 6x1 3x2 5x3x510Xi 0i 1,5列單純形表，用對(duì)偶單純形法求解Cj52400CB基bX1X2X3X4X50X44312100x1063501CjZj5240002x41011133321021501X233322CjZj103034X32301312X2031052CjZj10020最優(yōu)解為x 0,0,2 T，目標(biāo)值z(mì) 8。將該問題化為標(biāo)準(zhǔn)形式:maxz2x1X2X30X4 0X5X1X2X3X46st.X12X2X54xi 0 i 1,5用單純形表求解Cj21100CB基 bX1X2X

21、3X4X50X46111100X5412001CjZj211006Cb基bX1X2X3X4X52Xi6111100X51003111CjZj03-120由于j 0，所以已找到最優(yōu)解*X6i,0,C),0,1(令目標(biāo)函數(shù)maxz (21)X1(-1 +2) X2(1+3)X3(1)令230,將1反映到最終單純形表中Cj2 11100CB基bX1X2X3X4X521X4611110X51003111CjZj0 -3-1 -1- 12-10表中解為最優(yōu)的條件：-3-10，-1-1令130，將2反文映到:最終單纟純形表中Cj21 2100CB基bX1X2X3X4X52X1611110X51003111

22、CjZj0 2-3-1200，目標(biāo)函數(shù)值z(mì)12從而i 13 -1使問題最優(yōu)基不變的條件是100，從而16(c)(2)同理有0，從而10 210由于x(6,0,0,0,10)代入 x12x32，所以將約束條件減去剩余變量后的方(3)令12 0，將3反映到最終單純形表中Cj211300Cb基bX1X2X3X4X52X16111 100X510031 11CjZj0-33-120表中解為最優(yōu)的條件:-30 ,從而2表中解為最優(yōu)的條件:0,從而31(b)令線性規(guī)劃問題為max z 2x1 x2 x3為 x2 x36st.x1 2x24X 0 i 1,(1)先分析的變化程 X1 2x3 X62直接反映到

23、最終單純形表中Cj2-11000Cb基bX1X2X3X4X5X61111002x-i60311100x5 100X6 -21 0 -2 0 0 1CjZj0 -3 -1-20 0對(duì)表中系數(shù)矩陣進(jìn)行初等變換，得Cj2-11000CB基bX1X2X3X4X5X62X1611110 00X5100311100X6-80-1-3-1 01CjZj0-3-1-200Cj2-1 1000Cb基bX1X2X3X4X5X62X11%1%0% 0%0X52%0%0呂1%0X6%0131% 0130851CjZj00333因此增加約束條件后，新的最優(yōu)解為1082228X1，X3X5最優(yōu)值為3333線性規(guī)劃問題ma

24、x z 3x1 x2 4x36x1 3x2 5x345st. 3x1 4x2 5x330Xi, X2, X30單純形法求解Cb基bX1X2X3X4X50&45635100X53034501cjZj314000X415310114x3634101555cjZj31100455535111Xi103334X330111255cjZj1302055最優(yōu)解為X1，X2 ,X35,0,3，目標(biāo)值z(mì)27。(a)設(shè)產(chǎn)品A的利潤(rùn)為3 ，線性規(guī)劃問題變?yōu)閙axz3x1x24x36X13x2 5x345st.3X14X2 5X330X1, X2, X30單純形法求解基 bX1X2X3X4X5x44563510x5

25、3034501CjZj3140012都小于等于0解得IX41531011x36341015553114CjZj00555111Xi510333X33011125513CjZj02 -035 35 3為保持最優(yōu)計(jì)劃不變，應(yīng)使(b)線性規(guī)劃問題變?yōu)閙ax z 3xi x2 4x3 3x46x13x25x38x445s.t.3x14x25x32x430X1,X2,X3,X40單純形法求解Cb基bX1X2X3X4X5X0X5456358100X630345201CjZj3143000X4153106114X363412015555Cj31174Zj00555535111X11023334X330114

26、12555Cj113Zj02055505110111X4226664X3521310185151515CjZj1290071710153030此時(shí)最優(yōu)解為Xi，X2，X30,0,5，目標(biāo)值z(mì) 20，小于原最優(yōu)值，因此該種產(chǎn)品不值得生產(chǎn)。(c)設(shè)購(gòu)買材料數(shù)量為 y，則規(guī)劃問題變?yōu)閙ax z 3xi X2 4x30.4y6x1 3x2 5x345st. 3x1 4x2 5x3 y 30Xl,X2,X3,y 0單純形法求解CB基bX1X2X3yX4X50X5456350100X630345101CjZj31420050X4153101114X36341101555531124CjZj00555511113X151033334X33011212555113cjZj0205550y153101114X396310