運籌學(xué)部分課后習(xí)題解答1

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

2、1 5 -2 2原問題化成標(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/510Xi8/512/501/5Cj -Zj010-25X23/2015/14-3/1410Xi110-1/72/7Cj -Zj00-5/14-25/14z T所以有1,3 ,Zmax=10 1 5I 2 丿22P78 2.4已知線性規(guī)劃問題：max z =2x 4x2 x3 x4/ +3x2+x4 蘭 82咅 +x2

3、6彳x2 +x3 +x4 蘭 6x, + x2 + x39XZX, X4 一0求：(1)寫出其對偶問題；(2)已知原問題最優(yōu)解為X(2,2,410)，試根據(jù)對偶理論，直接求出對偶問題的最優(yōu)解。解：(1)該線性規(guī)劃問題的對偶問題為：min w =8y, 6y2 6y3 9y4i+2y2+y4 蘭23yrHyHyrHy4彳yyiyi, y2,y3,y40(2)由原問題最優(yōu)解為X* =(2,2,4,0)，根據(jù)互補(bǔ)松弛性得：y1 2y2y4 = 23y1 y2 ya y4Iya + yU把X* = (2,2,4,0)代入原線性規(guī)劃問題的約束中得第四個約束取嚴(yán)格不等號，即 2 2 4 =8 42xi +

4、2X2 +2x3 蘭3xi,x?,x 0(1)寫出其對偶問題；(2)用對偶單純形法求解原問題;解：(1)該線性規(guī)劃問題的對偶問題為:max w = 2% 4y2 3y33% +4y2 +2y3 W602% +y2 +2y3 玄40yi 3y2 2y3 80yi,y2,y0(2)在原問題加入三個松弛變量X4,X5,X6把該線性規(guī)劃問題化為標(biāo)準(zhǔn)型max z = -60旨-40x2 -80x33xi 2x? X3 + X4= -24xi x? 3X3 + X5 4-2 Xi 2 X2 2 X3+ = _3Xj j =1川,6Cj T-60-40-80000CbXbbX1X2X3X4X5X60X4-2

5、-3-2-11000X5-4-4-1-30100X6-3-2-2-2001Cj -Zj-60-40-800000X410-5/45/41-1/12080X1111/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,?,O)T,Zmax =60 540 -80 0 二空6 3633P81 2.12某廠生產(chǎn)A、B、C三種產(chǎn)品，其所需勞動力、材料等有關(guān)數(shù)據(jù)見下表。要求：（a）

6、確定獲利最大的產(chǎn)品生產(chǎn)計劃；（b）產(chǎn)品A的利潤在什么范圍內(nèi)變動時，上述最優(yōu)計劃不變；（c）如果設(shè)計一種新產(chǎn)品D,單件勞動力消耗為8單位，材料消耗為2單位，每件可獲利3元，問該種產(chǎn)品是否值得生產(chǎn)？ （d） 如果勞動力數(shù)量不增，材料不足時可從市場購買，每單位 0.4元。問該廠要不要購進(jìn)原材料擴(kuò)大生產(chǎn)，以購多少為宜消產(chǎn)品ABC可用量（單位）勞動力 材料6353454530產(chǎn)品利潤（元/件）314解：由已知可得，設(shè)Xj表示第j種產(chǎn)品，從而模型為:max z = 3片 x2 4x36x 3x2 5x3 乞 45st3為 +4x2 +5x3 蘭 30冷 X2,X3-0a）用單純形法求解上述模型為:Cj t

7、31400CBXbbX1X2X3X4X50X445635100X53034501Cj -Zj314000X4153-101-14X363/54/5101/55 -Zj3/5-11/500-4/53Xi51-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的利潤為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 -Z

8、j i0-2+ 九 /30-1/5-人/3-3/5+ 九/3要最優(yōu)計劃不變，要求有如下的不等式方程組成立-203-10解得:53_3一955從而產(chǎn)品A的利潤變化范圍為:3卻 91 即 _2r4lC)設(shè)產(chǎn)品D用X6表示，從已知可得；6 = 4 -cbB_P6 =1/5-F6 = B 巳=把X6加入上述11331 255模型中求1 -;2J 一解得：2【45 一Cj T314003CbXbbXiX2X3X4XX63Xi51-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/

9、154/1505 N-1/10-59/300-7/30-17/300從而得最優(yōu)解 x(0,0,5,0,0,5 /2)t ;最優(yōu)值為 zma4 5 327.5 272所以產(chǎn)品D值得生產(chǎn)。d)P101 3.1已知運輸問題的產(chǎn)銷量與單位運價如下表所示，用表上作業(yè)法求各題 的最優(yōu)解及最小運費。表 3-35解：由已知和最小元素法可得初始方案為檢驗:進(jìn)B1E2 I1391行位勢AI膽A3冏崗違20 頭丄 |5珂辿覽陶專3)15 出 10 0訶1&13列位勢-U 1314由于有兩個檢驗數(shù)小于零，所以需調(diào)整，調(diào)整一:檢驗:BlB2B3B4行位勢A1A2A3訓(xùn)15 20両場）1IJ 0 旬話 辺迪）迥迪）訓(xùn)o1

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

11、數(shù)都大于零，即為最優(yōu)方案最小運費為：Zmin =6 9 5 1 3 10 - 1 7 4 13 3 15 0 3=193表 3-37A18637520A25M84730A36396830銷量252520102035解：因為ai =80八口 =100，即銷大于產(chǎn)，所以需添加一個假想的產(chǎn)地，產(chǎn)i =1j d量為20,構(gòu)成產(chǎn)銷平衡問題，其對應(yīng)各銷地的單位運費都為0產(chǎn)地銷地B1B2B3B4B5產(chǎn)量A18637520A25M84730A36396830A40000020銷量2525201020由上表和最小元素法可得初始方案為銷地 產(chǎn)地弋、B1B2B3B4B5產(chǎn)量A12020A25101530A32553

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

13、目5勺了g1、二 創(chuàng)09A40a倒201列位勢-3-6-1-4-1從上表可以看出所有的檢驗數(shù)都大于零，即為最優(yōu)方案最小運費為：zmin =3 20 5 20 4 10 6 5 3 25 8 0 0 20 0 0 = 3055B2P127 4.8用割平面法求解整數(shù)規(guī)劃問題。max z = 7為 9x2-x1 3x2 6a)“7為+x2 蘭35x1,x2 0,且為整數(shù)解：該問題的松弛問題為:max z = 7 9x2-x 3屜 _ 6 7為 + x2 蘭 35 xx2 3 0 則單純形法求解該松弛問題得最后一單純形表為:Cj T7900CBXbbX1X2X3X49x7/2017/221/227%9

14、/210-1/223/22Cj _Zj00-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/

15、7)x5Cj T790003CBXbbXiX2X3X4X5X69X230i00i07Xi32/7i00i/7-i/700X3ii/700ii/7-22/700X6-4/7000-i/7-6/7i5 -Zj000-i-809X230i00i07Xi4i000-ii0X3i00i0-4i0X44000i6-75 -Zj0000-2-77 774 - 7-6+X41 一 7由上表可知該問題已經(jīng)達(dá)到整數(shù)解了，所以該整數(shù)解就是原問題的最優(yōu)解，即*tx =(4,3)，最優(yōu)值為 Zmax =7X4+93=55P144 5.3用圖解分析法求目標(biāo)規(guī)劃模型min Z = Pi di-+ P2 d2+ P3( 2d

16、3- +1d4-)c)xi + X2 + di- - di+= 40- +Xi + X2 + d2 - d2 = 40+10=50s.t. 0.xi、X2、di、di、d2、d2、d3、d3解：由下圖可知，滿足目標(biāo)函數(shù)的滿意解為圖中的A點、+ Xt= P170 6.4求下圖中的最小樹6解：避圈法為:(1) %二俐巴二3CD衛(wèi)GE 眄二&*巴二GD艮鳳(33 % = 3艮5耳=24衛(wèi)用,咼(4) (A.BtG.CDtE9 F.HQ)珂汛人EQG硏込=匹玖咼 巧二gEGCDS必二此旳 %二他及GGD盡再耳=詩) 眄=3&GC0艮見團(tuán)也=0得到最小樹為:P171 6.7用標(biāo)號法求下圖中點V1到各點的

17、最短路解：如下圖所示:IoV4V1ioP 173 6.14用Ford-Fulkerson的標(biāo)號算法求下圖中所示各容量網(wǎng)絡(luò)中從乂到V的最大流，并標(biāo)出其最小割集。圖中各弧旁數(shù)字為容量Cj，括弧中為流量fj.由于所有點都被標(biāo)號了，即可以找到增廣鏈，所以流量還可以調(diào)整，調(diào)整量為1, 得由圖可知，標(biā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)解：對上有向圖進(jìn)行 2F標(biāo)號得到，得由圖可知，標(biāo)號中斷，所以已經(jīng)是最大流了，最大流量等于最小割的容量， 最小割為與直線KK相交的弧的集合，即為OsN ), Vs v3 )“2 V，5)，所以 從Vs到Vt的