(完整版)應(yīng)用運籌學(xué)補充練習(xí)題參考答案

1、1、某商店要制定明年第一季度某種商品的進貨和銷售計劃，已知該店的倉庫容量最多可儲存該種商品500 件，而今年年底有200 件存貨。該店在每月月初進貨一次。已知各個月份進貨和銷售該種商品的單價如下表所示：月份1月2月3月進貨單價（元/件）869銷售單價（元/件）9810現(xiàn)在要確定每個月進貨和銷售多少件，才能使總利潤最大，把這個問題表達成一個線性規(guī)劃模型。解：設(shè)Xi 是第i 個月的進貨件數(shù)，Yi是第 i 個月的銷貨件數(shù)（i=1, 2, 3） ， Z 是總利潤，于是這個問題可表達為：目標函數(shù)：Max Z=9Y 1+8Y 2+10Y 3 8X 1 5X2 9X3約束條件：200+X 1 500200+

2、X 1 Y1+X 2 500月初庫存約束200+X 1 Y1 X2 Y2 X3 500200+X 1-Y 10200+X 1-Y 1+X2-Y20月末庫存約束200+X1-Y1+X2-Y2+X3-Y30X 1， X2， X3， Y 1， Y2， Y3 0Y 1*=500,Y 2*=0 ， Y3*=500,EXCEL 求解最優(yōu)解結(jié)果：X1*= 300 ， X 2*=500 ， X3*=0 ，Z*=41002、一種產(chǎn)品包含三個部件，它們是由四個車間生產(chǎn)的，每個車間的生產(chǎn)小時總數(shù)是有限的，下表中給出三個部件的生產(chǎn)率，目標是要確定每個車間應(yīng)該把多少工時數(shù)分配到各個部件上，才能使完成的產(chǎn)品件數(shù)最多。把這

3、個問題表示成一個線性規(guī)劃問題車間生產(chǎn)能力（小時）生產(chǎn)率（件數(shù)/小時）部件部件部件甲10010155乙15015105丙8020510丁200101520解：設(shè) Xij是車間 i 在制造部件j 上所花的小時數(shù)，Y 是完成產(chǎn)品的件數(shù)。最終的目的是Y 要滿足條件：min10X 11+15X21+20X31+10X41， 15X12+10X22+5X32+15X42， 5X13+5X23+10X33+20X43可將以上非線性條件轉(zhuǎn)化為以下線性規(guī)劃模型：目標函數(shù)：Max Z = Y約束條件：Y 10X11+15X21+20X31+10X41Y 15X12+10X22+5X32+15X42Y 5X13+5

4、X23+10X33+20X43X 11+X 12+X 13 100X21+X22+X23 150X31+X32+X33 80X41+X42+X43 200Xij0（ i=1 ，2，3，4；j=1 ，2，3） ,Y0EXCEL 求解最優(yōu)解結(jié)果：X 11*=X 12*=X13*=，X21*=， X22*= ，X23*=X 31*=X32*=X33*=，Y* =3、一個投資者打算把它的100000 元進行投資，有兩種投資方案可供選擇。第一種投資保證每元投資一年后可賺角錢。第二種投資保證每元投資兩年后可賺元。但對第二種投資，投資的時間必須是兩年的倍數(shù)才行。假設(shè)每年年初都可投資。為了使投資者在第三年年底

5、賺到的錢最多，他應(yīng)該怎樣投資？把這個問題表示成一個線性規(guī)劃問題。解：設(shè) Xi1 和 Xi2是第一種方案和第二種方案在第i 年年初的投資額（i =1, 2, 3） ， Z 是總利潤，于是這個問題的線性規(guī)劃模型是：目標函數(shù)：Max Z= 2X 22+0.7X 31（ 第一年年初總投資額不超過計劃投資額）約束條件：X 11+X 12 100 000X21+X221.7X11 （第二年年初投資額不超過第一年第一方案投資收回的本利值）X31 3X12+1.7X21 （第三年年初投資額不超過第二年年底收回的本利值）Xi1， Xi2 0（ i=1 ， 2， 3）EXCEL 求解最優(yōu)解結(jié)果：X11*=， X

6、12*=， X21*=，X22*=，X31*= ，Z*=4、 有 A， B 兩種產(chǎn)品，都需要經(jīng)過前后兩道化學(xué)反應(yīng)過程。每一個單位的A 產(chǎn)品需要前道過程小時和后道過程小時。每一個單位的B 產(chǎn)品需要前道過程小時和后道過程小時?？晒├玫那暗肋^程有16 小時，后道過程時間有24 小時。每生產(chǎn)一個單位B 產(chǎn)品的同時，會產(chǎn)生兩個單位的副產(chǎn)品C，且不需要外加任何費用。副產(chǎn)品C 最多可售出個單位，其余的只能加以銷毀，每個單位的銷毀費用是元。出售 A 產(chǎn)品每單位可獲利元， B 產(chǎn)品每單位可獲利10 元，而出售副產(chǎn)品C 每單位可獲利3 元。試建立為了使獲得的總利潤達到最大的線性規(guī)劃模型。解：設(shè)X1， X2分別是

7、產(chǎn)品A，產(chǎn)品B 的產(chǎn)量，X3是副產(chǎn)品C 的銷售量，X4是副產(chǎn)品C 的銷毀量，Z 是總利潤，于是這個問題的線性規(guī)劃模型是：目標函數(shù)：Max Z=4X 1+10X2+3X3 2X4約束條件：2X 2= X 3+X 4X3 52X1+3X3 163X1+4X2 24X1， X2， X 3， X4 0EXCEL 求解最優(yōu)解結(jié)果：X 1*=， X2*=， X3*=，Z*=5、考慮下面的線性規(guī)劃問題：目標函數(shù)：Max Z=30X 1+20X 2約束條件：2X1+ X 2 40X1+X2 25X1， X2 0用圖解法找出最優(yōu)解X 1 和 X2。解：圖解法結(jié)果如下，最優(yōu)解：X1*=15; X 2=10; Z*

8、=650X2606、某廠生產(chǎn)甲，乙兩種產(chǎn)品，每種產(chǎn)品都要在A,B 兩道工序上加工。其中B 工序可由B1 或B2 設(shè)備完成，但乙產(chǎn)品不能用B1 加工。生產(chǎn)這兩種產(chǎn)品都需要C,D,E 三種原材料，有關(guān)數(shù)據(jù)如下所示。又據(jù)市場預(yù)測，甲產(chǎn)品每天銷售不超過30 件。問應(yīng)如何安排生產(chǎn)才能獲利最大？試建立線性規(guī)劃模型。產(chǎn)品單耗日供應(yīng)量單位成本甲乙數(shù)量單位數(shù)量單位工序A2180工時6元 /工時B13-60工時2元 /工時B21470工時5元 /工時原材料C312300米2元 /米D53100件1元 /件E41.5150千克4元 /千克其他費用（元 /件）2629單價（元/件）80100解：設(shè)甲、乙兩種產(chǎn)品分別生

9、產(chǎn)X 1， X 2件，其中，甲產(chǎn)品在B1 設(shè)備上加工X3工時、在B2 設(shè)備上加工X4工時，則獲利為：Z=80X 1+100X 2-6(2X 1+X 2)-2X 3-5*(X 4+4X 2)-2*(3X 1+12X 2)-1*(5X 1+3X2)-4*(4X 1+1.5X 2)-26X 1-29X 2化簡后得到：目標函數(shù)：Max Z=15X 1+12X2 2X3 5X4s.t.2X 1+X2 80X3 604X 2+X4 703X1+12X2 3005X 1+3X 2 1004X1+1.5X2 150X1 30X1=+X4 (B1 每工時完成件甲產(chǎn)品，共X3個工時，B2 完成 X4件 )33Xj

10、 0,j=1,2,3,4EXCEL 求解最優(yōu)解結(jié)果：X 1*=X2*=， X3*= ，X4*=, Z*=7、制造某機床需要A、 B、 C 三種軸，其規(guī)格和需要量如下表所示。各種軸都用長5.5米長的圓鋼來截毛坯。如果制造100 臺機床，問最少要用多少根圓鋼？試建立線性規(guī)劃模型。軸類規(guī)格：長度（米）每臺機床所需件數(shù)A3 11B2 12C1 24解：用 5.5 米圓鋼截所需規(guī)格長度的所有各種可能性如下表所示：軸件（j）所截各種軸件數(shù)量剩余料頭（ m）所需圓鋼的量A（3.1）B（ 2.1）C（ 1.2）11100.3X121020X230210.1X340121.0X450040.7X5設(shè)按第 j 種

11、截法截Xj根圓鋼，則相應(yīng)的線性規(guī)劃模型為：目標函數(shù)：Min Z = X jj1s.t: X1+X2 100X1+2X3+ X4 2002X2+ X3+2X4+4X5 400 xj 0 且為整數(shù)（j=1,2,5）EXCEL 求解最優(yōu)解結(jié)果：X1*= 0 ， X 2*=100 ， X3*= 100 , X 4*= 0 ,X5*= 25 , Z*= 2258、 某木材公司經(jīng)營的木材貯存在倉庫中，最大貯存量為20 萬米3， 由于木材價格隨季節(jié)變化，該公司于每季初購進木材，一部分當(dāng)季出售，一部分貯存以后出售。貯存費為a+bu ， 其中a=7 元 /米 3， b=10 元 /米 3， u 為貯存的季度數(shù)。

12、由于木材久貯易損，因此當(dāng)年所有庫存應(yīng)于秋末售完。各季木材單價及銷量如下表所示。為獲全年最大利潤，該公司各季應(yīng)分別購銷多少木材？試建立線性規(guī)劃模型。季節(jié)購進價（元/米3）售出價（元/米3）最大銷售量（萬米3）冬31032110春32533314夏34835220秋34034416解：設(shè)Yi（ i=1,2,3,4）分別為冬，春，夏，秋四季采購的木材量（單位：m3） ， Xij（ i， j=1 ，2， 3， 4）代表第i 季節(jié)采購用于第j 季節(jié)銷售的木材量（m3） ，因此，冬季以 310 元 / m3購入 Y1, 當(dāng)季以 321 元 / m3賣出X11,同時，以7+10*1 的成本存儲到春季出售的有

13、X12, 以 7+10*2 的成本存儲到夏季出售的有X13, 以 7+10*3 的成本存儲到秋季出售的有X14；同樣地，春季購入。相應(yīng)的線性規(guī)劃模型為：MaxZ= ( 321X11+316X12+325X13+307X14 310Y1)+( 333X22+335X23+317X24 325Y2)(352X33+327X34 348Y 3)+( 344X 44 340Y4)s.t:Y1 200 000Y 1 X11 X 12 X 13 X 14=0X11 100 000X 12+X 13+X 14+Y 2 200 000Y2 X22 X23 X24 =0X12+X22 140 000X 13+X

14、 14+X 23+X 24+Y 3 200 000Y 3X33X34 0X13+X23+X33 200 000X 14+X 24+X 34+Y 4 200 000Y 4 X44 =0X 14+X 24+X 34+X 44 160 000xij 0， yi 0( i,j=1,2,3,4)EXCEL 求解最優(yōu)解結(jié)果：X 11*=， X 12*=， X 13*=， X14*=Y1*=X 22*=， X 23*=， X 24*=， Y2*=,X 33*=， X 34*=， Y 3*=,X 44*=， Y4*=, Z*=9、對以下線性規(guī)劃問題：Min Z 2X1+3X2+5X3+2X4+3X5s. t.

15、X1+X2+2X3+X4+3X5 42X1 - X2+3X3+X4+X5 3X 1, X2, X3, X4,X5 0Y 1*=4/5, Y 2*=3/5, W* = 5 。試求出原問題的解。解：設(shè)原問題的兩個剩余變量分別為：X6 ,X 7原問題的對偶問題為：s.t.YY2YY 3YY 因為Max W 4Y1+3Y21+2Y2 21-Y2 31+3Y2 51+Y2 21+ Y 2 31,Y2,Y3,Y4 0Y1*=4/5, Y 2*=3/5,松弛變量Y3松弛變量Y4松弛變量Y5松弛變量Y6松弛變量Y7Y4*=14/3 ， Y5*=8/5， Y6*=3/5 ， Y7*=0X3*=0， X4*=0，

16、 X6*=0， X7*=0*因此，計算對偶問題松弛變量值為：Y3 =0，根據(jù)對偶性質(zhì)（ 互補松弛定理） 則有：X2*=0，進一步有：2X 1+3X5=5X1+3X5=4 2X1+X5=3X4*=0， X5* =1,Z * = 5得到：X1*=1,X5*=1原問題的解為：X1 =1, X 2 =0， X3 =0，10、某廠擬生產(chǎn)甲、乙、丙三種產(chǎn)品，都需要在A、 B兩種設(shè)備上加工，有關(guān)數(shù)據(jù)如下表。產(chǎn)品設(shè)備單耗（臺時/ 件）設(shè)備有效臺時（每月）甲乙丙A121400B212500產(chǎn)值（千元/ 每件）321利用對偶性質(zhì)分析以下問題：1）如何充分發(fā)揮設(shè)備潛力，使產(chǎn)品的總產(chǎn)值最大？2）該廠如果以每臺時350

17、 元的租金租外廠的A設(shè)備，是否合算？解：設(shè)生產(chǎn)甲、乙、丙三種產(chǎn)品分別為X1,X 2,X 3件，線性規(guī)劃模型為：目標函數(shù): Max Z = 3X 1+2X2+X3松弛變量為X4松弛變量為X5約束條件：X 1+2X2+X3 4002X1+X2+2X3 500X1,X 2,X 3 0此原問題的對偶問題為：目標函數(shù): Min W = 400Y 1+500Y2約束條件：Y 1+2Y2 3 剩余變量為Y32Y1+ Y2 2剩余變量為Y4Y1+2Y2 1剩余變量為Y5Y1,Y 2 0對偶問題可通過圖解法求解，得到最優(yōu)解結(jié)果為：Y1* = 1/3， Y2* = 4/3進一步可知：Y3* =0， Y4* = 0

18、， Y5* = 2根據(jù)互補松弛定理可知：X3*=0,X 4*=0， X5*=0可得到：X 1+2X2=4002X1+X2=500可解得：X1*=200， X 2*=100根據(jù)以上計算結(jié)果可知：1）應(yīng)該生產(chǎn)甲產(chǎn)品200 件，乙產(chǎn)品100 件，丙產(chǎn)品不生產(chǎn)，此時總產(chǎn)值最大為800千元。2）因為Y 3*=1/3 ，設(shè)備 A 的影子價格為1/3 千元，小于租金350元，因此，該廠不應(yīng)該租用外廠的A 設(shè)備。11、某打井隊要從10 個可供選擇的井位中確定5 個進行探油，使總的探油費用最小。若10個井位的代號為S1,S2,S3, ,S10，相應(yīng)的探油費用為C1,C2,C3, ,C10，并且井位選擇要滿足下列

19、限制條件：1） 或選擇 S1 和 S7，或選擇S8；2） 選擇了 S3 或 S4，就不能選S5，或反過來也一樣；3） 在 S5,S6,S7,S8 中最多只能選兩個。試建立線性規(guī)劃模型。解：變量Xi取 0 或 1， 0 表示不選、1 表示選第i 井位； 模型如下：10目標函數(shù)：MinZ Ci Xi1110s.tXi 5i1X 1X 81（S1和S8只能選一個）X 7X 81（S7 和S8只能選一個）（以上兩式同時滿足時表明： S1 S7與 S8必須且只能選一）X 3X 51（S3和S5不能同時選中，也可都不選）X 4X 51（S4和S5不能同時選中，也可都不選）X5 X6 X7 X82Xi=0,

20、1i=1,2, 10EXCEL 求解最優(yōu)解結(jié)果：X 1*= ， X 2*= ， X 3*= , X4*=, X5*=X6*=， X 7*= ， X8*=, Z*=12、某廠可生產(chǎn)四種產(chǎn)品，對于三種主要資源的單位消耗及單位利潤見下表：產(chǎn)品 資源1234可供量鋼110305000人力26413000能源20253000單位利潤1784如果產(chǎn)品3 的生產(chǎn)需要用一特殊機器，這機器的固定成本（啟用成本）為3000，產(chǎn)品2和產(chǎn)品 4 的生產(chǎn)也同樣需要共用一特定的機器加工，其固定成本（啟用成本）為1000，寫出此時求利潤最大的線性規(guī)劃模型。解： 1)變量： Xi 為第 i 種產(chǎn)品的產(chǎn)量(i=1,2,3,4)

21、,1 X30Y3 為 0-1 變量， Y30 X301 X2X40Y24 為 0-1 變量， Y240X2 X4 02)目標函數(shù)：Max Z = X 1+7X2+8X3+4X4-3000Y3-1000Y243) 約束條件：資源約束：X1+10X2+3X3 50002X1+6X2+4X3+X4 30002X1+2X3+5X4 3000啟用約束：X3 M1Y3 （M 1為一足夠大的正數(shù)，比如取5000 ）X2+X4M2Y24 （M 2為一足夠大的正數(shù)，比如取5000 ）非負約束：Xi 0 （i=1,2,3,4）； Y3,Y24=0， 1EXCEL 求解最優(yōu)解結(jié)果：X1*= 0， X2*=400，

22、X3*= 0 , X 4*= 600 , Y 3=0,Y24=1, Z*=420013、 某化工廠要用三種原料D,P,H 混合配置三種不同規(guī)格的產(chǎn)品A,B,C。 各產(chǎn)品的規(guī)格、單價如左表所示，各原料的單價及每天的最大供應(yīng)量如右表所示，該廠應(yīng)如何安排生產(chǎn)才能使利潤最大？產(chǎn) 品規(guī)格單價（元 / 千克）A原料D 不少于50原料P 不超過2550B原料D 不少于25原料P 不超過5035C不限25原料最大供應(yīng)（千克/ 天）單價（元 / 千克）D10065P10025H6035解： 1) 變量：產(chǎn)品A中D,P,H含量分別為X11,X 12,X13產(chǎn)品B中D,P,H含量分別為X21,X 22,X23產(chǎn)品C

23、中D,P,H含量分別為X31,X 32,X33令：X11+X12+X13=X1X21+X22+X23 =X2X31+X32+X33=X32) 目標函數(shù)：Max Z = -15X 11+25X12+15X13- 30X 21+10X22-40X31-10X333) 約束條件：根據(jù)規(guī)格條件有：X11 0.5X 1X 12 0.25X 121 0.25X 2X22 0.5X 2進一步得到：- X-3X- X原材料供應(yīng)條件：XX非負約束：- X 11+ X 12+X13 011+3X12- X 13 021+ X 22+X23021+ X 22- X 230X 11+X21+X3110012+X22+

24、X3210013+X23+X3360X ij 0, i,j=1,2,3EXCEL 求解最優(yōu)解結(jié)果：X11*= 100 ， X 12*=50 ， X13*= 50 , X 21*=0 , X 22*=0 , X 23*=0X 31*=0， X 32*=0 ， X33*=0, Z*=500X 1*=X 11*+X 12*+X 13*=200,X2*=0,X3*=0; 每天只生產(chǎn)A 200kgX 11*+X 21*+X31*=100使用D100kg;X 12*+X 22*+X32*=50使用P50kg;X 13*+X 23*+X33*=50使用H50kg;14、某產(chǎn)品有A1和 A2兩種型號，需經(jīng)過B

25、1、 B2、 B3三道工序，單位工時、利潤、各工序每周B3工序有兩種加工方工時限制如下表所示，問工廠如何安排生產(chǎn)，才能使總利潤最大（式 B31和 B32，只能選擇其中一種；產(chǎn)品為整數(shù)）。工時 / 件 型號工序B1B2B3利潤（元 /件 ）B31B32A1323225A2715440每周工時（小時/ 周）250100150120解： 1）設(shè)變量如下：A1 生產(chǎn)量為X 1 ， A2 生產(chǎn)量為X2；選 B31 時 Y1=0；不選時Y1=1選 B32 時 Y2=0；不選時Y2=12）目標函數(shù)：Max Z = 25X 1+40X 23）約束條件：3X1+7X2 2502X 1+ X2 100為足夠大的正

26、數(shù), 如取 5000）3X 1+5X2 150+M*Y1 (M2X 1+4X2 120+M*Y2Y 1+Y2=1X 1,X2 0 且為整數(shù),Y 1,Y 2=0,1EXCEL 求解最優(yōu)解結(jié)果：X1*= ， X2*= ， Y1 *=, Y2 *=0 , Z*=15、甲、乙、丙、丁四人加工A、 B、 C、 D 四種工件所需時間（分鐘）如表所示，應(yīng)指派何人加工何種工件，能使總的加工時間最少？要求建立數(shù)學(xué)模型并求解。工件人ABCD甲149415乙117910丙132105丁1791513解： （匈牙利方法過程及模型略）答案：甲：C；乙：A；丙：D；?。?B16、某廠生產(chǎn)柴油機，1 4 月份訂貨任務(wù)為：1

27、 月 2000 臺； 2 月 3000 臺； 3 月 5500 臺； 4月 6000 臺；該廠的月正常生產(chǎn)能力為3000 臺，每臺的生產(chǎn)成本為1500 元，每月加班生產(chǎn)能力為2000 臺，加班生產(chǎn)成本為每臺2000 元，月庫存費用為每臺50 元， 1 月初庫存為 0。建立求成本最低生產(chǎn)計劃的線性規(guī)劃模型。解：設(shè)Xi（ i=1,2,3,4 ）為第 i 個月正常生產(chǎn)的柴油機數(shù)，Yi 為第i 個月加班生產(chǎn)的數(shù)量，Wi 為第i 月月初的庫存數(shù)。該問題的線性規(guī)劃模型為：目標函數(shù)：Min Z = 1500（X 1+X2+X3+X4）+2000（Y 1+Y2+Y3+Y4）+50（W2+W3+W4）約束條件：

28、X1+Y1-W2 = 2000X2+Y2+W2-W3 = 3000X3+Y3+W3-W4=5500X4+Y4+W4=6000Xi 3000( i=1,2,3,4 )Yi 2000( i=1,2,3,4 )Xi,Y i,Wi 0, ( i=1,2,3,4 ) ，且均為整數(shù)EXCEL 求解最優(yōu)解結(jié)果：X1*=，X2*=， X3*=, X4*=, Y1*=, Y2*=Y 3*=，Y4*=， W 1*=, W 2*=, W3*=, W4*=,Z*=17、 某鑄造廠接到一筆訂貨，要生產(chǎn) 1000 公斤 （一噸） 鑄件， 其成分是錳的含量至少達到0.45，硅達到 3.255.50% 。 鑄件的售價是4.5

29、元 /公斤。工廠現(xiàn)存三種可以利用的生鐵（ A、 B、C） ，存量很多，其性質(zhì)如下表所示。此外，生產(chǎn)過程允許把純錳直接加到融化金屬中。各種可能的爐料費用如下：生鐵A 210 元 /噸，生鐵B 250元 /噸，生鐵C 150 元 /噸，純錳 80 元 /公斤。每融化一噸生鐵要花費50 元。應(yīng)如何選擇爐料才能使利潤最大。元素生鐵種類ABC硅41%0.6%錳0.45 0.5%0.4%解：1) 變量：設(shè)所需生鐵A X 1 噸，生鐵B X2 噸，生鐵C X3噸，純錳X 4 公斤2 )目標函數(shù)：Max Z = 1000*4.5-210*X1-250*X2-150*X 3-80*X 4-50* ( X1+X2

30、+X3)即： Max Z = 450-260X 1-300X2-200X3-80X43)約束條件：(0.45%X 1+0.5%X2+0.4%X3)*1000+X4 0.45%*1000 (錳的含量)4%X 1+1%X 2+0.6%X 3 5.5%(硅的含量上限)4%X 1+1%X 2+0.6%X 3 3.25%(硅的含量上限)(X 1+X 2+X 3)*1000+X 4=1000X1,X2,X3,X4 0EXCEL 求解最優(yōu)解結(jié)果：X 1*=， X 2*= ， X3*=, X4*=, Z*=18、已知有三個產(chǎn)地給四個銷地供應(yīng)某產(chǎn)品，產(chǎn)銷地之間的供需量和單位運價如下：銷地 產(chǎn)地B1B2B3B4產(chǎn)

31、量A15267300A23546200A34523400銷量200100400200900要求： 1 ）建立此運輸問題的線性規(guī)劃模型（不需要求解）；2）由于市場情況的變化，B3 和 B4 的銷量各增加了50單位（運用表上作業(yè)法可求得此時最小運費為2950元）。 有關(guān)部門在研究調(diào)運方案時還需要依次考慮以下情況（已規(guī)定其優(yōu)先等級P1 P5） ：P1: B4是重點保證單位，必須盡可能滿足其需要；P2: A3向 B1 提供的量不少于100；P3: 因道路問題，盡量避免安排A2產(chǎn)品運往B4;P4: 給 B1 和 B3的需求供應(yīng)率要相等；P5: 與最小運費調(diào)運方案相比，總運費的增加不超過最小調(diào)運方案的試建

32、立求解滿意調(diào)運方案的目標規(guī)劃模型。10% 。解： 1)運輸問題線性規(guī)劃模型：此問題為供需平衡問題，用Cij 表示 Ai運到Bj的單位運價，ai為 Ai 的最大產(chǎn)量，bj為 Bj的最大銷量(i=1,2,3 ; j=1,2,3,4) ，則線性規(guī)劃模型：變量：設(shè)Xij 表示Ai運到Bj的運量(i=1,2,3 ;j=1,2,3,4)Min Z =i14Cij? Xij1約束條件：2)目標規(guī)劃求解：銷量增加后供不應(yīng)求，因此，供應(yīng)仍為絕對約束：需求約束為目標約束：Xijbjj 1,2,3,4i14Xij j1 Xij0,aii 1,2,31,2,3; j 12344Xij aij11,2,33Xij d

33、j d ji1bjj 1,2,3 ,4(已包含了B4要盡可能滿足的條件)X31+d5- d5+=100X24+ d6- - d6+=0X11 + X21 + X31(A3向 B1 提供的量不少于100)A2 產(chǎn)品運往B4)X13 + X23 + X33200450d7d70 (給 B1 和 B3的需求供應(yīng)率要相等)10%)34Cij ?Xij + d8- d8+= 2950(1+10%) i1j1非負約束：Xij，dk- ， dk+ 0 ( i=1,2,3； j=1,2,3,4； k=1,2,3, 8)目標函數(shù)：Min Z = P 1* d4- + P2* d5-+P3* d6+P4*( d

34、7-+ d7+)+P5* d8+19、某電臺根據(jù)政策 每天允許播出12小時，其中商業(yè)節(jié)目每分鐘可收入250元，新聞節(jié)目每分17.5 元。依 政策 規(guī)定：正常情況下商業(yè)節(jié)目只能5分鐘的新聞節(jié)目。試問該電臺每天如何安排節(jié)目？P2每天的純收入最大。建立此問題的目標規(guī)劃模鐘支出40元，音樂節(jié)目每播一分鐘支出占廣播時間的20%， 而每小時至少安排其優(yōu)先級如下：P1滿足 政策 的要求；型。解：設(shè)安排商業(yè)節(jié)目時間X1小時，新聞節(jié)目時間X2小時，音樂節(jié)目時間X3小時。目標函數(shù)：Min Z = P 1(d 1-+d2-+d3+)+P2d4-約束條件：X1+X2+X3+ d 1- d 1+ =12X1 + d 2

35、- d 2+ =2.4X2 + d 3- d 3+ =1250X1-40X2-17.5X 3+ d 4- d 4+ =250*2.4X1,X2,X3 0,di-,d i+ 0 （i=1,2,3,4）20、 A J 共 10 項工作需在兩臺機器上加工，各自的加工時間如下，如何安排加工順序使系 統(tǒng)效率最高（ 只要求寫出加工順序） 。ABCDEFGHIJ機器114192422640204125機器221083235183063528解： （約翰遜原則求解過程略）結(jié)果： I, H, E, G, D, J, F, B, C, A21、求出下圖中從A 到 E 的最短路線及其長度。解：方法一：動態(tài)規(guī)劃在B1

36、與D1之間增設(shè)一虛擬節(jié)點C3,使B1到C3的距離為4，而C3到D1的距離為0；在B3與D3之間增設(shè)一虛擬節(jié)點C4,使B3到C4的距離為3，而C4到D3的距離為0；用動態(tài)規(guī)劃方法，可求得A 到 E 的最短距離為8 最短路為：A-B2-C1-D1-E 。方法二：Dijkstra 方法（過程略）結(jié)果： A 到 E 的最短距離為8 , 最短路為：A-B2-C1-D1-E解：線性規(guī)劃模型：1 ）變量：設(shè)fij 為通過弧i-j（節(jié)點 i 節(jié)點 j ）的流量2）目標函數(shù)：Max Z = f 12+f 133）約束條件：f12=f25+f 24+f 23f13+f23=f 34+f 36f24+f34=f 4

37、5+f 46f25+f45+f 65=f 57f46+f36=f 65+f 67fij Fijfij 0對一切可能的弧 對一切可能的?。?出發(fā)點流出的總流量最大）（ 節(jié)點2的凈流量為0）（ 節(jié)點3的凈流量為0）（ 節(jié)點4的凈流量為0）（ 節(jié)點5的凈流量為0）（ 節(jié)點6的凈流量為0）i-j（弧的容量限制）i-j23、求網(wǎng)絡(luò)（23 題圖）從節(jié)點1 到節(jié)點 7 的最短路徑（寫出線性規(guī)劃模型，并用圖上標注的方法求解） 。解：方法一：線性規(guī)劃模型求解，假設(shè)通過網(wǎng)絡(luò)的最大流量為1，1） 變量：設(shè)Xij為弧 i-j（節(jié)點 i 節(jié)點 j ）是否流過，流過取值1，不流過取值02） 目標函數(shù)：通過網(wǎng)絡(luò)的總長度最小

38、，因此，有：Min Z = 5X 12+2X23+7X 25+2X 24+7X 34+4X 36+6X 45+2X 46+3X 57+X 65+X 673） 約束條件：X12+X13=1X12=X25+X24X13=X34+X36X24+X 34=X45+X46X25+X45+X65=X57X36+X46=X65+X67X57+X67=1Xij =0,1 所有可能的?。ü?jié)點1的流出量為1）（ 節(jié)點2的凈流量為0）（ 節(jié)點3的凈流量為0）（節(jié)點4的凈流量為0）（節(jié)點5的凈流量為0）（節(jié)點6的凈流量為0）（節(jié)點7的流入量為1）i-j方法二：Dijkstra 方法（過程略）結(jié)果：最短距離為10，最短

39、路為：1-3-6-5-724、某工廠的某臺機器可連續(xù)工作4 年，決策者在每年年初都要決定機器是否更新。若購置新機器，就要支付購置費；若繼續(xù)使用，則需要支付維修與運行費用，而且隨著機器使用年限的增加費用也會逐年增加。已知計劃期（4年）中每年的購置價格及維修運行費用如下表所示，試制定今后4 年的機器更新計劃，使總支付費用最小。年限1234購置費（萬元）2.52.62.83.1維修運行費（萬元）11.524解：把該問題看作最短路問題。設(shè)節(jié)點1 和節(jié)點 5 表示計劃期的始點和終點（節(jié)點5 可理解為第4 年年末） 。下圖中各弧（i , j）表示第i 年年初購進的機器使用到第j 年年初（即第j-1 年年底

40、） ，弧旁的數(shù)字（弧長）為購置價格與使用多年后的維修與運行總費用，如考慮節(jié)點1 到節(jié)點 3 的弧，這條弧對應(yīng)的是在第1 年初購進的機器，使用到第 3 年年初（使用了兩年），所以從節(jié)點1 到節(jié)點 3 的弧長為購置2.5 萬元加上第一年維修運行費1 萬和第二年維修運行費1.5 萬元，合計5 萬元。其余類似求得。求解結(jié)果：最短距離為10.3，最短路為：- - ，即：計劃期內(nèi)第1 年、 第 3年年初各購置一臺新機器，4 年總費用10.3萬元。77 口油井和16 口30 萬元，如出租25、某地擬進行石油勘探。統(tǒng)計資料表明，在相似地理區(qū)域鉆探的井中，有干井，每口油井收入都是大約130 萬元。若請勘探人員自

41、行開發(fā)需花費給別的公司開采可穩(wěn)得租金10 萬元，且若能出油還可額外再得10 萬元。該地領(lǐng)導(dǎo)應(yīng)如何決策？為提高決策的準確性，專家建議可先進行地震試驗，從而判斷該地區(qū)的地質(zhì)結(jié)構(gòu)是封閉的或開放的。從地質(zhì)學(xué)知道：有油地區(qū)多半是封閉結(jié)構(gòu)，無油地區(qū)多半是開放結(jié)構(gòu)，以往情況是有油地區(qū)勘測為封閉結(jié)構(gòu)的概率為0.8，無油地區(qū)勘探開放結(jié)構(gòu)的概率是0.6。若做地震試驗要花費5 萬元，該領(lǐng)導(dǎo)又該如何決策？解：在相似地區(qū)鉆井有油的概率為7/(7+16)=0.3，則無油的概率為0.7。設(shè)以 A1 表示自行開發(fā)，A2 表示出租，以 1 、 2 分別表示該地區(qū)的有油與無油狀態(tài)。根據(jù)題意可列出以下收益表：1) ) 先驗分析：計

42、算A1、 A2 兩方案的期望收益值EMV(A1)= 100*0.3+(-30)*0.7= 9EMV(A2)= 20*0.3+10*0.7= 13由于 EMV(A2)>EMV(A1), 因此，如不做地震實驗的決策是應(yīng)該選擇出租。此時， EMV*=13 (萬元)2) 預(yù)驗分析：計算完備信息的價值完備信息下最大期望收益ERPI= 100*0.3+10*0.7= 37 (萬元)完備信息價值EVPI=37-13=24(萬元)由于EVPI( 24 萬元)相比地震實驗的費用(5 萬元)大比較多，可嘗試進行。3) 后 驗分析：計算條件概率并決策設(shè) A3 為進行地震實驗，以S1， S2 分別表示勘探結(jié)果為

43、封閉結(jié)構(gòu)和開放結(jié)構(gòu)由題意可得以下條件概率：P(S1| 1)=0.8 , P(S2| 1)=0.2 , P(S1| 2)=0.4 , P(S2| 2)=0.6進一步利用貝葉斯公式計算決策所需條件概率P( | S )( 1)( 2)(3)=(1)*(2)iP( )P(S1| i)P(S2| i)P(S1 i)P(S2 i)10.30.80.20.240.06(4)20.70.40.40.280.42(5)(6)=(4)+(5)0.520.48P(Si)(7)=(4)/(6)0.460.125P(i|Si)(8)=(5)/(6)0.540.875得到：P(1|S1)=0.46 , P( 2|S1)=

44、0.54 , P(1|S2)=0.125 , P( 2|S2)=0.875地震實驗是封閉結(jié)構(gòu)的決策：計算期望收益值EMV(A1S1)=100*0.46+(-30)*0.54=30(萬元 )EMV(A2S1)=20*0.46+10*0.54=14.6(萬元 )EMV(A1S1)>EMV(A2S1),因此，此時的決策為選擇自行開采(A1)地震實驗是開放結(jié)構(gòu)的決策：計算期望收益值EMV(A1S2)=100*0.125+(-30)*0.875=-13.75(萬元 )EMV(A2S2)=20*0.125+10*0.875=11.25(萬元 )EMV(A2S2)>EMV(A1S2),因此，此時

45、的決策為選擇出租(A2)以上根據(jù)地震實驗結(jié)果所做決策的總期望收益為：EMV(S)=30*0.52+11.25*0.48 - 5= 16(萬元 )選擇做地震實驗的期望值增量為：?EMV=EMV(S)-EMV* = 16-13 = 3 ( 萬元 )綜上所述，最優(yōu)決策為：先進行地震實驗，如果結(jié)果為封閉結(jié)構(gòu)則自行鉆探開采，如為開放結(jié)構(gòu)則出租該地的開采權(quán)，這樣可獲期望收益16 萬元。26、畫出網(wǎng)絡(luò)圖(不考慮工序時間)網(wǎng)絡(luò)圖1網(wǎng)絡(luò)圖2網(wǎng)絡(luò)圖3工序緊后工序工序緊前工序工序緊前工序AC,DA-A-BC,D,EB-B-CGC-CADH,FDADAEH,FEBEBFGFCFBGIGB,DGD,EHIHEHD,EIG,HID,E,FJE,FJCKE,FKCLI,JLJMD,E,F,G,H,K3：27、已知某項工程的作業(yè)程序、作業(yè)時間、直接成本、最大可縮短時間、各工序縮短一天工期所增加的直接費用等信息如下表所示，正常時間完成各工序的直接費用總和為1300元，每天的間接費用為25元：工序緊后工序工序時間（天）最大可縮短工作天數(shù)直接費率g（元 / 天）AB、 C6230BD、 E、 F9440CE、 F3130DG10215EH8510FI2150G-10H-4120I-5230要求： 1 ）畫出網(wǎng)絡(luò)圖，計算每一節(jié)點的最早、最遲時間，確定關(guān)鍵線路；2）建立使該項工程達到最低成本時間的線性規(guī)劃模型；3 ）