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

1、運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用習(xí)題解答習(xí)題一 P464X| +2m> =4、 、 、 4.Xj + 6a 2 =6該問題有無窮多最優(yōu)解，即滿足4川+6叼=6且0公標(biāo)函數(shù)值Z = 3。(b)o 14、修用圖解法找不到滿足所有約束條件的公共范圍,1.2約束方程組的系數(shù)矩陣'12 3 6 3 0 0A= 8 1 -4 0 2 03 0 0 0 0 -1；2 4 1的所有(X|,X2),此時(shí)目 所以該問題無可行解。7 / 32基基解是否基可行解目標(biāo)函數(shù)值X, x2 X3 x4 x5 x6Pl Pl Pi167000036否Pl Pl0 100700是10Pl Pl P57 0300-02是3P Pl7

2、?!- -400044否P Pi P400 -8002否Pl 3 P500-0802是3Pl 3 61 o -1 0 0 32否Pl P4 PS0 00350是0Pl 46-00-2044否最優(yōu)解 x =(0,10,070,0)' o(b)約束方程組的系數(shù)矩陣莖R X2 X3 X4是否基可行解目標(biāo)函數(shù)值Pl P1-4 U 002否Pl 3011055是43TPl /%-1 00 U36否P2 301202是5Pl P4P3 P40-0220011否是5最優(yōu)解o1.3(a)(1)圖解法最優(yōu)解即為的解,最大值名若 (2)單純形法首先在各約束條件上添加松弛變量，將問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式max z

3、 = 1 Oxj + 52 + 0,丫3 +3xi +4x, +刀3 =95.Z.，5.¥| + 2%2 + 刀4 = 8則尸3,匕組成一個(gè)基。令M=切=。得基可行解x =(009.8),由此列出初始單純形表Cjf10500O 基 8陽入) 勺04934100 勺 85201C廠Zj10500Cjf10500O 基 bx x2 xi x40%擔(dān)35810m一1 51 3。55Cj-Zj010-2% >°，新的單純形表為Cjf10500“ 基 b陽 x2 x3 a45A,-210 Xj10 1 a -A1414io-1277ci -z003紀(jì)1414，表明已找到問題最優(yōu)

4、解XI = 1,勺=,心=。，心=。最大值Z* =(b)(1)圖解法(2)單純形法首先在各約束條件上添加松弛變量，將問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式max z = 2工1+ & + Ox3 + 0x4 + Ox5.5x2 +x3 = 15s.t. 6+ 2x2 +x4 =24+ x2+ x5 =5則B，8，A組成一個(gè)基。令陽=勺=0得基可行解X = (0,0,15,24,5),由此列出初始單純形表21000基 bXx 占 X.X.X.05100馬 150042462010 x5 5011001C廠Zj21000O' 。, oCL21000C8 基 b再 x2 x3 x4 x50v3152v4

5、40x51051001-0-0 36° 1 ° 4 1Cj-Zj1 10T 0 -T 0a2>0 9 0 = min新的單純形表為15 3、 3,24, =-、52) 2CjT21000基 bXx X, X.X.X.150/y72工4-0-2001-4_15-T10 o 149 / 3212010-4321Cj-Zj000-7412巧,6<o,表明已找到問題最優(yōu)解為=1 , x4=0, x5=0o最大值L6(a)在約束條件中添加松弛變量或剩余變量，且令心=勺-月卜2之。公。入 3 =一刀3, Z'=-Z該問題轉(zhuǎn)化為max z' = -3Xj -

6、x2 +x2 - 2x3 + 0x4 + Ox52X +3刀2 - 3.0 +4均 +心 =12 s.t.4x)+ x2 -x2 -2%-j5 =8 3xj - x2 + x2 - 34=6修，工2，八”，必，必，15 NO其約束系數(shù)矩陣為2 3 -3 410A= 4 1 -1 -2 0 -113 -11-3 0 0 ;在A中人為地添加兩列單位向量丹.八2 3 -3 410 0 04 1-1-20-1103 -11-30001/令 max z'= -3X| - x2 +.巧 一 2.巧 +0x4 +0x5 -Mv6 -Mv7得初始單純形表13 / 32-3-11-200 -M - M基

7、 力X x2 x2 x3 x4 x5 x6 x70a-41223-341000-M x6 841-1-20-110一 M Xy 63-11-30001Cj-Zj-3+7M -1 1 -2-5M 0 -M 00(b)在約束 條件中添加松 弛變量或剩余變量，且令 x3 =當(dāng)一“3 Xi 20,匹之。)，=-該問題轉(zhuǎn)化為99max z' = 一3$ - 5x2 + x3 - + 0x4 + Ox5 X + 2x2 + 占 一 X3 - x4 = 6 2x + X)- 3x3 - 3& + xs = 16” ,x + x2+ 5x3 - 5x3 = 10tiff'd"

8、% NO其約束系數(shù)矩陣為U21-1-10、A= 213-30-1J15-500 ,在A中人為地添加兩列單位向量為.小12 1 -1 -1010213-30100J1 5 -5 0001,令 max z' = -3xt - 5x2 + x3 - + 0x4 + 0.r5 - Mx6 - Mx1得初始單純形表Cjf-3-51 -100-M -M0 基 bX3X3X5%8-M x6 6121-1-10100 x516213-30100一 A/ x7 10115-50001C廠 Zj3 + 2M 5 + 3M 1+6M-1-6M -M 0001.7(a)解1 ：大M法在上述線性規(guī)劃問題中分別減

9、去剩余變量分均4，再加上人工變量max z = 2x1- x2 + 2x3 + 0x4 - Mx5 + 0x6 - Mx? + 0x8 - Mx,x1+x2+x3-x4+ xs= 6一 23+ e 4 + 47 =22x2 一 /一4 + "% = 0xpx2,x3,x4,x5,x6,x7,x8,x9 >0其中M是一個(gè)任意大的正數(shù)。據(jù)此可列出單純形表J-2-120-M0-M0-Mo外基b內(nèi)X2與%£%111-1100006-20100-110002-10000-110cj zi2 M3M-1 2 + M-M0-M0-M0103/2-11001/2-1/24-20Hl0

10、0-1100201-1/20000-1/2-1/2Cj-Zj2-M05M 3+ 2 2-M0-M0州 T-21 3M+2 2400-113/2 -3/2 1/2 -1/2-20100-1100-11000-1/2 1/2-1/2 1/23/4Cj-Z/u 八八八 3M+35M3 M l 1-3M4M+50002222100-1/41/43/8-3/81/8-1/8001-1/21/2-1/41/41/4-1/4010-1/41/4-1/81/8-3/83/8cj ZJ53-9 90005/4二一 3/8 488 8由單純形表計(jì)算結(jié)果可以看出，。且如0(i = l,2,3),所以該線性規(guī)劃 問題

11、有無界解解2：兩階段法。現(xiàn)在上述線性規(guī)劃問題的約束條件中分別減去剩余變量%補(bǔ)%再加上人工變量均即與,得第一階段的數(shù)學(xué)模型據(jù)此可列出單純形表勺一0000101014加基bX2與%Xs%Xi人再111-1100006-20100-1100012-10000-110cj zi1-3-1101010103/2-11001/2-1/24-20ID00-110()201-1/20000-1/2-1/2cj zi10-5/210-10"232400-113/2 -3/2 1/2 -1/2-20100-1100-11000-1/2 1/2-1/2 1/23/4Cj-Z/000010101100-1/

12、41/43/8-3/81/8-1/8001-1/21/2-1/41/41/4-1/4010-1/41/4-1/81/8-3/83/8ci ZJ000010101第一階段求得的最優(yōu)解x=(2,Z Z,0,0,0,0,0,o)T,目標(biāo)函數(shù)的最優(yōu)值 4 4 20) =0 Q因人工變量與=占=/ = 0，所以X'(,二,。,0,0,0,。,0尸是原線性規(guī)劃問題 4 4 2的基可行解。于是可以進(jìn)行第二階段運(yùn)算。將第一階段的最終表中的人工 變量取消，并填入原問題的目標(biāo)函數(shù)的系數(shù)，進(jìn)行第二階段的運(yùn)算，見下 表。Cj - Z/2-120000q基不w七%100-1/43/8-1/8001-1/2-1/

13、41/4010-1/4-1/8-3/8cj zi0005/4-3/8-9/8由表中計(jì)算結(jié)果可以看出，6 >0且 <0(7 = 123),所以原線性規(guī)劃問題 有無界解。(b)解1：大M法在上述線性規(guī)劃問題中分別減去剩余變量心均.再加上人工變量叼吃,與,得min z = 2玉 + 3x2 +x3+ 0x4 + Ox5 + Mx® - Mx7x + 4x2 + 2x3 - x4 + x6 = 83x1 + 2x2 - x5 +x7 =68/2，工3，%|，/，4"7，48，/>0其中M是一個(gè)任意大的正數(shù)。據(jù)此可列出單純形表CJ -2-120-M0-M0 -M0q

14、基人*w七毛%xi%142-101023200-1013CJ ZJ2-4M3-6M1-2MMM001/411/2-1/401/4085/20-11/2-1-1/214/55 5 0 -M4 2023 IM4 2M3M 32 -40013/5-3/101/103/10 -1/1010-2/51/5-2/5-1/52/5ci z)0001/21/2M 1/2M 1/2由單純形表計(jì)算結(jié)果可以看出，最優(yōu)解，目標(biāo)函數(shù)的最優(yōu)解值X存在非基變量檢驗(yàn)數(shù) =0,故該線性規(guī)劃問題有無窮多最優(yōu)解。解2：兩階段法。現(xiàn)在上述線性規(guī)劃問題的約束條件中分別減去剩余變量小與，再加上人工變量得第一階段的數(shù)學(xué)模型min/% +升

15、x1 + 4x2 + 2x. - x4 +4=83x + 2x2 - x5 +x7 =6內(nèi)/2，工3，工4，匕，幾，必，/，為2。據(jù)此可列出單純形表ci -0000011qq基力xiV2%七142-101023200-1013c廠Z,-4-6-211001/411/2-1/401/4085/20-11/2-1-1/214/5-5/201-1/213/20013/5-3/101/103/10-1/1010-2/51/5-2/5-1/52/5ci ZJ0000011第一階段求得的最優(yōu)解，目標(biāo)函數(shù)的最優(yōu)值方=0。因人工變量4 =七=0,所以是原線性規(guī)劃問題的基可行解。于是可以進(jìn)行第二階段運(yùn)算。將第一

16、階段的最終表中的人工變量取消，并填入原問題的 目標(biāo)函數(shù)的系數(shù)，進(jìn)行第二階段的運(yùn)算，見下表。cj zi23100o.外基b再X2&%與013/5-3/101/1010-2/51/5-2/5cj zi0001/21/2由單純形表計(jì)算結(jié)果可以看出，最優(yōu)解，目標(biāo)函數(shù)的最優(yōu)解值由于存在非 基變量檢驗(yàn)數(shù)6=0,故該線性規(guī)劃問題有無窮多最優(yōu)解。1.8表 1-23工2心必624-210*1-13201Cj-Zj3-1200表 1-24陽叼心*312-11/20入510511/21C廠Zj0-75- 3/201. 10354000內(nèi)為2心心*5工65x28/32/3101/3000XS14/3-4/30

17、5- 2/3100X629/35/304-2/301ci一q-1/304-5/300內(nèi)為2心心*5X65X28/32/3101/300414/15-4/150I-2/151/50089/1541/1500-2/15-4/51C廠Zj11/1500-17/15-4/50內(nèi)為2心心*5工65 x2 50/4101015/418/41-10/414 x3 62/41001-6/415/414/413 X) 89/41100-2/41-12/4115/41c廠Zj000-45/41-24/41-11/41最后一個(gè)表為所求。習(xí)題二P762. 1寫出對偶問題37 / 32對偶問題為:對偶問題為:(a)mi

18、n z = 2.V| + 2x2 +X| + 3x2 + 4入、> 22xi + X,+ 3as + y4 < 3 s.r.一 .Xj + 4x2 + 3與=5xl9x2 NO/3無約束(b)max z = 5X| +6x2 +3心Xj + 2x2 + 2x3 = 5-Xi +5r> -X3 > 3SL <4x)+ 7x2 + 3x3 < 8勺無約束,必0,%3 KOmax w = 2yi + 3y2 + 5y3yi+2y2+y3 <2口 3y|4-y2+4y3 <24為+3%+3力=4V| 0. y2 «0,為無約束min 卬=5丫+

19、3y2+8.Y3X -丫2+4)?3 =52力+5m+7為26 s.t.2»-%+3丫3 «3力無約束,4 0,乃2 02.2(a)錯(cuò)誤。原問題存在可行解，對偶問題可能存在可行解，也可能無可行解。(b)錯(cuò)誤。線性規(guī)劃的對偶問題無可行解，則原問題可能無可行解，也可 能為無界解。(C)錯(cuò)誤。(d)正確。2.6對偶單純形法(a)解：先將問題改寫為求目標(biāo)函數(shù)極大化，并化為標(biāo)準(zhǔn)形式max z' = -4xj -12x2 -18.x: + 0x4 + Ox5-3X3+/= -3sJ. <- 2x?-2與+”5 = 5x；O(i = L ,5)列單純形表，用對偶單純形法求解

20、，步驟如下Cjf-4- 12-1800cB 基8XjX2%3x4x50 x4 -30 .¥5 5-10-3100-2-201C廠Zj-4- 12-18000 必 一3-10-310T2 as |01102Cj-Zj-40-60-6-18 x3 1-01-1033-12 X,- -2-1101 -1332C廠Zj一2 00-2-6最優(yōu)解為，目標(biāo)值z = 39°(b)解：先將問題改寫為求目標(biāo)函數(shù)極大化，并化為標(biāo)準(zhǔn)形式max z'= -5Xj -2x2 - 4心 + Ox4 +0.v5s.t. 3%| - a*2 _+= -4-6a,| -5與+= -10x；之 O（i

21、= l,5）列單純形表，用對偶單純形法求解Cjf-5-2-400cB 基8AX2x3x4x50x4-40 x5TO-3 -1-210- 6 -3-501c廠Zj-5-2-4000a-4-43t 。 4 1 4、10-2 * y21-0 -i33Cj-Zj22-10-0 一一33-4 g -2301-31-2 x, 0-3105-2c廠Zj100-20最優(yōu)2.8將maxs.t. 4用單:解為 x =（0.0.2）7 ,目標(biāo)值 z = 8。該問題化為標(biāo)準(zhǔn)形式：Z = 2X| -X2 + 4 +0% +0*x + x2 4-x3 + x4 =6-.¥）+ 2x2 +x5 =4xr 2 0（

22、i = I,5）.純形表求解Cjf2-1100cB 基 bXX2工3X4 As0 x4 6111100,q 4-12001C廠Zj2-11008 = 6cB 基 bXj x2 x3 x4 x52.6111100 x5 1003111Cj-Zj0-3-1-20由于?<0,所以已找到最優(yōu)解X* =(600010),目標(biāo)函數(shù)值/=12(a)令目標(biāo)函數(shù)max z =(2 + 4)玉+(-1+人)x2 + (1+2,)巧(1)令4=4=0,將4反映到最終單純形表中Cjf2 + 4 -1100CB 基人x x2 x3 x4 x52 + 4 x4 6111100 x5 1003111cj - z J0

23、-3-4 -1-42-4 0表中解為最優(yōu)的條件：-3-4W0, -1-4W0, -2-440,從而令4 =4=。，將%反映到最終單純形表中2 1 + 4, 100cB 基 bX x2 x3%2 X1 61 1 1100 x5 1003111Cj-Zj0 % -3 -1-20表中解為最優(yōu)的條件：4-3W0,從而兒<3(3)令4 =4=0,將%反映到最終單純形表中Cjf2-11 + 400cB 基 6v.%2 X1 6111100 x5 1003111c廠Zj0-34 -1-20表中解為最優(yōu)的條件：4 -1«。，從而4Kl(b)令線性規(guī)劃問題為maxZ = 2Xj 一 工2 + 工

24、3%)+ x2 + < 6 + A4X1 + K 4 + 4KN0(i = L 3)(1)先分析的變化'4、>使問題最優(yōu)基不變的條件是/+/ =>0,從而4 >-6(2)同理有，從而4 2-10(c)由于/= (6,0,0,0,10)代入-巧+2.=-6< 2,所以將約束條件減去剩余變量后的方程-玉+2匕-凡=2直接反映到最終單純形表中2-110011100 x5 10003111004 - 210-2001Cj-Zj0-3-1-200對表中系數(shù)矩陣進(jìn)行初等變換，得Cjf2-11000Cb基X|x2 x3x4x5bX61111023600 J5 10031

25、1100 入6 -80-1-3-101。Zj0-3-1-200J-2-1100演 x2 x3 x4 x52%0-0 -0333因此增加約束條件后，新的最優(yōu)解為2. 12(a)線性規(guī)劃問題單純形法求解Cb基b陽叼 *X045635100力3034團(tuán)01CJ-Zj314000心15囪-101-14 x3 634.八1-10-555C廠Zj2 -11 o o -i 5 553畫54再31-101-1333011-i55c廠3130 -20- 一二55最優(yōu)解為(勺,叼，h)=(5,0,3),目標(biāo)值z = 27。(a)設(shè)產(chǎn)品A的利潤為3+人 線性規(guī)劃問題變?yōu)閙ax z =(3 + 九+x2 + 4.巧6

26、Xj +3勺 +5.巧45"< 3勺 +44 +513 w 30xx29x3 >0單純形法求解基b陽叼心心心x4 4563510.“3034501cj-z3+21400x4 153-101-1.¥36341-105553 .114一-勺4- A 005551 1 1X 51 () 333x3 3120115521/13 2c ； -z ；J JU乙十U十35 35 3為保持最優(yōu)計(jì)劃不變，應(yīng)使-2 + (, -1-, 一乎?都小于等于0,解得（b）線性規(guī)劃問題變?yōu)?Xj +3x2 +5.巧 +8x4 <453x( + 4x2 + 5x3 + 2x4 <

27、 304/2，心，口 NO單純形法求解基 bXX2X3X4 X5X60x5450x63063581034520 IC廠Zj3143000 x4 154 X3 63 -1061-1112015555Cj-Zj3117455553Aj54x331 -102-13133011-1-1555Cj-Zj0 -2 0 i -i -2 555。4 145111 1U126662 U 1 o -1 A5151515c廠Zj129cA717-一 00"-一10153030此時(shí)最優(yōu)解為。"T2，X3）=（O.O.5）,目標(biāo)值z = 20,小于原最優(yōu)值，因此該種 產(chǎn)品不值得生產(chǎn)。（O設(shè)購買材料數(shù)

28、量為），則規(guī)劃問題變?yōu)閙ax z = 3X| +x2 +44-0.4y 6Xj +3x2 +5.巧 <45 s.t. 3xj + 4.x2 + 5x3 - y < 30 修，工2"3，）'2°單純形法求解cB 基 b內(nèi) x2 Xi y x4 x50x5450x630635010345-101CZj314-0050 x4 154 xj 63 -1011-111 -i0 i5555c廠Zj2 -12 0 2 。 5 5553$54x331-1o111-i333212011-1±555W0 -2 0 i -1 -2 5550y154x3 93-1011-1510555c廠Zj3 9cA22一一一 0 o -5555此時(shí)最優(yōu)解為（凡,叼，“3，力=（。95）,目標(biāo)值z = 30,大于原最優(yōu)值，因此 應(yīng)該購進(jìn)原材料擴(kuò)大生產(chǎn)，以購材料15單位為宜。第三章3.1表3. 36用位勢法檢驗(yàn)，把上表中有數(shù)字的地方換成運(yùn)價(jià)BlB2B3B4UiAl88A2138A3127A481171112Vj1045令 vl=l則 ul+v2=8所以u3二7ul+v4=13v3=4u2+v3=12u4=7u3+vl=8v5=8u3+v3=llu2=8u4+v3=llv2=0u4+v4=12得檢驗(yàn)數(shù)表Bl B2 B3B4表中所有的