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

1、楚大2012-2013上學(xué)期經(jīng)濟(jì)信息管理及計(jì)算機(jī)應(yīng)用系運(yùn)籌學(xué)期末考試試題及答案班級(jí):學(xué)號(hào)一、單項(xiàng)選擇題：1、在下面的數(shù)學(xué)模型中，屬于線性規(guī)劃模型的為（A）。_22_minS=3XYmaxS=4XYmaxS=XYminS=2XYB.s.t.2XY之一1A.（s.t.XY<3C.st.X-Y<2D.s.t.X+Y之3X,Y>01X,Y>0X,Y>01X,Y之02、線性規(guī)劃問(wèn)題若有最優(yōu)解，則一定可以在可行域的（A）上達(dá)到。A.頂點(diǎn)B.內(nèi)點(diǎn)C.外點(diǎn)D.幾何點(diǎn)3、在線性規(guī)劃模型中，沒(méi)有非負(fù)約束的變量稱為（C）A.多余變量B.松弛變量C.自由變量D.人工變量4、若線性規(guī)劃問(wèn)題

2、的最優(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ī)劃的約束條件為<2x1+2x2+x4=4Xi,冬之0則基本可行解為(C)。A.(0,0,4,3)B.(3,4,0,0)C.(2,0,1,0)D.(3,0,4,0)7、若運(yùn)輸問(wèn)題已求得最優(yōu)解，此時(shí)所求出的檢驗(yàn)數(shù)一定是全部(D)A、小于或等于零B.大于零C.小于零D.大于或等于零8、對(duì)于m個(gè)發(fā)點(diǎn)、n個(gè)收點(diǎn)的運(yùn)輸問(wèn)題，敘述

3、錯(cuò)誤的是(D)A.該問(wèn)題的系數(shù)矩陣有mXn列B.該問(wèn)題的系數(shù)矩陣有m+n行C.該問(wèn)題的系數(shù)矩陣的秩必為m+n-1D.該問(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)10、若P為網(wǎng)絡(luò)G的一條流量增廣鏈，則P中所有正向弧都為G的A.對(duì)邊B.飽和邊C.鄰邊D.不飽和邊一、判斷題。1、圖解法和單純形法雖然求解的形式不同，但從幾何上理解，兩者是一致的。（T）2、單純形法的迭代計(jì)算過(guò)程是從一個(gè)可行解轉(zhuǎn)換到目標(biāo)函數(shù)值更大的另一個(gè)

4、可行解。（F）3、一旦一個(gè)人工變量在迭代中變?yōu)榉腔兞亢?，該變量及相?yīng)列的數(shù)字可以從單純形表中刪除，而不影響計(jì)算結(jié)果。（T）4、若線性規(guī)劃問(wèn)題中的bq值同時(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)用順推或逆推解法可能會(huì)得出不同的最優(yōu)解。（F）8、動(dòng)態(tài)規(guī)劃的基本方程是將一個(gè)多階段的決策問(wèn)題轉(zhuǎn)化為一系列具有遞推關(guān)系的單階段的決策問(wèn)題。（T）9、圖論中的圖不僅反映了研究對(duì)象之間的關(guān)系，而且是真

5、實(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)題模型中，m+n1個(gè)變量構(gòu)成基變量的充要條件是不含閉回路。4、動(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)題，用迭代法

6、求解，有_酉數(shù)迭代法和策略迭代法兩種方法。6、在圖論方法中，通常用點(diǎn)表示人們研究的對(duì)象，用邊表示對(duì)象之間的聯(lián)系。7、線性規(guī)劃maxZ=-Xi+x2,2x1+x2<6,4xi+X2<8,Xi,X220的最優(yōu)解是（0,6）,它的第1、2個(gè)約束中松馳變量（§§）=（0,2）8、運(yùn)輸問(wèn)題的檢驗(yàn)數(shù)為的經(jīng)濟(jì)含義是（Xj增加一個(gè)單位總運(yùn)費(fèi)增加入）四、計(jì)算題1、考慮線性規(guī)劃問(wèn)題:maxz=2k4x23&'3xi+4x2+2x3<602x+x2+2x3<40s.t.x1+3x2+2x3<80K,x2,&之0(a)、寫出其對(duì)偶問(wèn)題；(b)、

7、用單純形方法求解原問(wèn)題；(c)、用對(duì)偶單純形方法求解其對(duì)偶問(wèn)題；(d)、比較(b)(c)計(jì)算結(jié)果。1：解a)、其對(duì)偶問(wèn)題為minz=60yl40y280y3'3y#2y2+y3之24%+y2+3y3之4s.t.2y12y22y3一3%,y2,y3-0b）、用單純形方法求解原問(wèn)題時(shí)每步迭代結(jié)果:原問(wèn)題解第f(0,0,0,60,40,80)第二步(0,15,0,0,25,35)第三步(0,20/3,50/3,0,0,80/3)c）、用對(duì)偶單純形方法求解對(duì)偶問(wèn)題時(shí)每步迭代結(jié)果:對(duì)偶問(wèn)題問(wèn)題解第f(0,0,0,-2,-4,-3)(1,0,0,1,0,-1)第二步(5/6,2/3,0,11/6,0,0)第三步d)、對(duì)偶問(wèn)題的實(shí)質(zhì)是將單純形法應(yīng)用于對(duì)偶問(wèn)題的求解，又對(duì)偶問(wèn)題的對(duì)偶即原問(wèn)題，因此(b)、(c)的計(jì)算結(jié)果完全相同。五、證明題：1、對(duì)問(wèn)題minf(x1,x2)=x1八2+25x2八2中的變量x=(x1,x2)T作線性變換：y1=x1,y2=5x2則原來(lái)的無(wú)約束優(yōu)化問(wèn)題變?yōu)椋簃inF(y1,y2)=y1A2+y2A2證明：從任意初始點(diǎn)y0出發(fā)，用最速下降法問(wèn)題(*)迭代一輪即可求得最優(yōu)化解，從中你可以得到什么啟示？證：從任意初始點(diǎn)為y0=(y1A0,y2A0)T,令P0=-f(y0)則代入f(y)=(1+2t)A2(y10)A