運(yùn)籌學(xué)整數(shù)規(guī)劃例題

1、練習(xí)4.9 連續(xù)投資問(wèn)題某公司現(xiàn)有資金10萬(wàn)元,擬在今后五年內(nèi)考慮用于下列項(xiàng)目的投資:項(xiàng)目A:從第一年到第四年每年年初需要投資,并于次年收回本利115%,但要求第一年投資最低金額為4萬(wàn)元,第二.三.四年不限.項(xiàng)目B:第三年初需要投資,到第五年末能收回本利128%,但規(guī)定最低投資金額為3萬(wàn)元,最高金額為5萬(wàn)元.項(xiàng)目C:第二年初需要投資,到第五年末能收回本利140%,但規(guī)定其投資金額或?yàn)?萬(wàn)元,或?yàn)?萬(wàn)元,或?yàn)?萬(wàn)元,或?yàn)?萬(wàn)元.項(xiàng)目D:五年內(nèi)每年年初都可購(gòu)買公債,于當(dāng)年末歸還,并獲利6%,此項(xiàng)目投資金額不限.試問(wèn)該公司應(yīng)圖和確定這些項(xiàng)目的每年投資金額,使到第五年末擁有最大的資金收益.(1) 為項(xiàng)

2、目各年月初投入向量。(2) 為 i 種項(xiàng)目j年的月初的投入。(3) 向量c中的元素為i年末j種項(xiàng)目收回本例的百分比。(4) 矩陣A中元素為約束條件中每個(gè)變量的系數(shù)。(5) Z為第5年末能擁有的資金本利最大總額。因此目標(biāo)函數(shù)為束條件應(yīng)是每年年初的投資額應(yīng)等于該投資者年初所擁有的資金.第1年年初該投資者擁有10萬(wàn)元資金,故有.第2年年初該投資者手中擁有資金只有,故有.第3年年初該投資者擁有資金為從項(xiàng)目收回的本金: ,及從項(xiàng)目中第1年投資收回的本金: ,故有同理第4年、第5年有約束為,max=1.15*x4a+1.28*x3b+1.4*x2c+1.06*x5d; x1a+x1d=100000;-1.

3、06*x1d+x2a+x2c+x2d=0;-1.15*x1a-1.06*x2d+x3a+x3b+x3d=0;-1.15*x2a-1.06*x3d+x4a+x4d=0;-1.15*x3a-1.06*x4d+x5d=0;x2c=40000 ;x2c=60000;x2c=80000;x2c=20000; x3b>=30000;x3b<=50000;x1a>=0;x2a>=0;x3a>=0;x4a>=0;x5a>=0;x1b>=0;x2b>=0;x3b>=0;x4b>=0;x5b>=0;x1c>=0;x2c>=0;x3

4、c>=0;x4c>=0;x5c>=0;x1d>=0;x2d>=0;x3d>=0;x4d>=0;x5d>=0; Variable Value Reduced Cost X4A 22900.00 0.000000 X3B 50000.00 0.000000 X2C 40000.00 0.000000 X5D 0.000000 0.000000 X1A 62264.15 0.000000 X1D 37735.85 0.000000 X2A 0.000000 0.000000 X2D 0.000000 0.3036000E-01 X3A 0.000000

5、 0.000000 X3D 21603.77 0.000000 X4D 0.000000 0.2640000E-01 X5A 0.000000 0.000000 X1B 0.000000 0.000000 X2B 0.000000 0.000000 X4B 0.000000 0.000000 X5B 0.000000 0.000000 X1C 0.000000 0.000000 X3C 0.000000 0.000000 X4C 0.000000 0.000000 X5C 0.000000 0.000000 Row Slack or Surplus Dual Price 1 80000.00

6、1.000000 2 0.000000 1.401850 3 0.000000 1.322500 4 0.000000 1.219000 5 0.000000 1.150000 6 0.000000 1.060000 7 0.000000 -0.8388608E+18 8 -20000.00 -0.1280000E+10 9 -40000.00 -0.1280000E+10 10 -20000.00 0.1280000E+10 11 20000.00 0.000000 12 0.000000 0.6100000E-01 13 62264.15 0.000000 14 0.000000 0.00

7、0000 15 0.000000 0.000000 16 22900.00 0.000000 17 0.000000 0.000000 18 0.000000 0.000000 19 0.000000 0.000000 20 50000.00 0.000000 21 0.000000 0.000000 22 0.000000 0.000000 23 0.000000 0.000000 24 40000.00 0.000000 25 0.000000 0.000000 26 0.000000 0.000000 27 0.000000 0.000000 28 37735.85 0.000000 2

8、9 0.000000 0.000000 30 21603.77 0.000000 31 0.000000 0.000000 32 0.000000 0.0000004.10某城市的消防總站將全市劃分為11個(gè)防火區(qū)，現(xiàn)有4個(gè)消防站，圖4-11給出的是該城市各防火區(qū)域和防火站的示意圖，其中1,2,3,4，表示消防站1，2，11表示防火區(qū)域，根據(jù)歷史資料證實(shí)，各消防站可在事先規(guī)定允許的時(shí)間內(nèi)對(duì)所負(fù)責(zé)的區(qū)域內(nèi)的火災(zāi)予以撲滅，圖中沒(méi)有虛線連接的就表示不負(fù)責(zé)，現(xiàn)在總部提出：能否減少消防站的數(shù)目，仍能保證負(fù)責(zé)各地區(qū)的防火任務(wù)？如果可以的話，應(yīng)該關(guān)閉哪個(gè)？練習(xí)4.10某城市的消防站總部將全市劃分為11個(gè)防火區(qū)

9、，現(xiàn)有四的。解：根據(jù)題意，用xi表示第i個(gè)消防站的關(guān)系的打開(kāi)關(guān)閉情況X=1； 第i個(gè)消防站不關(guān)閉 0； 第i個(gè)消防站關(guān)閉用y代表第i個(gè)消防站到第j個(gè)防火區(qū)域的到達(dá)情況，0表示不可達(dá)，1表示可達(dá)，Y=1,1,1,1,0,1,1,1,0,0,0;1,1,0,1,0,0,0,1,1,0,0;0,0,0,1,1,1,0,0,0,0,1;0,0,0,0,0,1,1,1,1,1,1;則問(wèn)題可歸結(jié)為01整數(shù)規(guī)劃模型。min z=sum x（i）;St x（i）*y（i，j）>=1；j=1,2,3.11 x（i）<=3； X=0或1 利用lingo求解model:sets:n_i/1.4/:x;n

10、_j/1.11/;link(n_i,n_j):y;endsetsdata:y=1,1,1,1,0,1,1,1,0,0,0,1,1,0,1,0,0,0,1,1,0,0,0,0,0,1,1,1,0,0,0,0,1,0,0,0,0,0,1,1,1,1,1,1;enddataobjmin=sum(n_i(i):x(i);for(n_j(j):sum(n_i(i):x(i)*y(i,j)>=1;);for(n_j(j):sum(n_i(i):x(i)<=3;);for(n_i(i):bin(x(i);x(i)>=0;);end運(yùn)行結(jié)果：Global optimal solution f

11、ound. Objective value: 3.000000 Extended solver steps: 0 Total solver iterations: 0 Variable Value Reduced Cost X( 1) 1.000000 1.000000 X( 2) 0.000000 1.000000 X( 3) 1.000000 1.000000 X( 4) 1.000000 1.000000 Y( 1, 1) 1.000000 0.000000 Y( 1, 2) 1.000000 0.000000 Y( 1, 3) 1.000000 0.000000 Y( 1, 4) 1.

12、000000 0.000000 Y( 1, 5) 0.000000 0.000000 Y( 1, 6) 1.000000 0.000000 Y( 1, 7) 1.000000 0.000000 Y( 1, 8) 1.000000 0.000000 Y( 1, 9) 0.000000 0.000000 Y( 1, 10) 0.000000 0.000000 Y( 1, 11) 0.000000 0.000000 Y( 2, 1) 1.000000 0.000000 Y( 2, 2) 1.000000 0.000000 Y( 2, 3) 0.000000 0.000000 Y( 2, 4) 1.0

13、00000 0.000000 Y( 2, 5) 0.000000 0.000000 Y( 2, 6) 0.000000 0.000000 Y( 2, 7) 0.000000 0.000000 Y( 2, 8) 1.000000 0.000000 Y( 2, 9) 1.000000 0.000000 Y( 2, 10) 0.000000 0.000000 Y( 2, 11) 0.000000 0.000000 Y( 3, 1) 0.000000 0.000000 Y( 3, 2) 0.000000 0.000000 Y( 3, 3) 0.000000 0.000000 Y( 3, 4) 1.00

14、0000 0.000000 Y( 3, 5) 1.000000 0.000000 Y( 3, 6) 1.000000 0.000000 Y( 3, 7) 0.000000 0.000000 Y( 3, 8) 0.000000 0.000000 Y( 3, 9) 0.000000 0.000000 Y( 3, 10) 0.000000 0.000000 Y( 3, 11) 1.000000 0.000000 Y( 4, 1) 0.000000 0.000000 Y( 4, 2) 0.000000 0.000000 Y( 4, 3) 0.000000 0.000000 Y( 4, 4) 0.000

15、000 0.000000 Y( 4, 5) 0.000000 0.000000 Y( 4, 6) 1.000000 0.000000 Y( 4, 7) 1.000000 0.000000 Y( 4, 8) 1.000000 0.000000 Y( 4, 9) 1.000000 0.000000 Y( 4, 10) 1.000000 0.000000 Y( 4, 11) 1.000000 0.000000 Row Slack or Surplus Dual Price OBJ 3.000000 -1.000000 2 0.000000 0.000000 3 0.000000 0.000000 4

16、 0.000000 0.000000 5 1.000000 0.000000 6 0.000000 0.000000 7 2.000000 0.000000 8 1.000000 0.000000 9 1.000000 0.000000 10 0.000000 0.000000 11 0.000000 0.000000 12 1.000000 0.000000 13 0.000000 0.000000 14 0.000000 0.000000 15 0.000000 0.000000 16 0.000000 0.000000 17 0.000000 0.000000 18 0.000000 0

17、.000000 19 0.000000 0.000000 20 0.000000 0.000000 21 0.000000 0.000000 22 0.000000 0.000000 23 0.000000 0.000000 24 1.000000 0.000000 25 0.000000 0.000000 26 1.000000 0.000000 27 1.000000 0.000000結(jié)果如下： X= X=X=1，X=0；即應(yīng)關(guān)閉2號(hào)消防站。121234910117564834.11某航空公司主要經(jīng)營(yíng)A，B，C三個(gè)大城市之間的航線飛行，這些航線每天航班起飛與到達(dá)時(shí)間如表4-16所示，假如飛

18、機(jī)在機(jī)場(chǎng)停留損失費(fèi)用大致與停留時(shí)間的平方成正比，又知每架飛機(jī)從降落到下一班起飛至少需要2h的準(zhǔn)備時(shí)間，試分析確定一個(gè)使總的停留損失費(fèi)用最小的飛行方案。航班號(hào)出發(fā)城市起飛時(shí)間到達(dá)城市到達(dá)時(shí)間101A9：00B2:00（次日）102A10：00B12:00103A15：00B13:00104A20：00C18:00105A22：00C24:00106B4：00A7:00107B11：00A14:00108B15：00A18:00109C7：00A11:00110C15：00A19:00111B13：00C18:00112B18：00C23:00113C15：00B20:00114C7：00B12:00解：設(shè)飛機(jī)停留一小時(shí)的損失費(fèi)為a元，則停留兩小時(shí)損失為4a元，停留3小時(shí)的損失費(fèi)用為9a元，依次類推，對(duì)A.、B、C三個(gè)城市建立的指派問(wèn)題效率矩陣分別如下表： 城市A起飛到達(dá) 101 102103104105 106 4a 9a 64a169a225a 107 361a 400a 625a 36a 64