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

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

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

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

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

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

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

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

8、15;4+6 ×2+8 ×1+2 ×4=52（3 ）用標(biāo)號(hà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圖中已找不到負(fù)費(fèi)用增流圈，故得到最小費(fèi)用最大流，其費(fèi)用為：8 ×2+4 ×4+4 ×4+4 

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

10、生產(chǎn)，使獲得的利潤(rùn)最大？利潤(rùn)值是多少？（ 9 分）解析：本題考查的時(shí)不平衡運(yùn)輸問(wèn)題及表上作業(yè)法。需要注意的是，此時(shí)的“運(yùn)費(fèi)”包括單位運(yùn)價(jià)和加工費(fèi)，由于供需不平衡，需要虛設(shè)一個(gè)原材料基地D ，其供應(yīng)量為50t ；至于求檢驗(yàn)數(shù)的方法有閉回路和位勢(shì)法，一般情況下閉回路法較為簡(jiǎn)單，不易出錯(cuò)而位勢(shì)法需要求多個(gè)變量的值容易算錯(cuò)。解：（ 1 ）需要虛設(shè)一個(gè)原材料基地D ，其供應(yīng)量為50t ，得供需平衡表如下：加工廠甲乙銷量原料A640750200B600510300C660520400可編輯精品D0050產(chǎn)量450500用差值法求解（括號(hào)中即為運(yùn)量）：加工廠甲乙銷量原料A（ 200）200B（ 200）（ 100）300C（ 400）400D（50 ）50產(chǎn)量450500用閉回路法非基變量檢驗(yàn)數(shù)(括號(hào)中數(shù)字 )如下 :加工廠甲乙銷量原料A200(200)200B200100300C(50)400400D50(90)50產(chǎn)量450500所有檢驗(yàn)數(shù)都大于0, 已得最優(yōu)解為 (X11 ,X2