西南交通大學(xué)管理運(yùn)籌學(xué)929-2018年試題和解析

1、西南交通大學(xué)管理運(yùn)籌學(xué) 9292018 年試題和解析( 總 10 頁(yè))-本頁(yè)僅作為文檔封面，使用時(shí)請(qǐng)直接刪除即可-內(nèi)頁(yè)可以根據(jù)需求調(diào)整合適字體及大小-2222機(jī)密啟用前西南交通大學(xué) 2018 年碩士研究生招生入學(xué)考試試卷試題代碼：929試題名稱：管理運(yùn)籌學(xué)一考試時(shí)間：201712考生注意：3150效；請(qǐng)?jiān)诖痤}紙上按要求填寫試題代碼和試題名稱；試卷不得拆開，否則遺失后果自負(fù)。一、 問答題（60分，共10小題，每小題6分）（答在試卷上的內(nèi)容無效1、線性規(guī)劃模型中，何謂自由變量自由變量和決策變量是什么關(guān)系解答：用設(shè)定的未知數(shù)來表示線性規(guī)劃問題問題中的未知量，這個(gè)設(shè)定的未知量就叫做決策變量，決策變量沒

2、有非負(fù)約束即為自由變量；自由變量一定是決策變量，但決策變量不一定是自由變量。2、請(qǐng)分別解釋無可行解、無界解、最優(yōu)解的概念。解答：無可行解：約束方程組沒有公共解，造成線性規(guī)劃模型無解的解。無界解：沒有任何一個(gè)可行解能使得目標(biāo)函數(shù)達(dá)到最優(yōu)，即目標(biāo)函數(shù)沒有上界或下界。最優(yōu)解：在線性規(guī)劃模型的所有可行解中，使得目標(biāo)函數(shù)達(dá)到最優(yōu)的解3、說明下面的數(shù)學(xué)模型不符合線性規(guī)劃模型的什么特點(diǎn)z 6x 4x x 3xx 23303s.t. x 1 x1833(2x )2 2x3 49x ,10312解答：此模型不符合線性規(guī)劃模型目標(biāo)函數(shù)應(yīng)該是線性函數(shù)的特點(diǎn)；此模型不符合線性規(guī)劃模型目標(biāo)函數(shù)求最大值最小值的特點(diǎn)；式的

3、特點(diǎn)。4、以目標(biāo)函數(shù)Min 型為例，從基本可行解、求檢驗(yàn)數(shù)以及基本可行解改進(jìn)3333三個(gè)方面說明單純形法和表上作業(yè)法的區(qū)別。解答：本可行解。檢驗(yàn)數(shù)：?jiǎn)渭冃畏ㄊ撬愠鰴C(jī)會(huì)費(fèi)用 zj以后，直接計(jì)算檢驗(yàn)數(shù)的代數(shù)式c zjj，而表上作業(yè)法是通過另外的閉回路法或者位勢(shì)法來計(jì)算檢驗(yàn)數(shù)。c zjj 0 的情況下進(jìn)一步改進(jìn)基本可行解，即若基本可行解不是最小值，那么需要迭代調(diào) 通過行運(yùn)算進(jìn)行迭代。5、用表上作業(yè)法求運(yùn)輸問題的檢驗(yàn)數(shù)的方法有閉回路法和位勢(shì)法，位勢(shì)法的思路是針對(duì)基變量 xiju 和viju vij c 。請(qǐng)利用閉回路ij法的思路及以下圖形的回路， 證明位勢(shì)法求非基變量檢驗(yàn)數(shù)的公式ciju v 。ijx

4、ijxxijxijxi jxi j證明：基變量基變量因?yàn)?xij, xi j, xi j是基變量，由已知條件有以下方程：u vij c ,u vijic,u vi ji ci j根據(jù)閉回路法，非基變量的檢驗(yàn)數(shù)為ij (cijci j) (cijci j) cijcijci jci j故證得ij c uij即ijv 。j c u vuijijv u vji c u vijij6、針對(duì)整數(shù)規(guī)劃的分枝定界法：先使用什么方法求出不考慮整數(shù)約束的最優(yōu)解（3）xk取值為整數(shù)，但用分支定界算法求出 bk 的值不是整數(shù)，那么需要使用什么方法求出分支以后的解（3） 3 分）4444解答：法求得最優(yōu)解。分枝法：在

5、最優(yōu)解中選擇一個(gè)不符合整數(shù)約束條件的xj其值為 b ，以jjjjjb x x 別加入原 LP 與jjjj7、利用Ford-Fulkerson算法對(duì)網(wǎng)絡(luò)的流量進(jìn)行調(diào)整時(shí)，必須遵守容量約束條件和流量守恒條件。請(qǐng)利用以下圖形示例解釋：在增加網(wǎng)絡(luò)的流量時(shí)，為何增流鏈前向邊的流量要加上調(diào)整量 （xv v v y ）3 4 5v3v37，38，3v54，26，3v46，5v 點(diǎn)接受流量4之和為8v 點(diǎn)發(fā)出流量4之和4解析：針對(duì)中間點(diǎn)v4，接收流量之和與發(fā)出流量之和均為 8，滿足流量守恒，針xv v y ，邊(v v 是接收流量的邊，而邊(v v 是中間點(diǎn)發(fā)出流3 4 5344454量的邊。若給增流鏈 xv

6、 v v3 4 5y 加上調(diào)整量 ，就會(huì)導(dǎo)致中間點(diǎn)v4接收量之和為8+ ，為了滿足流量守恒的條件，中間點(diǎn)v48+ ，所以需要把增流鏈前向邊的流量要加上調(diào)整量 。8、假設(shè)某統(tǒng)籌圖的關(guān)鍵路線有 2 條，如果某一個(gè)非關(guān)鍵工序的工序時(shí)間長(zhǎng)，關(guān)鍵路線的狀態(tài)有什么變化？9、解析：若該非關(guān)鍵工序的工序時(shí)間延長(zhǎng)后不超過關(guān)鍵工序的工序時(shí)間，那么統(tǒng)籌圖的關(guān)鍵路線不變；若該非關(guān)鍵工序的工序時(shí)間延長(zhǎng)后超過關(guān)鍵工序的工序時(shí)間，那么統(tǒng)籌圖的關(guān)鍵路線變?yōu)樵撀肪€。11、對(duì)線性規(guī)劃模型目標(biāo)函數(shù)的cj進(jìn)行靈敏度分析時(shí)，如果 cj在允許范圍內(nèi)變動(dòng)，那么模型的目標(biāo)函數(shù)值是否會(huì)改變?yōu)槭裁唇馕觯寒?dāng)c xj為非基變量時(shí)，若cj在允許范圍內(nèi)

7、變動(dòng)，最優(yōu)解不會(huì)改變。另外，目標(biāo)函數(shù)值也不會(huì)改變。盡管c發(fā)生了變動(dòng)，但作為非基變量 x 的jj0，所以目標(biāo)函數(shù)中c xjj項(xiàng)的取值仍然為 0。5555當(dāng)c xj為基變量時(shí)，如果cj在允許范圍內(nèi)變動(dòng)，最優(yōu)解不會(huì)改沒有改變，但cj發(fā)生了變動(dòng)，所以目標(biāo)函數(shù)c xjj項(xiàng)的取值也發(fā)生了變動(dòng)，從而造成目標(biāo)函數(shù)值變動(dòng)。10、在排隊(duì)系統(tǒng)中，如果顧客到達(dá)時(shí)間的間隔是均衡固定的，是否會(huì)產(chǎn)生排隊(duì)現(xiàn)象？為什么解析：會(huì)產(chǎn)生排隊(duì)現(xiàn)象。理由是：排隊(duì)現(xiàn)象的產(chǎn)生是由于顧客到達(dá)的時(shí)間存在隨機(jī)性或者服務(wù)員的服務(wù)時(shí)間存在隨機(jī)性，因此在顧客到達(dá)的時(shí)間間隔均衡固定的情況下，服務(wù)時(shí)間不均衡固定是會(huì)產(chǎn)生排隊(duì)現(xiàn)象的。二、 計(jì)算題（75 分，共

8、 3 小題）（答在試卷上的內(nèi)容無效）(25B乙兩種產(chǎn)品獲利最多的生產(chǎn)方案，此方案求解過程如下表所示。已知 x、xx x x5454212均為松弛變量。cj23000cBxBbx1x2x3x4x52x21010-1/20 x800-4123x301001/4zj2320-1/4c zjj00-201/4請(qǐng)解決以下問題：求解該企業(yè)獲利最多的生產(chǎn)方案以及獲得的最大利潤(rùn)。（10）如果該企業(yè)打算制定將設(shè)備出租、A和 B此方案的線性規(guī)劃模型是什么（10）上面第（2）個(gè)問題中的線性規(guī)劃模型的最優(yōu)解是什么（4） 5 分）解答：題中單純性表中仍然有正檢驗(yàn)數(shù)c z55 1/ 4 ，所以沒有達(dá)到最優(yōu)解，并且存在有a

9、cBcB203cjxBx5x4x2zjc zjb4422x11003x20010 x30-21/20 x41/41/2-1/80 x50102j0303/2-3/21/8-1/8000，需要迭代循環(huán)求解，迭代后的單純形表如下：6666上表中所有的檢驗(yàn)數(shù)都是小于等于 0 的，所以已經(jīng)達(dá)到了最優(yōu)，其中最優(yōu)解為(x x x x x (4, 2,0,0, 4) 4212345z 14元。此問題即是寫出對(duì)偶問題的線性規(guī)劃模型，但必須先寫出原問題的的線性x x x 均為345松弛變量，所以在初始單純形表中，它們對(duì)應(yīng)的矩陣是單位矩陣，這需要在對(duì)x x x345對(duì)應(yīng)的矩陣變?yōu)閱挝痪仃?，結(jié)果如cBcB000cj

10、xBx3x4x523000bx1x2x3x4x581210016400101204001基于上表，可以寫出此方案的線性規(guī)劃模型如下：max z 2x13x2 x 2x 84x12 1614x 12x 0, 1,2j如果把生產(chǎn)方案看作原問題，那么將設(shè)備出租、AB兩種原材料出售獲利的方案可以看作是對(duì)偶問題?；谏a(chǎn)方案原問題的模型，即可寫出對(duì)偶問題的線性規(guī)劃模型：min q 8y116y212y3 y 4y 22 4y2 3 yj1 0, j3 1,2,3（5） 上面第（2）問的中線性規(guī)劃模型的最優(yōu)解即是對(duì)偶問題的最優(yōu)解，從第（1）個(gè)問題中的最優(yōu)單純形表即可讀出對(duì)偶問題決策變量的最優(yōu)解：y z1m

11、1 z 3/ 2,y3 z zm241/ 8, y3 z zm35 0,其中m 2 。y y12, y ) (3 / 2,1/ 8,0)3（25）57請(qǐng)?jiān)O(shè)計(jì)半年以后的運(yùn)輸方案。77775,1,25,1,2v33,1,3v46,1,23,0,52,0,4v1v64,4,3v24,4,35,4,3v5解答：首先找到增流鏈v v v134 v 取調(diào)整量 2 76網(wǎng)絡(luò)圖如下：5,3,25,3,2v33,3,3v46,3,23,0,52,0,4v1v64,4,3v24,4,35,4,3v5然后構(gòu)建此時(shí)運(yùn)輸量為7的網(wǎng)絡(luò)圖的增流網(wǎng)絡(luò)G，如下圖所示：f3,-23,-2v33,-3v43,23,-22,23,5

12、2,4v1v61,34,-3v24,-3v54,-3此時(shí)不存在負(fù)回路，說明當(dāng)前已是運(yùn)輸量為 7 的最小費(fèi)用流，總費(fèi)用為：W ( f) 32 33 32 43 43 43 57A(25工序代號(hào)a 工序代號(hào)a b cdba,c工序時(shí)間（天）10534工序代號(hào)e f gh緊前工序a,d ef , g工序時(shí)間（天）5655問題如下：繪制上述建設(shè)工程的統(tǒng)籌圖。（5）利用事項(xiàng)的最早時(shí)間和最遲時(shí)間，確定出關(guān)鍵路線和工期（10）8888c工序節(jié)省出一臺(tái)挖掘機(jī)，而一臺(tái)挖掘機(jī)投入到其他工序，可使其它工序的工序時(shí)間減少 2到哪個(gè)工序可使工程的工期提前為什么（10）解答：d4d4f245e665 gh57a51013

13、cb53利用事項(xiàng)的最早時(shí)間和最遲時(shí)間，確定出關(guān)鍵路線為：014014141010d4f20202525245e66h575 g501a103c1515b5357即有兩條關(guān)鍵工序工期均為 25 天： 需要把挖掘機(jī)放到工序a或h2524有關(guān)鍵工序，2b4序a或h中的一個(gè)?，F(xiàn)在對(duì)將挖掘機(jī)分別放到a 或h 進(jìn)行討論如下： 當(dāng)放于a 時(shí)，關(guān)鍵路線為99990 1201212882d4f1818232345e66h575 g501a83c1313b53554 、 當(dāng)放于h 時(shí)，關(guān)鍵路線為0140141410102d4f2920232345e66h375 g501a103c1515b5375 綜上所述：需要

14、把挖掘機(jī)放到工序a 或h 2523三、 建模題（15 分，共 1 小題）（答在試卷上的內(nèi)容無效）有一個(gè)運(yùn)輸網(wǎng)絡(luò)如下圖所示，圖中各個(gè)邊給出了容量和費(fèi)用。其中 x 有165x2有和兩種產(chǎn)品，數(shù)量分別為 412x 87y、y、為三個(gè)3123y167y2需要和兩49y3需要和兩種產(chǎn)品，需求量分別為 8噸和 13 噸；x2處的產(chǎn)品只能運(yùn)送到需求地 y2x 處的3y 。3請(qǐng)將此網(wǎng)絡(luò)圖轉(zhuǎn)換為可用于求解的單源單匯、單一品種的網(wǎng)絡(luò)圖模型。10101010(+6)(+5)(-6)x1(7,5)x1(7,5)y1(8,5)(6,5)(4,5)v1x2(4,5)（3,5）(5,5)y2(9,5)v2(6,5)(3,5

15、)(6,5)v3(4,5)(8,5)(7,5)x3(8,5)y3(+4)(+12)(-4)(-9)(+8)(+7)(-8)(-13)解析：42471491122x* 生產(chǎn)產(chǎn)品2x* 生產(chǎn)產(chǎn)品3x x 拆成分別生產(chǎn)產(chǎn)品,的產(chǎn)地123x1x1x2x2 x3x3 ；yy y拆成分別銷售產(chǎn)品,的銷地123y1 y1 y2 y2 y3 y3 ，將轉(zhuǎn)運(yùn)地v v拆成分別轉(zhuǎn)運(yùn)產(chǎn)品，的12v1,v1 ,v1 ,v2,v2 ,v2 ,v3,v3 ,v3；最后得到如下單源單匯的網(wǎng)絡(luò)圖：(+6)(+6)(6,0,5)(6,0,5)(+5)v1(6,0,5)(6,0,0)(5,0,5)(8,0,0)(+4)xv1(5,0,5)y1(8,0,0)2(4,0,5)(14,0,0)(4,0,5)y1(5,0,0)(16,