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

1、 運籌學(xué)部分課后習(xí)題解答P47 1.1 用圖解法求解線性規(guī)劃問題 a） 解：由圖1可知，該問題的可行域為凸集MABCN，且可知線段BA上的點都為最優(yōu)解，即該問題有無窮多最優(yōu)解，這時的最優(yōu)值為P47 1.3 用圖解法和單純形法求解線性規(guī)劃問題 a） 解：由圖1可知，該問題的可行域為凸集OABCO，且可知B點為最優(yōu)值點，即，即最優(yōu)解為這時的最優(yōu)值為單純形法：原問題化成標(biāo)準(zhǔn)型為10500b09341008520110500021/5014/51-3/5108/512/501/5010-253/2015/14-3/1410110-1/72/700-5/14-25/14所以有P78 2.4 已知線性規(guī)劃

2、問題：求: (1) 寫出其對偶問題；（2）已知原問題最優(yōu)解為，試根據(jù)對偶理論，直接求出對偶問題的最優(yōu)解。解：（1）該線性規(guī)劃問題的對偶問題為：（2）由原問題最優(yōu)解為，根據(jù)互補松弛性得：把代入原線性規(guī)劃問題的約束中得第四個約束取嚴(yán)格不等號，即 從而有 得所以對偶問題的最優(yōu)解為，最優(yōu)值為P79 2.7 考慮如下線性規(guī)劃問題：（1） 寫出其對偶問題；（2）用對偶單純形法求解原問題；解：（1）該線性規(guī)劃問題的對偶問題為：（2）在原問題加入三個松弛變量把該線性規(guī)劃問題化為標(biāo)準(zhǔn)型：-60-40-80000b0-2-3-2-11000-4-4-1-30100-3-2-2-2001-60-40-8000001

3、0-5/45/41-1/12080111/43/40-1/400-10-3/2-1/20-1/210-25-350-150011/6005/311/3-5/6805/6102/30-1/31/6402/3011/301/3-2/300-80/30-20/3-50/3P81 2.12 某廠生產(chǎn)A、B、C三種產(chǎn)品，其所需勞動力、材料等有關(guān)數(shù)據(jù)見下表。要求：（a）確定獲利最大的產(chǎn)品生產(chǎn)計劃；（b）產(chǎn)品A的利潤在什么圍變動時，上述最優(yōu)計劃不變；（c）如果設(shè)計一種新產(chǎn)品D，單件勞動力消耗為8單位，材料消耗為2單位，每件可獲利3元，問該種產(chǎn)品是否值得生產(chǎn)？ （d） 如果勞動力數(shù)量不增，材料不足時可從市場購

4、買，每單位0.4 元。問該廠要不要購進原材料擴大生產(chǎn)，以購多少為宜。消耗定額產(chǎn)品資源AB C可用量（單位）勞動力材料6 3 53 4 54530產(chǎn)品利潤（元/件）3 1 4解：由已知可得，設(shè)表示第種產(chǎn)品，從而模型為：a) 用單純形法求解上述模型為：31400b0456351003034501314000153-101-1463/54/5101/53/5-11/500-4/5351-1/301/3-1/343011-1/52/50-20-1/5-3/5得到最優(yōu)解為；最優(yōu)值為 b）設(shè)產(chǎn)品A的利潤為，則上述模型中目標(biāo)函數(shù)的系數(shù)用替代并求解得：1400b351-1/301/3-1/343011-1/5

5、2/5-20-1/5-3/50-2+/30-1/5-/3-3/5+/3要最優(yōu)計劃不變，要求有如下的不等式方程組成立解得：從而產(chǎn)品A的利潤變化圍為：,即C）設(shè)產(chǎn)品D用表示，從已知可得把加入上述模型中求解得：314003b351-1/301/3-1/3243011-1/52/5-4/50-20-1/5-3/51/535/21/2-1/601/6-1/61452/513/151-1/154/150-1/10-59/300-7/30-17/300從而得最優(yōu)解；最優(yōu)值為所以產(chǎn)品D值得生產(chǎn)。P101 3.1已知運輸問題的產(chǎn)銷量與單位運價如下表所示，用表上作業(yè)法求各題的最優(yōu)解與最小運費。表3-35產(chǎn)地銷地B

6、1B2B3B4產(chǎn)量A1A2A31012227142091611201815255銷量5151510解：因為，即產(chǎn)銷平衡.所以由已知和最小元素法可得初始方案為產(chǎn)地銷地B1B2B3B4產(chǎn)量A1A2A351501501015255銷量5151510檢驗：由于有兩個檢驗數(shù)小于零，所以需調(diào)整，調(diào)整一：產(chǎn)地銷地B1B2B3B4產(chǎn)量A1A2A351501510015255銷量5151510 檢驗：由于還有檢驗數(shù)小于零，所以需調(diào)整，調(diào)整二：產(chǎn)地銷地B1B2B3B4產(chǎn)量A1A2A355101510015255銷量5151510檢驗：從上表可以看出所有的檢驗數(shù)都大于零，即為最優(yōu)方案最小運費為：表3-36產(chǎn)地銷地B

7、1B2B3B4產(chǎn)量A1A2A386549314427372526銷量10102015解：因為，即產(chǎn)大于銷，所以需添加一個假想的銷地，銷量為3，構(gòu)成產(chǎn)銷平衡問題，其對應(yīng)各銷地的單位運費都為0。產(chǎn)地銷地B1B2B3B4B5產(chǎn)量A1A2A386549314427300072526銷量101020153由上表和最小元素法可得初始方案為產(chǎn)地銷地B1B2B3B4B5產(chǎn)量A1A2A3911071315372526銷量101020153檢驗：從上表可以看出所有的檢驗數(shù)都大于零，即為最優(yōu)方案最小運費為：表3-37 產(chǎn)地銷地B1B2B3B4B5產(chǎn)量A1A2A38566M3389746578203030銷量2525

8、201020解：因為，即銷大于產(chǎn)，所以需添加一個假想的產(chǎn)地，產(chǎn)量為20，構(gòu)成產(chǎn)銷平衡問題，其對應(yīng)各銷地的單位運費都為0。產(chǎn)地銷地B1B2B3B4B5產(chǎn)量A1A2A3A485606M3038907460578020303020銷量2525201020由上表和最小元素法可得初始方案為產(chǎn)地銷地B1B2B3B4B5產(chǎn)量A1A2A3A4520252001015520303020銷量2525201020檢驗：由于有兩個檢驗數(shù)小于零，所以需調(diào)整，調(diào)整一：產(chǎn)地銷地B1B2B3B4B5產(chǎn)量A1A2A3A4205252001051520303020銷量2525201020 檢驗：由于還有檢驗數(shù)小于零，所以需調(diào)整，

9、調(diào)整二：產(chǎn)地銷地B1B2B3B4B5產(chǎn)量A1A2A3A4205252001002020303020銷量2525201020檢驗：從上表可以看出所有的檢驗數(shù)都大于零，即為最優(yōu)方案最小運費為：P127 4.8 用割平面法求解整數(shù)規(guī)劃問題。a） 解：該問題的松弛問題為：則單純形法求解該松弛問題得最后一單純形表為：7900b97/2017/221/2279/210-1/223/2200-28/11-15/11割平面1為：從而有79000b97/2017/221/22079/210-1/223/2200-1/200-7/22-1/22100-28/11-15/1109301001732/71001/7-

10、1/7011/70011/7-22/7000-1-8割平面2為：790003b93010010732/71001/7-1/70011/70011/7-22/700-4/7000-1/7-6/71000-1-8093010010741000-11010010-410400016-70000-2-7由上表可知該問題已經(jīng)達(dá)到整數(shù)解了，所以該整數(shù)解就是原問題的最優(yōu)解，即，最優(yōu)值為P144 5.3 用圖解分析法求目標(biāo)規(guī)劃模型x1 + x2 + d1- - d1+= 40 x1 + x2 + d2- - d2+= 40+10=50x1 + d3- - d3+= 24 x2 + d4- - d4+= 30m

11、in Z = P1 d1-+ P2 d2+ P3（2d3- +1d4-）s.t.x1 、x2 、d1+、d1-、d2+、d2- 、d3+、d3- 、d4+、d4- 0 c） 解:由下圖可知，滿足mind1-的滿意解為區(qū)域X2CDX1； 滿足mind2+的滿意解為閉區(qū)域BCDEB； 滿足min2d3-的滿意解為圖中的A 點,滿足mind4-的滿意解為圖中的A 點，所以該問題的滿意解為圖中的點A（24，26） 。用圖解分析法求目標(biāo)規(guī)劃模型的滿意解。解：由下圖可知，滿足的滿意解為區(qū)域CDOA； 滿足的滿意解為閉區(qū)域MCDOM； 滿足的滿意解為圖中的陰影部分，即為圖中的凸多邊形OABCDO 。P170

12、 6.4 求下圖中的最小樹解：避圈法為：得到最小樹為：P171 6.7 用標(biāo)號法求下圖中點到各點的最短路。解：如下圖所示：P 173 6.14 用Ford-Fulkerson的標(biāo)號算法求下圖中所示各容量網(wǎng)絡(luò)中從到的最大流，并標(biāo)出其最小割集。圖中各弧旁數(shù)字為容量，括弧中為流量.B) 解：對上有向圖進行2F標(biāo)號得到由于所有點都被標(biāo)號了，即可以找到增廣鏈，所以流量還可以調(diào)整，調(diào)整量為1，得由圖可知，標(biāo)號中斷，所以已經(jīng)是最大流了，最大流量等于最小割的容量，最小割為與直線KK相交的弧的集合，即為所以從到的最大流為：C) 解：對上有向圖進行2F標(biāo)號得到由于所有點都被標(biāo)號了，即可以找到增廣鏈，所以流量還可以調(diào)整，調(diào)整量為1，得由圖可知，標(biāo)號中斷，所以已經(jīng)是最大流了，最大流量等于最小割的容量，最小割為與直線KK相交的弧的集合，即為，所以從到的最大流為：P193 7.1 根據(jù)下表給定的條件，繪制PERT網(wǎng)絡(luò)圖。表7-8作業(yè)代號 a1a2a3b1b2b3c1c2c3緊前作業(yè)無 a1a2 無 b1b2a1，b1a2，b2，c1a3，b3，c2解：繪制的PERT網(wǎng)絡(luò)圖為：表7-9作業(yè)代號A B C D E F