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

1、運(yùn)籌學(xué)部分課后習(xí)題解答P47 用圖解法求解線性規(guī)劃問(wèn)題min z=2x1 3x24x1 6x2 6a ) 1 2s.t. 4x1 2x2 4x1,x2 0解：由圖 1 可知，該問(wèn)題的可行域?yàn)橥辜?MABC，N且可知線段 BA上的點(diǎn)都為3最優(yōu)解，即該問(wèn)題有無(wú)窮多最優(yōu)解，這時(shí)的最優(yōu)值為 zmin =2 3 3 0 3min 2P47 用圖解法和單純形法求解線性規(guī)劃問(wèn)題 max z=10x1 5x2 3x1 4x2 9a ) 1 2s.t. 5x1 2x2 8x1,x2 0T1,3 T2解：由圖 1 可知，該問(wèn)題的可行域?yàn)橥辜?OABC，O且可知 B 點(diǎn)為最優(yōu)值點(diǎn)，即 3x1 4x2 9 3 ，即最

2、優(yōu)解為 x* 5x1 2x2 8x22這時(shí)的最優(yōu)值為 zmax=10 1 5 23 325單純形法：原問(wèn)題化成標(biāo)準(zhǔn)型為max z=10x1 5x23x1 4x2 x3 9cj10500CBXBbx1x2x3x40x3934100x485201Cj Z j105000x321/5014/51-3/510x18/512/501/5Cj Z j010-25x23/2015/14-3/1410x1110-1/72/7Cj Z j00-5/14-25/14s.t. 5x1 2x2 x4 8x1,x2,x3,x40maxz2x14x2x3 x4x13x2x482x1x26x2x3x46x1x2x39x1,

3、x2,x3,x40所以有 x*1,3210 1 5 32352P78 已知線性規(guī)劃問(wèn)題：求: (1) 寫出其對(duì)偶問(wèn)題；(2)已知原問(wèn)題最優(yōu)解為 X* (2,2,4,0) ，試根據(jù)對(duì)偶理論，直接求出對(duì)偶問(wèn)題的最優(yōu)解。 解：(1)該線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題為：2)minw8y16y26y39y4y12y2y423y1y2y3y44y3y41y1y31y1, y2,y3,y40由原問(wèn)題最優(yōu)解為*X*(2,2,4,0)，根據(jù)互補(bǔ)松弛性得y12y2y423y1 y2y3y44y3y41把 X * (2,2,4,0) 代入原線性規(guī)劃問(wèn)題的約束中得第四個(gè)約束取嚴(yán)格不等號(hào)，即 2 2 489 y40y12y22

4、從而有3y1y2 y34y3 1得 y 4得 y15,y2335,y31,y4 0所以對(duì)偶問(wèn)題的最優(yōu)解為 y* ( 4 , 3 ,1,0)T ，最優(yōu)值為 wmin 1655P79 考慮如下線性規(guī)劃問(wèn)題：min z 60x1 40x2 80x33x1 2x2 x3 24x1 x2 3x3 42x1 2x2 2x3 3x1, x2 , x3 0（1）寫出其對(duì)偶問(wèn)題；（2）用對(duì)偶單純形法求解原問(wèn)題；解：（1）該線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題為：max w 2y1 4y2 3y33y1 4y2 2y3 602y1 y2 2y3 40y1 3y2 2y3 80y1, y2 , y3 0（2）在原問(wèn)題加入三個(gè)松弛

5、變量 x4,x5,x6 把該線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)型max z60x1 40x2 80x33x12x2x3x424x1x23x3x542x12x22x3x63xj0, j1,L ,6cj-60-40-80000CBXBbx1x2x3x4x5x60x4-2-3-2-11000x5-4-4-1-30100x6-3-2-2-2001Cj Z j-60-40-800000x410-5/45/41-1/12080x1111/43/40-1/400x6-10-3/2-1/20-1/21Cj Z j0-25-350-1500x411/6005/311/3-5/680x15/6102/30-1/31/640x2

6、2/3011/301/3-2/3Cj Z j00-80/30-20/3-50/3x* (65,23,0) T,zmax 60 56 40 32 80 0 23306 3 6 3 3P81 某廠生產(chǎn) A、B、C 三種產(chǎn)品，其所需勞動(dòng)力、材料等有關(guān)數(shù)據(jù)見下表。 要求：（ 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 單位，每件可獲利 3 元，問(wèn)該種產(chǎn)品是否值得生產(chǎn) （d） 如果勞 動(dòng)力數(shù)量不增，材料不足時(shí)可從市場(chǎng)購(gòu)買，每單位 元。問(wèn)該廠要不要購(gòu)進(jìn)原材 料擴(kuò)大生產(chǎn)，以購(gòu)多少為

7、宜。消 耗 產(chǎn)品ABC可用量（單位）定額資源勞動(dòng)力63545材料34530產(chǎn)品利潤(rùn)（元 / 件）31 4解：由已知可得，設(shè) xj表示第 j 種產(chǎn)品，從而模型為：max z 3x1 x2 4x36x1 3x2 5x3 45s.t. 3x1 4x2 5x3 30 x1,x2,x3 0a) 用單純形法求解上述模型為：cj31400CBXBbx1x2x3x4x50x445635100x53034501Cj Z j314000x4153-101-14x363/54/5101/5Cj Z j3/5-11/500-4/53x151-1/301/3-1/34x33011-1/52/5Cj Z j0-20-1/

8、5-3/5得到最優(yōu)解為 x* (5,0,3) T ；最優(yōu)值為 zmax 3 5 4 3 27b )設(shè)產(chǎn)品 A 的利潤(rùn)為 3 ，則上述模型中目標(biāo)函數(shù) x1的系數(shù)用 3 替代并求解得：cj31400CBXBbx1x2x3x4x53x151-1/301/3-1/34x33011-1/52/5CZjj-20-1/5-3/5CZjj0-2+ /30-1/5- /3-3/5+ /3要最優(yōu)計(jì)劃不變，要求有如下的不等式方程組成立10 解得： 35353053230從而產(chǎn)品 A的利潤(rùn)變化范圍為： 3 3,3 9 ,即 22 ,445 5 5 5C)設(shè)產(chǎn)品 D用 x6表示，從已知可得16 c6 cB B P6 1

9、/ 5P6 B 1P6122所以產(chǎn)品 D 值得生產(chǎn)。55cj314003CBXBbx1x2x3x4x5x63x151-1/301/3-1/324x33011-1/52/5-4/5Cj Z j0-20-1/5-3/51/53x65/21/2-1/601/6-1/614x352/513/151-1/154/150Cj Z j-1/10-59/300-7/30-17/300把 x6 加入上述模型中求解得：從而得最優(yōu)解 x* (0,0,5,0,0,5 /2)T ；最優(yōu)值為 zmax 4 5 3 27.5 27 2d)P101 已知運(yùn)輸問(wèn)題的產(chǎn)銷量與單位運(yùn)價(jià)如下表所示，用表上作業(yè)法求各題的最 優(yōu)解及最小

10、運(yùn)費(fèi)。表 3-35解：由已知和最小元素法可得初始方案為檢驗(yàn)：由于有兩個(gè)檢驗(yàn)數(shù)小于零，所以需調(diào)整，調(diào)整一：檢驗(yàn)：檢驗(yàn)：由于還有檢驗(yàn)數(shù)小于零，所以需調(diào)整，調(diào)整二：從上表可以看出所有的檢驗(yàn)數(shù)都大于零，即為最優(yōu)方案最小運(yùn)費(fèi)為： zmin 2 5 2 5 7 10 9 15 11 10 18 0 335表 3-36A184127A2694725A3534326銷量10102015B1B2B358產(chǎn)地銷地B4產(chǎn)量3解：因?yàn)?aii14bj 55 ，即產(chǎn)大于銷，所以需添加一個(gè)假想的銷地，銷 j1量為 3，構(gòu)成產(chǎn)銷平衡問(wèn)題，其對(duì)應(yīng)各銷地的單位運(yùn)費(fèi)都為0由上表和最小元素法可得初始方案為檢驗(yàn)：從上表可以看出所有的

11、檢驗(yàn)數(shù)都大于零，即為最優(yōu)方案最小運(yùn)費(fèi)為： zmin 6 9 5 1 3 10 1 7 4 13 3 15 0 3 193解：因?yàn)?ai 80bj 100 ，即銷大于產(chǎn)，所以需添加一個(gè)假想的產(chǎn)地，產(chǎn)i 1 j1量為 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)：由于有兩個(gè)檢驗(yàn)數(shù)小于零，所以需調(diào)整，調(diào)整一：產(chǎn)地銷地B

12、1B2B3B4B5產(chǎn)量A12020A2201030A325530A4501520銷量2525201020檢驗(yàn)：由于還有檢驗(yàn)數(shù)小于零，所以需調(diào)整，調(diào)整二：銷地產(chǎn)地B1B2B3B4B5產(chǎn)量A12020A2201030A3525030A402020銷量2525201020檢驗(yàn)：從上表可以看出所有的檢驗(yàn)數(shù)都大于零，即為最優(yōu)方案最小運(yùn)費(fèi)為： zmin 3 20 5 20 4 10 6 5 3 25 8 0 0 20 0 0 305P127 用割平面法求解整數(shù)規(guī)劃問(wèn)題max z 7x1 9x2x1 3x2 6 a)7x1 x2 35x1,x2 0,且為整數(shù)解：該問(wèn)題的松弛問(wèn)題為：max z 7 x1 9

13、x2x1 3x2 67 x1 x2 35x1, x2 0則單純形法求解該松弛問(wèn)題得最后一單純形表為：cj7900CBXBbx1x2x3x49x27/2017/221/227x19/210-1/223/22Cj Z j00-28/11-15/11割平面 1為： (3 1/2) x2 (07/ 22)x3(0 1/ 22) x41 7 1711x3x4 x2 3 0x3x4 x52 22 3 22 4 2 從而有22 3222cj79000CBXBbx1x2x3x4x59x27/2017/221/2207x19/210-1/223/2200x5-1/200-7/22-1/221Cj Z j00-2

14、8/11-15/1109x23010017x132/71001/7-1/70x311/70011/7-22/7Cj Z j000-1-8割平面 2為： (4 4/7) x1 (0 1/ 7) x4 ( 1 6/7)x54 1 6 1 6 4 x4 x5 x1 x5 4 0 x4 x5 x67 7 4 7 5 1 5 7 4 7 5 6 7cj790003CBXBbx1x2x3x4x5x69x230100107x132/71001/7-1/700x311/70011/7-22/700x6-4/7000-1/7-6/71Cj Z j000-1-809x230100107x141000-110x31

15、0010-410x4400016-7Cj Z j0000-2-7由上表可知該問(wèn)題已經(jīng)達(dá)到整數(shù)解了，所以該整數(shù)解就是原問(wèn)題的最優(yōu)解，即*Tx* 4,3 T ，最優(yōu)值為 zmax 7 4 9 3 55P144 用圖解 分析法求目標(biāo)規(guī)劃模型min Z = P1 d1-+ P2 d2+ P3( 2d3- +1d4- )c )x1 + x 2 + d1- - d1+= 40x1 + x 2 + d2- - d2+= 40+10=50.x1+ d3- - d3+= 24x 2 + d4- - d4+= 30x1 、x2 、d1 、 d1 、d2 、d2 、d3 、d3 、d4 、d4 0解:由下圖可知，滿

16、足目標(biāo)函數(shù)的滿意解為圖中的 A 點(diǎn)P170 求下圖中的最小樹解：避圈法為：得到最小樹為：P171 用標(biāo)號(hào)法求下圖中點(diǎn) v1 到各點(diǎn)的最短路P 173 用Ford-Fulkerson 的標(biāo)號(hào)算法求下圖中所示各容量網(wǎng)絡(luò)中從 vs到vt 的最 大流，并標(biāo)出其最小割集。圖中各弧旁數(shù)字為容量 cij ，括弧中為流量 fij .B)解：對(duì)上有向圖進(jìn)行 2F 標(biāo)號(hào)得到由于所有點(diǎn)都被標(biāo)號(hào)了， 即可以找到增廣鏈， 所以流量還可以調(diào)整， 調(diào)整量為 1， 得由圖可知，標(biāo)號(hào)中斷，所以已經(jīng)是最大流了，最大流量等于最小割的容量，最小 割為與直線 KK相交的弧的集合，即為(vs, v3 ),( vs ,v4 ),( vs ,v5),( v1,vt ),( v2 ,vt ),( v2, v3)所以從 vs到vt 的最大流為： fs*t 1 2 5 3 2 1 14C)解：對(duì)上有向圖進(jìn)行 2F 標(biāo)號(hào)得到由圖可知， 標(biāo)號(hào)中斷，所以已經(jīng)是最大流了， 最大流量等于最小割的容量， 最小割為與直線KK 相交的弧的集合，即為(vs,v1),(vs,v3),(v2,v5) ，所以 從vs到vt 的最大流為：fst 5 3 5 13P193 根據(jù)下表給定的條件，繪制 PERT網(wǎng)絡(luò)圖 表 7