運(yùn)籌學(xué)課件：空中交通系統(tǒng)動(dòng)態(tài)規(guī)劃

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

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

例1

生產(chǎn)與存貯問題

某工廠每月需供應(yīng)市場一定數(shù)量的產(chǎn)品，并將所余產(chǎn)品存入倉庫。一般某月適當(dāng)增加產(chǎn)量可降低生產(chǎn)成本，但超產(chǎn)部分存入倉庫會增加庫存費(fèi)用。要求確定一個(gè)逐月的生產(chǎn)計(jì)劃，在滿足需求條件下，使一年的生產(chǎn)與存貯費(fèi)用之和最小。

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

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

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

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

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

可以分成從A到B(B有兩種選擇)，從B到C(C有四種選擇)，從C到D(D有三種選擇)，從D到E(E有兩種選擇)，再從E到F,五個(gè)階段。k＝1，2，3，4，5。5.2.1 動(dòng)態(tài)規(guī)劃的基本概念動(dòng)態(tài)規(guī)劃的基本概念狀態(tài)和狀態(tài)變量：狀態(tài)表示某一階段初所處的位置或狀況。通常一個(gè)階段包含若干個(gè)狀態(tài)。描述狀態(tài)的變量稱為狀態(tài)變量，常用sk表示第k階段的某一狀態(tài)，狀態(tài)變量sk的集合稱為狀態(tài)集合，用Sk表示。5.2.1 動(dòng)態(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 }動(dòng)態(tài)規(guī)劃中的狀態(tài)應(yīng)具有如下性質(zhì)：代表性。能夠反映過程的演變特征?？芍浴Ｄ軌蛲ㄟ^某種方式，直接或間接地確定下來。無后效性。所謂無后效性，是指某階段的狀態(tài)，只對該階段狀態(tài)以后過程的演變起作用，而不受以前各階段狀態(tài)的影響。這就是說，過程的過去歷史只能通過當(dāng)前的狀態(tài)去影響它的未來的發(fā)展，當(dāng)前的狀態(tài)就是未來過程的初始狀態(tài)5.2.1 動(dòng)態(tài)規(guī)劃的基本概念5.2.1 動(dòng)態(tài)規(guī)劃的基本概念要正確地定義狀態(tài)變量，就必須對問題具有深入的觀察和理解，可以從下面兩個(gè)方面來考慮：把階段連系在一起的因素是什么?需要用什么信息來進(jìn)行當(dāng)前的決策，而不用檢查以前階段所作決策的可行性。5.2.1 動(dòng)態(tài)規(guī)劃的基本概念決策和決策變量:

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

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

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

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

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

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

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

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

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

=Tk

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

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

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

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

(E1

)

4 f5

(E2

)

3第二步，k＝4，狀態(tài)變量s5可取三個(gè)值D1，D2，D3，這是經(jīng)過一個(gè)中途點(diǎn)到達(dá)終點(diǎn)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時(shí),

f

(C

)

122 2 3u*(B)

Cf2

(B2

)

152u*(B)

C2 1k

2時(shí),

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時(shí),

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

n

1

n

1(s )

0

f

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

fk(sk

)

opt {vk(sk,

uk)

fk

1(sk

1

)}

uk

Dk(

sk)

k

n,

n

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

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

2，問應(yīng)如何分配投資數(shù)額才能使總收益最大?

x

0 (i

1,2,3)

i

x1

x2

x3

103maxz

4x1

9x2

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

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

：第k段可以投資于第k項(xiàng)到第3個(gè)項(xiàng)目的資金數(shù)。決策變量xk

：決定給第k個(gè)項(xiàng)目投資的資金數(shù)。狀態(tài)轉(zhuǎn)移方程：

sk+1＝

sk

-

xk

。指標(biāo)函數(shù)：Vk

,3

gi

(

xi

)i

k最優(yōu)指標(biāo)函數(shù)人fk(sk)：當(dāng)可投資金數(shù)為sk時(shí)，投資第k——3項(xiàng)所得的最大收益數(shù)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動(dòng)態(tài)規(guī)劃模型的建立收益船廠012345A035789B046899C0137910例6 船舶總公司擬將5萬元資金投放到下屬A、B、C三個(gè)船廠，各船廠在獲得資金后的收益如表5-1所示。試用動(dòng)態(tài)規(guī)劃方法求使總收益最大的投資分配方案。表5-15.3.1動(dòng)態(tài)規(guī)劃模型的建立解：階段k：k=1,2,3狀態(tài)變量sk

：第k段可以投資于第k項(xiàng)到第3個(gè)項(xiàng)目的資金數(shù)。

S1

{5}

{0

,1,

2

,

3,

4,

5} k

2,

3

S

k決策變量xk

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

{0,1,2,3,

4,

5} k

1,

2

,

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

1k

1,2,

3

sk

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

Dk(sk

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

k——3項(xiàng)所得的最大收益數(shù)–基本方程：

fk(sk

)

m

ax {gk(xk

)

f

k

1

(

s

k

1

)}4 4k

3,

2

,

1

f (

s )

0

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

(s3

)

max{g3

(x3

)

f4

(s4

)}K=3時(shí)：階段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萬元。由上述計(jì)算結(jié)果可知:最大收益是：

例4的順序解法：5.3.2.

逆序法與順序法

從k＝0開始，f0

(s1

)

f0

(

A)

0

k＝2時(shí)，f2

(s3

) 定義有：

f2

(C1

)

d

(B1

,

C1

)

f1

(B1

)

2

4

6

u (C)

B

2 1 1是邊界條件

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

逆序法與順序法

k

3,2,10

xk

sk例5

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

為第k段可以投資于第k項(xiàng)到第3個(gè)項(xiàng)目的資金數(shù)；決策變量xk

決定給第k個(gè)項(xiàng)目投資的資金數(shù)；狀態(tài)轉(zhuǎn)移方程：

sk+1

＝

sk

-

xk

；最優(yōu)指標(biāo)函數(shù)fk(sk)表示當(dāng)可投資金數(shù)為sk時(shí)，投資第k到第3項(xiàng)所得的最大收益數(shù)；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時(shí)，f (s

)

max

{2x2}k＝2時(shí)，

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 ]端點(diǎn)取得f (0)

2s2

,

f (s )

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

s

時(shí),

有最大值2s23 3 32 22 2 22 22 2 222當(dāng)s

9

時(shí),

f (0)

f (s ),

此時(shí)x*

02s

9

時(shí),

f (0)

f (s ),

此時(shí)x*

sk＝1時(shí)，f1(s1)

max{4

x1

f2

(

s2)} 當(dāng)f2

(

s2

)

9s2時(shí),但此時(shí)

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

)時(shí),2s2

9s

, 則s

92 2 2 2 2 22 2 2 11 1 10

x1

10當(dāng)f (s )

2s

2時(shí),

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是極小點(diǎn).1比較[0,10]兩個(gè)端點(diǎn),

x1

0時(shí),

f1

(10)

200x

10時(shí),

f

(10)

40

,

所以,

x*

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

s

s

x*

10

0

102 1 1因?yàn)閟

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階段劃分和決策變量設(shè)置同逆序法；

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

表示可用于第1個(gè)到第k個(gè)項(xiàng)目投資的資金數(shù):s4＝10，s3＝s4–x3，s2＝s3–x2，s1＝s2–x1

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

sk＝

sk+1

-

xk

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

遞推方程：

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當(dāng)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當(dāng)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當(dāng)k=3時(shí)93所以x*

103dx2則極大值在[0,

s4

]端點(diǎn)取得當(dāng)x3

0時(shí),

f3

(10)

90,當(dāng)x3

10時(shí)f3

(10)

200d2h

4

0 則x3

4

是極小點(diǎn)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同逆序法結(jié)果相同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)轉(zhuǎn)移方程 :

(i

1,2,...,

n)

xi

0n

i

1

xi

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

z

gi

(

xi

)i

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

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

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

，2

,…,m

}

，

的大小可依據(jù)問題所要求的精度以及計(jì)算機(jī)的容量來定。決策變量xk也在離散點(diǎn)0，

，2

， … ，m

上取值，相應(yīng)的指標(biāo)函數(shù)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六個(gè)點(diǎn)，即狀態(tài)變量sk集合為{0，2，4，6，8，10}；允許決策集合為0

xk

sk

，xk與sk均在分割點(diǎn)上取值。例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}。計(jì)算結(jié)果見表7—1。3 3 30

x3

s3當(dāng)k＝3時(shí)，

f (s

)

max

{2x2}

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

*30022x3

=0000228882443232324667272726881281281288101020020020010指標(biāo) 最優(yōu)指標(biāo)

最優(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指標(biāo)計(jì)算結(jié)果見表7

2最優(yōu)指標(biāo)

最優(yōu)決策k

2時(shí),

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指標(biāo)計(jì)算結(jié)果見表7

2最優(yōu)指標(biāo)

最優(yōu)決策k

2時(shí),

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)指標(biāo)

最優(yōu)決策x1

)} 計(jì)算結(jié)果見表7

3指標(biāo)k

1時(shí),

f1

(s1

)

max{4x1

f2

(s10

x1

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

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

max

z

ci

(xi

)i

1ns.t.i ia

x

a

i

1

i

x

0 且為整數(shù)(i

1,

2,...,

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

sk

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

ak

xk0 1k

1,2,...,

n

f (s)

0xk允許決策集合：Dk

(

sk

1

)

{xk

|

0,1,

2,...,[

sk

1

/

ak

]}–最優(yōu)指標(biāo)函數(shù)：

fk

(

sk

+1

)–基本方程：

fk

(

sk

1

)

max{ck

(

xk

)

f

k

1

(

sk

1

ak

xk

)}

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

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

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

:裝入第k件物品的件數(shù)。5.4動(dòng)態(tài)規(guī)劃模型的應(yīng)用狀態(tài)轉(zhuǎn)移方程：

sk

1

skak

xkn

1 n

1k

n,...,

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

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

/ak]}–最優(yōu)指標(biāo)函數(shù)：

fk

(

sk

)–基本方程：

fk

(

sk

)

max{ck

(

xk

)

f

k

1

(

sk

1

)}

f(

s )

0

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

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

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

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

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

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

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

:裝入第k件貨物的數(shù)量。5.4動(dòng)態(tài)規(guī)劃模型的應(yīng)用狀態(tài)轉(zhuǎn)移方程： sk

1

skwk

xk

指標(biāo)函數(shù)：階段指標(biāo)即為第k階段裝載xk件貨物時(shí)所創(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動(dòng)態(tài)規(guī)劃模型的應(yīng)用K=3時(shí)：s3s4=s3-4x3K=2時(shí)：K=1時(shí)：5.4.2

生產(chǎn)存貯問題（庫存問題）

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

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

k0

sk

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

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

:為第k階段生產(chǎn)的船數(shù)。sk

6

d

k s1

s5

0xk

sk

d

k

最大庫存量4xk

sk

dii

kxk

sk

d

kksk

6(k

1)

dii

15.4動(dòng)態(tài)規(guī)劃模型的應(yīng)用狀態(tài)轉(zhuǎn)移方程：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– 指標(biāo)函數(shù)vk

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

0.6

ckxk

0.4

sk 若xk

0vk(sk,xk)

k

1,2,3,

4k k

0.4

s 若x

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

設(shè)備更新問題

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

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

a

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

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

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

1ks

s

1 當(dāng)xk

K(keep

)

1 當(dāng)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動(dòng)態(tài)規(guī)劃模型的應(yīng)用–指標(biāo)函數(shù)為：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實(shí)際上：–最優(yōu)指標(biāo)函數(shù)為：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當(dāng)xk

Kkk kk

1

r (0)

u (0)

c (

s )

f

kk(1) 當(dāng)x

R

f(

s )

0

n

1 n

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

rk(t)54.543.7532.5運(yùn)行費(fèi)

uk(t)0.511.522.53更新費(fèi)

ck(t)0.51.52.22.533.55.4動(dòng)態(tài)規(guī)劃模型的應(yīng)用解：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)此時(shí)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