《運(yùn)籌學(xué)》-期末考試-試卷A-答案

1、運(yùn)籌學(xué)試題樣卷（一）題號(hào)一二三四五六七八九十總分得分一、判斷題（共計(jì)10分，每小題1分，對(duì)的打，錯(cuò)的打X）1. 無孤立點(diǎn)的圖一定是連通圖。2. 對(duì)于線性規(guī)劃的原問題和其對(duì)偶問題，若其中一個(gè)有最優(yōu)解，另一個(gè)也一定有最優(yōu)解。 3. 如果一個(gè)線性規(guī)劃問題有可行解，那么它必有最優(yōu)解。4對(duì)偶問題的對(duì)偶問題一定是原問題。5用單純形法求解標(biāo)準(zhǔn)形式（求最小值）的線性規(guī)劃問題時(shí)，與對(duì)應(yīng)的變量都可以被選作換入變量。6若線性規(guī)劃的原問題有無窮多個(gè)最優(yōu)解時(shí)，其對(duì)偶問題也有無窮多個(gè)最優(yōu)解。7. 度為0的點(diǎn)稱為懸掛點(diǎn)。8. 表上作業(yè)法實(shí)質(zhì)上就是求解運(yùn)輸問題的單純形法。 9. 一個(gè)圖G 是樹的充分必要條件是邊數(shù)最少的無孤立

2、點(diǎn)的圖。10. 任何線性規(guī)劃問題都存在且有唯一的對(duì)偶問題。 二、建立下面問題的線性規(guī)劃模型（8分）某農(nóng)場(chǎng)有100公頃土地及15000元資金可用于發(fā)展生產(chǎn)。農(nóng)場(chǎng)勞動(dòng)力情況為秋冬季3500人日；春夏季4000人日。如勞動(dòng)力本身用不了時(shí)可外出打工，春秋季收入為25元 / 人日，秋冬季收入為20元 / 人日。該農(nóng)場(chǎng)種植三種作物：大豆、玉米、小麥，并飼養(yǎng)奶牛和雞。種作物時(shí)不需要專門投資，而飼養(yǎng)每頭奶牛需投資800元，每只雞投資3元。養(yǎng)奶牛時(shí)每頭需撥出1.5公頃土地種飼料，并占用人工秋冬季為100人日，春夏季為50人日，年凈收入900元 / 每頭奶牛。養(yǎng)雞時(shí)不占用土地，需人工為每只雞秋冬季0.6人日，春夏

3、季為0.3人日，年凈收入2元 / 每只雞。農(nóng)場(chǎng)現(xiàn)有雞舍允許最多養(yǎng)1500只雞，牛欄允許最多養(yǎng)200頭。三種作物每年需要的人工及收入情況如下表所示： 大豆玉米麥子秋冬季需人日數(shù)春夏季需人日數(shù)年凈收入（元/公頃）205030003575410010404600 試決定該農(nóng)場(chǎng)的經(jīng)營方案，使年凈收入為最大。三、已知下表為求解某目標(biāo)函數(shù)為極大化線性規(guī)劃問題的最終單純形表，表中為松弛變量，問題的約束為 形式（共8分） 5/201/211/25/211/201/61/300 (1)寫出原線性規(guī)劃問題；（4分）(2)寫出原問題的對(duì)偶問題；（3分）(3)直接由上表寫出對(duì)偶問題的最優(yōu)解。（1分）四、用單純形法解下

4、列線性規(guī)劃問題（16分） s. t. 3 x1 + x2 + x3 60 x 1- x 2 +2 x 3 10 x 1+ x 2- x 3 20 x 1, x 2 , x 3 0 五、求解下面運(yùn)輸問題。 （18分） 某公司從三個(gè)產(chǎn)地A1、A2、A3 將物品運(yùn)往四個(gè)銷地B1、B2、B3、B4，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如表所示：?jiǎn)枺簯?yīng)如何調(diào)運(yùn)，可使得總運(yùn)輸費(fèi)最小? 銷 地 產(chǎn) 地 產(chǎn) 量1089523674768252550銷 、靈敏度分析（共8分）線性規(guī)劃max z = 10 x1 + 6x2 + 4x3 s.t. x1 + x2 +

5、x3 100 10 x1 +4 x2 + 5 x3 600 2x1 +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)計(jì)劃不變？(4分)(2)b1在什么范圍內(nèi)變化，最優(yōu)基不變？(4分)七、試建立一個(gè)動(dòng)態(tài)規(guī)劃模型。（共8分）某工廠購進(jìn)100臺(tái)機(jī)器，準(zhǔn)備生產(chǎn) p1 , p2 兩種產(chǎn)品。若生產(chǎn)產(chǎn)品 p1 ，每臺(tái)機(jī)器每年可收入45萬元，損壞率為65%；若生產(chǎn)產(chǎn)品 p2 ，每臺(tái)機(jī)器 每年可收入35

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

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

8、規(guī)劃。共計(jì)16分解：引入松弛變量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-100120s102*-110000 x43004-51-307.52x1101-12010-0 x61002-30-115*s22001*-30-2

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

10、 x33 =30； x34=5 其余的xij=0。 3分（2）求最優(yōu)調(diào)運(yùn)方案：1會(huì)求檢驗(yàn)數(shù)，檢驗(yàn)解的最優(yōu)性：s11=2；s12=2；s13=3；s21=1；s23=5；s32= - 13分2會(huì)求調(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分。六、靈敏度分析。共計(jì)8分（1）（4分）（2）（4分）七、建動(dòng)態(tài)規(guī)劃模型。共計(jì)8分解：(1)設(shè)階

11、段變量k表示年度，因此，階段總數(shù)n=3。(2)狀態(tài)變量sk表示第k年度初擁有的完好機(jī)床臺(tái)數(shù)， 同時(shí)也是第 k1 年度末時(shí)的完好機(jī)床數(shù)量。(3)決策變量uk，表示第k年度中分配于生產(chǎn)產(chǎn)品 p1 的機(jī)器臺(tái)數(shù)。于是sk uk便為該年度中分配于生產(chǎn)產(chǎn)品 p1的機(jī)器臺(tái)數(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é)束這段時(shí)間的產(chǎn)品產(chǎn)量，根據(jù)最優(yōu)化原理有以下遞推關(guān)

12、系：（8）.邊界條件為八、解決對(duì)策問題。共10分（1）益損矩陣如下表所示：3分 銷 售訂 購S1500S21000S31500S42000A1 500A2 1000A3 1500A4 20001500015003000150030001500015003000450030001500300045006000（2）悲觀法：A1 ，訂購500公斤。2分（3）后悔矩陣如下表所示：3分 S1S2S3S4最大后悔值A(chǔ)101500300045004500A215000150030003000A330001500015003000A445003000150004500 按后悔值法商店應(yīng)取決策為A2或A3 ，即訂購1000公斤或1500公斤。2分68123457563793427830871114182626141811980九、求網(wǎng)絡(luò)計(jì)劃圖的各時(shí)間參數(shù)。（8分）工序代號(hào) 工序 時(shí)間最早開工時(shí)間最早完工時(shí)間最晚開工時(shí)間最晚完工時(shí)間機(jī)動(dòng)時(shí)間1-28080801-37072921-460651162-4381181102-5581391413-427991123-63710151884-531114111404-671118111804-7411152226115-791423172636-78182618260關(guān)鍵問題是：；2；6；6關(guān)鍵線路是：12467評(píng)分標(biāo)