1最優(yōu)化原理（貝爾曼最優(yōu)化原理）作為一個(gè)全過程的最優(yōu)策略具有這樣的性質(zhì)：對(duì)于最優(yōu)策略過程中的任意狀態(tài)而言，無論其過去的狀態(tài)和決策如何，余下的諸決策必構(gòu)成一個(gè)最優(yōu)子策略。該原理的具體解釋是，若某一全過程最優(yōu)策略為：

動(dòng)態(tài)規(guī)劃的基本原理

則對(duì)上述策略中所隱含的任一狀態(tài)而言，第k子過程上對(duì)應(yīng)于該狀態(tài)的最優(yōu)策略必然包含在上述全過程最優(yōu)策略p1*中，即為23.動(dòng)態(tài)規(guī)劃方法的基本步驟

1．應(yīng)將實(shí)際問題恰當(dāng)?shù)胤指畛蒼個(gè)子問題(n個(gè)階段)。通常是根據(jù)時(shí)間或空間而劃分的，或者在經(jīng)由靜態(tài)的數(shù)學(xué)規(guī)劃模型轉(zhuǎn)換為動(dòng)態(tài)規(guī)劃模型時(shí)，常取靜態(tài)規(guī)劃中變量的個(gè)數(shù)n，即k=n。

2．正確地定義狀態(tài)變量sk，使它既能正確地描述過程的狀態(tài)，又能滿足無后效性．動(dòng)態(tài)規(guī)劃中的狀態(tài)與一般控制系統(tǒng)中和通常所說的狀態(tài)的概念是有所不同的，動(dòng)態(tài)規(guī)劃中的狀態(tài)變量必須具備以下三個(gè)特征：33.動(dòng)態(tài)規(guī)劃方法的基本步驟

(1)要能夠正確地描述受控過程的變化特征。

(2)要滿足無后效性。即如果在某個(gè)階段狀態(tài)已經(jīng)給定，那么在該階段以后，過程的發(fā)展不受前面各段狀態(tài)的影響。

(3)要滿足可知性。即所規(guī)定的各段狀態(tài)變量的值，可以直接或間接地測(cè)算得到。在與靜態(tài)規(guī)劃模型的對(duì)應(yīng)關(guān)系上，通常根據(jù)經(jīng)驗(yàn)，線性與非線性規(guī)劃中約束條件的個(gè)數(shù)，相當(dāng)于動(dòng)態(tài)規(guī)劃中狀態(tài)變量sk的維數(shù)．而前者約束條件所表示的內(nèi)容，常就是狀態(tài)變量sk所代表的內(nèi)容。43.動(dòng)態(tài)規(guī)劃方法的基本步驟

3．正確地定義決策變量及各階段的允許決策集合Uk(sk)，根據(jù)經(jīng)驗(yàn)，一般將問題中待求的量，選作動(dòng)態(tài)規(guī)劃模型中的決策變量?；蛘咴诎鸯o態(tài)規(guī)劃模型(如線性與非線性規(guī)劃)轉(zhuǎn)換為動(dòng)態(tài)規(guī)劃模型時(shí)，常取前者的變量xj為后者的決策變量uk。

4.能夠正確地寫出狀態(tài)轉(zhuǎn)移方程，至少要能正確反映狀態(tài)轉(zhuǎn)移規(guī)律。如果給定第k階段狀態(tài)變量sk的值，則該段的決策變量uk一經(jīng)確定，第k+1段的狀態(tài)變量sk+1的值也就完全確定，即有sk+1=Tk(sk,uk)53.動(dòng)態(tài)規(guī)劃方法的基本步驟

5．根據(jù)題意,正確地構(gòu)造出目標(biāo)與變量的函數(shù)關(guān)系——目標(biāo)函數(shù)，目標(biāo)函數(shù)應(yīng)滿足下列性質(zhì)：

(1)可分性，即對(duì)于所有k后部子過程，其目標(biāo)函數(shù)僅取決于狀態(tài)sk及其以后的決策uk,uk+1,┈,un,就是說它是定義在全過程和所有后部子過程上的數(shù)量函數(shù)。

(2)要滿足遞推關(guān)系，即

(3)函數(shù)對(duì)其變?cè)猂k+1來說要嚴(yán)格單調(diào)。66．寫出動(dòng)態(tài)規(guī)劃函數(shù)基本方程例如常見的指標(biāo)函數(shù)是取各段指標(biāo)和的形式

其中表示第i階段的指標(biāo)，它顯然是滿足上述三個(gè)性質(zhì)的。所以上式可以寫成：3.動(dòng)態(tài)規(guī)劃方法的基本步驟71.動(dòng)態(tài)規(guī)劃的四大要素①狀態(tài)變量及其可能集合xk

Xk②

決策變量及其允許集合uk

Uk

③

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

xk+1=Tk

(xk,uk

)④

階段效應(yīng)rk

(xk,uk

)

4.動(dòng)態(tài)規(guī)劃方法應(yīng)用舉例82.動(dòng)態(tài)規(guī)劃基本方程

fn+1(xn+1)=0(邊界條件)

fk(xk)=opt

u{rk

(xk,uk

)+fk+1(xk+1)}

k=n,…,14.動(dòng)態(tài)規(guī)劃方法應(yīng)用舉例9求最短路徑

10

求最短路徑

例5.511

將問題分成五個(gè)階段，第k階段到達(dá)的具體地點(diǎn)用狀態(tài)變量xk表示，例如：x2=B3表示第二階段到達(dá)位置B3，等等。這里狀態(tài)變量取字符值而不是數(shù)值。

將決策定義為到達(dá)下一站所選擇的路徑，例如目前的狀態(tài)是x2=B3，這時(shí)決策允許集合包含三個(gè)決策，它們是D2(x2)=D2(B3)={B3

C1,B3

C2,B3

C3}求最短路徑

12最優(yōu)指標(biāo)函數(shù)fk(xk)表示從目前狀態(tài)到E的最短路徑。終端條件為

f5(x5)=f5(E)=0

其含義是從E到E的最短路徑為0。

第四階段的遞推方程為

:

求最短路徑

13其中*表示最優(yōu)值，在上表中，由于決策允許集合D4(x4)中的決策是唯一的，因此這個(gè)值就是最優(yōu)值。

由此得到f4(x4)的表達(dá)式。由于這是一個(gè)離散的函數(shù)，取值用列表表示：求最短路徑

14第三階段的遞推方程為：

求最短路徑

15由此得到f3(x3)的表達(dá)式：

求最短路徑

16求最短路徑

17由此得到f2(x2)的表達(dá)式：求最短路徑

18第一階段的遞推方程為：求最短路徑

19由此得到f1(x1)的表達(dá)式求最短路徑

例：某公司從甲地向丁地運(yùn)送物資，運(yùn)送過程中先后需要經(jīng)過乙、丙兩個(gè)中轉(zhuǎn)站，其中乙中轉(zhuǎn)站可以選擇乙1和乙2兩個(gè)可選地點(diǎn)，丙中轉(zhuǎn)站可以選擇丙1、丙2和丙3三個(gè)可選地點(diǎn)，各相鄰兩地之間的距離如表所示，則甲地到丁地之間的最短距離為：A、64 B、74 C、76 D、68

【答案】：B地點(diǎn)-距離-地點(diǎn)乙1乙2丙1丙2丙3丁甲2630乙1182832乙2303226丙130丙228丙32221資源分配問題22

例5.6:有資金4萬元，投資A、B、C三個(gè)項(xiàng)目，每個(gè)項(xiàng)目的投資效益與投入該項(xiàng)目的資金有關(guān)。三個(gè)項(xiàng)目A、B、C的投資效益（萬噸）和投入資金（萬元）關(guān)系見下表：求對(duì)三個(gè)項(xiàng)目的最優(yōu)投資分配，使總投資效益最大。資源分配問題23階段k：每投資一個(gè)項(xiàng)目作為一個(gè)階段；狀態(tài)變量xk：投資第k個(gè)項(xiàng)目前的資金數(shù)；決策變量dk：第k個(gè)項(xiàng)目的投資；決策允許集合：0≤dk≤xk狀態(tài)轉(zhuǎn)移方程：xk+1=xk-dk階段指標(biāo)：vk(xk,dk)見表中所示；遞推方程：fk(xk)=max{vk(xk,dk)+fk+1(xk+1)}終端條件：f4(x4)=0資源分配問題24k=4，f4(x4)=0

k=3，0≤d3≤x3，x4=x3-d3

資源分配問題25k=2，0≤d2≤x2，x3=x2-d2資源分配問題26k=1，0≤d1≤x1，x2=x1-d1資源分配問題27背包問題28背包問題29則Max

z= c1x1+c2x2+…+cnxn

s.t.w1x1+w2x2+…+wnxn≤W

x1,x2,…,xn為正整數(shù) 階段k：第k次裝載第k種物品（k=1,2,…,n）狀態(tài)變量xk：第k次裝載時(shí)背包還可以裝載的重量；決策變量dk：第k次裝載第k種物品的件數(shù)；背包問題304.決策允許集合： Dk(xk)={dk|0

dk

xk/wk，dk為整數(shù)}；5.狀態(tài)轉(zhuǎn)移方程：xk+1=xk-wkdk6.階段指標(biāo)：vk=ckdk7.遞推方程

fk(xk)=max{ckdk+fk+1(xk+1)}=max{ckdk+fk+1(xk-wkdk)}8.終端條件：fn+1(xn+1)=0背包問題31

例5.7:對(duì)于一個(gè)具體問題c1=65，c2=80，c3=30；w1=2，w2=3，w3=1；以及 W=5

用動(dòng)態(tài)規(guī)劃求解f4(x4)=0

對(duì)于k=3背包問題32對(duì)于k=3列出f3(x3)的數(shù)值表如下： 33對(duì)于k=2列出f2(x2)的數(shù)值表34對(duì)于k=1列出f1(x1)的數(shù)值表3536

機(jī)器負(fù)荷分配問題3738

構(gòu)造動(dòng)態(tài)規(guī)劃模型如下：

階段k：運(yùn)行年份（k=1,2,3,4,5,6），其中k=1表示第一年初，…，依次類推；k=6表示第五年末（即第六年初）。

狀態(tài)變量xk：第k年初完好的機(jī)器數(shù)（k=1,2,3,4,5,6），其中x6表示第五年末（即第六年初）的完好機(jī)器數(shù)。

決策變量dk：第k年投入高負(fù)荷運(yùn)行的機(jī)器數(shù)；

狀態(tài)轉(zhuǎn)移方程：xk+1=0.7dk+0.9(xk-dk)

決策允許集合：Dk(xk)={dk|0

dk

xk}

階段指標(biāo)：vk(xk,dk)=8dk+5(xk-dk)

終端條件：f6(x6)=0

機(jī)器負(fù)荷分配問題39遞推方程：fk(xk)=max{vk(xk,dk)+fk+1(xk+1)}

dk

Dk(xk)

=max{8dk+5(xk-dk)+fk+1[0.7dk+0.9(xk-dk)]}

0

dk

xk

機(jī)器負(fù)荷分配問題40f5(x5)=max{8d5+5(x5-d5)+f6(x6)}

0

d5

x5

=max{3d5+5x5}=8x5, d5*=x5

0

d5

x5

f4(x4)=max{8d4+5(x4-d4)+f5(x5)}

0

d4

x4

=max{8d4+5(x4-d4)+8x5}

0

d4

x4

=max{8d4+5(x4-d4)+8[0.7d4+0.9(x4-d4)]}

0

d4

x4

=max{1.4d4+12.3x4}=13.7x4, d4*=x4

0

d4

x4

機(jī)器負(fù)荷分配問題41f3(x3)=max{8d3+5(x3-d3)+f4(x4)}

0

d3

x3

=max{8d3+5(x3-d3)+13.7x4}

0

d3

x3

=max{8d3+5(x3-d3)+13.7[0.7d3+0.9(x3-d3)]}

0

d3

x3

=max{0.28d3+17.24x3}=17.52x3, d3*=x3

0

d3

x3

機(jī)器負(fù)荷分配問題42f2(x2)=max{8d2+5(x2-d2)+f3(x3)}

0

d2

x2

=max{8d2+5(x2-d2)+17.52x3}

0

d2

x2

=max{8d2+5(x2-d2)+17.52[0.7d2+0.9(x2-d2)]}

0

d2

x2

=max{-0.504d2+20.77x2}=20.77x2,d2*=0

0

d2

x2

機(jī)器負(fù)荷分配問題43f1(x1)=max{8d1+5(x1-d1)+f2(x2)}

0

d1

x1

=max{8d1+5(x1-d1)+20.77x2}

0

d1

x1

=max{8d1+5(x1-d1)+20.77[0.7d1+0.9(x1-d1)]}

0

d1

x1

=max{-0.05d1+23.69x1}=23.69x1,d1*=0

0

d1

x1

機(jī)器負(fù)荷分配問題44由此可以得到：f1(x1)=23.69x1, d1*=0f2(x2)=20.77x2, d2*=0f3(x3)=17.52x3, d3*=x3f4(x4)=13.60x4, d4*=x4f5(x5)=8x5

d5*=x5用x1=1000代入，得到五年最大產(chǎn)量為f1(x1)=f1(1000)=23690

機(jī)器負(fù)荷分配問題45每年投入高負(fù)荷運(yùn)行的機(jī)器數(shù)以每年初完好的機(jī)器數(shù)為：x1=1000d1*=0,x2=0.7d1+0.9(x1-d1)=900d2*=0,x3=0.7d2+0.9(x2-d2)=810d3*=x3=810,x4=0.7d3+0.9(x3-d3)=567d4*=x4=567,x5=0.7d4+0.9(x4-d4)=397d5*=x5=397,x6=0.7d5+0.9(x5-d5)=278

機(jī)器負(fù)荷分配問題46

在這個(gè)例子中，狀態(tài)變量的終端值x6是未加約束的，如果要求在第五年末（即第六年初）完好的機(jī)器數(shù)不