運籌學期末考試試題及答案

1、楚大2012 2 0 13上學期經(jīng)濟信息管理及計算機應(yīng)用系運籌學期末考試試題及答案班級; 學號一、單項選擇題:1、在下面的數(shù)學模型中，屬于線性規(guī)劃模型的為（A)oB/min S = 3X + Ys.t. 2X-Y>-1 A/X,Y>0max S = 4X + Ymax S = X2 +Y2minS = 2XYs.t. XY<3 C<X,Y>0s.t. X-Y<2 D<X.Y>0X + Y>3X.Y202、線性規(guī)劃問題若有最優(yōu)解，則一定可以在可行域的上達到。A.頂點B.內(nèi)點C.外點D.幾何3、在線性規(guī)劃模型中，沒有非負約束的變量稱為（A .多

2、余變量B.松弛變量C.自由變量D.人工變4、若線性規(guī)劃問題的最優(yōu)解同時在可行解域的兩個頂點處達到，那么該線性規(guī)劃問題最優(yōu)解為（C ）。A.兩個B.零個C.無窮多個 D.有限多個5、線性規(guī)劃具有唯一最優(yōu)解是指（B ）A.最優(yōu)表中存在常數(shù)項為零B.最優(yōu)表中非基變量檢驗數(shù)全部非零C.最優(yōu)表中存在非基變量的檢驗數(shù)為零D.可行解集合有界6、設(shè)線性規(guī)劃的約束條件為+ x2 + x3 = 3 < 2xj + 2x2 +x4 = 4 力,乙>0則基本可行解為(C)oA. (0,0, 4, 3 )B. (3, 4,0, 0)C. (2, 0, 1, 0 )D. (3,0,4,0)7、若運輸問題已求得

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

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

5、或逆推解法可能會得出不同的最優(yōu)解。(F)8、動態(tài)規(guī)劃的基本方程是將一個多階段的決策問題轉(zhuǎn)化為一系列具 有遞推關(guān)系的單階段的決策問題。(T )9、圖論中的圖不僅反映了研究對象之間的關(guān)系，而且是真實圖形的寫照，因而對圖中點與點的相對位置、點與點連線的長短曲直等都要嚴格注意。(F)10、網(wǎng)絡(luò)最短路線問題和最短樹問題實質(zhì)上是一個問題。(F )二、填空題。1、線性規(guī)劃中,滿足非負條件的基木解稱為基本可行解，對應(yīng)的基稱為可行基。2、線性規(guī)劃的目標函數(shù)的系數(shù)是其對偶問題的一右端常數(shù)一而若線性規(guī)劃為最大化問題，則對偶問題為 最小化問題3、在運輸問題模型中，? + -1個變量構(gòu)成基變量的充要條件是含閉回路 。4

6、、動態(tài)規(guī)劃方法的步驟可以總結(jié)為：逆序求解 最優(yōu)目標函數(shù),順序求最優(yōu)策略、最優(yōu)路線和最優(yōu)目標函數(shù)值。5、工程路線問題也稱為最短路問題，根據(jù)問題的不同分為定步數(shù)問題 和不定步數(shù)問題；對不定步數(shù)問題，用迭代法求解，有函數(shù)迭代法和策略 迭代法兩種方法。6、在圖論方法中，通常用 點 表示人們研究的對象，用邊 表示對象之間的聯(lián)系。7、線性規(guī)劃 max Z = 一為 +x2t2xt +x2 46,4玉 +x2 <8,xpx2 NO 的最優(yōu)解是(0,6),它的第1 、2個約束中松馳變量()=(0 ,2) 8、運輸問題的檢驗數(shù)入一的經(jīng)濟含義是(xu增加一個單位總運費增加入i j四、計算題。1、考慮線性規(guī)劃

7、問題：max z = 2x + 4x2 + 3x33芯 + 4x2 + 2x? < 602xl + 2x3 < 40s. t. <$ + 3x2 + 2x3 < 80Vpx2,x3 >0(a).寫出其對偶問題；(b )、用單純形方法求解原問題；(。、用對偶單純形方法求解其對偶問題；(d)、比較(b) (c)計算結(jié)果。1：解a)>其對偶問題為min z = 60y, + 40y2 + 80)、3%+2y2+ 為之 2S /町+ >2+3)、之4,2M +2%+2% >3. 加力,%2°b)、用單純形方法求解原問題時每步迭代結(jié)果：原問題解第

8、一步(0, 0 ,0, 6 0,4 0 , 80)第二步(0 , 1 5,0, 0,25, 35)第三步( 0,2 0 /3,50 / 3,0,0 , 80/3 )。、用對偶單純形方法求解對偶問題時每步迭代結(jié)果:對偶問題問題解第一步(0,0,0, -2, -4 , -3 )第二步第三步(5/6,2/3, 0 ,/6, 0,0)d)、對偶問題的實質(zhì)是將單純形法應(yīng)用于對偶問題的求解，又對偶問題的對偶即原問題，因此(b )、(。的計算結(jié)果完全相同。五、證明題：1、對問題 m i nf (xl,x2) =xl 八 2+25x20 中的變量 x =(xl, x2)T 作線性變換:yl=xl, y2=5x2,則原來的無約束優(yōu)化問題變?yōu)椋簃 i nF(yl,y2)=y 1 A2+y2A2證明:從任意初始點y 0出發(fā)，用最速下降法問題(*)迭代一輪即可求得最優(yōu)化解，從中你可以得到什么啟示？證：從任意初始點為y 0 =( y 1八0,y2A0) 號P 0 =-f(y 0 ),則代入f(y)=(l+