2019—2020運(yùn)籌學(xué)期末考試試題及答案

1、20192019 2020運(yùn)籌學(xué)期末考試試題及答案2012-2013 上學(xué)期經(jīng)濟(jì)信息管理及計(jì)算機(jī)應(yīng)用系運(yùn)籌學(xué)期末考試試題及答案班級: 學(xué)號一、單項(xiàng)選擇題：1、在下面的數(shù)學(xué)模型中；屬于線性規(guī)劃模型的為（ 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、線性規(guī)劃問題若有最優(yōu)解；則一定可以在可行域的（A ）上達(dá)到。A.頂點(diǎn) B .內(nèi)點(diǎn) C .外點(diǎn) D .幾何點(diǎn)3、在線性規(guī)劃模型中；沒有非負(fù)約束的變量稱為（C ）A.多余變

2、量B.松弛變量C.自由變量 D.人工變量4、若線性規(guī)劃問題的最優(yōu)解同時(shí)在可行解域的兩個(gè)頂點(diǎn)處達(dá)到；那么該線性規(guī)劃問題最優(yōu)解為（C ）。A.兩個(gè)B.零個(gè)C.無窮多個(gè)D.有限多個(gè)5、線性規(guī)劃具有唯一最優(yōu)解是指（ B ）A.最優(yōu)表中存在常數(shù)項(xiàng)為零 B.最優(yōu)表中非基變量檢驗(yàn)數(shù)全部非零C.最優(yōu)表中存在非基變量的檢驗(yàn)數(shù)為零D.可行解集合有界6、設(shè)線性規(guī)劃的約束條件為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、若運(yùn)輸問題已求得最優(yōu)解；此時(shí)所求出的檢驗(yàn)數(shù)一定是全部（D ）A、小于或等于零B.大于零 C.

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

4、；但從幾何上理解；兩者是一致的。（ T ）2、單純形法的迭代計(jì)算過程是從一個(gè)可行解轉(zhuǎn)換到目標(biāo)函數(shù)值更大的另一個(gè)可行解。（ F ）3、一旦一個(gè)人工變量在迭代中變?yōu)榉腔兞亢螅辉撟兞考跋鄳?yīng)列的數(shù)字可以從單純形表中刪除；而不影響計(jì)算結(jié)果。（ T ）4、若線性規(guī)劃問題中的bq值同時(shí)發(fā)生改變；反映到最終單純形表中；不會(huì)出現(xiàn)原問題與對偶問題均為非可行基的情況。（ F ）5、若線性規(guī)劃的原問題有無窮多最優(yōu)解；則其對偶問題也一定具有無窮多最優(yōu)解。（ T ）6、運(yùn)輸問題的表上作業(yè)法實(shí)質(zhì)上就是求解運(yùn)輸問題的單純形法。（ T ）7、對于動(dòng)態(tài)規(guī)劃問題；應(yīng)用順推或逆推解法可能會(huì)得出不同的最優(yōu)解。 （ F ）8、動(dòng)態(tài)規(guī)劃

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

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

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

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