2023《運(yùn)籌學(xué)》考試題及其答案

1、PAGE 2023學(xué)年第1學(xué)期?運(yùn)籌學(xué)?考試題答案要求:第一題必做50分，二三四題任選兩題每題各25分?？紤]下面線性規(guī)劃問題用圖解法求解該問題；寫出該問題的標(biāo)準(zhǔn)形式；求出該問題的松弛變量和剩余變量的值；用單純形法求解?！窘獯稹?1)圖中陰影局部為此線性規(guī)劃問題的可行域,目標(biāo)函數(shù),即是斜率為的一族平行直線,由線性規(guī)劃的性質(zhì)知,其最值在可行域的頂點(diǎn)取得,將直線沿其法線方向逐漸向上平移,直至A點(diǎn),A點(diǎn)的坐標(biāo)為(),所以此線性規(guī)劃問題有唯一解。(2)給等式2左端添加剩余變量，給等式3左端添加松弛變量，那么得到該問題的標(biāo)準(zhǔn)型為：3在上面標(biāo)準(zhǔn)型中令，得到剩余變量=0，松弛變量=0。4先在上面標(biāo)準(zhǔn)型中約束條

2、件(1)、2中分別參加人工變量,，得到如下數(shù)學(xué)模型，由此列出單純形表逐步迭代，用大M法求解計算結(jié)果如下表所示。CjCjxjXBCB4100MMbiM【3】1001031M43100163/2012010033rj7 4M1M0009M411/3001/3013M0【5/3】104/3126/5005/3011/3026/5rj(-z)0(5M+1)/3M0(7M+4)/304-2M4101/503/51/53/51/31013/504/53/56/5000【1】11100rj(-z)001/50M+8/5M-1/518/541001/52/503/510103/51/506/500011110

3、rj(-z)0001/5M+7/5M18/5表中所有檢驗(yàn)數(shù)rj0,根據(jù)最優(yōu)解定理，問題存在唯一的最優(yōu)解，目標(biāo)函數(shù)的最優(yōu)值。試用表上作業(yè)法求解以下運(yùn)輸問題的最優(yōu)解。產(chǎn)地 銷地B1B2B3B4產(chǎn)量A148846A295634A33114212銷量6277【解答】：顯然該問題是一個供需平衡問題，利用伏格法求出初始方案，如下表所示。B1B2B3B4產(chǎn)量A1648846A29256234A30311745212銷量6277用位勢法求出各非基變量即空格的檢驗(yàn)數(shù)，如下表所示。B1B2B3B4A164(3)8(3)8(1)4=0A2(5)925(1)623=0A303(7)117452=1=4=5=53因?yàn)樗?/p>

4、有非基變量的檢驗(yàn)數(shù)均為非負(fù)的，故表中的解為最優(yōu)解。按照此種方案調(diào)運(yùn)，最小費(fèi)用為：64+25+23+03+74+52= 78用標(biāo)號算法求解以下列圖中從V1到各點(diǎn)的最短路【解答】：此為最短路問題，權(quán)數(shù)為正，用Dijksta算法的計算步驟如下：初始值 T( ) 01P( )+wij0+20+80+0+0+0+0+0+0+0+T( ) 282P( )+wij2+62+2+12+2+2+2+2+2+T( ) 833P( )+wij3+53+3+3+3+3+13+3+T( ) 844P( )+wij4+4+4+64+4+74+4+T( ) 810115P( )+wij8+78+8+8+8+8+T( ) 1

5、510116P( )+wij10+10+410+10+10+T( ) 1514117P( )+wij11+11+11+11+9T( ) 1514208P( )+wij14+14+114+T( ) 1515119P( )+wij15+4T( ) 19由上表的迭代過程可得：，d(,)=2,最短路：,； d(,)=3,最短路：,；d(,)=4,最短路：,；d(,)=10,最短路：,； d(,)=8,最短路：,或,或,； d(,)=11,最短路：,；d(,)=14最短路：,；d(,)=15,最短路：,或,或,；d(,)=15,最短路：,； d(,)=19,最短路：,；某公司面對四種自然狀態(tài)的三種備選行

6、動方案收益表如下，假定狀態(tài)概率未知，試分別用悲觀準(zhǔn)那么、等可能性準(zhǔn)那么、懊悔值準(zhǔn)那么和樂觀系數(shù)準(zhǔn)那么=0.6進(jìn)行決策。狀狀態(tài)收益 值方案1234A115806A241483A3141012【解答】：1應(yīng)用悲觀準(zhǔn)那么：S2為最正確方案。(2)應(yīng)用等可能性準(zhǔn)那么：, , , ，S2為最正確方案。3應(yīng)用懊悔值準(zhǔn)那么：先求出懊悔值矩陣S2為最正確方案。(4)應(yīng)用樂觀系數(shù)準(zhǔn)那么=0.6：先計算各個方案的折中益損值：，S2為最正確方案下表為求解某目標(biāo)函數(shù)為極大化線性規(guī)劃問題的最終單純形表，表中為松弛變量，問題的約束為形式共8分5/201/211/25/211/201/61/300(1)寫出原線性規(guī)劃問題；

7、4分(2)寫出原問題的對偶問題；3分(3)直接由上表寫出對偶問題的最優(yōu)解。1分四、用單純形法解以下線性規(guī)劃問題16分 s. t. 3 x1 + x2 + x360 x 1- x 2 +2 x 310 x 1+x 2-x 320 x 1,x 2 ,x 30五、求解下面運(yùn)輸問題。18分某公司從三個產(chǎn)地A1、A2、A3將物品運(yùn)往四個銷地B1、B2、B3、B4，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如表所示：問：應(yīng)如何調(diào)運(yùn)，可使得總運(yùn)輸費(fèi)最小? 銷 地 產(chǎn) 地 產(chǎn) 量1089523674768252550銷 、靈敏度分析共8分線性規(guī)劃max z = 10

8、x1 + 6x2 + 4x3 s.t. x1 + x2 + x3 10010 x1 +4 x2 + 5 x3 6002x1 +2 x2 + 6 x3 300 x1 , x2 , x3 0的最優(yōu)單純形表如下：6x2200/305/615/3 1/6010 x1100/311/60-2/31/600 x6100040-201j08/30-10/3 2/30(1)C1在何范圍內(nèi)變化，最優(yōu)方案不變？(4分)(2)b1在什么范圍內(nèi)變化，最優(yōu)基不變？(4分)七、試建立一個動態(tài)規(guī)劃模型。共8分某工廠購進(jìn)100臺機(jī)器，準(zhǔn)備生產(chǎn) p1 , p2 兩種產(chǎn)品。假設(shè)生產(chǎn)產(chǎn)品 p1 ，每臺機(jī)器每年可收入45萬元，損壞率

9、為65%；假設(shè)生產(chǎn)產(chǎn)品 p2 ，每臺機(jī)器每年可收入35萬元，損壞率為35%；估計三年后將有新的機(jī)器出現(xiàn)，舊的機(jī)器將全部淘汰。試問每年應(yīng)如何安排生產(chǎn)，使在三年內(nèi)收入最多？八、求解對策問題。共10分某種子商店希望訂購一批種子。據(jù)已往經(jīng)驗(yàn)，種子的銷售量可能為500，1000，1500或2000公斤。假定每公斤種子的訂購價為6元，銷售價為9元，剩余種子的處理價為每公斤3元。要求：1建立損益矩陣；3分2用悲觀法決定該商店應(yīng)訂購的種子數(shù)。2分3建立懊悔矩陣，并用懊悔值法決定商店應(yīng)訂購的種子數(shù)。5分九、求以下網(wǎng)絡(luò)方案圖的各時間參數(shù)并找出關(guān)鍵問題和關(guān)鍵路徑。8分66812345756379342783工序代號

10、 工序 時間最早開工時間最早完工時間最晚開工時間最晚完工時間機(jī)動時間1-281-371-462-432-553-423-634-534-674-745-796-78十、用標(biāo)號法求V1到 V6的最短路。6分33V4V5V3V1V2V6465664384運(yùn)籌學(xué)樣卷一答案判斷題。共計10分，每題1分10XXXX二、建線性規(guī)劃模型。共計8分酌情扣分解：用分別表示大豆、玉米、麥子的種植公頃數(shù)；分別表示奶牛和雞的飼養(yǎng)數(shù)；分別表示秋冬季和春夏季的勞動力人日數(shù)，那么有三、對偶問題。共計8分解：原線性規(guī)劃問題：；4分原問題的對偶規(guī)劃問題為：；3分對偶規(guī)劃問題的最優(yōu)解為：T。1分四、單純形表求解線性規(guī)劃。共計16

11、分解：引入松弛變量x4、 x5、 x6，標(biāo)準(zhǔn)化得， s. t. 3 x1 + x2 + x3+ x4 = 60 x 1- x 2 +2 x 3 + x5 = 10 x 1+x 2-x 3+ x6 = 0 x 1,x 2 ,x 3，x4、 x5、 x6，03分建初始單純形表，進(jìn)行迭代運(yùn)算： 9分CBXbb2-11000 x1x2x3x4x5x60 x460311100200 x5101-1201010*0 x62011-100120102*-110000 x43004-51-307.52x1101-120100 x61002-30-115*22001*-30-200 x4100011-1-22x

12、115100.500.50.5-1x2501-1.50-0.50.532500-1.50-1.5-0.5由最優(yōu)單純形表可知，原線性規(guī)劃的最優(yōu)解為： ( 15 , 5 , 0 )T 2分最優(yōu)值為： z*=25。2分五、求解運(yùn)輸問題。共計18分解：1最小元素法：也可以用其他方法，酌情給分設(shè)xij為由Ai運(yùn)往Bj的運(yùn)量i=1,2,3; j=1,2,3,4,列表如下： 銷 地產(chǎn) 地產(chǎn) 量1231520302555252550銷 量152030351003分所以，根本的初始可行解為：x14 =25；x22=20 ；x24 =5 ；X31 =15；x33 =30；x34=5 其余的xij=0。3分2求最優(yōu)

13、調(diào)運(yùn)方案：1會求檢驗(yàn)數(shù)，檢驗(yàn)解的最優(yōu)性：11=2；12=2；13=3；21=1；23=5；32= - 13分2會求調(diào)整量進(jìn)行調(diào)整：=5 2分 銷 地產(chǎn) 地產(chǎn) 量12315155302510252550銷 量152030351003分3再次檢驗(yàn) 2分4能夠?qū)懗稣_結(jié)論解為：x14=25 ；x22 =15 ；x24 =10 x31 =15，x32 =5 x33=30其余的xij=0。1分最少運(yùn)費(fèi)為： 535 1分。六、靈敏度分析。共計8分14分24分七、建動態(tài)規(guī)劃模型。共計8分解：(1)設(shè)階段變量k表示年度，因此，階段總數(shù)n=3。(2)狀態(tài)變量sk表示第k年度初擁有的完好機(jī)床臺數(shù)，同時也是第k1

14、年度末時的完好機(jī)床數(shù)量。(3)決策變量uk，表示第k年度中分配于生產(chǎn)產(chǎn)品p1 的機(jī)器臺數(shù)。于是sk uk便為該年度中分配于生產(chǎn)產(chǎn)品p1的機(jī)器臺數(shù)4狀態(tài)轉(zhuǎn)移方程為5允許決策集合,在第k 段為6目標(biāo)函數(shù)。設(shè)gk(sk,uk)為第k年度的產(chǎn)量，那么 gk(sk,uk) = 45uk + 35(skuk) , 因此，目標(biāo)函數(shù)為7條件最優(yōu)目標(biāo)函數(shù)遞推方程。令fk(sk)表示由第k年的狀態(tài)sk出發(fā)，采取最優(yōu)分配方案到第3年度結(jié)束這段時間的產(chǎn)品產(chǎn)量，根據(jù)最優(yōu)化原理有以下遞推關(guān)系：8.邊界條件為八、解決對策問題。共10分1益損矩陣如下表所示：3分 銷 售訂 購S1500S21000S31500S42000A1

15、 500A2 1000A3 1500A4 200015000150030001500300015000150030004500300015003000450060002悲觀法：A1，訂購500公斤。2分3懊悔矩陣如下表所示：3分S1S2S3S4最大懊悔值A(chǔ)101500300045004500A215000150030003000A330001500015003000A445003000150004500按懊悔值法商店應(yīng)取決策為A2或A3，即訂購1000公斤或1500公斤。2分68168123457563793427830871114182626141811980工序代號 工序 時間最早開工時間最早完工時間最晚開工時間最晚完工時間機(jī)動時間1-28080801-37072921-460651162-4381181102-5581391413-427991123-63710151884-531114111404-671118111804-74