運籌學2016年學年期末考試題A卷及答案解析

1、WORD格式整理版學習好幫手運籌學2015年學年第二學期期末考試題（a卷）注意事項：1、答題前，考生務必將自己的姓名、班級填寫在答題卡上2、答案用鋼筆或圓珠筆寫在答題卡上，答在試卷上不給分D .無法確定3、考試結束，將試卷和答題卡一并交回。單項選擇題（每小題1分，共10分）1:在下面的數(shù)學模型中，屬于線性規(guī)劃模型的為（)max S =4X +YminS=3X 十丫max2 2S = X2 +Y2minS=2XYA. st.XY <3B.<s.t.2X -丫 工一1C. s.t.X Y 蘭 2D.<st.X +Y 33X,Y A0X, Y X01X,Y Z0X,Y ±

2、02.線性規(guī)劃冋題若有最優(yōu)解,則定可以在可行域的（）上達到。A.內點B頂點C.外點D.幾何點3:在線性規(guī)劃模型中，沒有非負約束的變量稱為()A.多余變量B.松弛變量C.自由變量D.人工變量A.兩個B.零個C.無窮多個D.有限多個5:原問題與對偶問題的最優(yōu)（）相同。A.解B目標值C.解結構D.解的分量個數(shù)6:若原冋題中Xi為自由變量，那么對偶問題中的第i個約束定為 （）4:若線性規(guī)劃問題的最優(yōu)解同時在可行解域的兩個頂點處達到，那么該線性規(guī)劃問題最優(yōu) 解為（）A.等式約束B .“W ”型約束 C”約束7:若運輸問題已求得最優(yōu)解，此時所求出的檢驗數(shù)一定是全部（ ）A.小于或等于零 B .大于零C .

3、小于零D大于或等于零&對于m個發(fā)點、n個收點的運輸問題，敘述錯誤的是（）B.該問題的系數(shù)矩陣有 m+n行D.該問題的最優(yōu)解必唯一）A.該問題的系數(shù)矩陣有mX n列C.該問題的系數(shù)矩陣的秩必為m+n-19:關于動態(tài)規(guī)劃問題的下列命題中錯誤的是（B狀態(tài)對決策有影響C動態(tài)規(guī)劃中，定義狀態(tài)時應保證在各個階段中所做決策的相對獨立性A、動態(tài)規(guī)劃分階段順序不同，則結果不同 B狀態(tài)對決策有影響D動態(tài)規(guī)劃的求解過程都可以用列表形式實現(xiàn)10:若P為網(wǎng)絡G的一條流量增廣鏈，則P中所有正向弧都為6的（）A.對邊B.飽和邊C.鄰邊D.不飽和邊二、判斷題（每小題1分，共10 分）1:圖解法和單純形法雖然求解的形式

4、不同，但從幾何上理解，兩者是一致的。（V）2:單純形法的迭代計算過程是從一個可行解轉換到目標函數(shù)值更大的另一個可行解。（X ）3: 旦一個人工變量在迭代中變?yōu)榉腔兞亢?，該變量及相應列的?shù)字可以從單純形表中 刪除，而不影響計算結果。（V ）4:若線性規(guī)劃問題中的bi，Cj值同時發(fā)生改變，反映到最終單純形表中，不會出現(xiàn)原問題與對偶問題均為非可行基的情況。（X）5:若線性規(guī)劃的原問題有無窮多最優(yōu)解，則其對偶問題也一定具有無窮多最優(yōu)解。（V ）6:運輸問題的表上作業(yè)法實質上就是求解運輸問題的單純形法。（V ）7:對于動態(tài)規(guī)劃問題，應用順推或逆推解法可能會得出不同的最優(yōu)解。（X ）&動態(tài)規(guī)劃的

5、基本方程是將一個多階段的決策問題轉化為一系列具有遞推關系的單階段的 決策問題。（V ）9:圖論中的圖不僅反映了研究對象之間的關系，而且是真實圖形的寫照，因而對圖中點與 點的相對位置、點與點連線的長短曲直等都要嚴格注意。（X ）10：網(wǎng)絡最短路線問題和最短樹問題實質上是一個問題。（X ）三、填空題（每空1分，共15分）1:線性規(guī)劃中，滿足非負條件的基本解稱為 基本可行解 ,對應的基稱為 可行基2:線性規(guī)劃的目標函數(shù)的系數(shù)是其對偶問題的右端常數(shù) ;而若線性規(guī)劃為最大化問題，則對偶問題為 最小化問題 。3：在運輸問題模型中，m + n-1個變量構成基變量的充要條件是 _不含閉回路 。4：動態(tài)規(guī)劃方法

6、的步驟可以總結為：逆序求解 最優(yōu)目標函數(shù) ，順序求最優(yōu)策略、 最優(yōu)路線和最優(yōu)目標函數(shù)值 。5： 工程路線問題也稱為最短路問題，根據(jù)問題的不同分為定步數(shù)問題和不定步數(shù)問題；對不定步數(shù)問題，用迭代法求解，有 函數(shù)迭代法和策略迭代法兩種方法。6:在圖論方法中，通常用 點表示人們研究的對象，用 邊表示對象之間的某種聯(lián)系。7: 一個無圈_且連通的圖稱為樹。四、計算題（每小題 15分，45 分） 1:考慮線性規(guī)劃問題：max z = 2x 4x2 3x3"3X! +4x2 +2x3 蘭 602音 + x2 +2x3 蘭 40 s. t.捲+ 3冷+ 2x3蘭80為，X2,x3 _0（a）:寫出其

7、對偶問題；（b）：用單純形方法求解原問題；（c）:用對偶單純形方法求解其對偶問題；（d）：比較（b）（ c）計算結果。1：解a ）：其對偶問題為mins. t. <z=60y）+40y2 +80y3 ”3% +2y? + y3 X24% + y 3y 42% +2y2 +2y3 2 3y1,y2,y0分）b）：用單純形方法求解原問題時每步迭代結果:原問題解第一步（0， 0， 0， 60， 40， 80）第二步（0， 15， 0， 0， 25， 35）第三步（0，20/3，50/3，0，0，80/3 ）-（5分）c）:用對偶單純形方法求解對偶問題時每步迭代結果：對偶問題問題解第一步（0,

8、0，0, -2，-4，-3 ）第二步（1，0，0，1，0，-1）第三步（5/6，2/3，0，11/6，0，0）（5分）d）：對偶問題的實質是將單純形法應用于對偶問題的求解，又對偶問題的對偶即原問題，因此（b）、（c）的計算結果完全相同。（2分）2:某公司打算在三個不同的地區(qū)設置4個銷售點，根據(jù)市場預測部門的估計，在不同的地區(qū)設置不同數(shù)量的銷售店，每月可得到的利潤如下表所示。試問各個地區(qū)應如何設置銷區(qū)341021632530320121721220101416172:解該問題可以作為三段決策問題，對1, 2, 3地區(qū)分別設置銷售店形成1 , 2,3三個階段。xk表示給地區(qū)k設置銷售店時擁有分配的

9、數(shù)量，uk表示給地區(qū)k設置銷售店的數(shù)量。狀態(tài)轉移方程為：Xk+=Xk-Uk ；階段效應題中表所示；目標函數(shù)：3max R=：Z gk（Uk）；其中gk（uQ表示在 k地區(qū)設置Uk個銷售店時的收益；k=1（3 分）首先逆序求解條件取有目標函數(shù)值集合和條件取有決策集合：k=3時，0 蘭X3 蘭 4, 0 蘭 U3 蘭怡，f3（X3）=maxg3（U3）+ f4（xj，其中u3f4（X4）=0于是有：f3（o）=g3（o）=o,u3（o）=o,f3（i） = g3（i） = io,u3（i） = i.f3（2） =g3（2） =14,u'3（2） =2,f3（ 3） =g3 （3） =16,

10、u'3 （3） =3,f3=g3 =17,u3（4）=4.-（3 分）k =2時，0 遼 x2 <4, Q < u2 乞 x2, f2（x2） = maxg2（u2） f3（x3）,0蟲2纟2于是有：f2（0muax gzU） f3（X3） =0, u 2（0） =0 ,f2（i）=腫£氣92（氏）f3（x3） =12, U2（i）=i,f2（2）二 muaxg2（u2） f?%） =22, u'2=i,f2 （3）max g2（U2） f3（X3） = 27, u'2 （3） =2,0 2 3f2（4） =maxg2（U2）"3（X3）

11、 =31, u'2（4） =2 or 3.02超（3 分）k = 3時，為=4, 0_山_為=4, 于是有：辦二maxgi（5） f2（x2” =47, u=2.（3分）因此，最優(yōu)的分配方案所能得到的最大利潤位47,分配方案可由計算結果反向查出得：口1（4） =2, u 2（2） =1, u 3 （1）=1。即為地區(qū)1設置兩個銷售店,地區(qū)2設置1各銷售店，地區(qū) 3設置1個銷售店。3:對下圖中的網(wǎng)絡，分別用破圈法和生長法求最短樹。3:解破圈法（1）：取圈 WMWV1，去掉邊vz。（2）：取圈 V2,V4,V3,V2，去掉邊V2,V4（3）：取圈 V2,V3,V5,V2，去掉邊V2,V5。

12、（ 4）:取圈 V3,V4,V5,V5,V3，去掉邊V3,V4。在圖中已無圈，此時，p=6，而qnp15，因此所得的是最短樹。結果如下圖,其樹的總長度為 12。（6分）(3生長法根據(jù)生長法的基本原理，得以下計算表V2V3V4V5VSi26COO0O0V2389QOS2389QOV353QOS353QOV5QO1S451V63S53據(jù)此也得到與破圈法相同的最短樹。-（6分）五、簡答題（每小題10分，共20分）1 試述單純形法的計算步驟，并說明如何在單純形表上判斷問題是具有唯一最優(yōu)解、無 窮多最優(yōu)解和無有限最優(yōu)解。解：1:單純形法的計算步驟第一步：找出初始可行解，建立初始單純形表。第二步：判斷最優(yōu)

13、，檢驗各非基變量Xj的檢驗數(shù)匚j =CBB Pj c若所有的Cr0，則基B為最優(yōu)基，相應的基可行解即為基本最優(yōu)解，計算停止。若所有的檢驗數(shù)- 0，又存在某個非基變量的檢驗數(shù)所有的二k = 0，則線性規(guī)劃問題有無窮多最優(yōu)解。若有某個非基變量的檢驗數(shù) 0，并且所對應的列向量的全部分量都非正，則該線性規(guī)劃問題的目標函數(shù)值無上界，既無界解，停止計算。第三步：換基迭代當存在二k 0，選Xk進基來改善目標函數(shù)。若檢驗數(shù)大于0的非基變量不止一個，則可以任選其中之一來作為進基變量。進基變量Xk確定后，按最小比值原則選擇出基變量Xr。若比值最小的不止一個，選擇其中之一出基。做主元變換。反復進行上述過程就可以找到

14、最優(yōu)解或判斷出沒有有限最優(yōu)解。（3 分）2 簡述最小費用最大流問題的提法以及用對偶法求解最小費用最大流的原理和步驟。解：2:最大流問題就是在一定條件下，要求流過網(wǎng)絡的物流、能量流或信息流等流量minE XjCij。這最大的問題。如果已知流過弧（V ,Vj）的單位流量要發(fā)生Cij的費用，要求使總費用為最小的最大流流量分配方法。即在上述最大流問題上還應增加關于費用的目標:種問題稱為最小費用最大流問題。模型可以描述為：min、% cmax fF 卩送対送勺才0s.tj jj0 < Xj < bj采用對偶法求解最大流最小費用問題，其原理為：用福德一富克遜算法求出網(wǎng)絡的最大 流量，然后用Ford算法找出從起點Vs到終點Vt的最短增廣鏈。在該增廣鏈上，找出最大調 整量；，并調整流量，得到一個可行流。則此可行流的費用最小。如果此時流量等于最大