1、2015年管理運籌學二真題解析一、問答題（70分，共10小題，每小題7分）（答在試卷上的內(nèi)容無效）1.應用單純型法求解線性規(guī)劃問題時，出現(xiàn)不可行解的特征是什么？答：當b的值出現(xiàn)負數(shù)時即表明出現(xiàn)不可行解。2.簡述建立對偶模型的規(guī)則。答：規(guī)則如下：（1）在原問題（P）中，目標函數(shù)為求，其約束條件統(tǒng)一成“”或“=”。（2）在對偶問題（D）中，目標函數(shù)為求。（3）在原問題（P）中與bi相應的一個約束條件，對應著對偶問題（D）的一個變量ui：如果該約束條件為不等式，則ui0；若該約束條件為等式，則ui為自由變量。（4）在原問題（P）的每個變量xj對應對偶問題（D）的每一個約束條件：若（P）中xj0，則（

2、D）中為；若xj為自由變量，則。3.針對增加約束條件方程時，應如何應用對偶單純型法進行求解？答：其步驟如下：（1）檢驗原來的最優(yōu)解是否滿足新增的約束條件，若滿足原最優(yōu)解就是新的最優(yōu)解，否則轉(zhuǎn)第二步；（2）將新增的約束條件方程加上松弛變量或減去多余變量使其化為等式，再把這個等式方程的系數(shù)補加到原模型的最有單純型表中；（3）令原來的基變量和新增的松弛或多余變量作為新的基變量；（4）對新的單純型表進行初等變換，使新基的系數(shù)矩陣變?yōu)閱挝痪仃嚕藭r可以得到一個滿足最優(yōu)檢驗但不一定滿足非負約束條件的可行解；（5）利用對偶單純型法進行迭代求解。4.對bi的靈敏度分析的目的是什么？答：其目的是在cj和aj不變

3、的前提下并在保證不改變原來最優(yōu)解基變量但基變量取值可以變動的情況下，求出bi值允許變化的范圍。并且是在求出最優(yōu)解以后不必將參數(shù)從頭算起，就知道最優(yōu)解及其目標函數(shù)值會發(fā)生什么變化，使決策者只花很少的費用就可以得到比一組最優(yōu)解更多的信息。5.簡述表上作業(yè)法的主要求解步驟。答：步驟如下：（1）利用差值法或最小值法求出一組初始可行解：（2）用閉回路法或位勢法求檢驗數(shù)，若無負檢驗數(shù)即得最優(yōu)解，若有，則轉(zhuǎn)第（3）步；（3）利用閉回路法進行調(diào)整；（4）重復第（2）步，直到得到最優(yōu)解。6.分支定界法在滿足什么情況下停止分支？答：當發(fā)生下列三種情況之一，就不再分支：（1）該分支子問題無可行解，再分也無可行解；（

4、2）已求得一個不違反任一整數(shù)約束的解，此時再分也不可能得到更優(yōu)的解；（3）此子問題的解不優(yōu)于任一不違反整數(shù)約束的另一子問題的目標函數(shù)值。7.簡述尋找最小生成樹的避圈法的思路。答：思路如下：（1）在連通的無向圖G中，從所有邊中選出一條權最小的邊，并把它納入樹中；（2）在G中剩余的邊中再選擇一條權最小且與選進樹中的邊不構成回路的邊，同樣將其納入樹中；（3）如此反復，直到找不出這樣的邊為止。8.簡述平行作業(yè)法在縮短工期時的思路。答：在工程項目任務十分緊迫、工作面允許以及資源保證供應的條件下，可以組織幾個相同的施工隊，在同一時間、不同的工區(qū)上進行施工，稱為平行施工組織方式。 可以充分利用工作面，爭取時

5、間、縮短施工工期。9.簡述時間參數(shù)法確定關鍵路線的思路。答：思路如下：（1）正確繪制統(tǒng)籌圖并計算出時間參數(shù)即最早時間和最遲時間；（2）計算出總時差，此時總時差為0的工序就是關鍵工序；（3）由關鍵工序組成的一條路線就是關鍵路線。10.針對網(wǎng)絡流f,如何鑒別其為最小費用流？答：構造圖G的伴隨網(wǎng)絡圖Gf，檢查其中是否存在負費用增流圈，若不存在，則是最小費用最大流，否則，就不是。二、計算題（60分，共4小題，每小題15分）（答在試卷上的內(nèi)容無效）1.某運輸網(wǎng)絡G如下圖，各條邊數(shù)字依次為容量、流量、費用。請完成（1）判斷圖G是否為可行流。（3分）（2）判斷圖G是否為流值為10 的最小費用流，若不是，將當

6、前網(wǎng)絡調(diào)整為最小費用流。要求計算出總費用。（6分）（3）求圖G的最小費用最大流。要求計算出總費用。（6分）解析：本題是求最小費用最大流，應當熟知什么是可行流，掌握求最大流和最小費用最大流的算法。解：（1）由于每條邊的流值均滿足容量限制，每個節(jié)點的流量也滿足流量守恒，故此流是可行流。（2）構造伴隨網(wǎng)絡Gf如下：圖中存在負費用增流圈v1 v2 t v1, 所以不是最小費用流。在增流圈上調(diào)整即具有負費用的邊減去調(diào)整值2，費用為正值的邊加上調(diào)整值2得：繼續(xù)構造伴隨網(wǎng)絡圖：此圖已不存在負費用增流圈。則已求得流值為10的最小費流，費用為：8×2+2×4+6×2+8×

7、1+2×4=52（3）用標號算法求最大流：找到增流鏈sv1v2t,調(diào)整量為2，調(diào)整后得：上圖已找不到增流鏈，故得最大流，流值為12.現(xiàn)構造其伴隨網(wǎng)絡圖：圖中已找不到負費用增流圈，故得到最小費用最大流，其費用為：8×2+4×4+4×4+4×2+8×1=64。2、某企業(yè)經(jīng)營管理2個加工廠甲和乙，有3個原材料基地以下列數(shù)量供應原料：原材料基地A：200t，單價200元/t；原材料基地B：300t，單價180元/t；原材料基地C：400t，單價600元/t；單位運價表（元/t）如下： 加工廠原材料基地甲乙A4050B2030C10060兩個加

8、工廠的容量及加工費如下：加工廠甲乙容量450t500t加工費400元/t300元/t請完成（1）試建立該運輸問題的模型。（6分）（2）加工廠出售產(chǎn)品的價格是900元/t，問該企業(yè)如何組織兩個加工廠的生產(chǎn)，使獲得的利潤最大？利潤值是多少？（9分）解析：本題考查的時不平衡運輸問題及表上作業(yè)法。需要注意的是，此時的“運費”包括單位運價和加工費，由于供需不平衡，需要虛設一個原材料基地D，其供應量為50t；至于求檢驗數(shù)的方法有閉回路和位勢法，一般情況下閉回路法較為簡單，不易出錯而位勢法需要求多個變量的值容易算錯。解：（1）需要虛設一個原材料基地D，其供應量為50t，得供需平衡表如下： 加工廠原料甲乙銷量

9、A640750200B600510300C660520400D0050產(chǎn)量450500用差值法求解（括號中即為運量）： 加工廠原料甲乙銷量A（200）200B（200）（100）300C（400）400D（50）50產(chǎn)量450500用閉回路法非基變量檢驗數(shù)(括號中數(shù)字)如下: 加工廠原料甲乙銷量A200(200)200B200100300C(50)400400D50(90)50產(chǎn)量450500所有檢驗數(shù)都大于0,已得最優(yōu)解為(X11,X21,X22,X32,X41)=(200,200,100,400,50)最大利潤900×900-200×640-200×600-1

10、00×510-400×520=303000元.3.下圖所示的運輸網(wǎng)絡，邊旁數(shù)字表示的最大通行能力。假設該運輸網(wǎng)絡中某些節(jié)點有流量需求，此處已知v6需要5個流量。請構造分配最大流的新網(wǎng)絡圖，并分配最大流。解析：本題是有節(jié)點流量限制的最大流分配問題，一般處理方法是將節(jié)點分成兩個節(jié)點中間相連接的邊的權即為該節(jié)點所需流量；解：將節(jié)點6拆分為v61和v62，新網(wǎng)絡圖如下：初始可行流為0，用標號算法求最大流：增流鏈v1v2v5v7,調(diào)整量2：繼續(xù)尋找增流鏈：增流鏈為v1v3v61v62v7,調(diào)整量4：繼續(xù)尋找增流鏈：增流鏈為v1v4v5v7，調(diào)整量為4：繼續(xù)尋找增流鏈：增流鏈為v1v3

11、v4v61v62v7，調(diào)整量為1：此時標號已無法進行，得到最大流，流值為11.4.下圖為統(tǒng)籌網(wǎng)絡圖，邊旁數(shù)字表示工序名稱和工序時間（天）。問題如下：（1）利用時間參數(shù)法計算總工期并確定關鍵路線及關鍵工序。（6分）（2）通過改進措施，使工序c的工序時間減少1天，是否對工程總工期有影響？為什么？（3）因為意外原因，使工序b的工序時間延長了2天，是否對工程總工期有影響？為什么？（3分）（4）因為意外原因，使工序b的工序時間延長了2天，工序d的工序時間延長了3天，是否對工程總工期有影響？為什么？（3分）解析：本題是繪制統(tǒng)籌圖相關的問題。解決本題的步驟是：先繪制完統(tǒng)籌圖，再計算時間參數(shù)，再確定關鍵路線。

12、解：（1）統(tǒng)籌圖如下：粗實線表示的即為關鍵路線為1，2，4，5；關鍵工序為ace。（2）c減少一天，總工期減少一天。因為c是關鍵工序，并且減少一天并未改變關鍵路線和關鍵工序。（3）b延長兩天對總工期無影響，因為b還未成為關鍵工序。（4）b的工序時間延長了2天，工序d的工序時間延長了3天，總工期會增加一天，因為此時的關鍵路線為1，3,4,5.關鍵工序為bde，總工期為13天。三、綜合題（20分，共2小題，每小題10分）（答在試卷上的內(nèi)容無效）1.已知某種產(chǎn)品有n個銷售點，有m個配送中心可供選擇以實現(xiàn)對該產(chǎn)品的配送。設在配送中心i對該產(chǎn)品的年配送能力上限為Ci，并因配送該產(chǎn)品而會增加年費用為Fi。

13、各個銷售點對該產(chǎn)品必須得到滿足，設在銷售點j對該產(chǎn)品的需求量為Dj。從配送中心i到銷售點j的單位產(chǎn)品運費為wij。要求建立整數(shù)規(guī)劃模型，使得運輸成本和配送成本總和最小。解析：此題是整數(shù)規(guī)劃問題中關于選址的問題，是0-1規(guī)劃問題，是書上（寇偉華版）原題的小改編。解：設有兩組決策變量，表示從配送中心i到銷售點j的產(chǎn)品數(shù)量，表示是否由配送點i進行配送，若是則，否則，則目標函數(shù)為：配送中心配送能力的約束條件為：不配送銷售點i時，上式左端必為0；配送銷售點i時，從配送中心到各銷售點的產(chǎn)品數(shù)量應小于等于該配送中心的配送能力。因此，為保證每個銷售點的需求都得到滿足，有約束條件方程：所以整個模型為：2.已知某產(chǎn)品有三個產(chǎn)地x1，x2，x3，三個銷地y1，y2，y3，供應量、需求量及運價如下表所示。 銷地產(chǎn)地y1y2y3供應量x156410x27936x3636