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

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