運(yùn)籌學(xué)課后習(xí)題解答-0001

1、WORD格式整理版運(yùn)籌學(xué)部分課后習(xí)題解答P47 1.1用圖解法求解線性規(guī)劃問(wèn)題min z=2x 3x24為 6x2 _ 6 st 4x1+2x2 >4Xi,X2 _0解：由圖1可知，該問(wèn)題的可行域?yàn)橥辜?MABC，且可知線段BA上的點(diǎn)都為3最優(yōu)解，即該問(wèn)題有無(wú)窮多最優(yōu)解，這時(shí)的最優(yōu)值為=2 - 3P47 1.3用圖解法和單純形法求解線性規(guī)劃問(wèn)題max z=10x1 5x213為 4x2乞9a )s.t5為+2x2蘭8x1, x 0解：由圖1可知，該問(wèn)題的可行域?yàn)橥辜?OABCO且可知B點(diǎn)為最優(yōu)值點(diǎn),即嚴(yán)+4卷=9斗|人3，即最優(yōu)解為x1,3(5X1 +2X2 =8& =2I 2丿

2、這時(shí)的最優(yōu)值為Zmax = 10 1 5 -2 2原問(wèn)題化成標(biāo)準(zhǔn)型為max z=10x1 5x23 4x2 x3 = 9 s.t <5 +2x2 +x4 =8Xi,X2,X3,X4 -0Cj T10500CbXbbX1X2X3X40X3934100X485201Cj -Zj105000X321/5014/51-3/510X18/512/501/5Cj -Zj010-25X23/2015/14-3/1410X1110-1/72/7Cj -Zj00-5/14-25/14所以有八1丁Zmax=10 15 352 2P78 2.4已知線性規(guī)劃問(wèn)題：max z =2x 4x2 x3 x4+3x2

3、+x4 蘭 82x +x2<6彳x2 +x3 +x4 蘭 6x, + x2 + x3<9xzx, X4 一0求：(1)寫(xiě)出其對(duì)偶問(wèn)題；(2)已知原問(wèn)題最優(yōu)解為X(2,2,410)，試根據(jù)對(duì)偶 理論，直接求出對(duì)偶問(wèn)題的最優(yōu)解。解：（1）該線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題為：min= 8 y1 6 y2 6 y3 9y4d+2y2+y4 蘭23yrHy<HyrHy4彳yy1y2”3,y40(2)由原問(wèn)題最優(yōu)解為X* =(2,2,40)，根據(jù)互補(bǔ)松弛性得：y1 2y2y4 = 23y1 y2 ya y4 Iya + yU把X* =(2,2,4,0)代入原線性規(guī)劃問(wèn)題的約束中得第四個(gè)約束取嚴(yán)格

4、不等號(hào),即 2 2 4 =8 < 9 - y4 =0y1 2y2=2從而有+y2 +ya =4Lya =1得 Y1,Y2,Ya = 1,y4 = 055所以對(duì)偶問(wèn)題的最優(yōu)解為y* =(4,3,1,0)T，最優(yōu)值為Wmin =165 5P79 2.7考慮如下線性規(guī)劃問(wèn)題:min z = 60xi 40x2 80x3” 3xi + 2x2 + X3 蘭 24xi + X2 + 3x > 42xi +2X2 +2x3 蘭3xi,x?,x >0(1)寫(xiě)出其對(duì)偶問(wèn)題；(2)用對(duì)偶單純形法求解原問(wèn)題;解：(1)該線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題為:max w = 2% 4y2 3y33% +4y2

5、 +2y3 W602% +y2 +2y3 玄40y1 3y2 2y3 80y1,y2,y0(2)在原問(wèn)題加入三個(gè)松弛變量X4,X5,X6把該線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)型max z = -60旨-40x2 -80x33x1 2x? X3 + X4= -24x<i x? 3X3 + X5 4-2 x<i 2 X? 2 X3+ = _3Xj "j =1川,6Cj T-60-40-80000CbXbbX1X2X3X4X5X60X4-2-3-2-11000X5-4-4-1-30100X6-3-2-2-2001Cj -Zj-60-40-800000X410-5/45/41-1/12080X

6、1111/43/40-1/400X6-10-3/2-1/20-1/21Cj -Zj0-25-350-1500X411/6005/311/3-5/680X15/6102/30-1/31/640X22/3011/301/3-2/3Cj -Zj00-80/30-20/3-50/3x* =(5,?,0)T,Zmax =60 540 -80 0 二空6 3633P81 2.12某廠生產(chǎn)A、B、C三種產(chǎn)品，其所需勞動(dòng)力、材料等有關(guān)數(shù)據(jù)見(jiàn) 下表。要求：（a）確定獲利最大的產(chǎn)品生產(chǎn)計(jì)劃；（b）產(chǎn)品A的利潤(rùn)在什么范圍 內(nèi)變動(dòng)時(shí)，上述最優(yōu)計(jì)劃不變；（c）如果設(shè)計(jì)一種新產(chǎn)品D,單件勞動(dòng)力消耗為8單位，材料消耗為2單

7、位，每件可獲利3元，問(wèn)該種產(chǎn)品是否值得生產(chǎn)？ （d） 如果勞動(dòng)力數(shù)量不增，材料不足時(shí)可從市場(chǎng)購(gòu)買(mǎi)，每單位 0.4元。問(wèn)該廠要不要購(gòu)進(jìn)原材料擴(kuò)大生產(chǎn)，以購(gòu)多少為宜消產(chǎn)品ABC可用量（單位）勞動(dòng)力 材料6353454530產(chǎn)品利潤(rùn)（元/件）314解：由已知可得，設(shè)Xj表示第j種產(chǎn)品，從而模型為:max z = 3片 x2 4x36x 3x2 5x3 乞 45st *3 +4x2 +5x3 蘭 30.為，X2,X3 藝 0a）用單純形法求解上述模型為:Cj t31400CBXbbX1X2X3X4X50X445635100X53034501Cj -Zj314000X4153-101-14X363/54

8、/5101/55 -Zj3/5-11/500-4/53X151-1/301/3-1/34X33011-1/52/55 £0-20-1/5-3/5得到最優(yōu)解為x* = (5,0,3)T ;最優(yōu)值為zax =3 5 4 3 = 27b ）設(shè)產(chǎn)品A的利潤(rùn)為3，貝U上述模型中目標(biāo)函數(shù)Xi的系數(shù)用3替代并求解得:5 t3+Z1400CBXbbX1X2X3X4X53X151-1/301/3-1/34X33011-1/52/55 -Zjk-20-1/5-3/5(5 -Zj i0-2+ 九 /30-1/5-人/3-3/5+ 九/3要最優(yōu)計(jì)劃不變，要求有如下的不等式方程組成立-203-10解得:53_

9、3一955從而產(chǎn)品A的利潤(rùn)變化范圍為:3卻 91 即 _2r4lC)設(shè)產(chǎn)品D用X6表示，從已知可得；6 = 4 -cbB_P6 =1/5-F6 = B 巳=把X6加入上述11331 255模型中求1 -;2J 一解得：2【45 一Cj T314003CbXbbX1X2X3X4X5X63X151-1/301/3-1/324X33011-1/52/5-4/55 -Zj0-20-1/5-3/51/53X65/21/2-1/601/6-1/614X352/513/151-1/154/1505 N-1/10-59/300-7/30-17/300從而得最優(yōu)解 x(0,0,5,0,0,5 /2)t ;最優(yōu)值

10、為 zma4 5 327.5 272所以產(chǎn)品D值得生產(chǎn)。d)學(xué)習(xí)指導(dǎo)參考P101 3.1已知運(yùn)輸問(wèn)題的產(chǎn)銷量與單位運(yùn)價(jià)如下表所示，用表上作業(yè)法求各題 的最優(yōu)解及最小運(yùn)費(fèi)。表 3-35解：由已知和最小元素法可得初始方案為檢驗(yàn):進(jìn)B1E2 I1391行位勢(shì)AI膽A3冏崗違20 頭丄 |5珂辿覽陶專3)15 出 10 0訶1&13列位勢(shì)-U 1314由于有兩個(gè)檢驗(yàn)數(shù)小于零，所以需調(diào)整，調(diào)整一:檢驗(yàn):BlB2B3B4行位勢(shì)A1A2A3訓(xùn)15 20両場(chǎng)®）1IJ 0 旬話 辺迪）迥迪）訓(xùn)o164列位勢(shì)-21314調(diào)整二:檢驗(yàn):由于還有檢驗(yàn)數(shù)小于零，所以需調(diào)整,B2B3B4行位勢(shì)A1昶5

11、1A2噸釣10勺156A38列位勢(shì)-61310從上表可以看出所有的檢驗(yàn)數(shù)都大于零，即為最優(yōu)方案最小運(yùn)費(fèi)為：zmin -2 5 2 5 7 10 9 15 11 10 18 0 =335解：因?yàn)閍i =58八bj =55，即產(chǎn)大于銷，所以需添加一個(gè)假想的銷地，銷i =1j =1量為3,構(gòu)成產(chǎn)銷平衡問(wèn)題，其對(duì)應(yīng)各銷地的單位運(yùn)費(fèi)都為0。由上表和最小元素法可得初始方案為檢驗(yàn):BlB2B354B5行位勢(shì)A1172J,®©倒1A26g 9|130IT4A35 1 創(chuàng)10%3列位勢(shì)2 000-4從上表可以看出所有的檢驗(yàn)數(shù)都大于零，即為最優(yōu)方案最小運(yùn)費(fèi)為：Zmin =6 9 5 1 3 1

12、0 - 1 7 4 13 3 15 0 3=193表 3-37A18637520A25M84730A36396830銷量252520102035解：因?yàn)閍i =80八口 =100，即銷大于產(chǎn)，所以需添加一個(gè)假想的產(chǎn)地，產(chǎn)i =1j d量為20,構(gòu)成產(chǎn)銷平衡問(wèn)題，其對(duì)應(yīng)各銷地的單位運(yùn)費(fèi)都為0。產(chǎn)地銷地B1B2B3B4B5產(chǎn)量A18637520A25M84730A36396830A40000020銷量2525201020由上表和最小元素法可得初始方案為銷地 產(chǎn)地弋、B1B2B3B4B5產(chǎn)量A12020A25101530A325530A420020銷量2525201020檢驗(yàn):BlB2B3B4B5行

13、位勢(shì)A1A2A3A4逅地355皿倂 也血gCJ20 21(+3)220啊山0力15創(chuàng)迪創(chuàng)50210叢134-2列位勢(shì)2-1214由于有兩個(gè)檢驗(yàn)數(shù)小于零，所以需調(diào)整，調(diào)整一:產(chǎn)地銷地B1B2B3B4B5產(chǎn)量A12020A2201030A325530A4501520銷量2525201020檢驗(yàn):由于還有檢驗(yàn)數(shù)小于零，所以需調(diào)整，調(diào)整二:銷地 產(chǎn)地，B1B2B3B4B5產(chǎn)量A12020A2201030A3525030A402020銷量2525201020檢驗(yàn):31B2B3B4B5行位勢(shì)A1320i-i施4A2創(chuàng)20皿胡虬08A3目5勺了g®1、二 創(chuàng)09A40a倒201列位勢(shì)-3-6-1-

14、4-1從上表可以看出所有的檢驗(yàn)數(shù)都大于零，即為最優(yōu)方案5B2最小運(yùn)費(fèi)為：zmin =3 20 5 20 4 10 6 5 3 25 8 0 0 20 0 0 = 305P127 4.8用割平面法求解整數(shù)規(guī)劃問(wèn)題。max z = 7為 9x2-x1 3x2 < 6a)“7為+x2 蘭35/1,x2 0,且為整數(shù)解：該問(wèn)題的松弛問(wèn)題為：max z = 7 9x2-x 3屜 _ 6 « 7為 + x2 蘭 35 xx2 3 0 則單純形法求解該松弛問(wèn)題得最后一單純形表為:Cj T7900CBXbbX1X2X3X49x7/2017/221/227%9/210-1/223/22Cj _Z

15、j00-28/11-15/11割平面 1 為：(3 1/2) =x2 (0 7 / 22)x3 (0 1/22)x4丄X3 -丄XX2 -3汕匚Z%丄X4f2 22 22 22 22從而有Cj T79000CBXbbX1X2X3X4X59X27/2017/221/2207X19/210-1/223/2200X5-1/200-7/22-1/221Cj -Zj00-28/11-15/1109X23010017X132/71001/7-1/70X311/70011/7-22/7Cj -Zj000-1-8割平面 2 為：(4 4/7)(0 1/7)x4 (-1 6/7)x5Cj T790003CBXb

16、bX1X2X3X4X5X69X230100107X132/71001/7-1/700X311/70011/7-22/700X6-4/7000-1/7-6/715 -Zj000-1-809X230100107X141000-110X310010-410X4400016-75 -Zj0000-2-77 774 - 7-6+X41 一 7由上表可知該問(wèn)題已經(jīng)達(dá)到整數(shù)解了，所以該整數(shù)解就是原問(wèn)題的最優(yōu)解，即*tx =(4,3)，最優(yōu)值為 Zmax =7X4+93=55P144 5.3用圖解分析法求目標(biāo)規(guī)劃模型min Z = Pi di-+ P2 d2+ P3( 2d3- +1d4-)c)X1 + X2

17、 + d1- - d1+= 40- +X1 + X2 + d2 - d2 = 40+10=50s.t. < X1+ d3 - d3 = 24- +X2 + d4 - d4 = 30<.X1、X2、d 1 > d2、d2、d3、d3、d4、d40解：由下圖可知，滿足目標(biāo)函數(shù)的滿意解為圖中的A點(diǎn)。、+ Xt= «P170 6.4求下圖中的最小樹(shù)6解：避圈法為:(1) %二俐巴二3CD衛(wèi)GE 眄二&*巴二GD艮鳳(33 % = 3艮5耳=24衛(wèi)用,咼(4) (A.BtG.CDtE9 F.HQ)珂汛人EQG硏込=匹玖咼 巧二gEGCDS必二此旳 %二他及GGD盡再耳

18、=詩(shī)) 眄=3&GC0艮見(jiàn)團(tuán)也=0得到最小樹(shù)為:P171 6.7用標(biāo)號(hào)法求下圖中點(diǎn)V1到各點(diǎn)的最短路P 173 6.14用Ford-Fulkerson的標(biāo)號(hào)算法求下圖中所示各容量網(wǎng)絡(luò)中從乂到V的最大流，并標(biāo)出其最小割集。圖中各弧旁數(shù)字為容量Cj，括弧中為流量fj.由于所有點(diǎn)都被標(biāo)號(hào)了，即可以找到增廣鏈，所以流量還可以調(diào)整，調(diào)整量為1, 得由圖可知，標(biāo)號(hào)中斷，所以已經(jīng)是最大流了，最大流量等于最小割的容量，最小 割為與直線KK相交的弧的集合，即為XVs,V3),(Vs,V4),(Vs,V5),(V!,Vt),(V2,Vt),(V2,V3)/所以從Vs到Vt的最大流為：fSt =1 2 5 3 2 14C)解：對(duì)上有向圖進(jìn)行 2F標(biāo)號(hào)得到，得由圖可知，標(biāo)號(hào)中斷，所以已經(jīng)是最大流了，最大流量等于最小割的容量， 最小割為與直線KK相交的弧的集合，即為OsN ), Vs v3 )“2 V，5)，所以 從Vs到Vt的最大流為:fs； =5 3 5 =13P193 7.1根據(jù)下表給定的條件，繪制 PERT網(wǎng)絡(luò)圖。 表7-8作業(yè)代號(hào)緊前作業(yè)al a2 a3blb2b3clc2c3al a2blb2 al, bl a2, b2, cla3, b3, c2解：繪制的PERT網(wǎng)絡(luò)圖為:a2c2blb3表 7-9作業(yè)代號(hào)緊前作業(yè)A B C D無(wú)無(wú)無(wú) A,B B B F,C B E,H E