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

1、運(yùn)籌學(xué)期末考試題（a卷）注意事項：1、答題前，考生務(wù)必將自己的姓名、班級填寫在答題卡上。2、答案用鋼筆或圓珠筆寫在答題卡上，答在試卷上不給分。3、考試結(jié)束，將試卷和答題卡一并交回。一、 單項選擇題(每小題1分，共10分)1：在下面的數(shù)學(xué)模型中，屬于線性規(guī)劃模型的為（ ） 2線性規(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人工變量 4：若線性規(guī)劃問題的最優(yōu)解同時在可行解域

2、的兩個頂點(diǎn)處達(dá)到，那么該線性規(guī)劃問題最優(yōu)解為（ ）A.兩個 B.零個 C.無窮多個 D.有限多個5：原問題與對偶問題的最優(yōu)（ ）相同。 A解 B目標(biāo)值 C 解結(jié)構(gòu) D解的分量個數(shù)6：若原問題中為自由變量，那么對偶問題中的第個約束一定為 （ ） A等式約束 B“”型約束 C“”約束 D無法確定      7：若運(yùn)輸問題已求得最優(yōu)解，此時所求出的檢驗數(shù)一定是全部（ ）                     A小于或等于零 B大于零 C小于零 D大于

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

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

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

6、最短路問題，根據(jù)問題的不同分為定步數(shù)問題和不定步數(shù)問題；對不定步數(shù)問題，用迭代法求解，有_迭代法和_迭代法兩種方法。6：在圖論方法中，通常用_表示人們研究的對象，用_表示對象之間的某聯(lián)系。7：一個_且_的圖稱為樹。四、計算題（每小題15分，45分）1：考慮線性規(guī)劃問題：（a）：寫出其對偶問題；（b）：用單純形方法求解原問題；（c）：用對偶單純形方法求解其對偶問題；（d）：比較（b）（c）計算結(jié)果。2：某公司打算在三個不同的地區(qū)設(shè)置4個銷售點(diǎn)，根據(jù)市場預(yù)測部門的估計，在不同的地區(qū)設(shè)置不同數(shù)量的銷售店，每月可得到的利潤如下表所示。試問各個地區(qū)應(yīng)如何設(shè)置銷售店，才能使每月獲得的總利潤最大？其值是多少

7、？銷售店利潤地區(qū)0 1 2 3 41230 16 25 30 320 12 17 21 220 10 14 16 173：對下圖中的網(wǎng)絡(luò)，分別用破圈法和生長法求最短樹。 五、簡答題(每小題10分，共20分)1試述單純形法的計算步驟，并說明如何在單純形表上判斷問題是具有唯一最優(yōu)解、無窮多最優(yōu)解和無有限最優(yōu)解。 2簡述最小費(fèi)用最大流問題的提法以及用對偶法求解最小費(fèi)用最大流的原理和步驟。甘肅政法學(xué)院20082009學(xué)年度第一學(xué)期運(yùn)籌學(xué)期末考試參考答案及評分標(biāo)準(zhǔn)（a卷）單項選擇題(每小題1分，共10分)1.B     2.B   

8、3.C    4.C     5.B     6.A     7.D    8.D    9.A   10.D 判斷題（每小題1分，共10分）1.T     2.F    3.T    4.F     5.T 

9、    6.T     7.F    8.T    9.F   10.F 填空題（每空1分，共15分）1：基本可行解、可行基；2：右端常數(shù)、最小化問題；3：不含閉回路；4：最優(yōu)目標(biāo)函數(shù)、最優(yōu)策略、最優(yōu)路線、最優(yōu)目標(biāo)函數(shù)值；5：函數(shù)、策略；6：點(diǎn)、邊；7：無圈、連通。計算題（每小題15分，45分）1：解 a）：其對偶問題為 -（3分）b）：用單純形方法求解原問題時每步迭代結(jié)果：原問題解第一步第二步第三步（0，0，0，60，40，80）（0

10、，15，0，0，25，35）（0，20/3，50/3，0，0，80/3） -（5分）c）：用對偶單純形方法求解對偶問題時每步迭代結(jié)果：對偶問題問題解第一步第二步第三步（0，0，0，-2，-4，-3）（1，0，0，1，0，-1）（5/6，2/3，0，11/6，0，0） -（5分）d）：對偶問題的實質(zhì)是將單純形法應(yīng)用于對偶問題的求解，又對偶問題的對偶即原問題，因此（b）、（c）的計算結(jié)果完全相同。 -(2分)2：解 該問題可以作為三段決策問題，對1，2，3地區(qū)分別設(shè)置銷售店形成1，2，3三個階段。 表示給地區(qū)k設(shè)置銷售店時擁有分配的數(shù)量，表示給地區(qū)k設(shè)置銷售店的數(shù)量。狀態(tài)轉(zhuǎn)移方程為：；階段效應(yīng)題中

11、表所示；目標(biāo)函數(shù)：； 其中表示在k地區(qū)設(shè)置個銷售店時的收益； -（3分）首先逆序求解條件最有目標(biāo)函數(shù)值集合和條件最有決策集合：時， 其中于是有：, , , .-（3分）時，,于是有：, . -（3分）時，于是有： .-（3分）因此，最優(yōu)的分配方案所能得到的最大利潤位47，分配方案可由計算結(jié)果反向查出得：。即為地區(qū)1設(shè)置兩個銷售店，地區(qū)2設(shè)置1各銷售店，地區(qū)3設(shè)置1個銷售店。 -（3分）3：解 破圈法（1）：取圈，去掉邊。（2）：取圈，去掉邊。（3）：取圈，去掉邊。（4）：取圈，去掉邊。在圖中已無圈，此時，而，因此所得的是最短樹。結(jié)果如下圖，其樹的總長度為12。 .-（6分） .-（3分）生長法

12、根據(jù)生長法的基本原理，得以下計算表 26389389535315133據(jù)此也得到與破圈法相同的最短樹。 .-（6分）簡答題(每小題10分，共20分)1：單純形法的計算步驟 第一步：找出初始可行解，建立初始單純形表。 第二步：判斷最優(yōu)，檢驗各非基變量的檢驗數(shù)。（1） 若所有的，則基B為最優(yōu)基，相應(yīng)的基可行解即為基本最優(yōu)解，計算停止。（2） 若所有的檢驗數(shù)，又存在某個非基變量的檢驗數(shù)所有的，則線性規(guī)劃問題有無窮多最優(yōu)解。（3） 若有某個非基變量的檢驗數(shù)，并且所對應(yīng)的列向量的全部分量都非正，則該線性規(guī)劃問題的目標(biāo)函數(shù)值無上界，既無界解，停止計算。第三步：換基迭代（1） 當(dāng)存在，選進(jìn)基來改善目標(biāo)函數(shù)。

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