運籌學(xué)2015學(xué)年期末考試題A卷及答案.doc

.運籌學(xué)2015年學(xué)年第二學(xué)期期末考試題（a卷）注意事項：1、答題前，考生務(wù)必將自己的姓名、班級填寫在答題卡上。2、答案用鋼筆或圓珠筆寫在答題卡上，答在試卷上不給分。3、考試結(jié)束，將試卷和答題卡一并交回。一、 單項選擇題(每小題1分，共10分)1：在下面的數(shù)學(xué)模型中，屬于線性規(guī)劃模型的為（ ） 2線性規(guī)劃問題若有最優(yōu)解，則一定可以在可行域的 （ ）上達(dá)到。 A內(nèi)點 B頂點 C外點 D幾何點3：在線性規(guī)劃模型中，沒有非負(fù)約束的變量稱為 （ ） A多余變量 B松弛變量 C.自由變量 D人工變量4：若線性規(guī)劃問題的最優(yōu)解同時在可行解域的兩個頂點處達(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ōu)解，此時所求出的檢驗數(shù)一定是全部（ ） A小于或等于零 B大于零 C小于零 D大于或等于零8：對于m個發(fā)點、n個收點的運輸問題，敘述錯誤的是( )A該問題的系數(shù)矩陣有mn列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、動態(tài)規(guī)劃的求解過程都可以用列表形式實現(xiàn)10：若P為網(wǎng)絡(luò)G的一條流量增廣鏈，則P中所有正向弧都為G的（ ） A對邊 B飽和邊 C鄰邊 D不飽和邊 二、 判斷題（每小題1分，共10分）1：圖解法和單純形法雖然求解的形式不同，但從幾何上理解，兩者是一致的。（） 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è)法實質(zhì)上就是求解運輸問題的單純形法。（ ） 7：對于動態(tài)規(guī)劃問題，應(yīng)用順推或逆推解法可能會得出不同的最優(yōu)解。（ ） 8：動態(tài)規(guī)劃的基本方程是將一個多階段的決策問題轉(zhuǎn)化為一系列具有遞推關(guān)系的單階段的決策問題。（ ） 9：圖論中的圖不僅反映了研究對象之間的關(guān)系，而且是真實圖形的寫照，因而對圖中點與點的相對位置、點與點連線的長短曲直等都要嚴(yán)格注意。（ ） 10：網(wǎng)絡(luò)最短路線問題和最短樹問題實質(zhì)上是一個問題。（ ）三、 填空題（每空1分，共15分）1：線性規(guī)劃中，滿足非負(fù)條件的基本解稱為_基本可行解_，對應(yīng)的基稱為_可行基_。2：線性規(guī)劃的目標(biāo)函數(shù)的系數(shù)是其對偶問題的_右端常數(shù)_；而若線性規(guī)劃為最大化問題，則對偶問題為_最小化問題_。3：在運輸問題模型中，個變量構(gòu)成基變量的充要條件是_不含閉回路_。4：動態(tài)規(guī)劃方法的步驟可以總結(jié)為：逆序求解_最優(yōu)目標(biāo)函數(shù)_，順序求_最優(yōu)策略、_、_最優(yōu)路線_和_最優(yōu)目標(biāo)函數(shù)值_。5：工程路線問題也稱為最短路問題，根據(jù)問題的不同分為定步數(shù)問題和不定步數(shù)問題；對不定步數(shù)問題，用迭代法求解，有_函數(shù)_迭代法和_策略_迭代法兩種方法。6：在圖論方法中，通常用_點_表示人們研究的對象，用_邊_表示對象之間的某種聯(lián)系。7：一個_無圈_且_連通_的圖稱為樹。四、計算題（每小題15分，45分）1：考慮線性規(guī)劃問題：（a）：寫出其對偶問題；（b）：用單純形方法求解原問題；（c）：用對偶單純形方法求解其對偶問題；（d）：比較（b）（c）計算結(jié)果。1：解 a）：其對偶問題為 -（3分）b）：用單純形方法求解原問題時每步迭代結(jié)果：原問題解第一步第二步第三步（0，0，0，60，40，80）（0，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：某公司打算在三個不同的地區(qū)設(shè)置4個銷售點，根據(jù)市場預(yù)測部門的估計，在不同的地區(qū)設(shè)置不同數(shù)量的銷售店，每月可得到的利潤如下表所示。試問各個地區(qū)應(yīng)如何設(shè)置銷售店，才能使每月獲得的總利潤最大？其值是多少？銷售店利潤地區(qū)0 1 2 3 41230 16 25 30 320 12 17 21 220 10 14 16 172：解 該問題可以作為三段決策問題，對1，2，3地區(qū)分別設(shè)置銷售店形成1，2，3三個階段。 表示給地區(qū)k設(shè)置銷售店時擁有分配的數(shù)量，表示給地區(qū)k設(shè)置銷售店的數(shù)量。狀態(tài)轉(zhuǎn)移方程為：；階段效應(yīng)題中表所示；目標(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：對下圖中的網(wǎng)絡(luò)，分別用破圈法和生長法求最短樹。3：解 破圈法（1）：取圈，去掉邊。（2）：取圈，去掉邊。（3）：取圈，去掉邊。（4）：取圈，去掉邊。在圖中已無圈，此時，而，因此所得的是最短樹。結(jié)果如下圖，其樹的總長度為12。 .-（6分） .-（3分）生長法根據(jù)生長法的基本原理，得以下計算表 26389389535315133據(jù)此也得到與破圈法相同的最短樹。 .-（6分） 五、簡答題(每小題10分，共20分)1試述單純形法的計算步驟，并說明如何在單純形表上判斷問題是具有唯一最優(yōu)解、無窮多最優(yōu)解和無有限最優(yōu)解。解：1：單純形法的計算步驟 第一步：找出初始可行解，建立初始單純形表。 第二步：判斷最優(yōu)，檢驗各非基變量的檢驗數(shù)。若所有的，則基B為最優(yōu)基，相應(yīng)的基可行解即為基本最優(yōu)解，計算停止。若所有的檢驗數(shù)，又存在某個非基變量的檢驗數(shù)所有的，則線性規(guī)劃問題有無窮多最優(yōu)解。若有某個非基變量的檢驗數(shù)，并且所對應(yīng)的列向量的全部分量都非正，則該線性規(guī)劃問題的目標(biāo)函數(shù)值無上界，既無界解，停止計算。第三步：換基迭代當(dāng)存在，選進(jìn)基來改善目標(biāo)函數(shù)。若檢驗數(shù)大于0的非基變量不止一個，則可以任選其中之一來作為進(jìn)基變量。進(jìn)基變量確定后，按最小比值原則選擇出基變量。若比值最小的不止一個，選擇其中之一出基。做主元變換。反復(fù)進(jìn)行上述過程就可以找到最優(yōu)解或判斷出沒有有限最優(yōu)解。 -（3分） 2簡述最小費用最大流問題的提法以及用對偶法求解最小費用最大流的原理和步驟。 解：2：最大流問題就是在一定條件下，要求流過網(wǎng)絡(luò)的物流、能量流或信息流等流量最大的問題。如果已知流過弧的單位流量要發(fā)生的費用，要求使總費用為最小的最大流流量分配方法。即在上述最大流問題上還應(yīng)增加關(guān)于費用的目標(biāo)：。這種問題稱為最小費用最大流問題。模型可以描述為：采用對偶法求解最大流最小費用問題，其原理為：用福德富克遜算法求出網(wǎng)絡(luò)的最大流量，然后用Ford算法找出從起點到終點的最短增廣鏈。在該增廣鏈上，找出最大調(diào)整量，并調(diào)整流量，得到一個可行流。則此可行流的費用最小。如果此時流量等于最大流量，則目前的流就是最小費用最大流，否則應(yīng)繼續(xù)調(diào)整。對偶法的步驟歸納如下：第0步：用