年961管理運籌學(xué)二解析(西南交通大學(xué))

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

2、 i 為自由變量。（ 4）在原問題（ P）的每個變量 xj 對應(yīng)對偶問題（ D ）的每一個約束條件：若（P）中mmxj0 ，則（ D ）中為aii ui cj ；若 xj 為自由變量，則aii uicj 。i 1i 13.針對增加約束條件方程時，應(yīng)如何應(yīng)用對偶單純型法進行求解？答：其步驟如下：（ 1 ）檢驗原來的最優(yōu)解是否滿足新增的約束條件，若滿足原最優(yōu)解就是新的最優(yōu)解，否則轉(zhuǎn)第二步；（ 2）將新增的約束條件方程加上松弛變量或減去多余變量使其化為等式，再把這個等式方程的系數(shù)補加到原模型的最有單純型表中；（ 3）令原來的基變量和新增的松弛或多余變量作為新的基變量；（ 4）對新的單純型表進行初等變

3、換，使新基的系數(shù)矩陣變?yōu)閱挝痪仃嚕藭r可以得到可編輯精品一個滿足最優(yōu)檢驗但不一定滿足非負約束條件的可行解；（ 5）利用對偶單純型法進行迭代求解。4.對 b i 的靈敏度分析的目的是什么？答：其目的是在cj 和 aj 不變的前提下并在保證不改變原來最優(yōu)解基變量但基變量取值可以變動的情況下，求出bi 值允許變化的范圍。并且是在求出最優(yōu)解以后不必將參數(shù)從頭算起，就知道最優(yōu)解及其目標(biāo)函數(shù)值會發(fā)生什么變化，使決策者只花很少的費用就可以得到比一組最優(yōu)解更多的信息。5.簡述表上作業(yè)法的主要求解步驟。答：步驟如下：（ 1）利用差值法或最小值法求出一組初始可行解：（ 2）用閉回路法或位勢法求檢驗數(shù)，若無負檢驗數(shù)

4、即得最優(yōu)解，若有，則轉(zhuǎn)第（3 ）步；（ 3）利用閉回路法進行調(diào)整；（ 4）重復(fù)第（ 2 ）步，直到得到最優(yōu)解。6.分支定界法在滿足什么情況下停止分支？答：當(dāng)發(fā)生下列三種情況之一，就不再分支：（ 1）該分支子問題無可行解，再分也無可行解；（ 2）已求得一個不違反任一整數(shù)約束的解，此時再分也不可能得到更優(yōu)的解；（ 3）此子問題的解不優(yōu)于任一不違反整數(shù)約束的另一子問題的目標(biāo)函數(shù)值。7.簡述尋找最小生成樹的避圈法的思路。可編輯精品答：思路如下：（ 1）在連通的無向圖G 中，從所有邊中選出一條權(quán)最小的邊，并把它納入樹中；（ 2）在 G 中剩余的邊中再選擇一條權(quán)最小且與選進樹中的邊不構(gòu)成回路的邊，同樣將其

5、納入樹中；（ 3）如此反復(fù)，直到找不出這樣的邊為止。8.簡述平行作業(yè)法在縮短工期時的思路。答：在工程項目任務(wù)十分緊迫、工作面允許以及資源保證供應(yīng)的條件下，可以組織幾個相同的施工隊，在同一時間、不同的工區(qū)上進行施工，稱為平行施工組織方式?？梢猿浞掷霉ぷ髅?，爭取時間、縮短施工工期。9.簡述時間參數(shù)法確定關(guān)鍵路線的思路。答：思路如下：（ 1）正確繪制統(tǒng)籌圖并計算出時間參數(shù)即最早時間和最遲時間；（ 2）計算出總時差，此時總時差為0 的工序就是關(guān)鍵工序；（ 3）由關(guān)鍵工序組成的一條路線就是關(guān)鍵路線。10. 針對網(wǎng)絡(luò)流 f ,如何鑒別其為最小費用流？答：構(gòu)造圖G 的伴隨網(wǎng)絡(luò)圖Gf，檢查其中是否存在負費用

6、增流圈，若不存在，則是最小費用最大流，否則，就不是。二、計算題（ 60 分，共 4 小題，每小題15 分）（答在試卷上的內(nèi)容無效）1.某運輸網(wǎng)絡(luò)G 如下圖，各條邊數(shù)字依次為容量、流量、費用?？删庉嬀穠16,4,48,8,2t10,4,2s8,6,14,2,4v2請完成（ 1 ）判斷圖 G 是否為可行流。 （3 分）（ 2 ）判斷圖 G 是否為流值為 10 的最小費用流，若不是，將當(dāng)前網(wǎng)絡(luò)調(diào)整為最小費用流。要求計算出總費用。 （ 6 分）（3 ）求圖 G 的最小費用最大流。要求計算出總費用。（ 6 分）解析： 本題是求最小費用最大流，應(yīng)當(dāng)熟知什么是可行流，掌握求最大流和最小費用最大流的算法。解

7、：（1 ）由于每條邊的流值均滿足容量限制，每個節(jié)點的流量也滿足流量守恒，故此流是可行流。（2 ）構(gòu)造伴隨網(wǎng)絡(luò)Gf 如下：4,-41v2,4t8,-24,-26,2s2,12,46,-12,-4v2圖中存在負費用增流圈v1 v2 t v 1, 所以不是最小費用流。在增流圈上調(diào)整即具有負費用的邊減去調(diào)整值2 ，費用為正值的邊加上調(diào)整值2 得：可編輯精品v16,2,48,8,2t10,6,2s8,8,14,2,4v2繼續(xù)構(gòu)造伴隨網(wǎng)絡(luò)圖：2,-4v14,48,-2t4,26,-2s8,-12,42,-4v2此圖已不存在負費用增流圈。則已求得流值為10 的最小費流，費用為：8 ×2+2 

8、15;4+6 ×2+8 ×1+2 ×4=52（3 ）用標(biāo)號算法求最大流：(-v2 ,2)v16,2,4(v1,2)8,8,2t10,6,2(0,+ )s4,2,48,8,1v2(s,2)可編輯精品找到增流鏈sv1v2 t,調(diào)整量為 2，調(diào)整后得：v16,4,4t8,8,210,4,2s4,4,48,8,1v2上圖已找不到增流鏈，故得最大流，流值為12. 現(xiàn)構(gòu)造其伴隨網(wǎng)絡(luò)圖：4,-4v12,48,-2t6,24,-2s8,-14,-4v2圖中已找不到負費用增流圈，故得到最小費用最大流，其費用為：8 ×2+4 ×4+4 ×4+4 

9、5;2+8 ×1=64 。2 、某企業(yè)經(jīng)營管理2 個加工廠甲和乙，有3 個原材料基地以下列數(shù)量供應(yīng)原料：原材料基地A ： 200t ，單價 200 元/t ；原材料基地B： 300t ，單價 180 元 /t ；原材料基地C： 400t ，單價 600 元 /t ；單位運價表（元/t ）如下：加工廠甲乙可編輯精品原材料基地A4050B2030C10060兩個加工廠的容量及加工費如下：加工廠甲乙容量450t500t加工費400 元 /t300 元 /t請完成（ 1 ）試建立該運輸問題的模型。 （ 6 分）（ 2 ）加工廠出售產(chǎn)品的價格是 900 元 /t ，問該企業(yè)如何組織兩個加工廠的

10、生產(chǎn)，使獲得的利潤最大？利潤值是多少？（ 9 分）解析：本題考查的時不平衡運輸問題及表上作業(yè)法。需要注意的是，此時的“運費”包括單位運價和加工費，由于供需不平衡，需要虛設(shè)一個原材料基地D ，其供應(yīng)量為50t ；至于求檢驗數(shù)的方法有閉回路和位勢法，一般情況下閉回路法較為簡單，不易出錯而位勢法需要求多個變量的值容易算錯。解：（ 1 ）需要虛設(shè)一個原材料基地D ，其供應(yīng)量為50t ，得供需平衡表如下：加工廠甲乙銷量原料A640750200B600510300C660520400可編輯精品D0050產(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 ,X2