管理運籌學(西南交通大學)

1、西南交通大學 2014 年全日制碩士研究生入學試題解析試題名稱： 管理運籌學二一、問題題（ 60 分，共 10小題，每小題 6 分）（答在試卷上的內(nèi)容無效）1、簡述單純形法的基本思路。解析： 這是一道考查單純形法基本知識的題目，是很容易出簡答題的知識點。解：詳見寇偉華運籌學 P40。2、簡述線性規(guī)劃問題求解出現(xiàn)退化解的特征。解析： P58 線性規(guī)劃問題各種解的情況都容易出問答題，應理解并會用自己的語言組 織。0。解：如果出現(xiàn)基變量等于零，就會造成基本可行解中非零變量的個數(shù)小于約束條件方 程的個數(shù)，這就是退化現(xiàn)象。在用單純形法求解時，退化現(xiàn)象表現(xiàn)為，若確定的換出 變量同時有兩個或兩個以上，就會造

2、成下一次迭代時有一個或幾個基變量的取值為3、什么是對偶問題的弱對偶性？解析： 考查的是對偶問題的性質(zhì)，對偶問題的性質(zhì)是?？碱}目，應熟練掌握。解：詳見寇偉華運籌學 P76 定理 3.24、簡述影子價值與邊際值的區(qū)別。解析： 這是考查概念的問題，影子價格和邊際值是兩個簡單的概念，理解了自然能說 出他們的區(qū)別。解：詳見寇偉華運籌學 P95 影子價格和邊際值概念5、簡述閉回路法求取運輸問題檢驗數(shù)的步驟。解析： 閉回路法求運輸問題檢驗數(shù)是基本知識和方法，運輸問題這里可以問的問題很 多，可以問你表上作業(yè)法，可以問你差值法求初試基本可行解的步驟，可以問你位勢 法求運輸問題檢驗數(shù)的步驟等等，需要對運輸問題的表

3、上作業(yè)法的過程非常熟悉，才 能有助于解決這類問答題以及計算題。解：詳見寇偉華運籌學 P128。6、簡述指派問題等效矩陣的方法及性質(zhì)。解析： 考查指派問題的簡答問答題，理解并用自己的語言組織即可。解：詳見寇偉華運籌學 P154 定理 6.1。7、簡述無向圖中連通圖與完備圖的區(qū)別。解析： 考查的是圖與網(wǎng)絡(luò)這章的基本知識的概念和區(qū)別，應理解并掌握基礎(chǔ)知識。解：詳見寇偉華運籌學 P216 和 P217 完備圖和連通圖的概念。8、判別可行流是最小費用流的依據(jù)是什么？解析： 考查圖與網(wǎng)絡(luò)中的基本判別條件，熟練掌握了最小費用流的解題過程也就能自己組織出答案。解：一個可行流是最小費用流的充要條件是網(wǎng)絡(luò)中不存在

4、負費用的增流圈。9、統(tǒng)籌方法制定最少工程費方案時，費用斜率的計算方法是什么？解析： 考查統(tǒng)籌方法的基本知識，應理解費用斜率代表的是什么含義，了解統(tǒng)籌方法的算法過程。解：費用斜率 (cij )趕工時間的工序直接費 用- 正常時間的工序直接費正常完工所需時間 - 趕工完成時間也可以用寇偉華運籌學 P318 的公式來回答。10、解釋下為何 M M1排隊模型指標當中，隊長與排隊長計算結(jié)果為何相 差不一定是 1。的范圍必須小解析： P343這是考查排隊論這章中基本公式和基礎(chǔ)知識的理解并間接考查了 取值原因。解：由于 Lq L ，故隊長和排隊長相差一個繁忙度 ，又由于到達強度 于服務(wù)強度 ，否則排隊系統(tǒng)排

5、隊長度將會越來越大，以致出現(xiàn)爆炸現(xiàn)象，此時就不 是排隊問題了，所以 0 1。、計算題（ 70 分，共 4個小題）1 某生產(chǎn)企業(yè)采用兩種原料鐵和鋁，生產(chǎn)三種產(chǎn)品A 、B 、 C，已知鐵和鋁每天可用資源單位量分別為 100和 120。生產(chǎn)有關(guān)資料如下表：產(chǎn)品單位產(chǎn)品鐵消耗量單位產(chǎn)品鋁消耗量單位產(chǎn)品利潤A2340B3345C1225假設(shè)三種產(chǎn)品 A、B、C 的日產(chǎn)量分別為 x1 、 x2 、 x3 ，建立模型使利潤最大；MaxZ 40 x1 40 x2 25x32x1 3x2 x3 100s.t 3x1 3x2 2x3 120 x1,x2,x3 0表為對上述模型運用單純形法求解的一次迭代步驟；Cj4

6、0452500CBXBbX1X2X3X4X545X2100/32/311/31/300X520101-11Zj304515150Cj-Zj10010-150請完成（ 1）進一步求解獲得最優(yōu)解（ 6 分）（2）判斷此問題最優(yōu)解屬于哪一種情況，為什么？（3 分）（ 3）若存在多重解，請寫出所有的最優(yōu)解。（6 分）解析： 考查單純形法的計算過程以及最優(yōu)解的判別，每年必考計算題目之一。解：（ 1） x1,x3的檢驗數(shù)相同，故選其中一個作為換入變量，這里選x3作為換入變量，根據(jù)最小比值原則，確定 x5 為換出變量，調(diào)整后得到單純形表如下：Cj40452500CBXBbX1X2X3X4X545X280/3

7、1/3101/3-1/325X32010101Zj4045251510Cj-Zj000-15-10單純形表中所有非基變量的檢 驗數(shù)全 部小于 等于 0，說明已達最 優(yōu)，最 優(yōu)解 為（x1,x2,x3,x4,x5） （0,80/ 3,20,0,0） ，目標函數(shù)值為 z 45 80/3 25 20 1700。（2）此問題屬于多重解。因為非基變量X 1 檢驗數(shù)為 0，即表明有多重解。（3）把 X1作為換入變量， 根據(jù)最小比值原則確定 X3 為換出變量， 調(diào)整后的單純形表如下：Cj40452500CBXBbX1X2X3X4X545X22001-1/31/3-2/340X12010101Zj404525

8、1510Cj-Zj000-15-10已 最 優(yōu) ， 新 的 最 優(yōu) 解 為 （x1,x2,x3,x4,x5） （ 20,20,0, 0,0） ， 目 標 函 數(shù) 值 z 45 20 40 20 1700，將（1）得出的最優(yōu) 解記 做 X （1） ，將（ 3）得到的最優(yōu)解 記做 X（2） ， 則可以求出無窮個最優(yōu)解：X X（1） （1 ）X（2） （0,80/3,20,0,0） （1 ）（20,20,0,0,0）。2 （ 15 分）某運輸網(wǎng)絡(luò) G 如下圖，各條邊數(shù)字依次為容量、流量、費用。請完成（ 1）判斷圖 G 是否為可行流。（ 3 分）（ 2）判斷圖 G 是否為流值為 10 的最小費用流，如

9、果不是，將當前的網(wǎng)絡(luò)調(diào)整為最 小費用流，要求計算出總費用。（ 6 分）（3）求圖 G 的最小費用最大流，要求計算出總費用。（6 分）解析： 考查的圖與網(wǎng)絡(luò)中可行流的判別條件， 最小費用流的算法， 以及最小費用最大流的算 法，每年必考計算題的類型之一。解（1）圖 G 滿足可行流的兩個條件：任意邊的容量限制條件，中間點的平衡條件。故 該圖為可行流。2）構(gòu)造增流網(wǎng)絡(luò) Gf 如下圖存在負回路 C tv1v2t ，故題目中給出的流并非流值為10 的最小費用流?，F(xiàn)在?。簃in 4,6,2 2 。對題目中所給的流修改得新的網(wǎng)絡(luò)圖如下：b( f ) 8 2 2 4 6 2 2 4 8 1 52 。(3)使用標

10、記算法求最大流標記：先給 s 表上(0， )檢查 s，邊 (s,v1)上， fs,1 cs,1，故 v1得不到標記，邊 (s,v2)上， f s,20 ，故對 v1標記(-v2,l(v1) ，其中， l(v1) min 2,6 2。檢查 v1，邊(v1,t)上， f1,t c1,t ，故對 t 標記( v1,l (t) ，其中， l(t) min 2,4 2，t 得到標記，進行下一步調(diào)整。調(diào)整：按頂點的第一個標記找到一條增流鏈 Q sv2v1t ，按l(t) 2 調(diào)整增流鏈上各邊的流量，調(diào)整后如下圖：上圖中不存在增流鏈， 已達最大流， 該流是在最小費用的基礎(chǔ)上得到的最大流， 故上圖即為 最小費

11、用最大流，總費用為 b( f) 8 2 4 4 4 2 4 4 8 1 64。3(20 分)某企業(yè)經(jīng)營管理 2個加工工廠甲和乙有 3個原材料基地以下列數(shù)量供 應原料：原材料基地 A: 200t ，單價 200 元/t：原材料基地 B: 300t ，單價 180 元/t：原材料基地 C: 400t 單價 160 元/t單價運價表(元 /t) 如下：原材料基地加工廠甲乙A4050B2030C10060兩個加工廠的容量及加工費用如下：加工廠甲乙容量450t500t加工費400 元 /t300 元 /t請完成（1）試建立該運輸問題的數(shù)學模型。（ 10 分）（2）加工廠出售產(chǎn)品的價格是 900 元 /t

12、。問該企業(yè)如何組織兩個加工廠的生產(chǎn)，使獲得的利潤 最大？利潤值是多少？（ 10 分）解析： 這是考查運輸問題的題型，考查了不平衡運輸問題的建模以及運輸問題的求解。解：（ 1）原材料供應量為 200+300+400=900t ，加工量為： 450+500=950t 。加工量大于供應 量 950-900=50t ，這是一個需大于求的不平衡運輸問題。虛設(shè)一個原材料基地為D ，供應量為 50t。設(shè) xij 為加工廠 i 加工來自原材料基地 j 的加工量， i= 甲，乙； j=A,B,C,D 。則建立的 運輸問題模型如下：原料加工廠ABCD銷量甲6406006600450乙5505105200500產(chǎn)量

13、20030040050950（2）將求最大利潤的問題轉(zhuǎn)化成求最小費用的問題，構(gòu)造綜合表，用差值法確定初始基本 可行解。原料加工廠ABCD銷量差值甲X 11640X 12600X1366050*0450600乙X21550X 22510X 235200500510產(chǎn)量20030040050950差值90901400用差值法重新構(gòu)造綜合表如下：原料加工廠ABCD銷量差值甲X 11640X 1260066050*045040乙X 21550X 22510400*520050010產(chǎn)量20030040050950差值90901400重新構(gòu)造綜合表如下：原料加工廠ABCD銷量差值甲X11640X1260

14、066050*045040乙X 21550X 22510400*520050040產(chǎn)量20030040050950差值909000A和 B兩列中差值相等，任選一個，這里選 B列，構(gòu)造出的初始基本可行解的綜合表如下：原料加工廠ABCD銷量差值甲200*640200*60066050*045040乙550100*510400*520050040產(chǎn)量20030040050950差值909000基變量個數(shù)為 5 個，已得初始基本可行解。 用位勢法進行檢驗， 在上表中， x11, x12 , x14 , x22 , x23為基變量，因此有如下方程組：u1v1c11640u1v2c12600u1v4c14

15、0u2v2c22510u2v3c23520令 u1 0 ，按照位勢法的步驟寫入表后，得下表：原料6406006100銷量加工廠ABCD0甲200*200*5050*45064060066000100*400*90-90乙5505105200500產(chǎn)量20030040050950表中沒有負檢驗數(shù)，說明已經(jīng)找到最優(yōu)解（x11,x12,x14,x22,x23） （200,200,50,100,400） 。即應該安排原材料 A 200t，原材料 B 200t ，原材料 D（虛） 50t 運往甲，原材料 B 100t, 原 材料 C 400t 運往乙。則最小費用為值 z 640 200 600 200

16、0 50 510 100 520 400 507000。 由于只能提供原材料 900t，所以最大利潤值 w 900 900 507000 303000元。4（20 分）某港口外運公司的貨場，裝貨汽車隨機到達平均間隔時間為7.5min，服從指數(shù)分布。裝車設(shè)備為叉車，經(jīng)統(tǒng)計一臺叉車裝一輛貨車的平均時間12min，服從指數(shù)分布，若兩臺叉車同時裝車時間縮短一半。問題如下： （1）“兩臺叉車同時裝一輛汽車方式”和“用兩臺叉車各裝一輛汽車”分別屬于哪種排隊 模型形式（A / B / C）？（ 4 分）（2）分別計算排隊長 Lq 和平均等待時間 Wq來比較兩種作業(yè)方式哪一種更好？（10分）（3）若采取叉車各

17、裝一輛汽車方式， 若想使汽車到達后不排隊的概率大于0.3，那么貨場應至少安排幾個叉車？（ 6 分）提示；M/M /C):/ /FCFS 模型參考 公式如下1nPnnn!nn!p0當1C!n0.35N 5N5N5N求得N1.91，取整數(shù)，則可知至少2 臺。三、建模題 (20 分，共兩個小題，每小題 10 分)1. 已知某種產(chǎn)品有 n 個銷售點，有 m 個配送中心可供選擇以實現(xiàn)對產(chǎn)品的配送。設(shè)在配送 中心 i 對該產(chǎn)品的年配送能力上限為 Ci ，并因配送該產(chǎn)品而會增加年配送費用為Fi。各個銷售點對該產(chǎn)品必須得到滿足， 設(shè)在銷售點 j對該產(chǎn)品的需求量為 Dj ，從配送中心 i 到銷售 點 j 的單位產(chǎn)品運費為 Wij 。要求建立整數(shù)規(guī)劃模型，使得運輸成本和配送成本總和最小。 解析： 這是一道考查整數(shù)規(guī)劃的建模題， 是?？碱愋皖}目之一， 應該學會分析并合理假設(shè)建 模的變量，然后寫出約束條件和目標函數(shù)。解：設(shè) xij 表示從配送中心 i 到銷售點 j 的數(shù)量， yi 表示配送中心 i 是否配送，若配送，為1 ，否則為 0 。其模型如下：mnmmin zwij xijFiyi1j1i1nxijyiCij1mxijDji1xij 0yi 為0或1,i 1m; j 1n2. 空車調(diào)整是鐵路運輸調(diào)整的重要組成部分。 假設(shè)三個空車多車站 A1, A2 , A3 ,三個空車缺車站 B1,B2