1、運籌學2015年學年第二學期期末考試題（a卷）注意事項：1、答題前，考生務必將自己的姓名、班級填寫在答題卡上。2、答案用鋼筆或圓珠筆寫在答題卡上，答在試卷上不給分。3、考試結束，將試卷和答題卡一并交回。一、 單項選擇題(每小題1分，共10分)1：在下面的數學模型中，屬于線性規劃模型的為（ ） 2線性規劃問題若有最優解，則一定可以在可行域的 （ ）上達到。 A內點 B頂點 C外點 D幾何點 3：在線性規劃模型中，沒有非負約束的變量稱為 （ ）         A多余變量 B松弛變量 C.自由變量 D人工變量 4：若線性規劃問題

2、的最優解同時在可行解域的兩個頂點處達到，那么該線性規劃問題最優解為（ ）A.兩個 B.零個 C.無窮多個 D.有限多個5：原問題與對偶問題的最優（ ）相同。 A解 B目標值 C 解結構 D解的分量個數6：若原問題中為自由變量，那么對偶問題中的第個約束一定為 （ ） A等式約束 B“”型約束 C“”約束 D無法確定      7：若運輸問題已求得最優解，此時所求出的檢驗數一定是全部（ ）                     A小于或等于零 B大

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

4、1：圖解法和單純形法雖然求解的形式不同，但從幾何上理解，兩者是一致的。（） 2：單純形法的迭代計算過程是從一個可行解轉換到目標函數值更大的另一個可行解。（× ） 3：一旦一個人工變量在迭代中變為非基變量后，該變量及相應列的數字可以從單純形表中刪除，而不影響計算結果。（ ） 4：若線性規劃問題中的值同時發生改變，反映到最終單純形表中，不會出現原問題與對偶問題均為非可行基的情況。（×） 5：若線性規劃的原問題有無窮多最優解，則其對偶問題也一定具有無窮多最優解。（ ） 6：運輸問題的表上作業法實質上就是求解運輸問題的單純形法。（ ） 7：對于動態規劃問題，應用順推或逆推解法可能會

5、得出不同的最優解。（× ） 8：動態規劃的基本方程是將一個多階段的決策問題轉化為一系列具有遞推關系的單階段的決策問題。（ ） 9：圖論中的圖不僅反映了研究對象之間的關系，而且是真實圖形的寫照，因而對圖中點與點的相對位置、點與點連線的長短曲直等都要嚴格注意。（× ） 10：網絡最短路線問題和最短樹問題實質上是一個問題。（× ）三、 填空題（每空1分，共15分）1：線性規劃中，滿足非負條件的基本解稱為_基本可行解_，對應的基稱為_可行基_。2：線性規劃的目標函數的系數是其對偶問題的_右端常數_；而若線性規劃為最大化問題，則對偶問題為_最小化問題_。3：在運輸問題模型中

6、，個變量構成基變量的充要條件是_不含閉回路_。4：動態規劃方法的步驟可以總結為：逆序求解_最優目標函數_，順序求_最優策略、_、_最優路線_和_最優目標函數值_。5：工程路線問題也稱為最短路問題，根據問題的不同分為定步數問題和不定步數問題；對不定步數問題，用迭代法求解，有_函數_迭代法和_策略_迭代法兩種方法。6：在圖論方法中，通常用_點_表示人們研究的對象，用_邊_表示對象之間的某種聯系。7：一個_無圈_且_連通_的圖稱為樹。四、計算題（每小題15分，45分）1：考慮線性規劃問題：（a）：寫出其對偶問題；（b）：用單純形方法求解原問題；（c）：用對偶單純形方法求解其對偶問題；（d）：比較（b

7、）（c）計算結果。1：解 a）：其對偶問題為 -（3分）b）：用單純形方法求解原問題時每步迭代結果：原問題解第一步第二步第三步（0，0，0，60，40，80）（0，15，0，0，25，35）（0，20/3，50/3，0，0，80/3） -（5分）c）：用對偶單純形方法求解對偶問題時每步迭代結果：對偶問題問題解第一步第二步第三步（0，0，0，-2，-4，-3）（1，0，0，1，0，-1）（5/6，2/3，0，11/6，0，0） -（5分）d）：對偶問題的實質是將單純形法應用于對偶問題的求解，又對偶問題的對偶即原問題，因此（b）、（c）的計算結果完全相同。 -(2分)2：某公司打算在三個不同的地區

8、設置4個銷售點，根據市場預測部門的估計，在不同的地區設置不同數量的銷售店，每月可得到的利潤如下表所示。試問各個地區應如何設置銷售店，才能使每月獲得的總利潤最大？其值是多少？銷售店利潤地區0 1 2 3 41230 16 25 30 320 12 17 21 220 10 14 16 172：解 該問題可以作為三段決策問題，對1，2，3地區分別設置銷售店形成1，2，3三個階段。 表示給地區k設置銷售店時擁有分配的數量，表示給地區k設置銷售店的數量。狀態轉移方程為：；階段效應題中表所示；目標函數：； 其中表示在k地區設置個銷售店時的收益； -（3分）首先逆序求解條件最有目標函數值集合和條件最有決策

9、集合：時， 其中于是有：, , , .-（3分）時，,于是有：, . -（3分）時，于是有： .-（3分）因此，最優的分配方案所能得到的最大利潤位47，分配方案可由計算結果反向查出得：。即為地區1設置兩個銷售店，地區2設置1各銷售店，地區3設置1個銷售店。 3：對下圖中的網絡，分別用破圈法和生長法求最短樹。3：解 破圈法（1）：取圈，去掉邊。（2）：取圈，去掉邊。（3）：取圈，去掉邊。（4）：取圈，去掉邊。在圖中已無圈，此時，而，因此所得的是最短樹。結果如下圖，其樹的總長度為12。 .-（6分） .-（3分）生長法根據生長法的基本原理，得以下計算表 26389389535315133據此也得到

10、與破圈法相同的最短樹。 .-（6分） 五、簡答題(每小題10分，共20分)1試述單純形法的計算步驟，并說明如何在單純形表上判斷問題是具有唯一最優解、無窮多最優解和無有限最優解。解：1：單純形法的計算步驟 第一步：找出初始可行解，建立初始單純形表。 第二步：判斷最優，檢驗各非基變量的檢驗數。若所有的，則基B為最優基，相應的基可行解即為基本最優解，計算停止。若所有的檢驗數，又存在某個非基變量的檢驗數所有的，則線性規劃問題有無窮多最優解。若有某個非基變量的檢驗數，并且所對應的列向量的全部分量都非正，則該線性規劃問題的目標函數值無上界，既無界解，停止計算。第三步：換基迭代當存在，選進基來改善目標函數。

11、若檢驗數大于0的非基變量不止一個，則可以任選其中之一來作為進基變量。進基變量確定后，按最小比值原則選擇出基變量。若比值最小的不止一個，選擇其中之一出基。做主元變換。反復進行上述過程就可以找到最優解或判斷出沒有有限最優解。 -（3分） 2簡述最小費用最大流問題的提法以及用對偶法求解最小費用最大流的原理和步驟。 解：2：最大流問題就是在一定條件下，要求流過網絡的物流、能量流或信息流等流量最大的問題。如果已知流過弧的單位流量要發生的費用，要求使總費用為最小的最大流流量分配方法。即在上述最大流問題上還應增加關于費用的目標：。這種問題稱為最小費用最大流問題。模型可以描述為：采用對偶法求解最大流最小費用問題，其原理為：用福德富克遜算法求出網絡的最大流量，然后用Ford算法找出從起點到終點的最短增廣鏈。在該增廣鏈上，找出最大調整量，并調整流量，得到一個可行流。則此可行流的費用最小。如果此時流量等于最大流量，則目前的流就是最小費用最大流，否則應繼續調整。對偶法的