運籌學課后知識題三

1、習題三3.1 某公司今后三年內有五項工程可以考慮投資。每項工程的期望收入和年度費用(萬元)如表3-10所不【解】設Xj1投資項目，模型為0不投資j項目maxZ 30x1 40x220x315x45x14x2 5x3 7x48x530X17x2 9x3 5x46x5258x12x2 6x3 2x49x530Xj =0或 1,j1,| ,51、30x5最優(yōu)解X=(1,1,1,0,1) , Z=110萬元，即選擇項目2、3、5時總收入最大。表 3-10工程費用收入A年第二年第三年151830247240359620475215586930資金擁啟量302530每項工程都需要三年完成，應選擇哪些項目使

2、總收入最大，建立該問題的數(shù)學模型。3.2 址問題。以漢江、長江為界將武漢市劃分為漢口、漢陽和武昌三鎮(zhèn)。某商業(yè)銀行計劃投資9000萬元在武漢市備選的12個點考慮設立支行，如圖圖 3-103-10所示。每個點的投資額與一年的收益見表3 10。計劃漢口投資23個支行，漢陽投資12個支行，武昌投資 34個支行。如何投資使總收益最大，建立該問題的數(shù)學模型，說明是什么模型，可以用什么方法求解。表 3-11地址i123456789101112投資額（萬元）900120010007506808007201150120012508501000收益（萬元）40050045035030040032046050051

3、0380400【解】設Xj為投資第j個點的狀態(tài)，Xj=1或0, j=1,2,12 maxZ 400x1 500x2 450x3400x12900x1 1200x2 1000x3850x11 10000 900044771212xj 2, xj 3,xj 1, xj 2,xj 3,xj 4j 1j 1j 5j 5j 8j 8xj 1 或0, j 1,|,12最優(yōu)解：x1 = x5=x12=0 ,其余xj=1,總收益Z=3870 萬元，實際完成投資額 8920萬元。3.3 一輛貨車的有效載重量是 20噸，載貨有效空間是 8X3.5X2 m?，F(xiàn)有六件貨物可供選 擇運輸，每件貨物的重量、體積及收入如表

4、表 3-12。另外，在貨物4和5中先運貨物5, 貨物1和2不能混裝，怎樣安排貨物運輸使收入最大，建立數(shù)學模型。表 3-12貨物號123456重量（T）653472體積（m3）374562收入（百元）584673【解】設xj為裝載第j件貨物的狀態(tài)，xj=1表示裝載第j件貨物，xj=0表示不裝載第j件貨 物，有maxZ5x18x24x36x47x53x66x15x23x34x47x52x6203x17x24x35x46x52x656x4x50x1x21Xj0或 13.4 女子體操團體賽規(guī)定：(1)每個代表隊由5名運動員組成，比賽項目是高低杠、平衡木、鞍馬及自由體操。(2)每個運動員最多只能參加 3

5、個項目并且每個項目只能參賽一次;(3)每個項目至少要有人參賽一次，并且總的參賽人次數(shù)等于10; (4)每個項目采用10分制記分，將10次比賽的得分求和，按其得分高低排名，分數(shù)越高成績越好。已知代表隊5名運動員各單項的預賽成績如表3-13所示。高低杠平衡木鞍馬自由體操甲8.69.78.99.4乙9.28.38.58.1丙8.88.79.39.6丁8.57.89.57.9戊8.09.48.27.7表 3-13怎樣安排運動員的參賽項目使團體總分最高，建立該問題的數(shù)學模型?！窘狻吭Oxij (i=1 , 2,，5; j= 1 , 2, 3, 4)為第i人參賽j項目的狀態(tài)，即1第i人參賽j項目xij 0第

6、i人不參賽j項目記第i人參賽j項目的成績?yōu)?Cj,目標函數(shù) 54maxZCij xji 1 j 1每個運動員最多只能參加 3個項目并且每個項目只能參賽一次 ，約束條件:xi1xi2xi3xi4每個項目至少要有人參賽一次，并且總的參賽人次數(shù)等于x1jx2 jx3jx4j x5j54xj101,2, ,510 ,約束條件:j 1,2,3,4數(shù)學模型為CijxjmaxZXil X2 X3Xi43 i 1,2,|,5Xij X2j X3j X4j X5j 1 j 1,2,3,454Xij10i 1 j 1Xij1 或0,i 1,2,|,5; j 1,2,3,43.5利用0 - 1變量對下列各題分別表示

7、成一般線性約束條件三個約束中至少兩個滿足(1) X1+2 X2W8、4x1 +X2>10 及 2x1+6 X2 W18(2)若 X1 >5,貝U X2>10 ,否貝U X2<8(3) X1取值2, 4, 6, 8中的一個2y1 4y2 6y3y2y y 10或 1, j 1,2,3,48y4X1 2X2 8 yM 4X1 x2 10 y2 M 【解】(1) 2X1 6x2 18 y3M y1 y2 y21y j 0或 1, j 1,2,3x15yMx15(1y)MX1(2) x2 10 yM (3)火X28 (1y)Myjy0或16.考慮下列數(shù)學模型min Z f (X

8、1)g(x2)其中f(xj10 6x1，若 x1 015 10x2，若 x2 0,g(X2).0,6x1 00, 右乂2 0滿足約束條件(1) xi >8 或 X2 >6(2) |X1 X2|=0 , 4 或 8(3) xi+2 X2>20 > 2xi+X2封20及xi+X2封20三個約束中至少一個滿足(4) X1>0, X2>0將此問題歸結為混合整數(shù)規(guī)劃的數(shù)學模型。min Z 10 yl 6x1 15y2 10x2x1y1M ; x2y2 Mx18 y3M條件（1）x26 (1 y3)Mxi x2 0y4 4 y54 y6 8 y7 8 y8【解】y4 y

9、5 y6 h y 1x1 2x220 y9 M條件（2）條件（3）2x1x220 y10Mx1x220 y11My9y10y112x10,x20; yj0或 1, j 1,2,11條件(4)maxZ Xf x?min Zx1 2x23x1 2x27x1/ 9 x2 102x1 4x25V2)/ 八10x12x2 50X, x2 0a為整數(shù)X1,X20且為整數(shù)7.用分枝定界法求解下列IP問題(2) X=(5,0),Z=5【解】(1)X=(1,2),或 X= (0,3) Z=38.用割平面法求解下列IP問題maxZ 2x1 3x2x1 2x29(1)2x1 x2 10Xi , x2 0且為整數(shù)mi

10、n Z 2x1 3x2x1 2x29(2)2x1 x2 10Xi,X2 0且為整數(shù)【解】(1)X=(3,3),Z=15(2)X=(5,2),Z=169 .用隱枚舉法求解下列BIP問題maxZ 4x1 3x2+x35xi 2x2 x364x1 2x2 x37xj 0或 1, j 1,2,3min Z 4x1 x2 x3 3x4x1x2 4x3 5x4(2) 3x1 x2 2x3 2x44x1 3x2 2x3 4x47xj0或 1, j 1,2,3,4【解】(1)X=(1,1,1),Z=8(2)X=(1,1,1,0),Z=410 .用分枝定界隱枚舉法求解下列BIP問題(1)max Z 4x1 x2

11、 x3 3x4x1 x2 4x35x43x1 x2 2x3 2x44(2)min Z5x23x1 x2 2x3 6x4 x5x32x4 x5 8x1xj3x2 2x3 4x47 0或 1, j 1,2,3,42x1 2x2 3x3 2x4 x54xj0m£ 1, j 1, ,5【解】(1)X=(1,0,1,1),Z=8(2)X=(1,1,0,0,0),Z=-2習題四4.1工廠生產甲、乙兩種產品，由A、B二組人員來生產。A組人員熟練工人比較多，工作 效率高，成本也高；B組人員新手較多工作效率比較低，成本也較低。例如，A組只生產甲產品時每小時生產10件，成本是50元有關資料如表4.21所

12、示。表 4.21產品甲產品乙效率（件/小時）成本（元/件）效率（件/小時）成本（元/件）A組1050845B組845540產品售價（元/件）8075二組人員每天正常工作時間都是8小時，每周5天。一周內每組最多可以加班10小時，加班生產的產品每件增加成本 5元。工廠根據市場需求、利潤及生產能力確定了下列目標順序：P1:每周供應市場甲產品 400件，乙產品300件P2：每周利潤指標不低于 500元P3：兩組都盡可能少加班，如必須加班由A組優(yōu)先加班建立此生產計劃的數(shù)學模型?！窘狻?解法一：設x1, x2分別為A組一周內正常時間生產產品甲、乙的產量，x3, x4分別為A組一周內加班時間生產產品甲、乙的

13、產量；X5, X6分別為B組一周內正常時間生產產品甲、乙的產量，X7, X8分別為B組一周內加班時間生產產品甲、乙的產量?？偫麧櫈?0(x1 x3 x5x7)(50xi55x345x550x7)75(x2 x4 x6x8)(45x250x440x645x8)30x1 30x225x325x435x535x630x730x8生產時間為A 組：0.1x1 0.125x2 0.1x3 0.125x4B 組：0.125x5 0.2x6 0.125x7 0.2x8數(shù)學模型為：min Z p1(d1d2x1 x3 x5 x d x2 x4 x6 x8 c 30x1 30x2 25x3 0.1x1 0.12

14、5x2 d 0.125x5 0.2x6 d 0.1x3 0.125x4 d 0.125x7 0.2x8 d xj 0,di ,di 0,i解法一：設x1, x2分別為A組- 生產產品甲、乙的加班時間； 分別為B組一周內生產產品甲、總利潤為10月 80 50 8x2(75 8x5(80 45) 5x6(75 / 300x1 240x2 250x3數(shù)學模型為)p2d3P3(d4 d5) P4(d6 2d7 )1 d140012 d230025x4 35x5 35x6 30x7 30x8 d； d35004 d4 40I5 d5406 d610I7 d7101,2,|(，7； j 1,2,|,8一周

15、內生產產品甲、乙的正常時間， x3, x4分別為A組一周內 x5, x6分別為B組一周內生產產品甲、乙的正常時間， x7, x8 乙的加班時間。45) 10x3 80 558x4(75 50)10) 8x7(80 50) 5x8(75 45)200x4 280% 175x6 240x7 150%min zPi(did?)p2d3P3(d4d5)P4(d62d7)10xi 10x3 8x5 8x7 di di 4008x2 8x4 5x6 5x8 d2 d2300500300x1 240x2 250x3 200x4 280x5 175x6 240x7 150x8 d3 d3x1x2d4d440x

16、5注d5d540x3刈d6d610x7x8d7d710為0,di ,di0,i 1,2,|,7; j 1,2,|,84.3雙擊下圖，打開幻燈片。4.2【解】min z設xij為Ai到Bj的運量，數(shù)學模型為P1d1P2(d2d3d4) P3d5 P4d6 P5(d7 d7) P6d8x13x23x33x11x21x31x12x22x32x14x33x24d5x34d5d1 d2 d3 d4 200d1 d2 d3 d4480272204323B3保證供應B1需求的85%B2需求的85%B4需求的85%x21st 2x123d6 I2x222x32A3 對 B34對今x13x23x33d7 d70

17、 B2 與 B3 的平衡4cij xijd81運費最小x11x21x12x22x13x23x14x24560400x31xijx320x33x34750(i 1,2,3; j 1,2,3,4);di，di0(i 1,2,8);習題4.3(2)116030401,2,3min Z p1dlP2(2d2 d3)習題4.3(2)P2d3min zPi(di61,2,3)d2)習題4.3(4)40605020)P2d30 (iP3d41, ,4)滿意解：X=(50,10)習題4.3(4)P2d31,2,3min Zp1(2dld2 )2224.4 已知某實際問題的線性規(guī)劃模型為max z 100x1

18、50x210x1 16x2 200(資源 1)11x1 3x225(資源 2)x1, x20假定重新確定這個問題的目標為:P 1 : Z的值應不低于 1900P2：資源1必須全部利用將此問題轉換為目標規(guī)劃問題，列出數(shù)學模型。m數(shù)學模型為min Z p1dlp2(d2 d2)100x1 50x2 d1 d1190010xi 16x2 d2 d220011x1 3x225Xj,dj,dj 0, j 1,24.5 已知目標規(guī)劃問題min z p1d1P2d2P3(5d3 3d4 ) P4d169420 (i 1,4)x12x2d1d1x12x2d2d2x12x2d3d3x2d4d4x1,x2,di

19、,di（1）分別用圖解法和單純形法求解;解的（2）分析目標函數(shù)分別變?yōu)?、兩種情況時（中分析 W1、W2的比例變動）變化。 minz p1d1P2d2P3d1P4(5d3 3d4 )m min zp1 d1P2d2P3 (w1 d3w2d4) P4d1【解】（1）圖解法（雙擊下圖，打開幻燈片）習題4.5(1)min z p1d1Rd2P3(5d3 3d4 ) P4d1(1 )單純形法Cj00P1P40F25 P303P30bCb基x1X2d1d1+d2-d2+d3d3+d4d4+P1d1121-160d2121-195 P3d31-21-143 Rd411-12Pi-1-21表P21CZjP3-5753P41P1d111-1-2220d211-1-2255 F3d311-12-280X211-12表（2）G-