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

2、問題：求: (1) 寫出其對偶問題；（2）已知原問題最優解為，試根據對偶理論，直接求出對偶問題的最優解。解：（1）該線性規劃問題的對偶問題為：（2）由原問題最優解為，根據互補松弛性得：把代入原線性規劃問題的約束中得第四個約束取嚴格不等號，即 從而有 得所以對偶問題的最優解為，最優值為P79 2.7 考慮如下線性規劃問題：（1） 寫出其對偶問題；（2）用對偶單純形法求解原問題；解：（1）該線性規劃問題的對偶問題為：（2）在原問題加入三個松弛變量把該線性規劃問題化為標準型：-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/3 P81 2.12 某廠生產A、B、C三種產品，其所需勞動力、材料等有關數據見下表。要求：（a）確定獲利最大的產品生產計劃；（b）產品A的利潤在什么范圍內變動時，上述最優計劃不變；（c）如果設計一種新產品D，單件勞動力消耗為8單位，材料消耗為2單位，每件可獲利3元，問該種產品是否值得生產？ （d） 如果勞動力數量不增，材料不足時可從

4、市場購買，每單位0.4 元。問該廠要不要購進原材料擴大生產，以購多少為宜。消耗定額產品資源AB C可用量（單位）勞動力材料6 3 53 4 54530產品利潤（元/件）3 1 4解：由已知可得，設表示第種產品，從而模型為：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得到最優解為；最優值為 b）設產品A的利潤為，則上述模型中目標函數的系數用替代并求解得：1400b351-1/301/3-1/343011-

5、1/52/5-20-1/5-3/50-2+/30-1/5-/3-3/5+/3要最優計劃不變，要求有如下的不等式方程組成立解得：從而產品A的利潤變化范圍為：,即C）設產品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從而得最優解；最優值為所以產品D值得生產。d）P101 3.1已知運輸問題的產銷量與單位運價如下表所示，用表上作業法求各題的最優解及最小運費。表3-3

6、5產地銷地B1B2B3B4產量A1A2A31012227142091611201815255銷量5151510解：由已知和最小元素法可得初始方案為產地銷地B1B2B3B4產量A1A2A351501501015255銷量5151510檢驗：由于有兩個檢驗數小于零，所以需調整，調整一： 產地銷地B1B2B3B4產量A1A2A351501510015255銷量5151510 檢驗：由于還有檢驗數小于零，所以需調整，調整二：產地銷地B1B2B3B4產量A1A2A355101510015255銷量5151510檢驗：從上表可以看出所有的檢驗數都大于零，即為最優方案最小運費為：表3-36產地銷地B1B2B

7、3B4產量A1A2A386549314427372526銷量10102015解：因為，即產大于銷，所以需添加一個假想的銷地，銷量為3，構成產銷平衡問題，其對應各銷地的單位運費都為0。產地銷地B1B2B3B4B5產量A1A2A386549314427300072526銷量101020153由上表和最小元素法可得初始方案為產地銷地B1B2B3B4B5產量A1A2A3911071315372526銷量101020153檢驗： 從上表可以看出所有的檢驗數都大于零，即為最優方案最小運費為：表3-37 產地銷地B1B2B3B4B5產量A1A2A38566M3389746578203030銷量2525201

8、020解：因為，即銷大于產，所以需添加一個假想的產地，產量為20，構成產銷平衡問題，其對應各銷地的單位運費都為0。產地銷地B1B2B3B4B5產量A1A2A3A485606M3038907460578020303020銷量2525201020由上表和最小元素法可得初始方案為產地銷地B1B2B3B4B5產量A1A2A3A4520252001015520303020銷量2525201020檢驗： 由于有兩個檢驗數小于零，所以需調整，調整一：產地銷地B1B2B3B4B5產量A1A2A3A4205252001051520303020銷量2525201020 檢驗：由于還有檢驗數小于零，所以需調整，調整

9、二：產地銷地B1B2B3B4B5產量A1A2A3A4205252001002020303020銷量2525201020檢驗：從上表可以看出所有的檢驗數都大于零，即為最優方案最小運費為：P127 4.8 用割平面法求解整數規劃問題。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-1/

10、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由上表可知該問題已經達到整數解了，所以該整數解就是原問題的最優解，即，最優值為P144 5.3 用圖解分析法求目標規劃模型x1 + x2 + d1- - d1+= 40 x1 + x2 + d2- - d2+= 40+10=50x1 + d3- - d3+= 24 x2 + d4- - d4+= 30min

11、 Z = P1 d1-+ P2 d2+ P3（2d3- +1d4-）s.t.x1 、x2 、d1+、d1-、d2+、d2- 、d3+、d3- 、d4+、d4- 0 c） 解:由下圖可知，滿足目標函數的滿意解為圖中的A 點。 P170 6.4 求下圖中的最小樹解：避圈法為：得到最小樹為：P171 6.7 用標號法求下圖中點到各點的最短路。解：如下圖所示：P 173 6.14 用Ford-Fulkerson的標號算法求下圖中所示各容量網絡中從到的最大流，并標出其最小割集。圖中各弧旁數字為容量，括弧中為流量.B) 解：對上有向圖進行2F標號得到由于所有點都被標號了，即可以找到增廣鏈，所以流量還可以調

12、整，調整量為1，得由圖可知，標號中斷，所以已經是最大流了，最大流量等于最小割的容量，最小割為與直線KK相交的弧的集合，即為所以從到的最大流為： C) 解：對上有向圖進行2F標號得到由于所有點都被標號了，即可以找到增廣鏈，所以流量還可以調整，調整量為1，得由圖可知，標號中斷，所以已經是最大流了，最大流量等于最小割的容量，最小割為與直線KK相交的弧的集合，即為，所以從到的最大流為： P193 7.1 根據下表給定的條件，繪制PERT網絡圖。表7-8作業代號 a1 a2 a3 b1 b2 b3 c1 c2 c3緊前作業無 a1 a2 無 b1 b2 a1，b1 a2，b2，c1 a3，b3，c2解：繪制的P