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

1、運(yùn)籌學(xué)2015年學(xué)年第二學(xué)期期末考試題（a卷）注意事項(xiàng)：1、答題前，考生務(wù)必將自己的姓名、班級(jí)填寫在答題卡上2、答案用鋼筆或圓珠筆寫在答題卡上，答在試卷上不給分3、考試結(jié)束，將試卷和答題卡一并交回單項(xiàng)選擇題（每小題1分，共10分）maxS X2Y2minS 2XYC. s.t.X Y2D. st.X Y 3X,Y0X,Y 0maxS 4XYminS 3XYA. st.XY3B. s.t.2X Y1X,Y0X,Y0）上達(dá)到。1：在下面的數(shù)學(xué)模型中，屬于線性規(guī)劃模型的為（）2線性規(guī)劃問題若有最優(yōu)解，則一定可以在可行域的（.幾何點(diǎn)A. 內(nèi)點(diǎn) B.頂點(diǎn)C .外點(diǎn)D3:在線性規(guī)劃模型中，沒有非負(fù)約束的變

2、量稱為（）A.多余變量B.松弛變量C. 自由變量D.人工變量4:若線性規(guī)劃問題的最優(yōu)解同時(shí)在可行解域的兩個(gè)頂點(diǎn)處達(dá)到，那么該線性規(guī)劃問題最優(yōu)解為（）A.兩個(gè)B.零個(gè)C.無窮多個(gè)5:原問題與對(duì)偶問題的最優(yōu)（）相同。A .解B .目標(biāo)值C.解結(jié)構(gòu)D.有限多個(gè)D .解的分量個(gè)數(shù)6：若原問題中Xi為自由變量，那么對(duì)偶問題中的第 i個(gè)約束一定為 （）B . “W型約束 C . 約束 D 7:若運(yùn)輸問題已求得最優(yōu)解，此時(shí)所求出的檢驗(yàn)數(shù)一定是全部（ A .小于或等于零B .大于零C.小于零&對(duì)于m個(gè)發(fā)點(diǎn)、n個(gè)收點(diǎn)的運(yùn)輸問題，敘述錯(cuò)誤的是（A.等式約束.無法確定心曰 定是D .大于或等于零）A .該問題的系數(shù)

3、矩陣有 mx n列B .該問題的系數(shù)矩陣有m+n行C.該問題的系數(shù)矩陣的秩必為m+n-1D .該問題的最優(yōu)解必唯一9:關(guān)于動(dòng)態(tài)規(guī)劃問題的下列命題中錯(cuò)誤的是（）A、動(dòng)態(tài)規(guī)劃分階段順序不同，則結(jié)果不同B、狀態(tài)對(duì)決策有影響C、動(dòng)態(tài)規(guī)劃中，定義狀態(tài)時(shí)應(yīng)保證在各個(gè)階段中所做決策的相對(duì)獨(dú)立性D、動(dòng)態(tài)規(guī)劃的求解過程都可以用列表形式實(shí)現(xiàn)10:若P為網(wǎng)絡(luò)G的一條流量增廣鏈，則P中所有正向弧都為 G的（ ）A .對(duì)邊B .飽和邊C.鄰邊D .不飽和邊二、判斷題（每小題1分，共10 分）1:圖解法和單純形法雖然求解的形式不同，但從幾何上理解，兩者是一致的。（V）2:單純形法的迭代計(jì)算過程是從一個(gè)可行解轉(zhuǎn)換到目標(biāo)函數(shù)

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

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

6、題也稱為最短路問題，根據(jù)問題的不同分為定步數(shù)問題和不定步數(shù)問題；對(duì)不定步數(shù)問題，用迭代法求解，有 函數(shù)迭代法和策略迭代法兩種方法。6:在圖論方法中，通常用 點(diǎn)表示人們研究的對(duì)象，用 邊表示對(duì)象之間的某種聯(lián)系。7: 一個(gè)無圈_且連通的圖稱為樹。四、計(jì)算題（每小題 15分，45 分）1:考慮線性規(guī)劃問題：max z2為4X23x33xi4X22x3602xiX22X340s. t.Xi3冷2X380X1,X2,X30(a) ：寫出其對(duì)偶問題；(b) :用單純形方法求解原問題；(c) ：用對(duì)偶單純形方法求解其對(duì)偶問題;(d) :比較(b) ( c)計(jì)算結(jié)果。1：解 a)：其對(duì)偶問題為min z60%

7、40y280y33y12y2y32s. t.4y1y2y342y12y22y33Yi,y2,Y30(3 分)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):用對(duì)偶單純形方法求解對(duì)偶問題時(shí)每步迭代結(jié)果:對(duì)偶問題問題解第一步(0, 0 , 0 , -2 , -4 , -3)第二步(1, 0 , 0 , 1 , 0 , -1)第三步(5/6 , 2/3 , 0 , 11/6 , 0 , 0)(5分)d)：對(duì)偶問題的實(shí)質(zhì)是將單純形

8、法應(yīng)用于對(duì)偶問題的求解，又對(duì)偶問題的對(duì)偶即原問題， 因此(b)、(c)的計(jì)算結(jié)果完全相同。(2分)2:某公司打算在三個(gè)不同的地區(qū)設(shè)置4個(gè)銷售點(diǎn)，根據(jù)市場(chǎng)預(yù)測(cè)部門的估計(jì)，在不同的地區(qū)設(shè)置不同數(shù)量的銷售店，每月可得到的利潤(rùn)如下表所示。試問各個(gè)地區(qū)應(yīng)如何設(shè)置銷2:解 該問題可以作為三段決策問題，對(duì)1, 2, 3地區(qū)分別設(shè)置銷售店形成1 ,2, 3三個(gè)階段。Xk表示給地區(qū)k設(shè)置銷售店時(shí)擁有分配的數(shù)量，Uk表示給地區(qū)k設(shè)置銷售店的數(shù)量。狀態(tài)轉(zhuǎn)移方程為：Xk 1XkUk ；階段效應(yīng)題中表所示；目標(biāo)函數(shù)：3max Rgk(uk)；其中g(shù)k(uk)表示在k地區(qū)設(shè)置uk個(gè)銷售店時(shí)的收益;k 1k 3時(shí)，0 X3

9、4, 0 U3 X3,3（X3） max（U3）U3f4 （X4 ）0于是有：f3（0）g3（0）0,U3 （0）0,f3（1）g3（1）10,U3（1）1,f3（2）g3（2）14,U3 （2）2f4(Xj,其中(3 分)首先逆序求解條件最有目標(biāo)函數(shù)值集合和條件最有決策集合:f3（3）g3（3） 16,u3（3）3,016253032012172122010141617f3（4）g3（4）17, u3（4）（3 分）k 2 時(shí)，0 X24, 0 U2 X2,f2 （X2 ）maxg2（U2） f3（X3）,0 U2 X2于是有:f2（0）0叫3侶（吐）f3（X3）0, U2（0）0,f2（1

10、）max.g2（U2）f3（X3）12,U2（1）1,f2（2）magu）f3（X3）22,U2 （2）1 ,f2（3）max）f3（X3）27,u2 （3）2,f2 （4） max0 U2 492（氏）3（X3）31,u 2（4）2 or 3-（3 分）k 3時(shí)，為4,0U1x（4,于是有：hmax.g1（U1）f2（X2）47, U12.（3 分）因此，最優(yōu)的分配方案所能得到的最大利潤(rùn)位47,分配方案可由計(jì)算結(jié)果反向查出得：u；（4）2, u*2（2）1, u*3（1） 1。即為地區(qū)1設(shè)置兩個(gè)銷售店,地區(qū)2設(shè)置1各銷售店，地區(qū) 3設(shè)置1個(gè)銷售店。3:對(duì)下圖中的網(wǎng)絡(luò)，分別用破圈法和生長(zhǎng)法求最

11、短樹。3:解（1）：取圈 WN2N3M，去掉邊，3】。（2）：取圈 V2,V4,V3,V2，去掉邊V2,V4。（3）：取圈 V2，V3，V5,V2，去掉邊V2，V5。（ 4）:取圈 V3，V4,V5,V5,V3，去掉邊也皿。在圖中已無圈，此時(shí)，p 6，而q p 1 5，因此所得的是最短樹。結(jié)果如下圖，其樹的總長(zhǎng)度為12。.（6分）4（3 分）生長(zhǎng)法根據(jù)生長(zhǎng)法的基本原理，得以下計(jì)算表V2V3V4V5vSi26V2389S2389V353S353v1S451V63S53據(jù)此也得到與破圈法相同的最短樹。- （6分）五、簡(jiǎn)答題（每小題10分，共20分）1 試述單純形法的計(jì)算步驟，并說明如何在單純形表上

12、判斷問題是具有唯一最優(yōu)解、無 窮多最優(yōu)解和無有限最優(yōu)解。解：1:單純形法的計(jì)算步驟第一步：找出初始可行解，建立初始單純形表。CbB1PjCj。x -第二步：判斷最優(yōu)，檢驗(yàn)各非基變量j的檢驗(yàn)數(shù)0若所有的j ，則基b為最優(yōu)基，相應(yīng)的基可行解即為基本最優(yōu)解，計(jì)算停止。若所有的檢驗(yàn)數(shù) j 0 ，又存在某個(gè)非基變量的檢驗(yàn)數(shù)所有的 k 0 ，則線性規(guī)劃問 題有無窮多最優(yōu)解。0若有某個(gè)非基變量的檢驗(yàn)數(shù) j ，并且所對(duì)應(yīng)的列向量的全部分量都非正，則該線 性規(guī)劃問題的目標(biāo)函數(shù)值無上界，既無界解，停止計(jì)算。第三步：換基迭代當(dāng)存在 k 0，選 xk 進(jìn)基來改善目標(biāo)函數(shù)。若檢驗(yàn)數(shù)大于0的非基變量不止一個(gè)，則可以任選其

13、中之一來作為進(jìn)基變量。進(jìn)基變量Xk確定后，按最小比值原則選擇出基變量Xr。若比值最小的不止一個(gè)，選擇其中之一出基。做主元變換。 反復(fù)進(jìn)行上述過程就可以找到最優(yōu)解或判斷出沒有有限最優(yōu)解。 （ 3 分）2 簡(jiǎn)述最小費(fèi)用最大流問題的提法以及用對(duì)偶法求解最小費(fèi)用最大流的原理和步驟。解： 2：最大流問題就是在一定條件下，要求流過網(wǎng)絡(luò)的物流、能量流或信息流等流量 最大的問題。如果已知流過?。╲,vj）的單位流量要發(fā)生Cij的費(fèi)用，要求使總費(fèi)用為最小的最大流流量分配方法。即在上述最大流問題上還應(yīng)增加關(guān)于費(fèi)用的目標(biāo)：min Xijcij 。這種問題稱為最小費(fèi)用最大流問題。模型可以描述為：minXij cijmaX ffisXijXji0i s, ts.t. jjjfit0 Xijbij采用對(duì)偶法求解最大流最小費(fèi)用問題，其原理為：用福德富克遜算法求出網(wǎng)絡(luò)的最大流量，然后用Ford算法找出從起點(diǎn)Vs到終點(diǎn)Vt的最短增廣鏈。在該增廣鏈上，找出最大調(diào) 整量 ，并調(diào)整流量，得到一個(gè)可行流。則此可行流的費(fèi)用最小。如果此時(shí)流量等于最大流 量，則目前的流就是最小費(fèi)用