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

一、問答題(70分，共10小題，每小題7分)(答在試卷上的內(nèi)容無效)1.應(yīng)用單純型法求解線性規(guī)劃問題時，出現(xiàn)不可行解的特征是什么？當(dāng)b的值出現(xiàn)負(fù)數(shù)時即表明出現(xiàn)不可行解。。答：規(guī)則如下： xjjj=1 (2)在對偶問題(D)中，目標(biāo)函數(shù)為求minz=mbu。iii=1 (3)在原問題(P)中與bi相應(yīng)的一個約束條件，對應(yīng)著對偶問題(D)的一個變量ui (4)在原問題(P)的每個變量xj對應(yīng)對偶問題(D)的每一個約束條件：若(P)中xj≥0，則(D)中為mauc；若xj為自由變量，則mau=c。iiijiiijii=13.針對增加約束條件方程時，應(yīng)如何應(yīng)用對偶單純型法進(jìn)行求解？答：其步驟如下： (1)檢驗原來的最優(yōu)解是否滿足新增的約束條件，若滿足原最優(yōu)解就是新的最優(yōu)解，否則轉(zhuǎn)第二步； (2)將新增的約束條件方程加上松弛變量或減去多余變量使其化為等式，再把這個等式方程的系數(shù)補加到原模型的最有單純型表中； (3)令原來的基變量和新增的松弛或多余變量作為新的基變量； (4)對新的單純型表進(jìn)行初等變換，使新基的系數(shù)矩陣變?yōu)閱挝痪仃?，此時可以得到一個滿足最優(yōu)檢驗但不一定滿足非負(fù)約束條件的可行解； (5)利用對偶單純型法進(jìn)行迭代求解。答：其目的是在cj和aj不變的前提下并在保證不改變原來最優(yōu)解基變量但基變量取值可以變動的情況下，求出bi值允許變化的范圍。并且是在求出最優(yōu)解以后不必將參數(shù)從頭算起，就知道最優(yōu)解及其目標(biāo)函數(shù)值會發(fā)生什么變化，使決策者只花很少的費用就可以得到優(yōu)解更多的信息。法的主要求解步驟。答：步驟如下： (1)利用差值法或最小值法求出一組初始可行解： (2)用閉回路法或位勢法求檢驗數(shù)，若無負(fù)檢驗數(shù)即得最優(yōu)解，若有，則轉(zhuǎn)第(3)步； (3)利用閉回路法進(jìn)行調(diào)整； (4)重復(fù)第(2)步，直到得到最優(yōu)解。6.分支定界法在滿足什么情況下停止分支？發(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ù)，直到找不出這樣的邊為止。8.簡述平行作業(yè)法在縮短工期時的思路?？棊讉€相同的施工隊，在同一時間、不同的工區(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,如何鑒別其為最小費用流？二、計算題(60分，共4小題，每小題15分)(答在試卷上的內(nèi)容無效)tv2v1s請完成 (1)判斷圖G是否為可行流。(3分) (2)判斷圖G是否為流值為10的最小費用流，若不是，將當(dāng)前網(wǎng)絡(luò)調(diào)整為最小費用流。 (3)求圖G的最小費用最大流。要求計算出總費用。(6分)解析：本題是求最小費用最大流，應(yīng)當(dāng)熟知什么是可行流，掌握求最大流和最小費用最大流解：(1)由于每條邊的流值均滿足容量限制，每個節(jié)點的流量也滿足流量守恒，故此流是 (2)構(gòu)造伴隨網(wǎng)絡(luò)Gf如下：v1tsv2vvtv1,所以不是最小費用流。在增流圈上調(diào)整即具有負(fù)費用的邊正值的邊加上調(diào)整值2得：t8,8,210,6,2v2繼續(xù)構(gòu)造伴隨網(wǎng)絡(luò)圖：v1tssv2此圖已不存在負(fù)費用增流圈。則已求得流值為8×2+2×4+6×2+8×1+2×4=52此圖已不存在負(fù)費用增流圈。則已求得流值為8×2+2×4+6×2+8×1+2×4=52 (3)用標(biāo)號算法求最大流：2v1tsv2tv2vs上圖已找不到增流鏈，故得最大流，流值為12.現(xiàn)構(gòu)造其伴隨網(wǎng)絡(luò)圖：v1t4,-4v2圖中已找不到負(fù)費用增流圈，故得到最小費用最大流，其費用為：8×2+4×4+4×4+4×2+8×1=64。2、某企業(yè)經(jīng)營管理2個加工廠甲和乙，有3個原材料基地以下列數(shù)量供應(yīng)原料：單位運價表(元/t)如下：加工廠加工廠乙原材料基地ABC兩個加工廠的容量及加工費如下：40甲甲450t400元/t乙加工廠容量加工費請完成 (1)試建立該運輸問題的模型。(6分) (2)加工廠出售產(chǎn)品的價格是900元/t，問該企業(yè)如何組織兩個加工廠的生產(chǎn)，使獲得的利潤最大？利潤值是多少？(9分)解析：本題考查的時不平衡運輸問題及表上作業(yè)法。需要注意的是，此時的“運費”包括單檢驗數(shù)的方法有閉回路和位勢法，一般情況下閉回路法較為簡單，不易出錯而位勢法需要求易算錯。解：(1)需要虛設(shè)一個原材料基地D，其供應(yīng)量為50t，得供需平衡表如下：原料ABC加工廠甲乙銷量400DD產(chǎn)量04500用差值法求解(括號中即為運量)：原料ABCD產(chǎn)量加工廠甲 (200) (200) (50)450乙 (100) (400)銷量400用閉回路法非基變量檢驗數(shù)(括號中數(shù)字)如下:乙乙100400甲2002000450原料ABCD產(chǎn)量銷量400加工廠所有檢驗數(shù)都大于0,已得最優(yōu)解為(X11,X21,X22,X32,X41)=(200,200,100,400,50)最大利潤900×900-200×640-200×600-100×510-400×520=303000元.3.下圖所示的運輸網(wǎng)絡(luò)，邊旁數(shù)字表示的最大通行能力。假設(shè)該運輸網(wǎng)絡(luò)中某些節(jié)點有流量6需求，此處已知v需要5個流量。請構(gòu)造分配最大流的新網(wǎng)絡(luò)圖，并分配最大流。65584v766244v24v335解析：本題是有節(jié)點流量限制的最大流分配問題，一般處理方法是將節(jié)點分成兩個節(jié)點中間相連接的邊的權(quán)即為該節(jié)點所需流量；解：將節(jié)點6拆分為v61和v62，新網(wǎng)絡(luò)圖如下：223446345835v24v3571初始可行流為0，用標(biāo)號算法求最大流：25v025v22(0,+∞)v31257,增流鏈vvv1257,v224,05,24v74v16,03繼續(xù)尋找增流鏈：55v22(v(0,+∞)4(0,+∞)4333增流鏈為vvvvv增流鏈為vvvvv調(diào)整量4：v224,05,24v74v16,03繼續(xù)尋找增流鏈：v220,+∞)0,+∞)v1v3145145724,4v4v35v71繼續(xù)尋找增流鏈：55v224,4,+∞),+∞)324,4v4v35v71此時標(biāo)號已無法進(jìn)行，得到最大流，流值為11.4.下圖為統(tǒng)籌網(wǎng)絡(luò)圖，邊旁數(shù)字表示工序名稱和工序時間(天)。cc4fd23a3b1問題如下： (1)利用時間參數(shù)法計算總工期并確定關(guān)鍵路線及關(guān)鍵工序。(6分) (2)通過改進(jìn)措施，使工序c的工序時間減少1天，是否對工程總工期有影響？為什么？ (3分) (4)因為意外原因，使工序b的工序時間延長了2天，工序d的工序時間延長了3天，是否對工程總工期有影響？為什么？(3分)解析：本題是繪制統(tǒng)籌圖相關(guān)的問題。解決本題的步驟是：先繪制完統(tǒng)籌圖，再計算時間參0000解：(1)統(tǒng)籌圖如下：a3b1774d253c4f5 (2)c減少一天，總工期減少一天。因為c是關(guān)鍵工序，并且減少一天并未改變關(guān)鍵路線 (3)b延長兩天對總工期無影響，因為b還未成為關(guān)鍵工序。 (4)b的工序時間延長了2天，工序d的工序時間延長了3天，總工期會增加一天，因為三、綜合題(20分，共2小題，每小題10分)(答在試卷上的內(nèi)容無效)1.已知某種產(chǎn)品有n個銷售點，有m個配送中心可供選擇以實現(xiàn)對該產(chǎn)品的配送。設(shè)在配點對該產(chǎn)品必須得到滿足，設(shè)在銷售點j對該產(chǎn)品的需求量為Dj。從配送中心i到銷售點j的單位產(chǎn)品運費為wij。要求建立整數(shù)規(guī)劃模型，使得運輸成本和配送成本總和最小。解析：此題是整數(shù)規(guī)劃問題中關(guān)于選址的問題，是0-1規(guī)劃問題，是書上(寇偉華版)原題的小改編。ijiiiijijiii=1j=1i=1配送中心配送能力的約束條件為：ijiij=1ii此，為保證每個銷售點的需求都得到滿足，有約束條件方程：ijji=1所以整個模型為：ijijiii=1j=1i=1ii銷地y1產(chǎn)地x15y2y6y34供應(yīng)量yxyxyxyxxxx需求量36768