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

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

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

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

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

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

7、工時間機動時間1-281-371-462-432-553-423-634-534-674-745-796-78十、用標號法求V1 到 V6 的最短路。（6分）3V4V5V3V1V2V6465664384運籌學試題樣卷（二）題號一二三四五六七八九十總分得分一、判斷題（對的打，錯的打X. 共計10分，答在下面的表格中）1、單純形法計算中，選取最大正檢驗數(shù)對應的變量作為換入變量，可使目標函數(shù)值得到最快的減少。2、單純形法計算中，如不按最小非負比值原則選出換出變量，則在下一個解中至少有一個基變量的值是負的。 3、對于一個動態(tài)規(guī)劃問題，應用順推法和逆推法可能會得到不同的最優(yōu)解。 4、應用對偶單純形法計算

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

9、產(chǎn)品在下一年個季度的合同預定數(shù)如下表所示，該三種產(chǎn)品第一季度初無庫存，要求在在第四季度末每種產(chǎn)品的庫存為150件。已知該廠每季度生產(chǎn)工時為15000小時，生產(chǎn)產(chǎn)品、每件需3，4，3小時。因更換工藝裝備，產(chǎn)品在第二季度無法生產(chǎn)。規(guī)定當產(chǎn)品不能按期交貨時，產(chǎn)品、每件每遲交一個季度賠償20元，產(chǎn)品賠償15元，又生產(chǎn)出來的產(chǎn)品不在本季度交貨的，每件每季度的庫存費為5元。問應如何安排生產(chǎn)，使總的賠償加庫存費用最小。產(chǎn) 品季 度1234150010002000120015001500120015001500200015002500三、用單純形法求解線性規(guī)劃問題 （ 16分 ）Max Z = 1500 x1

10、 + 2500 x2s.t. 3x1 + 2 x2 652 x1 + x2 403x2 75x1, x2 0四、寫出下面線性規(guī)劃的對偶問題 ( 8分 )；五 、求解下面運輸問題。 （ 18分 ） 某公司從三個產(chǎn)地A1、A2、A3 將物品運往四個銷地B1、B2、B3、B4，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地每件物品的運費如表所示銷 地產(chǎn) 地產(chǎn) 量311310719284741059銷 量365620問：應如何調(diào)運，可使得總運輸費最小?六、靈敏度分析（ 8分 ）線性規(guī)劃 的最終單純形表如下：41500451/301/31/3530111/52/5sj08/3/32/3（1） 的系數(shù)C1在

11、什么范圍變化，上述最優(yōu)解不變？（4分）（2）b2在什么范圍變化，最優(yōu)基不變？（4分）七、建動態(tài)規(guī)劃模型。（8分）某公司擁有資金 10 萬元，若投資于項目 i (i1，2，3) 的投資額為 xi 時，其收益分別為 g1(x1)=4x1 , g2(x2)=9x2 , g3(x3)=2x32 ,問應如何分配投資數(shù)額才能使總收益最大? 八、解決對策問題。（10分）根據(jù)已往的資料，一家超級商場每天所需面包數(shù)（當天市場需求量）可能是下列當中的某一個：100，150，200，250，300，但其概率分布不知道。如果一個面包當天賣不掉，則可在當天結(jié)束時每個0.5元處理掉。新鮮面包每個售價1.2元，進價0.9元

12、，假設進貨量限制在需求量中的某一個，要求（1）建立面包進貨問題的損益矩陣；（3分）（2）用樂觀法確定進貨量。（2分）（3）建立后悔矩陣，并用后悔值法確定進貨量。（5分）九、用雙標號法求下列圖中到的最短路線及其長度。（ 6分 ）4323483331221十、下圖是商業(yè)中心建設項目的網(wǎng)絡計劃圖，請用標號法計算出表中的各個參數(shù)，最后指出關鍵問題，并畫出關鍵線路。 （8分，直接答在下面）ABCDGHEFJI314591068720108248141061262工序時間開工時間完工時間機動時間最早最晚最早最晚A （20）B （10）C （8）D （24）E （8）F （14）G （10）H （6）I （

13、12）J （6）運籌學樣卷（一）答案一、 判斷題。共計10分，每小題1分10XXXX二、建線性規(guī)劃模型。共計8分（酌情扣分）解：用分別表示大豆、玉米、麥子的種植公頃數(shù)；分別表示奶牛和雞的飼養(yǎng)數(shù)；分別表示秋冬季和春夏季的勞動力（人日）數(shù)，則有三、對偶問題。共計8分解：（）原線性規(guī)劃問題：；4分（）原問題的對偶規(guī)劃問題為：； 3分（）對偶規(guī)劃問題的最優(yōu)解為：T 。1分四、單純形表求解線性規(guī)劃。共計16分解：引入松弛變量x4、 x5、 x6，標準化得，s. t. 3 x1 + x2 + x3+ x4 = 60x 1- x 2 +2 x 3 + x5 = 10x 1+ x 2- x 3 + x6 =

14、0x 1, x 2 , x 3， x4、 x5、 x6，03分建初始單純形表，進行迭代運算： 9分CBXbb2-11000x1x2x3x4x5x60x460311100200x5101-1201010*0x62011-100120s102*-110000x43004-51-307.52x1101-12010-0x61002-30-115*s22001*-30-200x4100011-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*=

15、25。2分五、求解運輸問題。共計18分解：（1）最小元素法：（也可以用其他方法，酌情給分）設xij為由Ai運往Bj的運量（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)調(diào)運方案：1會求檢驗數(shù)，檢驗解的最優(yōu)性：s11=2；s12=2；s13=3；s21=1；s23=5；s32= - 13分2會求調(diào)整量進行調(diào)整：=5 2分銷 地產(chǎn) 地產(chǎn) 量1231

16、5155302510252550銷 量152030351003分3再次檢驗 2分4能夠?qū)懗稣_結(jié)論解為：x14=25 ； x22 =15 ； x24 =10 x31 =15， x32 =5 x33=30其余的xij=0。 1分最少運費為： 535 1分。六、靈敏度分析。共計8分（1）（4分）（2）（4分）七、建動態(tài)規(guī)劃模型。共計8分解：(1)設階段變量k表示年度，因此，階段總數(shù)n=3。(2)狀態(tài)變量sk表示第k年度初擁有的完好機床臺數(shù)， 同時也是第 k1 年度末時的完好機床數(shù)量。(3)決策變量uk，表示第k年度中分配于生產(chǎn)產(chǎn)品 p1 的機器臺數(shù)。于是sk uk便為該年度中分配于生產(chǎn)產(chǎn)品 p1的

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

18、00450030001500300045006000（2）悲觀法：A1 ，訂購500公斤。2分（3）后悔矩陣如下表所示：3分S1S2S3S4最大后悔值A101500300045004500A215000150030003000A330001500015003000A445003000150004500按后悔值法商店應取決策為A2或A3 ，即訂購1000公斤或1500公斤。2分68123457563793427830871114182626141811980九、求網(wǎng)絡計劃圖的各時間參數(shù)。（8分）工序代號工序時間最早開工時間最早完工時間最晚開工時間最晚完工時間機動時間1-28080801-3707

19、2921-460651162-4381181102-5581391413-427991123-63710151884-531114111404-671118111804-7411152226115-791423172636-78182618260關鍵問題是：；2；6；6關鍵線路是：12467評分標準：能正確給各頂點標號并填表.4分正確寫出關鍵問題. 2分正確畫出關鍵線路. 分十、用標號法求v1 到 v6 的最短路。（6分）4V4V5V3V1V2V6628737152(0,0)(4,v1)(6,v2)（8,v1）(9,v3)(10,v2) (10,v4)(11,v2)(13,v3)(12,v5)

20、(14,v4) 最短路為：v1,v2,v3,v4,v5,v6長度為：12正確標號：4分；正確寫出結(jié)論：2分運籌學樣卷(二)答案二、 判斷題。（共計10分，每小題1分）10XXXXXXX二、建線性規(guī)劃模型。（8分）（酌情給分）解：設為第個季度生產(chǎn)的產(chǎn)品的數(shù)量；為第個季度末需庫存的產(chǎn)品的數(shù)量；為第個季度不能交貨的產(chǎn)品的數(shù)量；為第個季度對產(chǎn)品的預定數(shù)量，則有：三、求解線性規(guī)劃。（16分）解：引入松弛變量x3, x4, x5，標準化得，Max Z = 1500X1 + 2500X2s.t. 3 x1 + 2x2 + x3 = 652x1 + x2 + x4 = 403 x2 + x5 =75x1, x

21、2 0 3分建初始單純形表，進行迭代運算：9分CBXb1x2x3x4x50x3653210032.50x44021010400x575030012.5*s1015002500*0000x3153010-2/35*0x4152001-1/37.52500x225010 01/3-s2625001500*000-2500/31500x15101/30-2/90x4500-2/311/92500x22501001/3s37000000-5000-500由最優(yōu)單純形表可知原線性規(guī)劃的最優(yōu)解為： ( 5, 25 , 0, 5 , 0 )T 2分最優(yōu)值為： z*=70000。2分

22、四、解：原問題的對偶規(guī)劃問題為：（共8分）Max f=7y1+5y2+3y3五、求解運輸問題。（18分）解：（1）最小元素法：設xij為由Ai運往Bj的運量（i=1,2,3; j=1,2,3,4）,列表如下： 銷 地產(chǎn) 地產(chǎn) 量123364133749銷 量3656203分所以，基本的初始可行解為：x13=4 ； x14 =3 ；x21 =3 x23 =21x32 =6 x34=3其余的xij=0。 3分（2）求最優(yōu)調(diào)運方案：1會求檢驗數(shù)，檢驗解的最優(yōu)性：3分2會求調(diào)整量進行調(diào)整： 2分銷 地產(chǎn) 地產(chǎn) 量123365213749銷 量3656203分3再次檢驗 2分4能夠?qū)懗稣_結(jié)論解為：x13=5 ； x14 =2 ； x21 =3 x24 =1， x32 =6 x34=3其余的xij=0。 1分最少運費 1分六、靈敏度分析。（8分）（1）（4分）（2）（4分）七、建動態(tài)規(guī)劃模型。（8分）1分階段：設階段變量 k 表示依次對第 k 個項目投資，因此，階段總數(shù) n = 3。( k = 1 , 2 , 3 )2. 狀態(tài)變量：用 sk 表示已經(jīng)對第 1 至第 k-1 個項目投資后的剩余資金；即第 k 段初擁有的可以分配給第 k 到第3個項目的資金額 （單位：萬元） 。3. 決策變量：用 xk 表示對第 k 個項目投資 的資金數(shù)量（單位：