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

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

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

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

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

1.

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

Dk(sk)

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

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

(s1).即

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

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

由第k

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

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

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

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

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

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

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

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

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

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

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

將多階段決策過程劃分階段，恰當(dāng)?shù)剡x取狀態(tài)變量、決策變量、及定義最優(yōu)指標(biāo)函數(shù)，正確寫出基本的遞推關(guān)系式和恰當(dāng)?shù)倪吔鐥l件（簡(jiǎn)言之為基本方程）。從而把問題化成一族同類的子問題；求解的各個(gè)階段,我們利用了k階段與k+1階段之間的遞推關(guān)系:在求整個(gè)問題的最優(yōu)策略時(shí)，由于初始狀態(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將問題按時(shí)空特性恰當(dāng)?shù)貏澐譃槿舾蓚€(gè)階段

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

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

某公司有資金10萬元，若投資于項(xiàng)目(i=1,2,3)的投資額為xi時(shí)，其效益分別為狀態(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時(shí)，有f3(s3)=max｛2x32｝

0≤

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