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

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

2、余變量B.松弛變量C.自由變量D.人工變4、若線性規(guī)劃問(wèn)題的最優(yōu)解同時(shí)在可行解域的兩個(gè)頂點(diǎn)處達(dá)到，那么該線性規(guī)劃問(wèn)題最優(yōu)解為（C ）。A.兩個(gè)B.零個(gè)C.無(wú)窮多個(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ī)劃的約束條件為+ 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、若運(yùn)輸問(wèn)題已求得

3、最優(yōu)解，此時(shí)所求出的檢驗(yàn)數(shù)一定是全部(D )A、小于或等于零 B.大于零C.小于零D.大于或等于零公、對(duì)于m個(gè)發(fā)點(diǎn)、n個(gè)收點(diǎn)的運(yùn)輸問(wèn)題，敘述錯(cuò)誤的是(D )A.該問(wèn)題的系數(shù)矩陣有mXn列。B.該問(wèn)題的系數(shù)矩陣有m+n行C.該問(wèn)題的系數(shù)矩陣的秩必為m+n l，。D.該問(wèn)題的最優(yōu)解必唯一9、關(guān)于動(dòng)態(tài)規(guī)劃問(wèn)題的下列命題中錯(cuò)誤的是(A )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ī)劃的求解過(guò)程都可以用列表形式實(shí)現(xiàn)1 0、若P為網(wǎng)絡(luò)G的一條流量增廣鏈，則P中所有正向弧都為G的(D ) 4A.對(duì)邊B.飽和邊C.鄰邊D

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

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

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

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

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