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

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

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

3、#215; 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：圖解法和單純形法雖然求解的形式不同，但從幾何上理解，兩者是一致的。2：?jiǎn)渭冃畏ǖ牡?jì)算過程是從一個(gè)可行解轉(zhuǎn)換到目標(biāo)函數(shù)值更大的另一個(gè)

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

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

6、序求 _最優(yōu)策略、 _、_最優(yōu)路線 _和 _最優(yōu)目標(biāo)函數(shù)值 _。5：工程路線問題也稱為最短路問題，根據(jù)問題的不同分為定步數(shù)問題和不定步數(shù)問題；對(duì)不定步數(shù)問題，用迭代法求解，有_函數(shù) _迭代法和 _策略 _迭代法兩種方法。6：在圖論方法中，通常用_點(diǎn) _表示人們研究的對(duì)象，用_邊 _表示對(duì)象之間的某種聯(lián)系。7：一個(gè) _無圈 _且 _連通 _的圖稱為樹。四、計(jì)算題（每小題15 分， 45 分）1：考慮線性規(guī)劃問題：max z2 x1 4x23x33x1 4x22x3602x1x22x340s. t .3x22x380x1x1, x2 , x30（a）：寫出其對(duì)偶問題；（b）：用單純形方法求解原問題

7、；（c）：用對(duì)偶單純形方法求解其對(duì)偶問題；（d）：比較（ b）（ c）計(jì)算結(jié)果。1：解 a）：其對(duì)偶問題為minz60 y140 y280 y33y12 y2y32s. t.4 y1y2y342 y12y2 2 y33y1 , 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，

8、 0， 1， 0， -1）第三步（ 5/6， 2/3， 0， 11/6， 0，0）-（ 5分）d）：對(duì)偶問題的實(shí)質(zhì)是將單純形法應(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è)置銷售店，才能使每月獲得的總利潤(rùn)最大？其值是多少？銷利售0店潤(rùn)1地2區(qū)341021632530320121721220101416172：解該問題可以作為三段決策問題，對(duì)1， 2， 3 地區(qū)分別設(shè)置銷售店形成1，2

9、，3 三個(gè)階段。xk 表示給地區(qū) k 設(shè)置銷售店時(shí)擁有分配的數(shù)量，uk 表示給地區(qū)k 設(shè)置銷售店的數(shù)量。狀 態(tài) 轉(zhuǎn) 移 方 程 為 ： xk 1xkuk ； 階 段 效 應(yīng) 題 中 表 所 示 ； 目 標(biāo) 函 數(shù) ：3gk (uk ) ； 其中 gk (uk ) 表示在 k 地區(qū)設(shè)置 uk 個(gè)銷售店時(shí)的收益；max Rk1- （ 3 分）首先逆序求解條件最有目標(biāo)函數(shù)值集合和條件最有決策集合：k3時(shí)， 0x34, 0u3x3 ,f3 ( x3 )max g3 (u3 )f 4 ( x4 ) ， 其中u3f4 (x4 ) 0于是有：f3 (0)g3 (0)0,u'3 (0)0,f3 (1)

10、g3 (1)10,u'3 (1)1,f3 (2)g3 (2)14,u '3 (2)2,f3 (3) g3 (3) 16,u '3 (3)3 ,f 3 (4)g3 (4)17,u '3 (4)4.- （ 3 分）k2時(shí)， 0x24, 0 u2x2 ,f2 (x2 )max g2 (u2 )f3 (x3 ) ,0u2 x2于是有：f2 (0)max g2 (u2 )f 3 ( x3 )0, u'2 (0)0 ,0 u20f2 (1)max g2 (u2 )f 3 ( x3 )12,u'2 (1)1,0 u21f 2 (2)max g2 (u2 )f

11、3 ( x3 )22,u'2 (2)1,0 u22f2 (3)max g2 (u2 )f3 ( x3 )27,u'2 (3)2,0 u2 3f2 (4)max g2 (u2 ) f3 ( x3 )31,u'2 (4) 2 or 3 .0u2 4- （ 3 分）k 3時(shí)， x1 4, 0u1x14,于是有：f1 (4)max g10 u14(u1 )f2(x2 )47, u'1 (4)2.- （ 3 分）因此， 最優(yōu)的分配方案所能得到的最大利潤(rùn)位出得：47，分配方案可由計(jì)算結(jié)果反向查u*1 (4)2, u*2 (2)1, u*3 (1)1 。即為地區(qū)1 設(shè)置兩個(gè)銷

12、售店，地區(qū)2 設(shè)置1 各銷售店，地區(qū)3 設(shè)置1 個(gè)銷售店。3：對(duì)下圖中的網(wǎng)絡(luò)，分別用破圈法和生長(zhǎng)法求最短樹。3：解破圈法（ 1）：取圈 v1 ,v2 , v3 , v1 ，去掉邊 v1, v3 。（ 2）：取圈 v2 ,v4 , v3 , v2 ，去掉邊 v2 , v4 。（ 3）：取圈 v2 ,v3 , v5 ,v2 ，去掉邊 v2 , v5 。（ 4）：取圈 v3 , v4 ,v5 , v5 , v3 ，去掉邊 v3 , v4 。在圖中已無圈，此時(shí)，p 6 ，而 qp 1 5 ，因此所得的是最短樹。結(jié)果如下圖，其樹的總長(zhǎng)度為 12。.- （6分）.- （ 3 分）生長(zhǎng)法根據(jù)生長(zhǎng)法的基本原理

13、，得以下計(jì)算表v2v3v4v5v626S1v2389S2389v353S353v51S451v63S53據(jù)此也得到與破圈法相同的最短樹。.- （ 6 分）五、簡(jiǎn)答題 ( 每小題 10 分，共 20 分 )1試述單純形法的計(jì)算步驟，并說明如何在單純形表上判斷問題是具有唯一最優(yōu)解、無窮多最優(yōu)解和無有限最優(yōu)解。解： 1：?jiǎn)渭冃畏ǖ挠?jì)算步驟第一步：找出初始可行解，建立初始單純形表。xj 的檢驗(yàn)數(shù) jCB1 PCj 。第二步：判斷最優(yōu)，檢驗(yàn)各非基變量Bj若所有的 j0 ，則基 B 為最優(yōu)基，相應(yīng)的基可行解即為基本最優(yōu)解，計(jì)算停止。若所有的檢驗(yàn)數(shù)題有無窮多最優(yōu)解。j0 ，又存在某個(gè)非基變量的檢驗(yàn)數(shù)所有的k

14、0 ，則線性規(guī)劃問若有某個(gè)非基變量的檢驗(yàn)數(shù)j0 ，并且所對(duì)應(yīng)的列向量的全部分量都非正，則該線性規(guī)劃問題的目標(biāo)函數(shù)值無上界，既無界解，停止計(jì)算。第三步：換基迭代當(dāng)存在k0 ，選 xk 進(jìn)基來改善目標(biāo)函數(shù)。若檢驗(yàn)數(shù)大于0 的非基變量不止一個(gè)，則可以任選其中之一來作為進(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ò)的物流、能量流或信息流等流量最大的問題。如果已知流過弧(vi , vj ) 的單位流量要發(fā)生 cij 的費(fèi)用，要求使總費(fèi)用為最小的最大流流量分配方法。即在上述最大流問題上還應(yīng)增加關(guān)于費(fèi)用的目標(biāo)：種問題稱為最小費(fèi)用最大流問題。模型可以描述為：minxij cij 。這minxij cijmaxffisxijx ji0is, ts. t . jjfit0 xij bij采用對(duì)偶法求解最大流最小費(fèi)用問題，其原理為： 用福德富克遜算法求出網(wǎng)絡(luò)的最大流量，然后用Ford 算法找出從起點(diǎn)vs 到終點(diǎn) vt 的最短增廣鏈。在該增廣鏈上，找出最大調(diào)整量 ，并調(diào)整流量，得到一個(gè)可行流。則此可行流的費(fèi)用最小。如果此時(shí)流量等