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

本文格式為Word版，下載可任意編輯——運籌學(xué)整數(shù)規(guī)劃例題...

....

練習(xí)4.9連續(xù)投資問題

某公司現(xiàn)有資金10萬元,擬在今后五年考慮用于以下工程的投資:

工程A:從第一年到第四年每年年初需要投資,并于次年收回本利115%,但要求第一年投資最低金額為4萬元,其次.三.四年不限.

工程B:第三年初需要投資,到第五年末能收回本利128%,但規(guī)定最低投資金額為3萬元,最高金額為5萬元.

工程C:其次年初需要投資,到第五年末能收回本利140%,但規(guī)定其投資金額或為2萬元,或為4萬元,或為6萬元,或為8萬元.

工程D:五年每年年初都可購買公債,于當(dāng)年末歸還,并獲利6%,此工程投資金額不限.

試問該公司應(yīng)圖和確定這些工程的每年投資金額,使到第五年末擁有最大的資金收益.

(1)為工程各年月初投入向量。

(2)為i種工程j年的月初的投入。

(3)向量c中的元素為i年末j種工程收回本例的百分比。

(4)矩陣A中元素為約束條件中每個變量的系數(shù)。

(5)Z為第5年末能擁有的資金本利最大總額。

因此目標(biāo)函數(shù)為

束條件應(yīng)是每年年初的投資額應(yīng)等于該投資者年初所擁有的資金.

第1年年初該投資者擁有10萬元資金,故有

.

第2年年初該投資者手中擁有資金只有,故有

.

第3年年初該投資者擁有資金為從工程收回的本金:,及從工程中第1年投資收回的本金:,故有

同理第4年、第5年有約束為

,

max=1.15*x4a+1.28*x3b+1.4*x2c+1.06*x5d;

x1a+x1d=100000;

-1.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;x3c=0;x4c=0;x5c=0;

x1d=0;x2d=0;x3d=0;x4d=0;x5d=0;

VariableValueReducedCost

X4A22900.000.000000

X3B50000.000.000000

X2C40000.000.000000

X5D0.0000000.000000

X1A62264.150.000000

X1D37735.850.000000

X2A0.0000000.000000

X2D0.0000000.3036000E-01

X3A0.0000000.000000

X3D21603.770.000000

X4D0.0000000.2640000E-01

X5A0.0000000.000000

X1B0.0000000.000000

X2B0.0000000.000000

X4B0.0000000.000000

X5B0.0000000.000000

X1C0.0000000.000000

X3C0.0000000.000000

X4C0.0000000.000000

X5C0.0000000.000000

RowSlackorSurplusDualPrice

180000.001.000000

20.0000001.401850

30.0000001.322500

40.0000001.219000

50.0000001.150000

60.0000001.060000

70.000000-0.8388608E+18

8-20000.00-0.1280000E+10

9-40000.00-0.1280000E+10

10-20000.000.1280000E+10

1120000.000.000000

120.0000000.6100000E-01

1362264.150.000000

140.0000000.000000

150.0000000.000000

1622900.000.000000

170.0000000.000000

180.0000000.000000

190.0000000.000000

2050000.000.000000

210.0000000.000000

220.0000000.000000

230.0000000.000000

2440000.000.000000

250.0000000.000000

260.0000000.000000

270.0000000.000000

2837735.850.000000

290.0000000.000000

3021603.770.000000

310.0000000.000000

320.0000000.000000

4.10

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

練習(xí)4.10

某城市的消防站總部將全市劃分為11個防火區(qū)，現(xiàn)有四的。。。。。。

解：根據(jù)題意，用xi表示第i個消防站的關(guān)系的開啟關(guān)閉狀況

X=1；第i個消防站不關(guān)閉

0；第i個消防站關(guān)閉

用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é)為0—1整數(shù)規(guī)劃模型。

minz=sumx（i）;

Stx（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_j/1..11/;

link(n_i,n_j):y;

endsets

data:

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;

enddata

[obj]min=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é)果：

Globaloptimalsolutionfound.

Objectivevalue:3.000000

Extendedsolversteps:0

Totalsolveriterations:0

VariableValueReducedCost

X(1)1.0000001.000000

X(2)0.0000001.000000

X(3)1.0000001.000000

X(4)1.0000001.000000

Y(1,1)1.0000000.000000

Y(1,2)1.0000000.000000

Y(1,3)1.0000000.000000

Y(1,4)1.0000000.000000

Y(1,5)0.0000000.000000

Y(1,6)1.0000000.000000

Y(1,7)1.0000000.000000

Y(1,8)1.0000000.000000

Y(1,9)0.0000000.000000

Y(1,10)0.0000000.000000

Y(1,11)0.0000000.000000

Y(2,1)1.0000000.000000

Y(2,2)1.0000000.000000

Y(2,3)0.0000000.000000

Y(2,4)1.0000000.000000

Y(2,5)0.0000000.000000

Y(2,6)0.0000000.000000

Y(2,7)0.0000000.000000

Y(2,8)1.0000000.000000

Y(2,9)1.0000000.000000

Y(2,10)0.0000000.000000

Y(2,11)0.0000000.000000

Y(3,1)0.0000000.000000

Y(3,2)0.0000000.000000

Y(3,3)0.0000000.000000

Y(3,4)1.0000000.000000

Y(3,5)1.0000000.000000

Y(3,6)1.0000000.000000

Y(3,7)0.0000000.000000

Y(3,8)0.0000000.000000

Y(3,9)0.0000000.000000

Y(3,10)0.0000000.000000

Y(3,11)1.0000000.000000

Y(4,1)0.0000000.000000

Y(4,2)0.0000000.000000

Y(4,3)0.0000000.000000

Y(4,4)0.0000000.000000

Y(4,5)0.0000000.000000

Y(4,6)1.0000000.000000

Y(4,7)1.0000000.000000

Y(4,8)1.0000000.000000

Y(4,9)1.0000000.000000

Y(4,10)1.0000000.000000

Y(4,11)1.0000000.000000

RowSlackorSurplusDualPrice

OBJ3.000000-1.000000

20.0000000.000000

30.0000000.000000

40.0000000.000000

51.0000000.000000

60.0000000.000000

72.0000000.000000

81.0000000.000000

91.0000000.000000

100.0000000.000000

110.0000000.000000

121.0000000.000000

130.0000000.000000

140.0000000.000000

150.0000000.000000

160.0000000.000000

170.0000000.000000

180.0000000.000000

190.0000000.000000

200.0000000.000000

210.0000000.000000

220.0000000.000000

230.0000000.000000

241.0000000.000000

250.0000000.000000

261.0000000.000000

271.0000000.000000

結(jié)果如下：

X=X=X=1，X=0；即應(yīng)關(guān)閉2號消防站。

1

1

2

1

2

3

4

9

10

11

7

5

6

4

8

3

4.11

某航空公司主要經(jīng)營A，B，C三個大城市之間的航線飛行，這些航線每天航班起飛與到達時間如表4-16所示，假使飛機在機場停留損失費用大致與停留時間的平方成正比，又知每架飛機從下降到下一班起飛至少需要2h的準(zhǔn)備時間，試分析確定一個使總的停留損失費用最小的飛行方案。

航班號

出發(fā)城市

起飛時間

到達城市

到達時間

101

A

9：00

B

2:00（次日）

102

A

10：00

B

12:00

103

A

15：00

B

13:00

104

A

20：00

C

18:00

105

A

22：00

C

24:00

106

B

4：00

A

7:00

107

B

11：00

A

14:00

108

B

15：00

A

18:00

109

C

7：00

A

11:00

110

C

15：00

A

19:00

111

B

13：00

C

18:00

112

B

18：00

C

23:00

113

C

15：00

B

20:00

114

C

7：00

B

12:00

解：設(shè)飛機停留一小時的損失費為a元，則停留兩小時損失為4a元，停留3小時的損失費用為9a元，依次類推，對A.、B、C三個城市建立的指派問題效率矩陣分別如下表：

城市A

起飛

到達

101

102

103

104

105

106

4a

9a

64a

169a

225a

107

361a

400a

625a

36a

64a

108

225a

256a

441a

4a

16a

109

484a

529a

16a

81a

121a

110

196a

225a

400a

625a

9a

用匈牙利法

解得最優(yōu)解為：

起飛

到達

101

102

103

104

105

106

0

1

0

0

0

107

0

0

0

1

0

108

0

0

0

0

1

109

0

0

1

0

0

110

1

0

0

0

0

城市B

起飛

到達

101

102

103

104