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ī)則如下：（1）在原問(wèn)題（P）中，目標(biāo)函數(shù)為求，其約束條件統(tǒng)一成“”或“=”。（2）在對(duì)偶問(wèn)題（D）中，目標(biāo)函數(shù)為求。（3）在原問(wèn)題（P）中與bi相應(yīng)的一個(gè)約束條件，對(duì)應(yīng)著對(duì)偶問(wèn)題（D）的一個(gè)變量ui：如果該約束條件為不等式，則ui0；若該約束條件為等式，則ui為自由變量。（4）在原問(wèn)題（P）的每個(gè)變量xj對(duì)應(yīng)對(duì)偶問(wèn)題（D）的每一個(gè)約束條件：若（P）中xj0，則（

2、D）中為；若xj為自由變量，則。3.針對(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)行初等變換，使新基的系數(shù)矩陣變?yōu)閱挝痪仃?，此時(shí)可以得到一個(gè)滿足最優(yōu)檢驗(yàn)但不一定滿足非負(fù)約束條件的可行解；（5）利用對(duì)偶單純型法進(jìn)行迭代求解。4.對(duì)bi的靈敏度分析的目的是什么？答：其目的是在cj和aj不變

3、的前提下并在保證不改變?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ù)即得最優(yōu)解，若有，則轉(zhuǎn)第（3）步；（3）利用閉回路法進(jìn)行調(diào)整；（4）重復(fù)第（2）步，直到得到最優(yōu)解。6.分支定界法在滿足什么情況下停止分支？答：當(dāng)發(fā)生下列三種情況之一，就不再分支：（1）該分支子問(wèn)題無(wú)可行解，再分也無(wú)可行解；（

4、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)成回路的邊，同樣將其納入樹(shù)中；（3）如此反復(fù)，直到找不出這樣的邊為止。8.簡(jiǎn)述平行作業(yè)法在縮短工期時(shí)的思路。答：在工程項(xiàng)目任務(wù)十分緊迫、工作面允許以及資源保證供應(yīng)的條件下，可以組織幾個(gè)相同的施工隊(duì)，在同一時(shí)間、不同的工區(qū)上進(jìn)行施工，稱(chēng)為平行施工組織方式。 可以充分利用工作面，爭(zhēng)取時(shí)

5、間、縮短施工工期。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)用增流圈，若不存在，則是最小費(fèi)用最大流，否則，就不是。二、計(jì)算題（60分，共4小題，每小題15分）（答在試卷上的內(nèi)容無(wú)效）1.某運(yùn)輸網(wǎng)絡(luò)G如下圖，各條邊數(shù)字依次為容量、流量、費(fèi)用。請(qǐng)完成（1）判斷圖G是否為可行流。（3分）（2）判斷圖G是否為流值為10 的最小費(fèi)用流，若不是，將當(dāng)

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

7、1+2×4=52（3）用標(biāo)號(hào)算法求最大流：找到增流鏈sv1v2t,調(diào)整量為2，調(diào)整后得：上圖已找不到增流鏈，故得最大流，流值為12.現(xiàn)構(gòu)造其伴隨網(wǎng)絡(luò)圖：圖中已找不到負(fù)費(fèi)用增流圈，故得到最小費(fèi)用最大流，其費(fèi)用為：8×2+4×4+4×4+4×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è)加

8、工廠的容量及加工費(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è)加工廠的生產(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，得供需平衡表如下： 加工廠原料甲乙銷(xiāo)量

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

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

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

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

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