1、20192019 2020運籌學期末考試試題及答案2012-2013 上學期經濟信息管理及計算機應用系運籌學期末考試試題及答案班級: 學號一、單項選擇題：1、在下面的數學模型中；屬于線性規劃模型的為（ A ）。 -222_minS 3X Y maxS 4X Y maxS XY minS 2XYB. st.2X Y 1A. s.t.XY3 C. st.X Y2D. s.t.X Y 3X, Y 0X, Y 0X,Y 0X,Y 02、線性規劃問題若有最優解；則一定可以在可行域的（A ）上達到。A.頂點 B .內點 C .外點 D .幾何點3、在線性規劃模型中；沒有非負約束的變量稱為（C ）A.多余變

2、量B.松弛變量C.自由變量 D.人工變量4、若線性規劃問題的最優解同時在可行解域的兩個頂點處達到；那么該線性規劃問題最優解為（C ）。A.兩個B.零個C.無窮多個D.有限多個5、線性規劃具有唯一最優解是指（ B ）A.最優表中存在常數項為零 B.最優表中非基變量檢驗數全部非零C.最優表中存在非基變量的檢驗數為零D.可行解集合有界6、設線性規劃的約束條件為2x1 2x2 x4 4x1 , x40則基本可行解為（C ） 。A（0；0；4；3）B（3；4；0；0）C（2；0；1 ；0）D（3；0；4；0）7、若運輸問題已求得最優解；此時所求出的檢驗數一定是全部（D ）A、小于或等于零B.大于零 C.

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

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

5、的基本方程是將一個多階段的決策問題轉化為一系列具有遞推關系的單階段的決策問題。（ T ）9、圖論中的圖不僅反映了研究對象之間的關系；而且是真實圖形的點與點連線的長短曲直等都要寫照； 因而對圖中點與點的相對位置、嚴格注意。（F ）10、網絡最短路線問題和最短樹問題實質上是一個問題。（F ）二、填空題。1、線性規劃中；滿足非負條件的基本解稱為基本可行解 ；對應的基稱為可行基 。2、線性規劃的目標函數的系數是其對偶問題的右端常數;而若線性規劃為最大化問題；則對偶問題為最小化問題。3、在運輸問題模型中；m n 1個變量構成基變量的充要條件是 一不含閉回路。4、動態規劃方法的步驟可以總結為：逆序求解最優

6、目標函數；順序求最優策略 、 最優路線 禾口 最優目標函數值。5、工程路線問題也稱為最短路問題；根據問題的不同分為定步數問 題和不定步數問題；對不定步數問題；用迭代法求解；有_酉數迭代法和 策略迭代法兩種方法。6、在圖論方法中；通常用 點表示人們研究的對象；用 邊表示對象之間的聯系。7、線性規劃 maxZ Xi X2,2Xi % 6,4x1 x? 8, Xi, X2 0 的最優解是（0；6）;它的第1、2個約束中松馳變量（SS）= （。；2）8、運輸問題的檢驗數 加的經濟含義是（的增加一個單位總運費增力口為）四、計算題。1、考慮線性規劃問題:max z 2xi 4x2 3x33x1 4x2 2

7、x3 602% x2 2x340s.t. x1 3x2 2x380XE，% 0(a)、寫出其對偶問題；(b)、用單純形方法求解原問題；(c)、用對偶單純形方法求解其對偶問題；(d)、比較(b) (c)計算結果。1：解a)、其對偶問題為minz 60y140y280y33y12y2y32,4y1V2V34s.t.2y12y22y33y1, y2, y30b）、用單純形方法求解原問題時每步迭代結果:原問題解第f(0; 0; 0; 60; 40; 80)第二步(0; 15; 0; 0; 25; 35)第三步(0; 20/3; 50/3; 0; 0; 80/3)c）、用對偶單純形方法求解對偶問題時每步

8、迭代結果:對偶問題問題解第f(0; 0; 0; -2; -4; -3)第二步(1; 0; 0; 1; 0; -1)第三步(5/6; 2/3; 0; 11/6; 0; 0)d)、對偶問題的實質是將單純形法應用于對偶問題的求解；又對偶問題的對偶即原問題；因此(b)、(c)的計算結果完全相同。五、證明題：1、對問題 minf (x1; x2) =x1八2+25x2八2中的變量x=(x1; x2)T作線性變換：y1=x1; y2=5x2;則原來的無約束優化問題變為：minF(y1; y2)=y1A2+y2A2證明：從任意初始點y0出發；用最速下降法問題(* *)迭代一輪 即可求得最優化解；從中你可以得到什么啟示？證：從任意初始點為y0= (y1A0； 丫2-0) T；令P0=-f(y0)；