運籌學(xué)期末試題

1、運籌學(xué)試題樣卷（一）題號-一-二二三四五六七八九十總分得分、判斷題（共計 10 分，每小題 1 分，對的打，錯的打 X）1.無孤立點的圖一定是連通圖。2.對于線性規(guī)劃的原問題和其對偶問題，若其中一個有最優(yōu)解，另一個也一定有最優(yōu)解。3.如果一個線性規(guī)劃問題有可行解，那么它必有最優(yōu)解。4對偶問題的對偶問題一定是原問題。05 用單純形法求解標(biāo)準形式（求最小值）的線性規(guī)劃問題時，與j對應(yīng)的變量都可以被選作換入變量。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)雞時不占用土地

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

4、原問題的對偶問題；（3 分）（3）直接由上表寫出對偶問題的最優(yōu)解。（1 分）四、用單純形法解下列線性規(guī)劃問題（16 分）max Z2xx2x3S. t.3 X1+X2+X360 x1-X2+2 X310X1+X2-x320 x1,x2,x30五、求解下面運輸問題。（18 分）某公司從三個產(chǎn)地 A1、A2、A3將物品運往四個銷地 B1、B2、B3、B4，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地每件物品的運費如表所示：問：應(yīng)如何調(diào)運，可使得總運輸費最小 ？銷地產(chǎn)地BB2B3B4產(chǎn)量A1056725A2827625A3934850銷、靈敏度分析（共 8 分）線性規(guī)劃ma

5、x z = 10X1+ 6x2+ 4x3S.t. X1+ X2+ X310010 x1+4 X2+ 5 X3600X4,X5為2x1+2 X2+ 6 X3300X1, X2, X30的最優(yōu)單純形表如下:6X2200/305/615/3-1/6010X1100/311/60-2/31/600X6100040-201j0-/30-10/3-2/30（1）C1在何范圍內(nèi)變化，最優(yōu)計劃不變？（4 分）（2）bi在什么范圍內(nèi)變化，最優(yōu)基不變？（4 分）七、試建立一個動態(tài)規(guī)劃模型。（共 8 分）某工廠購進 100 臺機器，準備生產(chǎn) pl , p2 兩種產(chǎn)品。若生產(chǎn)產(chǎn)品 pl，每臺機器每年可收 入 45 萬

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

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

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

9、建立此問題的數(shù)學(xué)模型。（8 分）某工廠I、川三種產(chǎn)品在下一年個季度的合同預(yù)定數(shù)如下表所示，該三種產(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)品不在本季度交貨的，每件每季度的庫存費為5 元。問應(yīng)如何安排生產(chǎn)，使總的賠償加庫存費用最小。含 口 產(chǎn) 口仃季度1234I1500100020001200n1500150012001500出1500

10、200015002500三、 用單純形法求解線性規(guī)劃問題（16 分）Max Z = 1500 xi+ 2500 x2s.t.3xi+ 2 x2652 xi+ x2403X275xi, x20四、 寫出下面線性規(guī)劃的對偶問題（8 分）min zx1x22x32x1x22x372x13x2X353x15x24X33x1,x20, x3無約束；五、求解下面運輸問題。（18 分）某公司從三個產(chǎn)地 A1、A2、A3將物品運往四個銷地 B1、B2、B3、B4，各產(chǎn)地的產(chǎn)量、各 銷地的銷量和各產(chǎn)地運往各銷地每件物品的運費如表所示銷地產(chǎn)地B1B2B3B4產(chǎn)量A3113107A219284A3741059銷量3

11、65620問：應(yīng)如何調(diào)運，可使得總運輸費最小六、靈敏度分析（8 分）線性規(guī)劃maxz 4xlx25x36x13x23x14x25x3455x330為，X2, X30的最終單純形表如下:Cj41500CBXBbX1X2X3X4X54X1511/301/31/35x330111/52/5j08/301/32/3(1)Xl的系數(shù) Ci在什么范圍變化，上述最優(yōu)解不變？ (4 分)(2)b2在什么范圍變化，最優(yōu)基不變？( 4 分)七、 建動態(tài)規(guī)劃模型。(8 分)某公司擁有資金 10 萬元，若投資于項目 i (i = 1, 2, 3)的投資額為 xi 時，其收益分別為 g1(x1)=4x1 ,g2(x2)

12、=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 元，進價 0.9 元，假設(shè)進貨量限制在需求量中的某一個，要求(1)建立面包進貨問題的損益矩陣；(3 分)(2) 用樂觀法確定進貨量。(2 分)(3)建立后悔矩陣，并用后悔值法確定進貨量。(5分)九、用雙標(biāo)號法求下列圖中Vl到V9的最短路線及其長度。（6

13、 分）十、下圖是商業(yè)中心建設(shè)項目的網(wǎng)絡(luò)計劃圖，請用標(biāo)號法計算出表中的各個參數(shù)，最后指工序時間開工時間完工時間機動時間最早最晚最早最晚A （ 20）B （ 10）C （ 8）D （ 24）Vi出關(guān)鍵問題，并畫出關(guān)鍵線路。（8 分，直接答在下面）B C D E JV34121E （ 8）答案判斷題。共計 10 分，每小題 1 分10XXVVXVXV（2）原問題的對偶規(guī)劃問題為:maxZ3000X14100X24600X3900X420X520X625X7X1X2X31.5X4100（土地限制）400X43x515000（資金限制）20 x135x210 x3100 x40.6%x63500（勞動力

14、限制）50 x1175x240X350X40.3%x74000（勞動力限制）X4200（牛欄限制）X51500（雞舍限制）Xj0 (j1,2,7)三、對偶問題。共計-8分解：（1）原線性規(guī)劃問題：maxz 6x12x210 x3x22x253x1x2x310則有Xi, X24 分F (14)G (10)H (6)I (12)J (6)運籌學(xué)樣卷（一）二、建線性規(guī)劃模型。共計 8 分（酌情扣分）解：用Xi，X2，X3分別表示大豆、玉米、麥子的種植公頃數(shù)； 飼養(yǎng)數(shù)；X6，X7分別表示秋冬季和春夏季的勞動力（人日）數(shù),X4，X5分別表示奶牛和雞的min w 5y110 y23y26yiy222yiy

15、210yi，y20；3分（3）對偶規(guī)劃問題的最優(yōu)解為：Y （4，2）T。1分四、單純形表求解線性規(guī)劃。共計16 分解：引入松弛變量X4、X5、X6，標(biāo)準化得，maxZ 2x1x2x3s. t. 3X1+X2+X3+X4=60X1-X2+2 X3+X5=10X1+X2-X3+X6=0X1,X2,X3,X4、X5、X6,0.3分建初始單純形表，進行迭代運算：.9分CBXbb2-110000X1X2X3X4X5X60X460311100200X5101-1201010*0X62011-100120102*-110000X43004-51-307.52X1101-120100X61002-30-115

16、*22001*-30-200X4100011-1-22X115100.500.50.5-1X2501-1.50-0.50.532500-1.50-1.5-0.5由最優(yōu)單純形表可知，原線性規(guī)劃的最優(yōu)解為：（15,5,0 ）T分最優(yōu)值為：z*=25。.2分五、求解運輸問題。共計 18 分解：(1)最小兀素法：(也可以用其他方法，酌情給分)設(shè)Xij為由 Ai運往Bj的運量(i=1,2,3; j=1,2,3,4 )列表如下：銷地 產(chǎn)地B1B2B3B4產(chǎn)量1252522052531530550銷3分所以，基本的初始可行解為：X14 =25；X22=20；X24 =5；X31 =

17、15；X33 =30；X34=5其余的Xij=o。.3分(2)求最優(yōu)調(diào)運方案：1 會求檢驗數(shù)，檢驗解的最優(yōu)性：1 仁 2;12=2 ;13=3 ;21=1 ;23=5 ;32= - 1.3分2 會求調(diào)整量進行調(diào)整： =5.2分銷地 產(chǎn)地B1B2B3B4產(chǎn)量12525215102531553050銷量152030351003分3 再次檢驗.2分4 能夠?qū)懗稣_結(jié)論解為：X14=25;X22 =15;X24 =10X31 =15,X32 =5X33=30其余的Xij=0。.1分最少運費為： 535.1分。六、靈敏度分析。共計 8 分(1) (4 分)(2) (4 分)8/32/3max,-10/3

18、G min -c15 , 610 4 c1c110 515按后悔值法商店應(yīng)取決策為A2或 A3，即訂購 1000 公斤或 1500 公斤。2分200/3.100/3100max ,b. min,-5/32/3240 b 10七、 建動態(tài)規(guī)劃模型。共計8 分解：(1)設(shè)階段變量 k 表示年度，因此，階段總數(shù)n=3。狀態(tài)變量 sk 表示第 k 年度初擁有的完好機床臺數(shù)，同時也是第 k -1 年度末時的完好機床數(shù)量。(3) 決策變量 uk，表示第 k 年度中分配于生產(chǎn)產(chǎn)品p1 的機器臺數(shù)。于是 sk-uk 便為該年度中分配于生產(chǎn)產(chǎn)品p1 的機器臺數(shù).(4)狀態(tài)轉(zhuǎn)移方程為Sk10.35uk0.65(

19、s0.3分建初始單純形表，進行迭代運算：.9分CBXbb150025001000X1X2X3X4X50X3653210032.50X44021010400X575030012.5*1015002500*0000X3153010-2/35*0X4152001-1/37.52500X22501001/32625001500*000-2500/31500X15101/30-2/90X4500-2/311/92500X22501001/337000000-5000-500由最優(yōu)單純形表可知原線性規(guī)劃的最優(yōu)解為：(5, 25,0, 5,0 )T.2 分最優(yōu)值為：z*=70000。.2 分四、解：原問題的

20、對偶規(guī)劃問題為：(共 8 分)Max f=7y計5y2+3y32yi2y23y31yi3y25y312yiy24y32yl0,y2無約束，y30五、求解運輸問題。(18 分) 解：(1)最小元素法：設(shè)Xij為由 Ai運往Bj的運量(i=1,2,3; j=1,2,3,4) 列表如下：銷地 產(chǎn)地B1B2B3B4產(chǎn)量143723143639銷量365620所以，基本的初始可行解為：X13=4；X14 =3；X21 =3X23 =21X32 =6X34=3其余的Xij=0。.3分(2)求最優(yōu)調(diào)運方案：1 會求檢驗數(shù)，檢驗解的最優(yōu)性：2 會求調(diào)整量進行調(diào)整：1111,122,221,241,3110,3

21、3123 再次檢驗4 能夠?qū)懗稣_結(jié)論解為：Xi3=5;X14 =2;X21 =3X24 =1,X32 =6X34=3其余的Xj=o。.1分最少運費f 3 5 10 2 1 3 8 1 4 6 5 3 85.i分六、靈敏度分析。（8 分）（1）（ 4 分）max1/3C1min8/32/31/31/3,1/31(2) (4 分)C12 ,34 1C1c14 26max3b2min52/51/37.5b215七、 建動態(tài)規(guī)劃模型。（8 分）1 分階段：設(shè)階段變量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ù)量（單位：萬元）。4 .狀態(tài)轉(zhuǎn)移方程為：sk 1skXk5.決策變量的取值：0Xk sk6.基本方程為：最優(yōu)指標(biāo)函數(shù)fk（sk）表示第k階段，初始狀態(tài)為sk時，從第k到第 3 個 項目所獲最大收益fk（sk） maXgk（Xk） fk1（Sk1）k