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

1、機(jī)密啟用前西南交通大學(xué)2018年碩士研究生招生入學(xué)考試試卷試題代碼：961試題名稱：管理運(yùn)籌學(xué)二考試時(shí)間：2017年12月考生注意：.本試題共三大題，共3頁(yè)，滿分150分，請(qǐng)認(rèn)真檢查；.答題時(shí)，請(qǐng)直接將答題內(nèi)容寫(xiě)在考場(chǎng)提供的答題紙上， 答在試卷上的內(nèi)容無(wú)效；.請(qǐng)?jiān)诖痤}紙上按要求填寫(xiě)試題代碼和試題名稱；.試卷不得拆開(kāi)，否則遺失后果自負(fù)。一、 問(wèn)答題(70分，共10小題，每小題7分)(答在試卷上的內(nèi)容無(wú)效)1、利用數(shù)學(xué)表達(dá)式凸集與凹集的區(qū)別。解析：設(shè)K是n維歐式空間的一個(gè)點(diǎn)集，若任意兩點(diǎn) X(1) w K、Xw K的連線上一切 點(diǎn)ax+ (1-叼XWK (0ESE1),則稱K為凸集；相反，不滿足上

2、述條件的 稱為凹集。2、以max為例，如何運(yùn)用檢驗(yàn)數(shù) 坊-zj判斷基本可行解是否為最優(yōu)解？ 解析：當(dāng)可行解全部檢驗(yàn)數(shù)cj -zj E0時(shí)達(dá)到最優(yōu)解。3、如果原問(wèn)題模型存在約束方程是“=”形式，那么轉(zhuǎn)換對(duì)偶模型應(yīng)該怎么處 理？解析：有兩種處理方式：將“=”形式的約束條件方程變?yōu)椤皩W(xué)”和兩個(gè)不等式方程；可以不進(jìn)行變動(dòng)，對(duì)偶問(wèn)題中對(duì)應(yīng)的變量yi就作為自由變量。4、若新增加了約束條件方程，簡(jiǎn)述運(yùn)用對(duì)偶單純形法擴(kuò)展應(yīng)用的求解思路。解析：第一步：檢驗(yàn)原來(lái)的最優(yōu)解是否滿足新增加的約束條件方程，如果滿足，原來(lái)的最優(yōu)解就是新模型的最優(yōu)解，否則轉(zhuǎn)到第二步；第二步：將新增加的約束條件方程加上松弛變量或減去多余變量使

3、其化為等式，再把這個(gè)等式方程的系數(shù)補(bǔ)加到原模型的最優(yōu)單純形表中；第三步：另原來(lái)的基變量和新增加的松弛變量或多余變量作為新的基變量；第四步：對(duì)新的單純形表進(jìn)行初等變換，使新基變量的系數(shù)矩陣變?yōu)閱挝痪仃?，此時(shí)可以得到一個(gè)滿足最優(yōu)檢驗(yàn)但不一定滿足非負(fù)約束的可行解；第五步：利用對(duì)偶單純形法繼續(xù)迭代求解。5、設(shè)有一閉回路如下所示，UhUjVjVj是圖中基變量對(duì)應(yīng)的位勢(shì)。證明：對(duì)于非基變量xj而言，其對(duì)應(yīng)的檢驗(yàn)數(shù)為入=5 -Ui -Vj。非基變量基變量xijxijxijxij基變量 1基變量證明：因?yàn)閬V3了？門是基變量，由已知條件有以下方程：ui vj，ui vj =9j，ui vj =cij根據(jù)閉回路法

4、，非基變量的檢驗(yàn)數(shù)為 =（q +與,）-（*,+%） =cj-*,+了-q,j 即： 入 =cj -ui - Vj +u； +Vj -Ui -vj = cj -ui - vj故證得九j =Cij Ui Vj o n n6、針對(duì)目標(biāo)函數(shù)求最大值maxz = 倒面的非標(biāo)準(zhǔn)指派問(wèn)題，如何處理？ i 4 j 4解析：令bj =M -Cj ,其中M是足夠大的常數(shù)，這樣，原有的系數(shù)矩陣 C就變?yōu)樾碌膎 n系數(shù)矩陣B =也），目標(biāo)函數(shù)變?yōu)閙in z = Z卻面，由M是足夠大的常數(shù)可知，m j Tbij 0,這已符合匈牙利法的條件，所以使得新目標(biāo)函數(shù)達(dá)到最小的最優(yōu)解即為 原有目標(biāo)函數(shù)達(dá)到最大的最優(yōu)解。7、寫(xiě)出

5、下列圖形的鄰接矩陣，并說(shuō)明有何特征？解析：鄰接矩陣如下:Vl V2 V3 V4 V5Vi 0 1 0 1 2V2 1 0A = V3 0 0V4 11V5200 1 00 1 01 0 10 1 0可知無(wú)向鄰接矩陣的特點(diǎn)為:對(duì)角線上元素均為0,同時(shí)鄰接矩陣也是對(duì)稱矩陣;每行或每列的數(shù)據(jù)之和對(duì)應(yīng)頂點(diǎn)的邊的數(shù)量；鄰接矩陣比關(guān)聯(lián)矩陣小。8、利用標(biāo)號(hào)法尋找增流鏈，旁邊數(shù)據(jù)是邊的容量與流量，如下網(wǎng)絡(luò)圖G中，假設(shè)將x標(biāo)號(hào)為(0,+,+比),要求在網(wǎng)絡(luò)圖G中畫(huà)出全部標(biāo)號(hào)結(jié)果。解析:首先給起點(diǎn)x標(biāo)號(hào)為(0,+,五c),邊(x,V1)為前向邊，l(x,V1)= 10-5 = 5,則l (M) = min ll

6、(x),l (x,V1)= min-二,5)= 5對(duì)標(biāo)號(hào)(x,+,5)，頂點(diǎn)V1沒(méi)有后續(xù)邊，停止。邊(x,V2)為前向邊，l(x,V2)= 9-7 = 2 , 則l(v2) = min il (x),l(x, v2 = min t：；3,2) = 2對(duì)V2標(biāo)號(hào)(x,+,2),頂點(diǎn)V2有后續(xù)邊，繼續(xù)標(biāo)號(hào)。邊(V2,V3)為后向邊，l(V2,V3)=1, 則l (v3) = min ll(v2),l (v2,v3 = min 12,1 = 1對(duì)V3標(biāo)號(hào)(V2 ,-，1),頂點(diǎn)V3有后續(xù)邊，繼續(xù)標(biāo)號(hào)。邊(V3,V4)為后向邊，l (V3, V4) =6-3=3,則l (v4) = min ll(v3

7、),l (v3,v4) = min 11,3)= 1對(duì)V4標(biāo)號(hào)”3,十,1),頂點(diǎn)V4沒(méi)有后續(xù)邊，停止，至此全部標(biāo)號(hào)完畢，標(biāo)號(hào)結(jié)果如 下圖所示：（0,二）（x, ,2）9、假設(shè)某統(tǒng)籌圖的關(guān)鍵線路有3條，如果有一個(gè)非共有的關(guān)鍵工序時(shí)間延長(zhǎng)，會(huì)不會(huì)改變關(guān)鍵路線的狀態(tài)，為什么？解析：若該非關(guān)鍵工序的工序時(shí)間延長(zhǎng)后不超過(guò)關(guān)鍵工序的工序時(shí)間，那么統(tǒng)籌圖的關(guān)鍵路線不變；若該非關(guān)鍵工序的工序時(shí)間延長(zhǎng)后超過(guò)關(guān)鍵工序的工序時(shí)間，那么統(tǒng)籌圖的關(guān)鍵路線變?yōu)樵撀肪€。10、簡(jiǎn)述（M /M /C）: （N/8/FCFS）模型有何特征？解析：顧客到達(dá)時(shí)間間隔和服務(wù)員服務(wù)時(shí)間都服從指數(shù)分布；該系統(tǒng)有C個(gè)服務(wù)員；系統(tǒng)可以容納N

8、個(gè)顧客；顧客來(lái)源總體數(shù)目是無(wú)限多；排隊(duì)規(guī)則是服從先 到先服務(wù)。具特點(diǎn)是排隊(duì)系統(tǒng)排隊(duì)的顧客數(shù)最多只能有N-C個(gè)，另外，當(dāng)系統(tǒng)的顧客數(shù)達(dá)到N時(shí)，新到達(dá)的顧客數(shù)就不能進(jìn)入系統(tǒng)而自動(dòng)消失。二、 計(jì)算題（60分，共4小題，每小題15分）（答在試卷上的內(nèi)容無(wú)效）max z = x1 5x2 3x3 4x41.某公司利用3種資源，擬生產(chǎn)4種產(chǎn)品，根據(jù)生產(chǎn)約束條件構(gòu)建的線性規(guī)劃 模型如下所示：st2為 +3x2 +x3 +2x4 800 （資源 1） 5xi 4x2 3x3 4x4 1200 （資源 2） 3x1 +4x2 +5x3 +3x4 1000 （資源 3） Xj 之0,j=1,2,3,4設(shè)Xs ,

9、Xg , x?是松弛變量,求解得到該模型的單純性表為:Cj T1534000CbXbbX1X2X3X4X5X6X70X51001/40-13/4011/4-14X420020-2101-15X2100-3/4111/400-3/41zj17/4523/4401/41Cj -zj-13/40-11/400-1/4-1問(wèn)題如下：該公司研制了一種產(chǎn)品，已知該新產(chǎn)品消耗資源1為5,耗用資源2為4,耗用資源3為3,該產(chǎn)品單位利潤(rùn)為6.（1）以新的最優(yōu)生產(chǎn)方案，建立數(shù)學(xué)模型。（5分）（2）利用單純形法的擴(kuò)展應(yīng)用（即增加決策變量的方法），驗(yàn)證說(shuō)明生產(chǎn)此種 新產(chǎn)品是否有利？（不要求計(jì)算得出新方案的最終求解結(jié)果

10、）（10分）解析：（D用決策變量X8表示新產(chǎn)品的生產(chǎn)數(shù)量，新決策變量是原有的模型變?yōu)閙ax z =x1 5x2 3x3 4x46x82x1 +3x2 +x3 +2x4 +5x4 800 （資源 1）t 5x1 +4x2 +3x3 +4x4 +4x4 3) = ：；k 1 = -: 0.3164 = 31.64%4(4)觀眾安檢停留時(shí)間超過(guò)18分鐘的概率：P(T0.3)=eW)=e40J30).3 定 4.98%三、 綜合題(20分，共2小題，每小題10分)(答在試卷上的內(nèi)容無(wú)效).證明：X是原問(wèn)題的可行解，Y是對(duì)偶問(wèn)題的可行解，當(dāng)CX=bTY時(shí)，X和 Y就分別是各自問(wèn)題的最優(yōu)解。證明：對(duì)偶問(wèn)題的任意一個(gè)可行解Y都有CX bTY再由前提條件CX =bTY ,有bTY = bTY即Ymy,可見(jiàn)Y是對(duì)偶問(wèn)題的目標(biāo)函數(shù)取值最小的可行解，因此Y是最優(yōu)解。同樣也可證明，對(duì)于原問(wèn)題的任意一個(gè)可行解 X，都有CX 三 bTY再由前提條件CX =bTY ,有CX -CX即X EX,可見(jiàn)X是使原問(wèn)題的目標(biāo)函數(shù)取值最大的可行解， 因此又是最優(yōu)解。.某工廠生產(chǎn)長(zhǎng)度為60個(gè)單位長(zhǎng)度的標(biāo)準(zhǔn)玻璃紙，現(xiàn)需要將這種玻璃紙截成長(zhǎng) 度分別為28, 20和15個(gè)單位長(zhǎng)的三種規(guī)格產(chǎn)品。已知它們的市場(chǎng)需求分別 為30、60和80卷。問(wèn)該如何裁剪，以滿足市場(chǎng)需要所消耗的標(biāo)準(zhǔn)玻璃紙最 少。(要求建立數(shù)學(xué)模型但不用求