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

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

3、如下表所示：大豆秋冬季需人日數203510春夏季需人日數507540年凈收入（元/公頃）300041004600試決定該農場的經營方案，使年凈收入為最大。三、已知下表為求解某目標函數為極大化線性規劃問題的最終單純形表，表中x4 ,x5為松弛變量，問題的約束為形式（共8分）xix2乂3x4x5x35/201/211/20xi5/211/20-1/61/3cj -zj0一 40一 42（1）寫出原線性規劃問題；（4分）（2）寫出原問題的對偶問題；（3分）（3）直接由上表寫出對偶問題的最優解。（1分）四、用單純形法解下列線性規劃問題（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五、求解下面運輸問題。（18分）某公司從三個產地AA2、A3將物品運往四個銷地B1、B2、B3、B4,各產地的產量、各銷地的銷量和各產地運往各銷地每件物品的運費如表所示：問：應如何調運，可使得總運輸費最小？產地銷地B2B3B4產量Ai1056725A2827625A3934850銷、靈敏度分析（共 8分）線性規戈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的最優單純形表如下:6X2200/305/615/3-1/6010X1100/311/60-2/31/600X6100040-201可06/30-10/3-2/30（1）C1在何范圍內變化，最優計劃不變？（4分）（2）bl在什么范圍內變化，最優基不變？（4分）七、試建立一個動態規劃模型。（共8分）某工廠購進100臺機器，準備生產pl , p2兩種產品。若生產產品 pl，每臺機器每年可收入45萬元，損壞率為 65%;若生產產品 p2 ,每臺機器 每年可收入35萬元，損壞率為35% ;估計三年后將有

6、新 的機器出現，舊的機器將全部淘汰。試問每年應如何安排生產，使在三年內收入最多？八、求解對策問題。（共10分）某種子商店希望訂購一批種子。據已往經驗，種子的銷售量可能為 500, 1000, 1500或2000公斤。假定每公斤種子的訂購價為6元，銷售價為9元，剩余種子的處理價為每公斤3元。要求：（1）建立損益矩陣；（3分）（2）用悲觀法決定該商店應訂購的種子數。（2分）（3）建立后悔矩陣，并用后悔值法決定商店應訂購的種子數。（5分）九、求下列網絡計劃圖的各時間參數并找出關鍵問題和關鍵路徑。（8分）工序 代號工序 時間最早開 工時間最早完 工時間最晚開 工時間最晚完 工時間機動 時間1-281-

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

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

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

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

11、總運輸費最小六、靈敏度分析（8分）線性規劃 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的系數Ci在什么范圍變化，上述最優解不變？ (4分)(2) b2在什么范圍變化，最優基不變？ (4分)七、建動態規劃模型。(8分)某公司擁有資金 10萬元，若投資于項目i (i=1, 2, 3)的投資額為xi時，其收益分別為g1

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

13、路線及其長度。（6分）最后指出關鍵問題，并畫出關鍵線路。（8分，直接答在下面）十、下圖是商業中心建設項目的網絡計劃圖，請用標號法計算出表中的各個參數,工序時間開工時間完工時間機動時間最早最晚最早最晚A (20)B (10)C (8)D (24)E (8)F (14)G (10)H (6)I (12)J (6)運籌學樣卷（一）答案判斷題。共計10分，每小題1分10XXXXV二、建線性規劃模型。共計 8分（酌情扣分）解：用X1, x2，X3分別表示大豆、玉米、麥子的種植公頃數；X4，x5分別表示奶牛和雞的飼養數；X6，X7分別表示秋冬季和春夏季的勞動力（人日）數，則有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）三、對偶問題。共計 8分解：（1）原線性規劃問題：maxz = 6x1 -2+10x3x2 + 2x2 蕓 5

15、« 3x1 - x2 + x3 M10lx1，x2 - 0;4 分（2）原問題的對偶規劃問題為：min w = 5y1 10 y23y2 >6j yi - y2 - -22yi y2 -10yl , y2 - 0；3 分(3 )對偶規劃問題的最優解為：Y* = ( 4,2 )T。1分四、單純形表求解線性規劃。共計 16分解：引入松弛變量 X4 X5 X6,標準化得，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分建初始單純形表，進行迭代運算： 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由最優單純形表可知，原線性規劃的最優解為：(15,5,0 )T2分最優值為： z*=25。2分五、求解運輸問題。共計 1

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

18、B4產量12525215102531553050銷量152030351003分3再次檢驗 2分4能夠寫出正確結論解為：x14=25 ； X22 =15 ； X24 =10 X31 =15 X32 =5 X33=30其余的xj=0。1分最少運費為：535 1分。六、靈敏度分析。共計 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七、建動態規劃模型。共計 8分解：(1)設階段變量k表示年度，因此，階段總數n=3。(2)狀態變量sk表示第k年度初擁有的完好機床臺數，同時也是第 kT年度末時的完好機床數量。(3)決策變量uk,表示第k年度中分配于生產產品pl的機器臺數。于是 sk-uk便為該年度中分配于生產產品pl的機器臺數.(4)狀態轉移方程為Sk 1 =0.355 0.65(Sk -Uk)(5)允許決策集合，在第k段為Uk(sk)=uk 0< uk <sk(6)目標函數。設 gk(sk,uk)為第k年度的產量，則gk

20、(sk,uk) = 45 uk + 35(sk pk),因此，目標函/為Rk = " gk(Sk,uk) i -k(7)條件最優目標而數遞推方程。fk(Sk) =mqx(uk(Sk)uk Uk令fk(sk)表示由第k年的狀態sk出發，采取最優分配方案到第3年度結束這段時間的產品產量，根據最優化原理有以下遞推關系：45uk 35(sk - uk) fk 10.35uk 0.65(標-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最大后悔值Ai01500300045004500A215000150030003000A330001500015003000A445003000150004500按后悔值法商店應取決策為A2或A3 ,即訂購1000公斤或1500公斤。九、求網絡計劃圖的各時間參數。（8分）/14 1-14、 526 01118工序 代號工序 時間最早開 工時間最早完 工時間最晚開 工時間最晚完

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

23、（酌情給分）解：設為j為第i個季度生產的產品j的數量；si j為第i個季度末需庫存的產品j的數量;ti j為第i個季度不能交貨的產品 j的數量；yi j為第i個季度對產品j的預定數量，則有： 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三、求解線性規劃。(16分)解：引入松弛變量 x3, x4, x5,標準化得，Max Z = 1500X1 + 2500X2s.t. 3 x1 + 2x2 + x3 = 652x1 + x2 + x4 = 403 x2 + x5 =75x1, x2 >0 3分建初始單純形表，進行迭代運算： 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 分由最優單純形表可知原線性規劃的最優解為:最優值為：z*=70000。2分四、解：原問題的對偶規劃問題為：（共8分）Max f=7y 1+5y2+3y32yi +2y2 -3y3 W1%-3y2+5丫3<12yi - y2 - 4y3 = 2&i«0,y2無約束,V3±Q五、求解運輸問題。（18分）解：（1）最小元素法：設 xj 為由 Ai 運往 Bj

26、的運量（i=1,2,3; j=1,2,3,4 ）, 列表如下：銷地 產地B1B2B3B4產量143723143639銷量3656203分所以，基本的初始可行解為：x13=4 ； x14 =3 ；X21 =3 X23 =21X32 =6 X34=3其余的Xij=0 3分（2）求最優調運方案：0 11 二 1,C12 = 2,0 22 二 1,1會求檢驗數，檢驗解的最優性：仃24 = -1031 =10933 =122會求調整量進行調整：e=1 2分銷地 產地B1B2B3B4產量152723143639銷量3656203再次檢驗4能夠寫出正確結論解為：xi3=5 ； x14 =2 ； x21 =3 x24 =1x32 =6 x34=3其余的xj=0。1分最少運費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七、建動態規劃模型。(8分)1 .分階段：設階段變量 k表示依次對第