運(yùn)籌學(xué)期末試題.

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

2、必要條件是邊數(shù)最少的無孤立點(diǎn)的圖。9.3500人日；春夏季4000人日。如勞動力本身用不了時可外出打工，春秋季收入為25元/人日，秋冬季收入為 20元/人日。該農(nóng)場種植三種作物：大豆、玉米、小麥，并飼養(yǎng)奶牛和雞。種作物時不需要專門投資，而飼養(yǎng)每頭奶牛需投資800元，每只雞投資 3元。養(yǎng)奶牛時每頭需撥出 1.5公頃土地種飼料，并占用人工秋冬季為 100人日，春夏季為50 人日，年凈收入 900元/每頭奶牛。養(yǎng)雞時不占用土地，需人工為每只雞秋冬季0.6人日，春夏季為0.3人日，年凈收入 2元/每只雞。農(nóng)場現(xiàn)有雞舍允許最多養(yǎng) 1500只 雞，牛欄允許最多養(yǎng) 200頭。三種作物每年需要的人工及收入情況

3、如下表所示：大豆秋冬季需人日數(shù)203510春夏季需人日數(shù)507540年凈收入（元/公頃）300041004600試決定該農(nóng)場的經(jīng)營方案，使年凈收入為最大。三、已知下表為求解某目標(biāo)函數(shù)為極大化線性規(guī)劃問題的最終單純形表，表中x4 ,x5為松弛變量，問題的約束為形式（共8分）xix2乂3x4x5x35/201/211/20xi5/211/20-1/61/3cj -zj0一 40一 42（1）寫出原線性規(guī)劃問題；（4分）（2）寫出原問題的對偶問題；（3分）（3）直接由上表寫出對偶問題的最優(yōu)解。（1分）四、用單純形法解下列線性規(guī)劃問題（16分）max Z = 2x1 - x2 x3s. t. 3 X1

4、 + X2 + X3 - 60x 1-x 2 + 2 x 3 - 10x 1 + x 2- x 34 20x 1 , x 2 , x 3 -0五、求解下面運(yùn)輸問題。（18分）某公司從三個產(chǎn)地AA2、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)最?。慨a(chǎn)地銷地B2B3B4產(chǎn)量Ai1056725A2827625A3934850銷、靈敏度分析（共 8分）線性規(guī)戈U max z= 10x1 + 6x2 + 4x3s.t. x1 + x2 + x3 父 10010x1 +4 x2

5、+ 5 x3 4 6002x1 +2 x2 + 6 x3 三 300x1 , x2 , x3 - 0的最優(yōu)單純形表如下:6X2200/305/615/3-1/6010X1100/311/60-2/31/600X6100040-201可06/30-10/3-2/30（1）C1在何范圍內(nèi)變化，最優(yōu)計(jì)劃不變？（4分）（2）bl在什么范圍內(nèi)變化，最優(yōu)基不變？（4分）七、試建立一個動態(tài)規(guī)劃模型。（共8分）某工廠購進(jìn)100臺機(jī)器，準(zhǔn)備生產(chǎn)pl , p2兩種產(chǎn)品。若生產(chǎn)產(chǎn)品 pl，每臺機(jī)器每年可收入45萬元，損壞率為 65%;若生產(chǎn)產(chǎn)品 p2 ,每臺機(jī)器 每年可收入35萬元，損壞率為35% ;估計(jì)三年后將有

6、新 的機(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ò)計(jì)劃圖的各時間參數(shù)并找出關(guān)鍵問題和關(guān)鍵路徑。（8分）工序 代號工序 時間最早開 工時間最早完 工時間最晚開 工時間最晚完 工時間機(jī)動 時間1-281-

7、371-462-432-553-423-634-534-674-745-796-78Mo短最的6求 法 號 標(biāo) 用、 十運(yùn)籌學(xué)試題樣卷（二）題號一一三四五六七八九十總分得分一、判斷題（對的打 M錯白打X.共計(jì)io分，答在下面的表格中）1、單純形法計(jì)算中，選取最大正檢驗(yàn)數(shù)° k對應(yīng)的變量xk作為換入變量，可使目標(biāo)函數(shù)值得到最快的減少。2、單純形法計(jì)算中，如不按最小非負(fù)比值原則選出換出變量，則在下一個解中至少有一個 基變量的值是負(fù)的。3、對于一個動態(tài)規(guī)劃問題，應(yīng)用順推法和逆推法可能會得到不同的最優(yōu)解。4、應(yīng)用對偶單純形法計(jì)算時，若單純形表中某一基變量Xi <0,且xi所在行的所有元

8、素都大于或等于零，則其對偶問題具有無界解。5、用位勢法計(jì)算檢驗(yàn)數(shù)時，每一行（或列）的位勢的值是唯一的，所以每一個空格的檢驗(yàn) 數(shù)是唯一的。6、動態(tài)規(guī)劃的最短路問題也可以用圖論中求最短路問題的方法求解。7、圖論中的圖是為了研究問題中有哪些對象及對象之間的關(guān)系，它與圖的幾何形狀無關(guān)。8、動態(tài)規(guī)劃只是用來解決和時間有關(guān)的問題。9、在畫網(wǎng)絡(luò)計(jì)劃圖時，允許有多個起點(diǎn)和多個終點(diǎn)。10、因?yàn)檫\(yùn)輸問題是一種特殊的線性規(guī)劃模型，因而求其解也可能出現(xiàn)下列四種情況：有 唯一最優(yōu)解；有無窮多個最優(yōu)解；無界解；無可行解。10二、試建立此問題的數(shù)學(xué)模型。（8分）某工廠I、n、出三種產(chǎn)品在下一年個季度的合同預(yù)定數(shù)如下表所示，

9、該三種產(chǎn)品第一季度初無庫存，要求在在第四季度末每種產(chǎn)品的庫存為150件。已知該廠每季度生產(chǎn)工時為15000小時，生產(chǎn)產(chǎn)品I、n、出每件需 3, 4, 3小時。因更換工藝裝備，產(chǎn)品I在第二季度無法生產(chǎn)。規(guī)定當(dāng)產(chǎn)品不能按期交貨時，產(chǎn)品I、n每件每遲交一個季度賠償20元，產(chǎn)品出賠償15元，又生產(chǎn)出來的產(chǎn)品不在本季度交貨的，每件每季度的庫存費(fèi)為5元。問應(yīng)如何安排生產(chǎn)，使總的賠償加庫存費(fèi)用最小。產(chǎn)品季度i234Ii500i0002000i200ni500i500i200i500mi5002000i5002500三、用單純形法求解線性規(guī)劃問題（16分）Max Z = 1500 xi + 2500 X2s.

10、t. 3xi + 2 x2<652 xi + x2 ,403x2三 75xi，x2 -0四、寫出下面線性規(guī)劃的對偶問題（8分）min z = x1 x2 2x3'2x1 +x2 +2x3 < 72xi - 3x2 - x? = 5- 3x1 5x2 -4x3 一 3x1 ,x20,x3無約束.五、求解下面運(yùn)輸問題。 （18分）某公司從三個產(chǎn)地Ai、A2、A3將物品運(yùn)往四個銷地Bi、B2、B3、B4,各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如表所示銷地產(chǎn)地B1B2B3B4產(chǎn)量A3ii3i07A2i9284A374i059銷量365620問：應(yīng)如何調(diào)運(yùn)，可使得

11、總運(yùn)輸費(fèi)最小六、靈敏度分析（8分）線性規(guī)劃 maxz = 4xi . x? 5x3 6x1 +3x2 +5x3 < 453x1 +4x2 +5x3 <30 x1 ,x2 , x3 > 0的最終單純形表如下：cj41500CBX Bbx1x2x3x4x54X1511/301/3-1/35x33011-1/52/550-8/301 /3-2/3(1) x1的系數(shù)Ci在什么范圍變化，上述最優(yōu)解不變？ (4分)(2) b2在什么范圍變化，最優(yōu)基不變？ (4分)七、建動態(tài)規(guī)劃模型。(8分)某公司擁有資金 10萬元，若投資于項(xiàng)目i (i=1, 2, 3)的投資額為xi時，其收益分別為g1

12、(x1)=4x1 , g2(x2)=9x2 , g3(x3)=2x32，問應(yīng)如何分配投資數(shù)額才能使總收益最大?八、解決對策問題。(10分)根據(jù)已往的資料，一家超級商場每天所需面包數(shù)(當(dāng)天市場需求量)可能是下列當(dāng)中的某一個：100, 150, 200, 250, 300,但其概率分布不知道。如果一個面包當(dāng)天賣不掉，則可在當(dāng)天結(jié)束時每個 0.5元處理掉。新鮮面包每個售價1.2元，進(jìn)價0.9元，假設(shè)進(jìn)貨量限制在需求量中的某一個，要求(1)建立面包進(jìn)貨問題的損益矩陣；(3分)(2)用樂觀法確定進(jìn)貨量。(2分)(3)建立后悔矩陣，并用后悔值法確定進(jìn)貨量。（5分）九、用雙標(biāo)號法求下列圖中 V1到V9的最短

13、路線及其長度。（6分）最后指出關(guān)鍵問題，并畫出關(guān)鍵線路。（8分，直接答在下面）十、下圖是商業(yè)中心建設(shè)項(xiàng)目的網(wǎng)絡(luò)計(jì)劃圖，請用標(biāo)號法計(jì)算出表中的各個參數(shù),工序時間開工時間完工時間機(jī)動時間最早最晚最早最晚A (20)B (10)C (8)D (24)E (8)F (14)G (10)H (6)I (12)J (6)運(yùn)籌學(xué)樣卷（一）答案判斷題。共計(jì)10分，每小題1分10XXXXV二、建線性規(guī)劃模型。共計(jì) 8分（酌情扣分）解：用X1, x2，X3分別表示大豆、玉米、麥子的種植公頃數(shù)；X4，x5分別表示奶牛和雞的飼養(yǎng)數(shù)；X6，X7分別表示秋冬季和春夏季的勞動力（人日）數(shù)，則有maxZ = 3000x141

14、00x24600x3900x420x520x625x71234567'x1 +x2 +x3 +1.5x4W100（土地限制）400x4 +3x5<15000（資金限制）20x1 +35x2 +10x3 +100x4 +0.6x5 +x6 <3500 （勞動力限制）50x1 + 175x2 +40x3 +50x4 +0.3x5 +x7 <4000 （勞動力限制）x4< 200（牛欄限制）x5<1500（雞舍限制）xj >0 （j =1,2，7）三、對偶問題。共計(jì) 8分解：（1）原線性規(guī)劃問題：maxz = 6x1 -2+10x3x2 + 2x2 蕓 5

15、« 3x1 - x2 + x3 M10lx1，x2 - 0;4 分（2）原問題的對偶規(guī)劃問題為：min w = 5y1 10 y23y2 >6j yi - y2 - -22yi y2 -10yl , y2 - 0；3 分(3 )對偶規(guī)劃問題的最優(yōu)解為：Y* = ( 4,2 )T。1分四、單純形表求解線性規(guī)劃。共計(jì) 16分解：引入松弛變量 X4 X5 X6,標(biāo)準(zhǔn)化得，maxZ =2x1 -x2 x3s. t. 3xi + X2 + X3+ X4 = 60x 1 - x 2 + 2 x 3 + X5 = 10x 1 + x 2 x 3 + X6 = 0x 1 , x 2 , x 3

16、, x4 x5 x6 > 03分建初始單純形表，進(jìn)行迭代運(yùn)算： 9分CbXbb，2-110000x1x2x3x4x5x60x460311100200x5101-1201010*0x62011-100120O102*-110000x43004-51-307.52x1101-12010-0x61002-30-115*022001*-30-200x4100011-1-22x115100.500.50.5-1x2501-1.50-0.50.552500-1.50-1.5-0.5由最優(yōu)單純形表可知，原線性規(guī)劃的最優(yōu)解為：(15,5,0 )T2分最優(yōu)值為： z*=25。2分五、求解運(yùn)輸問題。共計(jì) 1

17、8分解：(1)最小元素法：(也可以用其他方法，酌情給分)設(shè) Xj 為由 Ai 運(yùn)往 Bj 的運(yùn)量(i=1,2,3; j=1,2,3,4 ), 列表如下：銷地 產(chǎn)地B1B2B3B4產(chǎn)量1252522052531530550銷量152030351003分所以，基本的初始可行解為：X14 =25； X22=20 ； X24 =5 ；X31 =15； x33 =30； x34=5其余的Xj=0。3分(2)求最優(yōu)調(diào)運(yùn)方案：1會求檢驗(yàn)數(shù)，檢驗(yàn)解的最優(yōu)性：011=2; <512=2; 013=3;021=1 ; 023=5 ; 032= - 13 分2會求調(diào)整量進(jìn)行調(diào)整：=52分銷地 產(chǎn)地B1B2B3

18、B4產(chǎn)量12525215102531553050銷量152030351003分3再次檢驗(yàn) 2分4能夠?qū)懗稣_結(jié)論解為：x14=25 ； X22 =15 ； X24 =10 X31 =15 X32 =5 X33=30其余的xj=0。1分最少運(yùn)費(fèi)為：535 1分。六、靈敏度分析。共計(jì) 8分(1) (4 分)'8/3 2/3、1八,'-10/3、max,>< i c, < min/2、1/61/6 ,2 -2/3 ,-4 _ c1 -5 , 6=10-4 -C1c1 -10 5.15-200/31". f-100/3 -1001max一8，><

19、ib1 <min?,->,5/3 ；, -2/3-2 :-40 <山=10七、建動態(tài)規(guī)劃模型。共計(jì) 8分解：(1)設(shè)階段變量k表示年度，因此，階段總數(shù)n=3。(2)狀態(tài)變量sk表示第k年度初擁有的完好機(jī)床臺數(shù)，同時也是第 kT年度末時的完好機(jī)床數(shù)量。(3)決策變量uk,表示第k年度中分配于生產(chǎn)產(chǎn)品pl的機(jī)器臺數(shù)。于是 sk-uk便為該年度中分配于生產(chǎn)產(chǎn)品pl的機(jī)器臺數(shù).(4)狀態(tài)轉(zhuǎn)移方程為Sk 1 =0.355 0.65(Sk -Uk)(5)允許決策集合，在第k段為Uk(sk)=uk 0< uk <sk(6)目標(biāo)函數(shù)。設(shè) gk(sk,uk)為第k年度的產(chǎn)量，則gk

20、(sk,uk) = 45 uk + 35(sk pk),因此，目標(biāo)函/為Rk = " gk(Sk,uk) i -k(7)條件最優(yōu)目標(biāo)而數(shù)遞推方程。fk(Sk) =mqx(uk(Sk)uk Uk令fk(sk)表示由第k年的狀態(tài)sk出發(fā)，采取最優(yōu)分配方案到第3年度結(jié)束這段時間的產(chǎn)品產(chǎn)量，根據(jù)最優(yōu)化原理有以下遞推關(guān)系：45uk 35(sk - uk) fk 10.35uk 0.65(標(biāo)-uk) (8).f3 1 (s3 1 ) = 0八、解決對策問題。共 10分(1)益損矩陣如下表所示：3分銷售 訂購Si500S21000S3 1500S42000Ai 500150015001500150

21、0A210000300030003000A3 1500-1500150045004500A4 2000 3000030006000(2)悲觀法：Ai ,訂購500公斤。2分(3)后悔矩陣如下表所示： 3分SiS2S3S4最大后悔值A(chǔ)i01500300045004500A215000150030003000A330001500015003000A445003000150004500按后悔值法商店應(yīng)取決策為A2或A3 ,即訂購1000公斤或1500公斤。九、求網(wǎng)絡(luò)計(jì)劃圖的各時間參數(shù)。（8分）/14 1-14、 526 01118工序 代號工序 時間最早開 工時間最早完 工時間最晚開 工時間最晚完

22、工時間機(jī)動 時間1-28080801-37072921-460651162-4381181102-5581391413-427991123-63710151884-531114111404-671118111804-7411152226115-791423172636-78182618260關(guān)鍵問題是：；2f ； -6; 6f 關(guān)鍵線路是：評分標(biāo)準(zhǔn)：能正確給各頂點(diǎn)標(biāo)號并填表 4分正確寫出關(guān)鍵問題 2分正確畫出關(guān)鍵線路2分十、用標(biāo)號法求V1到V6的最短路。（6分）正確標(biāo)號：4分；正確寫出結(jié)論：2分運(yùn)籌學(xué)樣卷（二）答案判斷題。（共計(jì)10分，每小題1分）10XXXXXXX二、建線性規(guī)劃模型。（8分）

23、（酌情給分）解：設(shè)為j為第i個季度生產(chǎn)的產(chǎn)品j的數(shù)量；si j為第i個季度末需庫存的產(chǎn)品j的數(shù)量;ti j為第i個季度不能交貨的產(chǎn)品 j的數(shù)量；yi j為第i個季度對產(chǎn)品j的預(yù)定數(shù)量，則有： min Z 二1 20（ti1 ti2） 15ti3 1 5;二 si）'ll I 4 /I jjI jXii+Xi2+Xi3 £15000 (i=1,2,3,4)X21 = 0 44£ " =£ yij +150 (j =1,2,3) iqiii工 Xkj +3 Sj =£ ykj (i =1,2,3,4; j =1,2,3) kqkJ xi j

24、 , si j , ti j - 0三、求解線性規(guī)劃。(16分)解：引入松弛變量 x3, x4, x5,標(biāo)準(zhǔn)化得，Max Z = 1500X1 + 2500X2s.t. 3 x1 + 2x2 + x3 = 652x1 + x2 + x4 = 403 x2 + x5 =75x1, x2 >0 3分建初始單純形表，進(jìn)行迭代運(yùn)算： 9 分CbXbb，150025001000X1X2X3X4X50X3653210032.50X44021010400X575030012.5*O1015002500*0000X3153010-2/35*0X4152001-1/37.52500X22501001/3-

25、02625001500*000-2500/31500X15101/30-2/90X4500-2/311/92500X22501001/3a37000000-5000-500(5, 25,0, 5,0 )T 2 分由最優(yōu)單純形表可知原線性規(guī)劃的最優(yōu)解為:最優(yōu)值為：z*=70000。2分四、解：原問題的對偶規(guī)劃問題為：（共8分）Max f=7y 1+5y2+3y32yi +2y2 -3y3 W1%-3y2+5丫3<12yi - y2 - 4y3 = 2&i«0,y2無約束,V3±Q五、求解運(yùn)輸問題。（18分）解：（1）最小元素法：設(shè) xj 為由 Ai 運(yùn)往 Bj

26、的運(yùn)量（i=1,2,3; j=1,2,3,4 ）, 列表如下：銷地 產(chǎn)地B1B2B3B4產(chǎn)量143723143639銷量3656203分所以，基本的初始可行解為：x13=4 ； x14 =3 ；X21 =3 X23 =21X32 =6 X34=3其余的Xij=0 3分（2）求最優(yōu)調(diào)運(yùn)方案：0 11 二 1,C12 = 2,0 22 二 1,1會求檢驗(yàn)數(shù)，檢驗(yàn)解的最優(yōu)性：仃24 = -1031 =10933 =122會求調(diào)整量進(jìn)行調(diào)整：e=1 2分銷地 產(chǎn)地B1B2B3B4產(chǎn)量152723143639銷量3656203再次檢驗(yàn)4能夠?qū)懗稣_結(jié)論解為：xi3=5 ； x14 =2 ； x21 =3 x24 =1x32 =6 x34=3其余的xj=0。1分最少運(yùn)費(fèi)f =3M5+10M2+1M3+8M1+4M6+5M3 = 85i 分六、靈敏度分析。(8分)(1) (4 分)max 3-1/31/3< A C）< min n-8/3 -2/3-1/3, -1/3-1 _ ：c1 _2 , 3 =4 -1 _c1：c1 _ 4 2 = 6（4分）3C30 , 2/5<ib2 < min一 一5-1/3-7.5 < . ： b2 =15七、建動態(tài)規(guī)劃模型。(8分)1 .分階段：設(shè)階段變量 k表示依次對第