運籌學課件：空中交通系統(tǒng)動態(tài)規(guī)劃

空中交通系統(tǒng)優(yōu)化與管理動態(tài)規(guī)劃什么是動態(tài)規(guī)劃動態(tài)規(guī)劃是解決多階段決策過程最優(yōu)化的一種方法。1951年美國數學家貝爾曼（R·Bellman）等人提出了解決這類問題的“最優(yōu)化原理”，并研究了許多實際問題。什么是動態(tài)規(guī)劃在工程技術、企業(yè)管理、工農業(yè)生產及軍事部門中都有廣泛應用：解決最優(yōu)路徑問題、資源分配問題、生產調度問題、庫存問題、裝載問題、排序問題、設備更新問題、生產過程最優(yōu)控制問題等等。動態(tài)規(guī)劃模型分類：離散確定型、離散隨機型、連續(xù)確定型、連續(xù)隨機型。5.1多階段決策問題的最優(yōu)化多階段決策問題，是指可將過程劃分為若干個互相聯系的階段，在它的每一個階段都需要作出決策，并且一個階段的決策確定以后，常影響下一階段的決策，從而影響整個過程的活動。各個階段所確定的決策就構成一個決策序列，通常稱為策略。由于每一個階段可供選擇的決策往往不只一個，因而就有許多策略可供選擇。多階段的決策問題，就是要在允許選擇的那些策略中，選擇一個最優(yōu)策略，使在預定的標準下達到最好的效果。5.1多階段決策問題的最優(yōu)化5.1多階段決策問題的最優(yōu)化階段往往可以用時段來表示。在各個時間階段，采用不同的決策是隨時間而變動的，這就有“動態(tài)”的含義。它是在時間的推移過程中要在每一段選擇最恰當的決策，以期整體上達到最優(yōu)。5.1多階段決策問題的最優(yōu)化

動態(tài)規(guī)劃在一定條件下也可以解決一些與時間無關的問題，只要人為地引進"時段"因素以后，這些問題就可變?yōu)橐粋€多階段決策問題。5.1多階段決策問題的最優(yōu)化

例1

生產與存貯問題

某工廠每月需供應市場一定數量的產品，并將所余產品存入倉庫。一般某月適當增加產量可降低生產成本，但超產部分存入倉庫會增加庫存費用。要求確定一個逐月的生產計劃，在滿足需求條件下，使一年的生產與存貯費用之和最小。

全年分為12個階段逐次決策。5.1多階段決策問題的最優(yōu)化例2投資決策問題某公司現有資金Q萬元，在今后5年內考慮給A，B，C，D

4個項目投資，這些項目投資的回收期限、回報率均不相同，問該公司應如何確定這些項目每年的投資額，使到第5年末擁有資金的本利總額最大。這是一個5階段決策問題。5.1多階段決策問題的最優(yōu)化例3設備更新問題

企業(yè)在使用設備時都要考慮設備的更新問題，因為設備越陳舊所需的維修費用越多，但購買新設備則要一次性支出較大的費用；現某企業(yè)要決定一臺設備未來8年的更新計劃，已預測了第j年購買設備的價格為Kj，設Gj為設備經過j年后的殘值，Cj為設備連續(xù)使用j-1年后在第j年的維修費(j＝1，2，…，8)，問應在哪些年更新設備可使總費用最小。這是一個8階段決策問題

例4：最短路線問題5.1多階段決策問題的最優(yōu)化圖5-35.2動態(tài)規(guī)劃的基本概念和基本原理動態(tài)規(guī)劃的基本概念使用動態(tài)規(guī)劃方法解決多階段決策問題，首先要將實際問題寫成動態(tài)規(guī)劃模型，此時要用到以下概念：階段；狀態(tài)；決策和策略；(4)狀態(tài)轉移；(5)指標函數。

例4最短路線問題5.2.1 動態(tài)規(guī)劃的基本概念圖5—3如圖5-3所示，給定一個線路網絡圖，要從A地向F地鋪設一條輸油管道，各點間連線上的數字表示距離，問應選擇什么路線，可使總距離最短。階段和階段變量：將所給問題的過程，按時間或空間特征分解成若干互相聯系的階段，以便按次序去求每階段的解，常用字母k表示階段變量。例4中，從A到F,

可以分成從A到B(B有兩種選擇)，從B到C(C有四種選擇)，從C到D(D有三種選擇)，從D到E(E有兩種選擇)，再從E到F,五個階段。k＝1，2，3，4，5。5.2.1 動態(tài)規(guī)劃的基本概念動態(tài)規(guī)劃的基本概念狀態(tài)和狀態(tài)變量：狀態(tài)表示某一階段初所處的位置或狀況。通常一個階段包含若干個狀態(tài)。描述狀態(tài)的變量稱為狀態(tài)變量，常用sk表示第k階段的某一狀態(tài)，狀態(tài)變量sk的集合稱為狀態(tài)集合，用Sk表示。5.2.1 動態(tài)規(guī)劃的基本概念在例4中，第一階段狀態(tài)為A,第二階段狀態(tài)：B1，B2，或s1=A， s21=B1 ，s22= B2。狀態(tài)變量的集合:S1 = {A}S2 ＝ {B1，B2 }S3 ＝ {C1，C2， C3，C4 }S4＝{D1，D2，D3}S5＝{E1，E2 }動態(tài)規(guī)劃中的狀態(tài)應具有如下性質：代表性。能夠反映過程的演變特征。可知性。能夠通過某種方式，直接或間接地確定下來。無后效性。所謂無后效性，是指某階段的狀態(tài)，只對該階段狀態(tài)以后過程的演變起作用，而不受以前各階段狀態(tài)的影響。這就是說，過程的過去歷史只能通過當前的狀態(tài)去影響它的未來的發(fā)展，當前的狀態(tài)就是未來過程的初始狀態(tài)5.2.1 動態(tài)規(guī)劃的基本概念5.2.1 動態(tài)規(guī)劃的基本概念要正確地定義狀態(tài)變量，就必須對問題具有深入的觀察和理解，可以從下面兩個方面來考慮：把階段連系在一起的因素是什么?需要用什么信息來進行當前的決策，而不用檢查以前階段所作決策的可行性。5.2.1 動態(tài)規(guī)劃的基本概念決策和決策變量:

決策就是某階段狀態(tài)給定以后，從該狀態(tài)演變到下一階段某狀態(tài)的選擇。描述決策的變量，稱為決策變量。常用uk(sk)表示第k階段當狀態(tài)為sk時的決策變量。在實際問題中，決策變量的取值往往限制在一定范圍內，我們稱此范圍為允許決策集合，常用Dk(sk)表示第k階段從狀態(tài)sk出發(fā)的允許決策集合，顯然有：uk(sk)

Dk(sk) 。5.2.1 動態(tài)規(guī)劃的基本概念5.2.1 動態(tài)規(guī)劃的基本概念在例4中，從第二階段的狀態(tài)集合為S2={B1,B2}

，從B1出發(fā)，允許決策集合為：D2(B1)＝{C1，C2，C3}如我們決定選擇C3：，則可表為：u2(B1)＝C3策略和最優(yōu)策略:由第1階段開始到最后一個階段終點為止的過程，稱為問題的全過程。由每階段的決策uk(sk)組成的決策序列就構成一個全過程策略，簡稱為策略，記為P1,n：P1,n(s1)={u1(s1),u2(s2),…

,un(sn)}由過程的第k階段開始到終點為止的過程，稱為原過程的后部子過程(或稱為k子過程)。其決策函數序列稱為k子過程策略，簡稱子策略，記為Pk,n

即：Pk,n(sk)={uk(sk),uk+1(sk+1),…

,un(sn)}5.2.1 動態(tài)規(guī)劃的基本概念– 允許策略集合用P表示。從允許策略集合中找出達到最優(yōu)效果的策略稱為最優(yōu)策略。在上圖中，用P1,5={A，B1，C2，D2，E1，F}是一個策略，P3,5={C2，D2，E1，F}

是P1,5的一個子策略。5.2.1 動態(tài)規(guī)劃的基本概念狀態(tài)轉移方程動態(tài)規(guī)劃中本階段的狀態(tài)往往是上一階段狀態(tài)和上一階段的決策結果。如果給定了第k段的狀態(tài)sk

，則第k+1段的狀態(tài)sk+1

也就完全確定。狀態(tài)轉移方程：由k段到k十l段的狀態(tài)轉移規(guī)律,sk+1

=Tk

(sk,uk)。例4中，狀態(tài)轉移方程為：sk+1

= uk(sk)5.2.1 動態(tài)規(guī)劃的基本概念動態(tài)規(guī)劃的基本概念指標函數及最優(yōu)指標函數在多階段決策過程最優(yōu)化問題中，用來衡量所實現過程的優(yōu)劣的數量指標，稱為指標函數；它是一個定義在全過程和所有后部子過程上的確定的數量函數，常用Vk,n表示．即：Vk,n=

Vk,n（sk,sk+1,…,sn）指標函數Vk,n的最優(yōu)值，稱為相應的最優(yōu)指標函數，記為fk(sk)。5.2動態(tài)規(guī)劃的基本概念和基本原理5.1.2.動態(tài)規(guī)劃的基本原理Bellman最優(yōu)化原理作為整個過程的最優(yōu)策略具有這樣的性質：即無論過去的狀態(tài)和決策如何，對前面的決策所形成的狀態(tài)而言，余下的諸決策必須構成最優(yōu)策略。結合例4最短路線問題介紹動態(tài)規(guī)劃的基本思想。從過程的最后一段開始，用逆序遞推方法求解，逐步求各段各點到終點廠的最短路線，最后求得A點到F點的最短路線。5.1.2.動態(tài)規(guī)劃的基本原理

第一步，從s＝5開始，狀態(tài)變量s5可取兩種狀態(tài)E1，E2，它們到F點的路長分別為f5

(E1

)

4 f5

(E2

)

3第二步，k＝4，狀態(tài)變量s5可取三個值D1，D2，D3，這是經過一個中途點到達終點F的兩級決策問題，從D1到F只有兩條路線，需加以比較，取其中最短的，即：

1 2 5 2

1 1 5 1

5

3

min

7

d(D,E)

f

(E

) 3

4

d(D

,

E )

f

(E )

f4

(D1

)

min

5

2

3

6

4

min

2 2 5 2

d(D

,

E )

f(E

)

d

(D2

,

E1

)

f5

(E1

)f4(D2)

min14 1u*(D)

E2u*(D )

E4 2

53

3

1

4

min

3 2 5 2

d(D,E)

f(E

)

d

(D3,

E1

)

f5

(E1

)f4

(D3

)

minu*(D)

E4 3 1u*(C)

D3 4 3f3

(C4

)

9u*(C)

D3 3 2f3

(C3

)

8u*(C)

D3 2 2f3

(C2

)

103 1 1u*(C)

D3 1k

3時,

f

(C

)

122 2 3u*(B)

Cf2

(B2

)

152u*(B)

C2 1k

2時,

f2

(B1

)

132 11d

(

A,

B

)

f (B

)1

5

15

4

13

min

17

2 2 2

d

(

A,

B

)

f (B

)

k

1時,

f

(

A)

min最短路為17,路徑為A

B1

C2

D2

E2

Fu*(A)

B1 1圖7-2

f6

(s6

)

0)

f (s )} k

5,4,3,2,1k

1 k

1(sk,

ukkfk(sk)

min{duk動態(tài)規(guī)劃方法的基本思想：將多階段決策過程劃分階段，恰當地選取狀態(tài)變量、決策變量及定義最優(yōu)指標函數，從而把問題化成一族同類型的子問題，然后逐個求解。求解時從邊界條件開始，逆(或順)過程行進方向，逐段遞推尋優(yōu)。在每一個子問題求解時，都要使用它前面已求出的子問題的最優(yōu)結果，最后一個子問題的最優(yōu)解，就是整個問題的最優(yōu)解。動態(tài)規(guī)劃方法是既把當前一段與未來各段分開，又把當前效益和未來效益結合起來考慮的一種最優(yōu)化方法，因此每段的最優(yōu)決策選取是從全局考慮的，與該段的最優(yōu)選擇一般是不同的。5.1.2.動態(tài)規(guī)劃的基本原理Bellman最優(yōu)化原理：作為整個過程的最優(yōu)策略具有這樣的性質：即無論過去的狀態(tài)和決策如何，對前面的決策所形成的狀態(tài)而言，余下的諸決策必須構成最優(yōu)策略。

n

1

n

1(s )

0

f

動態(tài)規(guī)劃的基本方程是遞推逐段求解的根據，一般的動態(tài)規(guī)劃基本方程可以表為：

fk(sk

)

opt {vk(sk,

uk)

fk

1(sk

1

)}

uk

Dk(

sk)

k

n,

n

1,...,15.1.2.動態(tài)規(guī)劃的基本原理動態(tài)規(guī)劃的基本解題步驟如下：第一步：劃分階段；第二步：確定狀態(tài)變量及其取值范圍；代表性。2)可知性。3)無后效性。第三步：確定決策變量及其取值范圍；第四步：建立狀態(tài)轉移方程；第五步：確定指標函數第六步：建立動態(tài)規(guī)劃基本方程，然后從k＝n開始，逐段向前推移，直到求出f1(s1)時，就得到了整個過程的最優(yōu)解，包括最優(yōu)策略和相應的最優(yōu)指標函數值5.1.2.動態(tài)規(guī)劃的基本原理動態(tài)規(guī)劃模型的建立與求解動態(tài)規(guī)劃模型的建立

資源分配問題例5 某公司有資金10萬元，若投資于項目j(j＝1，2，3)的投資額為xi時，其收益分別為g1(x1)3＝4x1，g2(x2)＝9x2，g3(x3)＝2x

2，問應如何分配投資數額才能使總收益最大?

x

0 (i

1,2,3)

i

x1

x2

x3

103maxz

4x1

9x2

2x2且滿足約束這是一個與時間無明顯關系的靜態(tài)最優(yōu)化問題，可列出其靜態(tài)模型： 求x1，x2，x2：，使5.3.1動態(tài)規(guī)劃模型的建立

用動態(tài)規(guī)劃方法求解：基本方程：3階段k：k=1,2,3狀態(tài)變量sk

：第k段可以投資于第k項到第3個項目的資金數。決策變量xk

：決定給第k個項目投資的資金數。狀態(tài)轉移方程：

sk+1＝

sk

-

xk

。指標函數：Vk

,3

gi

(

xi

)i

k最優(yōu)指標函數人fk(sk)：當可投資金數為sk時，投資第k——3項所得的最大收益數k k k k k

1 k

10

xk

skf (

s )

max

{g (

x )

f (

s )} k

3,

2,1

f4(

s4)

05.3.1動態(tài)規(guī)劃模型的建立收益船廠012345A035789B046899C0137910例6 船舶總公司擬將5萬元資金投放到下屬A、B、C三個船廠，各船廠在獲得資金后的收益如表5-1所示。試用動態(tài)規(guī)劃方法求使總收益最大的投資分配方案。表5-15.3.1動態(tài)規(guī)劃模型的建立解：階段k：k=1,2,3狀態(tài)變量sk

：第k段可以投資于第k項到第3個項目的資金數。

S1

{5}

{0

,1,

2

,

3,

4,

5} k

2,

3

S

k決策變量xk

:為第k階段分配給第k個船廠的資金數。顯然:Dk(sk)

{0,1,2,3,

4,

5} k

1,

2

,

3– 狀態(tài)轉移方程：sk

1k

1,2,

3

sk

xk5.3.1動態(tài)規(guī)劃模型的建立xk

Dk(sk

)–指標函數：階段指標函數gk(sk)如表5-1所示–最優(yōu)指標函數人fk(sk)：當可投資金數為sk時，投資第

k——3項所得的最大收益數–基本方程：

fk(sk

)

m

ax {gk(xk

)

f

k

1

(

s

k

1

)}4 4k

3,

2

,

1

f (

s )

0

用逆序法由最后一階段向前推進計算。5.3.1動態(tài)規(guī)劃模型的建立x3f3

(s3

)

max{g3

(x3

)

f4

(s4

)}K=3時：階段s3g3

(x3)f3

(s3

)f4(s4

)x3

*k=300000111012330237703499045101005階段s2x2g2(x2

)f

2

(

x2

)f3(s2

x2

)x2

*k=20000001000+1=1f3(1)=1144+0=4f3(0)=012000+3=3f3(2)=3144f3(1)=1266f3(0)=023007f3(3)=7147f3(2)=3267f3(1)=1388f3(0)=034009f3(4)=91411f3(3)=71269f3(2)=3389f3(1)=1499f3(0)=050010f3(5)=101413f3(4)=

912613f3(3)=723811f3(2)=34910f3(1)=1599f3(0)=0階段s1x1g1

(x1

)f2

(5

s1

)x1

*k=1500131313141112513837136481245990f1

(5)

14(萬元)最優(yōu)策略(對船廠A、B、C的資金分配序列)是：分給船廠A 1萬元，分給船廠B 1萬元，分給船廠C3萬元最大收益是14萬元。由上述計算結果可知:最大收益是：

例4的順序解法：5.3.2.

逆序法與順序法

從k＝0開始，f0

(s1

)

f0

(

A)

0

k＝2時，f2

(s3

) 定義有：

f2

(C1

)

d

(B1

,

C1

)

f1

(B1

)

2

4

6

u (C)

B

2 1 1是邊界條件

k＝1時，f1

(s2

) 定義有：

f1(B1)

4

f1

(B2

)

5

u1(B1)

A

u1(B2)

Ad

(B1

,

C2

)

f1

(B1

)f2(C2)

min3

4

min

7

d(B

,

C )

f(B

)

2 2 1 2

8

5

u (C )

B

2 2 1

d

(B1

,C3

)

f1

(B1

)2 36

4f (C)

min

min

10

d(B,C)

f(B

)

2 3 1 2

7

5

u(C)

B

2 3 1

f2

(C4

)

d

(B2

,

C4

)

f1

(B2

)

7

5

12

u2(C4)

B2類似有：

f3

(D1

)

11f3

(D2

)

12f3

(D3

)

14f4

(E1

)

14f4

(E2

)

14f5

(F

)

17u3

(D1

)

C1或C2u3

(D2

)

C2u3(D3)

C3u4(E1)

D1u4(E2)

D2u5(F

)

E2路徑為:

A

B1

C2

D2

E2

F動態(tài)規(guī)劃模型的求解：1)離散變量的分段窮舉算法動態(tài)規(guī)劃模型中的狀態(tài)變量與決策變量若被限定只能取離散值，則可采用分段窮舉法。用分段窮舉法求最優(yōu)指標函數值時，要正確確定每段狀態(tài)變量取值范圍及允許決策集合的范圍。連續(xù)變量的解法當動態(tài)規(guī)劃模型中狀態(tài)變量與決策變量為連續(xù)變量，就要根據方程的具體情況靈活選取求解方法，如經典解析方法、線性規(guī)劃方法、非線性規(guī)劃法或其它數值計算方法等?？捎媚嫘蚪夥ê晚樞蚪夥▉砬蠼?。連續(xù)變量的離散化解法5.3.2.

逆序法與順序法

k

3,2,10

xk

sk例5

某公司有資金10萬元，若投資于項目j(j＝1，2，3)的投資額為xi時，其收益分別為g1(x1)＝4x1，g2(x2)＝9x2，g3(x3)＝2x32，問應如何分配投資數額才能使總收益最大?解：階段k=1,2,3;狀態(tài)變量sk

為第k段可以投資于第k項到第3個項目的資金數；決策變量xk

決定給第k個項目投資的資金數；狀態(tài)轉移方程：

sk+1

＝

sk

-

xk

；最優(yōu)指標函數fk(sk)表示當可投資金數為sk時，投資第k到第3項所得的最大收益數；f1(s1)

為所求的總收益；遞推方程：

fk(

sk)

max{gk(xk

)

f

k

1

(

sk

1

)}4 4

f (

s )

0(a)用逆序解法解例5 3 3 33 30

x

sk＝3時，f (s

)

max

{2x2}k＝2時，

2(s

x )2}2 222 3

2s2}

max

{9x

max

{9x0

x2

s20

x2

s222 2f (s )

max

{9x

f3

(s3)}0

x2

s222

x

)2

9

4(s2

x2

)

0令 h2

(s2

,

x2

)

9x2

2(sdh22

2

4

0 x2

s2

29 d

2

h4 d

2xx2

s2

2則極大值在[0,

s ]端點取得f (0)

2s2

,

f (s )

9s2 2 2 2 294dx是極小值x*

s

時,

有最大值2s23 3 32 22 2 22 22 2 222當s

9

時,

f (0)

f (s ),

此時x*

02s

9

時,

f (0)

f (s ),

此時x*

sk＝1時，f1(s1)

max{4

x1

f2

(

s2)} 當f2

(

s2

)

9s2時,但此時

s2

s1

x1

10

0

9

/

2,

與s2

9

/

2矛盾故舍去0

x

s11f1

(10)

max{4x1

9s1

9x1

)}

max{9s1

5x1

)}

9s1x*

00

x1

10 0

x1

102令f (0)

f (s

)時,2s2

9s

, 則s

92 2 2 2 2 22 2 2 11 1 10

x1

10當f (s )

2s

2時,

f

(10)

max

{4

x

2(s

x )2

}211 1 1 1 1 1

4

4(s1

x1)

01d

2hdx2解得x1

s1

1,

而

1

1

0,

所以x1

s1

1是極小點.1比較[0,10]兩個端點,

x1

0時,

f1

(10)

200x

10時,

f

(10)

40

,

所以,

x*

01 1 1再由狀態(tài)方程順推,

s

s

x*

10

0

102 1 1因為s

9

/

2,

所以x*

0,

s

s

x*

10

0

102 2 3 2 2所以 x*

s

103 3max

z

200萬元令h

(s

,

x )

4

x

2(s

x ) ,由dhdx階段劃分和決策變量設置同逆序法；

狀態(tài)變量sk+1

表示可用于第1個到第k個項目投資的資金數:s4＝10，s3＝s4–x3，s2＝s3–x2，s1＝s2–x1

;狀態(tài)轉移方程：

sk＝

sk+1

-

xk

；最優(yōu)指標函數fk(sk+1)表示第k階段投資金數為sk+1時，投資第1到第k項所得的最大收益數；

遞推方程：

f

k

(

sk

1

)

k

1,2,3max {gk(xk

)

f

k

1

(

sk

)}0

xk

sk

10 1

f (s)

0 (b)用順序解法解例5 1 20

x1

s2當k

1,

f1(s2

)

max{g1(

x1)

f0

(s1

)}1 2

max

{4x

}

4s0

x

s

max

{5x2

4s3

}

9s30

x2

s3

4(s3

x2

)}

max{9x2

4s2

}

max

{9x20

x2

s3 0

x2

s30

x2

s3當k

2,

f2

(s3

)

max

{9x2

f1(s2

)}x*

s1 2x*

s2 33

x )}4

9(s2 3 33 4 3f (

s )

max

{2

x

2

f (

s )}

max

{2

x

20

x3

s4 0

x3

s4當k=3時93所以x*

103dx2則極大值在[0,

s4

]端點取得當x3

0時,

f3

(10)

90,當x3

10時f3

(10)

200d2h

4

0 則x3

4

是極小點3解得x

9

/

4333令 h(s,x)

2x2

9(s

x

)4 3 3 4dx由 dh

4

x

9

0再由狀態(tài)方程逆推,

s

10

x*

03 3x*

0,

s

s

x*

0, x*

02 2 3 2 1同逆序法結果相同max

z

200萬元xksk

1

skk kk k k

1 k

10

xk

skf (

s )

max

{g (

x )

f (

s )} k

n,n

1,...,1

f

n

1

(

sn

1

)

0狀態(tài)轉移方程 :

(i

1,2,...,

n)

xi

0n

i

1

xi

an3)連續(xù)變量的離散化解法投資分配問題的一般靜態(tài)模型為：max

z

gi

(

xi

)i

1動態(tài)規(guī)劃模型，其基本方程為：5.3.2.

逆序法與順序法由于sk與xk都是連續(xù)變量，當各階段指標gk(xk)沒有特殊性質而較為復雜時，要求出fk(sk)會比較困難，這時常常把連續(xù)變量離散化求其數值解。具體做法如下：把a分成m份，每份

大小。Sk的取值范圍為：{0

，2

,…,m

}

，

的大小可依據問題所要求的精度以及計算機的容量來定。決策變量xk也在離散點0，

，2

， … ，m

上取值，相應的指標函數fk(sk)就被定義在這些離散值上，于是:02

1

q

a(m

)… …012qmq

＝sk，

xk＝p

5.3.2.

逆序法與順序法(c)按逆序（或順序）方法，逐步遞推求出fn(sn),

…，f1(s1) ，最后求出最優(yōu)資金分配方案。

x

0 (i

1,2,3)

i

x1

x2

x3

10maxz

4x

9x

2x2 且滿足約束1 2 3解: 令

＝2，將區(qū)間[0，l0]分割成0，2，4，6，8，10六個點，即狀態(tài)變量sk集合為{0，2，4，6，8，10}；允許決策集合為0

xk

sk

，xk與sk均在分割點上取值。例5

k

n,n

1,...,1p

0

,1,

2

,...,

q

f

n

1

(

sn

1

)

0

fk(

sk)

max {gk(

p

)

f

k

1

(

sk

p

)}其中q

＝

sk

，

xk

＝p

遞推方程就變?yōu)榱耍菏街衳3與s3的集合均為：{0，2，4，6, 8，10}。計算結果見表7—1。3 3 30

x3

s3當k＝3時，

f (s

)

max

{2x2}

表7-1階段skxkvkvkn=vk+fk+1fkPkn

*30022x3

=0000228882443232324667272726881281281288101020020020010指標 最優(yōu)指標

最優(yōu)決策

表7-2階段skxkvkvkn=vk+fk+1fkPkn

*2009x2=000020002-022x9=1818+0184000+32=324-022x9=1818+8=2644x9=3636+0=36366000+72=72720-622x9=1818+32=5044x9=3636+8=4465454+0=54810指標計算結果見表7

2最優(yōu)指標

最優(yōu)決策k

2時,

f2

(s2

)

max{9x2

f3(s2

x2

)}0

x2

s2階段skxkvkvkn=vk+fk+1fkPkn

*28000+128=1281280-822x9=1818+72=9044x9=3636+32=6865454+8=6287272+0=7210000+200=2002000-1022x9=1818+1282=14644x9=3636+72=10865454+32=8687272+8=80109090+0=90

表7-2指標計算結果見表7

2最優(yōu)指標

最優(yōu)決策k

2時,

f2

(s2

)

max{9x2

f3(s2

x2

)}0

x2

s2

表7-3階段skxkvkvkn=vk+fk+1fkPkn

*11004x1=00+200=2002000-0-10288+128=13644x4=1624+36=6062454+32=8683232+18=50104040+0=40最優(yōu)指標

最優(yōu)決策x1

)} 計算結果見表7

3指標k

1時,

f1

(s1

)

max{4x1

f2

(s10

x1

10計算結果表明，最優(yōu)決策為：x1*＝0，x2*＝0，x3*＝10，最大收益為f1(10)＝200，與例5結論完全相同。5.4動態(tài)規(guī)劃模型的應用5.4.1背包問題（裝載問題）n一位旅行者攜帶背包去登山，已知他所能承受的背包重量限度為a千克，現有n種物品可供他選擇裝入背包，第i種物品的單件重量為ai千克，其價值(可以是表明本物品對登山的重要性的數量指標)是攜帶件數xi的函數ci(xi)

(i=1,2,...,n),問旅行者應如何選擇攜帶各種物品的件數，以使總價值最大？靜態(tài)數學模型：

max

z

ci

(xi

)i

1ns.t.i ia

x

a

i

1

i

x

0 且為整數(i

1,

2,...,

n)5.4動態(tài)規(guī)劃模型的應用

sk

1狀態(tài)轉移方程：sk

ak

xk0 1k

1,2,...,

n

f (s)

0xk允許決策集合：Dk

(

sk

1

)

{xk

|

0,1,

2,...,[

sk

1

/

ak

]}–最優(yōu)指標函數：

fk

(

sk

+1

)–基本方程：

fk

(

sk

1

)

max{ck

(

xk

)

f

k

1

(

sk

1

ak

xk

)}

動態(tài)規(guī)劃順序法：–階段k：(k=1,2,…,n)

按裝入物品排序–狀態(tài)變量sk

：第k段開始時裝入前k種物品的總重量。–決策變量xk

:裝入第k件物品的件數。5.4動態(tài)規(guī)劃模型的應用狀態(tài)轉移方程：

sk

1

skak

xkn

1 n

1k

n,...,

2,1xk允許決策集合：Dk(xk)

{0,1,2,...,[sk

/ak]}–最優(yōu)指標函數：

fk

(

sk

)–基本方程：

fk

(

sk

)

max{ck

(

xk

)

f

k

1

(

sk

1

)}

f(

s )

0

動態(tài)規(guī)劃逆序法：–階段k：(k=1,2,…,n)

按裝入物品排序–狀態(tài)變量sk

：第k段開始時剩余的空間。–決策變量xk

:裝入第k件物品的件數。5.4動態(tài)規(guī)劃模型的應用例7

今有三種貨物需要裝船，各種貨物的重量與運輸利潤關系如圖5-7所示。船的最大裝載能力為w＝6(t)，問應如何裝載才能使總利潤最大?貨物種類(i)貨物質量(Wi)(t)利潤(vi)(千元）12823133418動態(tài)規(guī)劃逆序法：階段k：(k=1,2,3)

按裝入物品排序狀態(tài)變量sk

：第k段開始時剩余的空間(可裝載第k種至第n種的載貨量。決策變量xk

:裝入第k件貨物的數量。5.4動態(tài)規(guī)劃模型的應用狀態(tài)轉移方程： sk

1

skwk

xk

指標函數：階段指標即為第k階段裝載xk件貨物時所創(chuàng)的利潤vkxk。– 基本方程：xk

Dk(sk

)sk

{0

,1,...,6}

fk(sk

)

max {vk

xk

f

k

1

(

sk

1

)}

xk

Dk(sk

)sk

{0

,1,...,6}

max {vk

xk

fk

1(sk

wkxk)}k

3,

2,1

f (

s )

0

4 4

5.4動態(tài)規(guī)劃模型的應用K=3時：s3s4=s3-4x3K=2時：K=1時：5.4.2

生產存貯問題（庫存問題）

如果已知某企業(yè)所生產產品的生產費用、存貯費用和市場的需要量，在其生產能力和存貯能力許可的前提下，正確確定各個時期的生產量，使既完成交貨計劃，又使總支出最少，這就是生產與存貯問題。例8

某船廠根據合同，從當年起連續(xù)4年年末要為客戶提供規(guī)格型號相同的大型客貨船，每年的交船數及生產每艘船的生產費用如表5—5所示。5.4動態(tài)規(guī)劃模型的應用5.4動態(tài)規(guī)劃模型的應用4i

k0

sk

di該廠的生產能力為每年6艘船。在進行生產的年度，船廠還要支出經常費用60萬元。若造出的船當年不交貨，則每艘船每積壓一年造成的積壓損失費為40萬元。假定開始時及第四年年未交貸后均無積壓船只，問船廠應如何安排這四年的生產計劃，使所花的總費用為最低?解：動態(tài)規(guī)劃逆序法：階段k：(k=1,2,3,4)狀態(tài)變量sk

：第k階段初貯存(積壓)的船數。–決策變量xk

:為第k階段生產的船數。sk

6

d

k s1

s5

0xk

sk

d

k

最大庫存量4xk

sk

dii

kxk

sk

d

kksk

6(k

1)

dii

15.4動態(tài)規(guī)劃模型的應用狀態(tài)轉移方程：sk

1

sk

xk

dk k

1,2,3,

4– 基本方程：k

1 k

1)

f (

s )} k

1,2,3,

4k kk kk0

xk

6f (

s )

min

{v (

s ,

x

f5(s5)

0– 指標函數vk

：就是第k年度的生產成本(包括生產費用與存貯費用兩部分)。

0.6

ckxk

0.4

sk 若xk

0vk(sk,xk)

k

1,2,3,

4k k

0.4

s 若x

0k＝2時，d2＝3k＝1時，x1*＝1，x2*=5，x3*＝0，x4*＝25.4.3

設備更新問題

設備更新問題一般提法：在已知一臺設備的效益函數r(t)，維修費用函數u(t)及更新費用函數c(t)條件下，要求在n年內的每年年初作出決策,

是繼續(xù)使用舊設備還是更換一臺新的，使n年總效益最大。rk(t)：在第k年設備已使用過t年(或稱役齡為t年)，再使用1年時的效益。uk(t)：在第k年設備役齡為t年，再使用一年的維修費用。ck(t)：在第k年賣掉一臺役齡為t年的設備，買進一臺新設備的更新凈費用。a為折扣因子(0

a

1)，表示一年以后的單位收入價值相當于現年的a單位。5.4動態(tài)規(guī)劃模型的應用動態(tài)規(guī)劃模型：階段k：表示計劃使用該設備的年限數。(k=1,…,n)狀態(tài)變量sk

：第k年初設備已使用過的年數，即役齡。決策變量xk

:是第k年初更新(Replacement)，還是保留使用(keep)舊設備，分別用R與K表示。狀態(tài)轉移方程為：5.4動態(tài)規(guī)劃模型的應用–階段指標為：k

1ks

s

1 當xk

K(keep

)

1 當xk

R

(

Replacement

)v (s ,

x )

rk(sk)

uk(sk

)若xk

Kj k kk k kk

k

r(0)

u (0)

c (s ) 若x

R5.4動態(tài)規(guī)劃模型的應用–指標函數為：k kj kf (

s )

max

{v (

skk

1 k

1,

x )

f (

s )} k

n,n

1,

...,1

xk

K

或R

fn

1

(

sn

1

)

0實際上：–最優(yōu)指標函數為：Vk

,n(k

1,2,...,

n)nj

k

vj(sk,

xk)k k k

1

kr (

s )

uk(

sk)

f(

s

1)fk(sk)

max當xk

Kkk kk

1

r (0)

u (0)

c (

s )

f

kk(1) 當x

R

f(

s )

0

n

1 n

1例：設某臺新設備的年效益及年均維修費用、更新凈費用如下表，試確定今后五年內的更新策略，使總效益最大。（設a=1）（單位：萬元）役齡項目012345效益

rk(t)54.543.7532.5運行費

uk(t)0.511.522.53更新費

ck(t)0.51.52.22.533.55.4動態(tài)規(guī)劃模型的應用解：n=55 5 5 55 5r(s)

u(s

)

k

5 f(s)

max

x5

Kx5

R

r5

(0)

u5

(0)

c5

(s5

)狀態(tài)變量s5可取1，2，3，4f (1)

max

r5

(1)

u

5

(1) x5

K逆序法55 5 55

r(0)

u (0)

c (1) x

R

5

max

4.5

1

3.5x (1)

K

5

0.5

1.5

f (2)

max

r5

(2)

u5

(2)x5

K55 555

r(0)

u (0)

c

(2) x

R

5

max

4

1.5

2.5x(2)

K

5

0.5

2.2

f (3)

max

r5(3)

u5

(3) x5

K55 5 55

r(0)

u (0)

c (3) x

R

5

max

3.75

2

2 x (3)

R

5

0.5

2.5

f(4)

max

r5(4)

u5

(4)x5

K55 555

r(0)

u(0)

c

(4) x

R

5

max

3

2.5

1.5x(4)

R

5

0.5

3

5 5 5 5x5

Kx5

R5 5r(s)

u(s

)

k

5 f(s)

max

r5

(0)

u5

(0)

c5

(s5

)r4

(s4

)

u4

(s4

)

f5

(s4

1)x4

K4 44 4 4 54k

4 f (s )

max

r(0)

u (0)

c

(s )

f (1) x

R

4

狀態(tài)變量s4可取1，2，35 4x4

Kx4

R4r4

(

s4

)

u

4

(

s4

)

f (

s

1)4

max

4.5

1

2.5

6.5x (1)

R

5

0.5

1.5

3.5

f (1)

maxs4

1

r4

(0)

u

4

(0)

c4(

s4

)

f5

(1)

x4

Kx4

R4r4(s4)

u4(s4)

f5(s4

1)4

max

4

1.5

2

5.8x (2)

R

5

0.5

2.2

3.5

f (2)

maxs4

2

r4(0)

u4

(0)

c4

(s4

)

f5

(1)

r4

(s4

)

u4

(s4

)

f5

(s4

1)x4

K4 44 4 4 54k

4f (s )

max

r(0)

u (0)

c

(s )

f (1) x

R

4

r4(s4)

u4(s4)

f5(s4

1)x4

Kx4

R4s4

34f (3)

max

max

3.75

2

1.5

5.5x(3)

R

5

0.5

2.5

3.5

r4

(0)

u4

(0)

c4

(s4

)

f5

(1)

3 3 3 3 4 3x3

Kx3

R3 3r(s)

u(s)

f(s

1)k

3 f(s)

max

r3

(0)

u3

(0)

c3

(s3

)

f4

(1)此時s3可取1或24 3r3

(

s3

)

u3

(

s3

)

f (s

1)x3

Kx3

R3s3

13f (1)

max

max

4.5

1

5.8

9.5x (1)

R

5

0.5

1.5

6.5

r3

(0)

u3

(0)

c3

(

s3

)

f

4(1)

4 3r3

(

s3

)

u3

(

s3)

f (

s

1)x3

Kx3

R3s3

23f (2)

max

max

4

1.5

5.5

8.8x (2)

R

5

0.5

2.2

6.5

r3

(0)

u3

(0)

c3

(

s3

)

f

4(1)

r2

(

s2

)

u

2

(

s2

)

f

3

(

s2

1)x2

K

x2

R2s2

12f (1)

max

max

4.5

1

8.8

12.5x (1)

R

5

0.5

1.5

9.5

r2

(0)

u

2

(0)

c2(

s2)

f3

(1)

f (s

)

max

r2

(s2

)

u2

(s2

)

f3

(s2

1)x2

K2 22 2 2 32k

2

r(0)

u (0)

c(s)

f (1) x

R

2由于狀態(tài)s2只能取1，所以有f(s)

max

r1(s1)

u1(s1

)

f2(s1

1)x1

K1 11 1 1 21k

1

r(0)

u(0)

c(s

)

f