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

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

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

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

4、)步；(3)利用閉回路法進(jìn)行調(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)最小 且與選進(jìn)樹中的邊不構(gòu)成回路的邊，同樣將其納 入樹中；(3)如此反復(fù)，直到找不出這樣的邊為止

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

6、則，就不是。二、計算題(60分，共4小題，每小題15分) (答在試卷上的內(nèi)容無效)1.某運(yùn)輸網(wǎng)絡(luò)G如下圖，各條邊數(shù)字依次為容 量、流量、費(fèi)用。vi6,4,48,8,2J,、jjyy8,6,14,2,4-* 2?請完成(1)判斷圖G是否為可行流。(3分)(2)判斷圖G是否為流值為10的最小費(fèi)用流，若不是，將當(dāng)前網(wǎng)絡(luò)調(diào)整為最小費(fèi)用流。 要求計 算出總費(fèi)用。(6分)(3)求圖G的最小費(fèi)用最大流。要求計算出總費(fèi)用。(6分)解析：本題是求最小費(fèi)用最大流，應(yīng)當(dāng)熟知什么 是可行流，掌握求最大流和最小費(fèi)用最大流的算 法。解：(1)由于每條邊的流值均滿足容量限制，每 個節(jié)點(diǎn)的流量也滿足流量守恒，故此流是可行 流

7、。(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)用為: 8X2+2X 4+6X2+8X1+2X 4=52(3)用標(biāo)號算法求最大流:上圖已找不到增流鏈，故得最大流，流值為 12現(xiàn)構(gòu)造其伴隨網(wǎng)絡(luò)圖：圖中已找不到負(fù)費(fèi)用增流圈，故得到最小費(fèi)用最 大流，其費(fèi)用為：8X2+4X 4+4X 4+4X 2+8X 1=64。2、某企業(yè)經(jīng)營管理2個加工廠甲和乙，有3個 原材料基地以下列數(shù)量供應(yīng)原料：原材料基地A: 2

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

9、般情況下閉回路法較 為簡單，不易出錯而位勢法需要求多個變量的值 容易算錯。解：（1）需要虛設(shè)一個原材料基地D,其供應(yīng)量 為50t,得供需平衡表如下:銷量加工廠 原料A640750200B600510300C660520400D0050r#450500用差值法求解（括號中即為運(yùn)量）原料甲乙銷量A(200)200B(200)(100)300C(400)400D(50)50450500用閉回路法非基變量檢驗數(shù)（括號中數(shù)字）如下:加卜原料 甲乙銷量A200(200)200B200100300C(50)400400D50(90)50450500所有檢驗數(shù)都大于0,已得最優(yōu)解為 (Xii,X2i,X22,

10、X32,X4i)=(200,200,100,400,50)最大禾I潤 900 X 900-200 X 640-200 X 600-100 X 510-400X520=303000 元.3.下圖所示的運(yùn)輸網(wǎng)絡(luò)，邊旁數(shù)字表示的最大通 行能力。假設(shè)該運(yùn)輸網(wǎng)絡(luò)中某些節(jié)點(diǎn)有流量需 求，此處已知V6需要5個流量。請構(gòu)造分配最 大流的新網(wǎng)絡(luò)圖，并分配最大流。解析：本題是有節(jié)點(diǎn)流量限制的最大流分配問 題，一般處理方法是將節(jié)點(diǎn)分成兩個節(jié)點(diǎn)中間相 連接的邊的權(quán)即為該節(jié)點(diǎn)所需流量；解：將節(jié)點(diǎn)6拆分為V61和V62,新網(wǎng)絡(luò)圖如下:2增流鏈為Viv3V61V62V7,調(diào)整量4：繼續(xù)尋找增流鏈:增流鏈為Viv4V5V7）

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

12、題。解決本題 的步驟是：先繪制完統(tǒng)籌圖，再計算時間參數(shù)， 再確定關(guān)鍵路線。解：（1）統(tǒng)籌圖如下：粗實(shí)線表示的即為關(guān)鍵路線為1, 2, 4, 5;關(guān)鍵工序為ace。(2) c減少一天，總工期減少一天。因為c是關(guān) 鍵工序，并且減少一天并未改變關(guān)鍵路線和關(guān)鍵 工序。(3) b延長兩天對總工期無影響，因為 b還未 成為關(guān)鍵工序。(4) b的工序時間延長了 2天，工序d的工序 時間延長了 3天，總工期會增加一天，因為此時 的關(guān)鍵路線為1, 3,4,5.關(guān)鍵工序為bde,總工期 為13天。三、綜合題(20分，共2小題，每小題10分) (答在試卷上的內(nèi)容無效)1.已知某種產(chǎn)品有n個銷售點(diǎn)，有m個配送中心 可

13、供選擇以實(shí)現(xiàn)對該產(chǎn)品的配送。 設(shè)在配送中心 i對該產(chǎn)品的年配送能力上限為 Ci,并因配送該 產(chǎn)品而會增加年費(fèi)用為Fi。各個銷售點(diǎn)對該產(chǎn)品 必須得到滿足，設(shè)在銷售點(diǎn)j對該產(chǎn)品的需求量 為Dj。從配送中心i到銷售點(diǎn)j的單位產(chǎn)品運(yùn)費(fèi) 為Wij。要求建立整數(shù)規(guī)劃模型，使得運(yùn)輸成本 和配送成本總和最小。解析：此題是整數(shù)規(guī)劃問題中關(guān)于選址的問題，是0-1規(guī)劃問題，是書上（寇偉華版）原題的小 改編。解：設(shè)有兩組決策變量，表示從配送中心i到 銷售點(diǎn)j的產(chǎn)品數(shù)量，表示是否由配送點(diǎn)i進(jìn)行 配送，若是則y 1,否則y 0,則目標(biāo)函數(shù)為： m nmmin zWjj xjF, yi 1 j 1i 1配送中心配送能力的約

14、束條件為： nXij Ci y,i 1,2.3.mj 1不配送銷售點(diǎn)i時，y 0,上式左端必為0；配送 銷售點(diǎn)i時，y 1,從配送中心到各銷售點(diǎn)的產(chǎn)品 數(shù)量應(yīng)小于等于該配送中心的配送能力。因此， 為保證每個銷售點(diǎn)的需求都得到滿足， 有約束條 件方程：所以整個模型為： m nmmin z Wu xjFi yii 1 j 1i 1n 為Ciyi,i1,2,3.mj 1 m XjDj,j 1,2,3. n1 1 xj0,i 1,2,.,m; j 1,2,.,n0 yi1y為整數(shù)，i 1,2,.,m2 .已知某產(chǎn)品有三個產(chǎn)地 X1, X2, X3,三個銷地y1, y2）y3）供應(yīng)量、需求量及運(yùn)價如下表所示產(chǎn)地y1y2y3供應(yīng)量X156410X27936X36