運(yùn)籌學(xué)2016年學(xué)年期末考試題A卷及答案解析

1、WORD格式整理版學(xué)習(xí)好幫手運(yùn)籌學(xué)2015年學(xué)年第二學(xué)期期末考試題（a卷）注意事項(xiàng)：1、答題前，考生務(wù)必將自己的姓名、班級填寫在答題卡上2、答案用鋼筆或圓珠筆寫在答題卡上，答在試卷上不給分D .無法確定3、考試結(jié)束，將試卷和答題卡一并交回。單項(xiàng)選擇題（每小題1分，共10分）1:在下面的數(shù)學(xué)模型中，屬于線性規(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)解,則定可以在可行域的（）上達(dá)到。A.內(nèi)點(diǎn)B頂點(diǎn)C.外點(diǎn)D.幾何點(diǎn)3:在線性規(guī)劃模型中，沒有非負(fù)約束的變量稱為()A.多余變量B.松弛變量C.自由變量D.人工變量A.兩個(gè)B.零個(gè)C.無窮多個(gè)D.有限多個(gè)5:原問題與對偶問題的最優(yōu)（）相同。A.解B目標(biāo)值C.解結(jié)構(gòu)D.解的分量個(gè)數(shù)6:若原冋題中Xi為自由變量，那么對偶問題中的第i個(gè)約束定為 （）4:若線性規(guī)劃問題的最優(yōu)解同時(shí)在可行解域的兩個(gè)頂點(diǎn)處達(dá)到，那么該線性規(guī)劃問題最優(yōu) 解為（）A.等式約束B .“W ”型約束 C”約束7:若運(yùn)輸問題已求得最優(yōu)解，此時(shí)所求出的檢驗(yàn)數(shù)一定是全部（ ）A.小于或等于零 B .大于零C .

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

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

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

6、的步驟可以總結(jié)為：逆序求解 最優(yōu)目標(biāo)函數(shù) ，順序求最優(yōu)策略、 最優(yōu)路線和最優(yōu)目標(biāo)函數(shù)值 。5： 工程路線問題也稱為最短路問題，根據(jù)問題的不同分為定步數(shù)問題和不定步數(shù)問題；對不定步數(shù)問題，用迭代法求解，有 函數(shù)迭代法和策略迭代法兩種方法。6:在圖論方法中，通常用 點(diǎn)表示人們研究的對象，用 邊表示對象之間的某種聯(lián)系。7: 一個(gè)無圈_且連通的圖稱為樹。四、計(jì)算題（每小題 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）計(jì)算結(jié)果。1：解a ）：其對偶問題為mins. t. <z=60y）+40y2 +80y3 ”3% +2y? + y3 X24% + y 3y 42% +2y2 +2y3 2 3y1,y2,y0分）b）：用單純形方法求解原問題時(shí)每步迭代結(jié)果:原問題解第一步（0， 0， 0， 60， 40， 80）第二步（0， 15， 0， 0， 25， 35）第三步（0，20/3，50/3，0，0，80/3 ）-（5分）c）:用對偶單純形方法求解對偶問題時(shí)每步迭代結(jié)果：對偶問題問題解第一步（0,

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

9、數(shù)量，uk表示給地區(qū)k設(shè)置銷售店的數(shù)量。狀態(tài)轉(zhuǎn)移方程為：Xk+=Xk-Uk ；階段效應(yīng)題中表所示；目標(biāo)函數(shù)：3max R=：Z gk（Uk）；其中g(shù)k（uQ表示在 k地區(qū)設(shè)置Uk個(gè)銷售店時(shí)的收益；k=1（3 分）首先逆序求解條件取有目標(biāo)函數(shù)值集合和條件取有決策集合：k=3時(shí)，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時(shí)，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時(shí)，為=4, 0_山_為=4, 于是有：辦二maxgi（5） f2（x2” =47, u=2.（3分）因此，最優(yōu)的分配方案所能得到的最大利潤位47,分配方案可由計(jì)算結(jié)果反向查出得：口1（4） =2, u 2（2） =1, u 3 （1）=1。即為地區(qū)1設(shè)置兩個(gè)銷售店,地區(qū)2設(shè)置1各銷售店，地區(qū) 3設(shè)置1個(gè)銷售店。3:對下圖中的網(wǎng)絡(luò)，分別用破圈法和生長法求最短樹。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。在圖中已無圈，此時(shí)，p=6，而qnp15，因此所得的是最短樹。結(jié)果如下圖,其樹的總長度為 12。（6分）(3生長法根據(jù)生長法的基本原理，得以下計(jì)算表V2V3V4V5VSi26COO0O0V2389QOS2389QOV353QOS353QOV5QO1S451V63S53據(jù)此也得到與破圈法相同的最短樹。-（6分）五、簡答題（每小題10分，共20分）1 試述單純形法的計(jì)算步驟，并說明如何在單純形表上判斷問題是具有唯一最優(yōu)解、無 窮多最優(yōu)解和無有限最優(yōu)解。解：1:單純形法的計(jì)算步驟第一步：找出初始可行解，建立初始單純形表。第二步：判斷最優(yōu)

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

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