運籌學整數(shù)規(guī)劃例題

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

2、目各年月初投入向量。(2) 為 i 種項目j年的月初的投入。(3) 向量c中的元素為i年末j種項目收回本例的百分比。(4) 矩陣A中元素為約束條件中每個變量的系數(shù)。(5) Z為第5年末能擁有的資金本利最大總額。因此目標函數(shù)為束條件應是每年年初的投資額應等于該投資者年初所擁有的資金.第1年年初該投資者擁有10萬元資金,故有.第2年年初該投資者手中擁有資金只有,故有.第3年年初該投資者擁有資金為從項目收回的本金: ,及從項目中第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個防火區(qū)，現(xiàn)有4個消防站，圖4-11給出的是該城市各防火區(qū)域和防火站的示意圖，其中1,2,3,4，表示消防站1，2，11表示防火區(qū)域，根據(jù)歷史資料證實，各消防站可在事先規(guī)定允許的時間內(nèi)對所負責的區(qū)域內(nèi)的火災予以撲滅，圖中沒有虛線連接的就表示不負責，現(xiàn)在總部提出：能否減少消防站的數(shù)目，仍能保證負責各地區(qū)的防火任務？如果可以的話，應該關閉哪個？練習4.10某城市的消防站總部將全市劃分為11個防火區(qū)

9、，現(xiàn)有四的。解：根據(jù)題意，用xi表示第i個消防站的關系的打開關閉情況X=1； 第i個消防站不關閉 0； 第i個消防站關閉用y代表第i個消防站到第j個防火區(qū)域的到達情況，0表示不可達，1表示可達，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;則問題可歸結(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運行結(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；即應關閉2號消防站。121234910117564834.11某航空公司主要經(jīng)營A，B，C三個大城市之間的航線飛行，這些航線每天航班起飛與到達時間如表4-16所示，假如飛

18、機在機場停留損失費用大致與停留時間的平方成正比，又知每架飛機從降落到下一班起飛至少需要2h的準備時間，試分析確定一個使總的停留損失費用最小的飛行方案。航班號出發(fā)城市起飛時間到達城市到達時間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解：設飛機停留一小時的損失費為a元，則停留兩小時損失為4a元，停留3小時的損失費用為9a元，依次類推，對A.、B、C三個城市建立的指派問題效率矩陣分別如下表： 城市A起飛到達 101 102103104105 106 4a 9a 64a169a225a 107 361a 400a 625a 36a 64