教案動態(tài)規(guī)劃

動態(tài)規(guī)劃（DynamicProgramming）

R.Bellman1957年發(fā)表“DynamicProgramming”一書，標(biāo)識動態(tài)規(guī)劃的正式誕生。

動態(tài)規(guī)劃的研究對象和引例動態(tài)規(guī)劃的理論基礎(chǔ)和具體迭代方法動態(tài)規(guī)劃的基本思想和基本方程動態(tài)規(guī)劃的基本概念和定義

動態(tài)規(guī)劃是解決多階段決策過程的基本方法之一。12345第一節(jié)動態(tài)規(guī)劃的研究對象和引例最短路問題A12345678E64587789338956562134動態(tài)決策問題的特點(diǎn)：在多階段決策過程中,系統(tǒng)的動態(tài)過程可以按照時間或空間進(jìn)程分為狀態(tài)相互聯(lián)系而又相互區(qū)別的各個階段每個階段都要進(jìn)行決策,目的是使整個過程的決策達(dá)到最優(yōu)效果。12n狀態(tài)決策狀態(tài)決策狀態(tài)狀態(tài)決策但要便于把問題的過程能轉(zhuǎn)化為多階段決策的過程。狀態(tài)變量的取值有一定的允許集合或范圍，此集合稱為狀態(tài)允許集合。第二節(jié)動態(tài)規(guī)劃的基本概念和定義

1.

階段（stage）把所給問題的過程，適當(dāng)?shù)胤譃槿舾蓚€相互聯(lián)系的階段;描述階段的變量稱為階段變量，常用k表示；階段的劃分，一般是按時間和空間的自然特征來劃分；2.狀態(tài)（state）每個階段開始所處的自然狀態(tài)或客觀條件。通常一個階段有若干個狀態(tài)。描述過程狀態(tài)的變量稱為狀態(tài)變量，常用sk表示第k階段的狀態(tài)。在實(shí)際問題中決策變量的取值往往在某一范圍之內(nèi)，此范圍稱為允許決策集合。常用Dk(sk)表示第k階段從狀態(tài)sk出發(fā)的允許決策集合，顯然有一個數(shù)一組數(shù)一個向量決定下一階段的狀態(tài)，這種決定稱為決策。在最優(yōu)控制中也稱為控制。描述決策的變量，稱為決策變量。決策變量是狀態(tài)變量的函數(shù)。常用uk(sk)表示第k階段當(dāng)狀態(tài)為sk時的決策變量。3.決策和策略（DecisionandPolicy)過程的某一階段、某個狀態(tài),可以做出不同的決定(選擇),uk(sk)

Dk(sk)

由每段的決策按順序排列組成的決策函數(shù)序列稱為k子過程策略，

當(dāng)k=1時，此決策函數(shù)序列成為全過程的一個策略，簡稱策略，記為p1,n

(s1).即

可供選擇的策略有一定范圍，此范圍稱為允許策略集合，用p表示。從允許策略集合中找出達(dá)到最優(yōu)效果的策略稱為最優(yōu)策略。

策略:按順序排列的決策組成的集合；

由第k

n(終止?fàn)顟B(tài))為止的過程，稱為問題的后部子過程（k子過程）。簡稱子策略，記為pk,n(sk)，即系統(tǒng)在某一階段的狀態(tài)轉(zhuǎn)移不但與系統(tǒng)的當(dāng)前的狀態(tài)和決策有關(guān)，而且還與系統(tǒng)過去的歷史狀態(tài)和決策有關(guān)。其狀態(tài)轉(zhuǎn)移方程如下（一般形式）狀態(tài)轉(zhuǎn)移方程是確定過程由一個狀態(tài)到另一個狀態(tài)的演變過程。如果第k階段狀態(tài)變量sk的值、該階段的決策變量一經(jīng)確定，第k+1階段狀態(tài)變量sk+1的值也就確定。4.狀態(tài)轉(zhuǎn)移方程可以在各個階段進(jìn)行決策，去控制過程發(fā)展的多段過程；其發(fā)展是通過一系列的狀態(tài)轉(zhuǎn)移來實(shí)現(xiàn)的；12ks1u1s2u2s3skukSk+1能用動態(tài)規(guī)劃方法求解的多階段決策過程是一類特殊的多階段決策過程，即具有無后效性的多階段決策過程。圖示如下：它是定義在全過程或所有后部子過程上確定的數(shù)量函數(shù)。動態(tài)規(guī)劃模型的指標(biāo)函數(shù)，應(yīng)具有可分離性，并滿足遞推關(guān)系。費(fèi)用、成本、利潤、路長等。用Vk,n

表示之。5.指標(biāo)函數(shù)和最優(yōu)值函數(shù)用來衡量所實(shí)現(xiàn)過程優(yōu)劣的一種數(shù)量指標(biāo)，稱為指標(biāo)函數(shù)；

第k階段第n階段狀態(tài)sk

終止?fàn)顟B(tài)采取最優(yōu)策略所得到的指標(biāo)函數(shù)值。最優(yōu)值函數(shù)：即12345A12345678E64587789338956562134第三節(jié)：動態(tài)規(guī)劃的基本思想和基本方程

最短路的特性（最優(yōu)化原理）：如果已有從起點(diǎn)到終點(diǎn)的一條最短路，那么從最短路線上中間任何一點(diǎn)出發(fā)到終點(diǎn)的路線仍然是最短路。（證明用反證法）第一步：從k=4開始，狀態(tài)變量可取兩種狀態(tài)⑦、⑧，它們到E點(diǎn)的路長分別為4，3。即：

第二步：k=3，狀態(tài)變量可取三個值④、⑤、⑥，這是經(jīng)過一個中途點(diǎn)到達(dá)終點(diǎn)E的兩級決策問題，從城市④到E有兩條路線，需加以比較，取其中最短的，即：

這說明由城市④到終點(diǎn)E最短距離為7，其路徑為④→⑦→E。相應(yīng)決策為：

即城市⑤到終點(diǎn)最短距離為5，其路徑為⑤→⑧→E。相應(yīng)決策為

即城市⑥到終點(diǎn)最短距離為5，其路徑⑥→⑦→E。相應(yīng)決策為第三步：k=2,這是具有三個初始狀態(tài)①、②、③，要經(jīng)過兩個中途站才能到達(dá)終點(diǎn)的三級決策問題。由于第3段各點(diǎn)④，⑤，⑥到終點(diǎn)E的最短距離已知，所以我們?nèi)羟蟪鞘孝俚紼的最短距離，只需以它們?yōu)榛A(chǔ)，分別加上城市①與④、⑤、⑥的一段距離，加以比較取其短者即可。

即城市①到終點(diǎn)最短距離為9，其路徑為①→⑤→⑧→E。本段相應(yīng)決策為同理有：第四步k=1,只要一個狀態(tài)A，則：即從城市A到城市E的距離為17。本段決策為:

再按計算順序反推可得最優(yōu)決策序列{}即：

所以最優(yōu)路線為：

A→城市①→城市⑤→城市⑧→E

用動態(tài)規(guī)劃（逆序法求解的）基本特性：求解時從邊界條件開始，逆（或順）過程行進(jìn)方向，逐段遞推尋優(yōu)。在每個問題求解時，都要使用它前面已求出的子問題的最優(yōu)結(jié)果，最后問題的最優(yōu)解，就是整個問題的最優(yōu)解。

將多階段決策過程劃分階段，恰當(dāng)?shù)剡x取狀態(tài)變量、決策變量、及定義最優(yōu)指標(biāo)函數(shù)，正確寫出基本的遞推關(guān)系式和恰當(dāng)?shù)倪吔鐥l件（簡言之為基本方程）。從而把問題化成一族同類的子問題；求解的各個階段,我們利用了k階段與k+1階段之間的遞推關(guān)系:在求整個問題的最優(yōu)策略時，由于初始狀態(tài)是已知的，每段的決策是該段狀態(tài)的函數(shù)，故沿最優(yōu)化策略所經(jīng)過的各段狀態(tài)便可確定了最優(yōu)路線。fk(sk)=opt｛vk(sk,uk(sk))+fk+1(uk(sk))｝ukDk(sk)fn+1(sn+1)=0k=n,..,2,1將問題按時空特性恰當(dāng)?shù)貏澐譃槿舾蓚€階段

選擇狀態(tài)變量sk,既能描述過程的變化又滿足無后效性；確定決策變量uk及每一階段的允許決策集合Dk(sk)；正確寫出狀態(tài)轉(zhuǎn)移方程；正確地定義各階段的直接指標(biāo)函數(shù)和后部子過程的最優(yōu)指標(biāo)函數(shù)，并寫出其基本方程：動態(tài)規(guī)劃模型及其求解五要素：問如何分配投資數(shù)額才能使總效益最大?解：可列出靜態(tài)規(guī)劃問題的模型如下分階段：分三個階段，即k=1，2，3。

確定決策變量：通?？梢匀§o態(tài)規(guī)劃中的變量為決策變量。確定狀態(tài)變量：狀態(tài)變量與決策變量有密切關(guān)系，狀態(tài)變量一般為累計量或隨遞推過程變化的量。例

某公司有資金10萬元，若投資于項(xiàng)目(i=1,2,3)的投資額為xi時，其效益分別為狀態(tài)轉(zhuǎn)移方程

指標(biāo)函數(shù)

最優(yōu)指標(biāo)函數(shù)fk(sk)

基本方程最優(yōu)目標(biāo)函數(shù)f3(s3)=2s32

此問題中可設(shè)（因此可得狀態(tài)轉(zhuǎn)移方程）：當(dāng)階段k=3時，有f3(s3)=max｛2x32｝

0≤

x3≤s3最優(yōu)決策為x3*=s3當(dāng)階段k=2時，有是凹函數(shù)，最大值點(diǎn)只能在[0，s2]端點(diǎn)上取得，即當(dāng)當(dāng)當(dāng)時，時，時，此時此時當(dāng)階段k=1時，有是凹函數(shù)，故比較[0,10]的端點(diǎn)因?yàn)椤嘧顑?yōu)投資方案是全部資金投于第3個項(xiàng)目，可得最大收益200萬元。S2>9/2當(dāng)當(dāng)時時矛盾，舍去。（最優(yōu)決策）S2<9/22階導(dǎo)數(shù)>0動態(tài)規(guī)劃的優(yōu)