運(yùn)籌學(xué)-CH5動(dòng)態(tài)規(guī)劃課件

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

(Dynamicprogramming)多階段決策問(wèn)題動(dòng)態(tài)規(guī)劃的基本概念最優(yōu)性原理建模的一般步驟動(dòng)態(tài)規(guī)劃應(yīng)用例解本章主要內(nèi)容：教學(xué)目的與要求【教學(xué)目的與要求】了解動(dòng)態(tài)規(guī)劃的基本思想、基本概念和基本方程，熟悉動(dòng)態(tài)規(guī)劃的最優(yōu)性原理和建模的一般步驟；【教學(xué)重難點(diǎn)】重點(diǎn)是動(dòng)態(tài)規(guī)劃的基本思想方法，難點(diǎn)是基本方程。2511214106104131112396581052C1C3D1AB1B3B2D2EC2例5.1試求下圖中從A地到E地的最短路徑：引例從A到E的最短路徑為19，路線為A→B2→C1→D1→E

多階段決策問(wèn)題動(dòng)態(tài)規(guī)劃（簡(jiǎn)稱：DP）

是解決多階段決策過(guò)程最優(yōu)化問(wèn)題的一種方法，無(wú)特定的數(shù)學(xué)模型。

動(dòng)態(tài)規(guī)劃是求解某類問(wèn)題的一種方法，是考察問(wèn)題的一種途徑，而不是一種算法。必須對(duì)具體問(wèn)題進(jìn)行具體分析，運(yùn)用動(dòng)態(tài)規(guī)劃的原理和方法，建立相應(yīng)的模型，然后再用動(dòng)態(tài)規(guī)劃方法去求解。

動(dòng)態(tài)規(guī)劃是現(xiàn)代企業(yè)管理中的一種重要決策方法，可用于最優(yōu)路徑問(wèn)題、資源分配問(wèn)題、生產(chǎn)計(jì)劃和庫(kù)存問(wèn)題、投資問(wèn)題、裝載問(wèn)題、排序問(wèn)題及生產(chǎn)過(guò)程的最優(yōu)控制等。多階段決策問(wèn)題多階段決策過(guò)程：

是指在一類特殊的活動(dòng)過(guò)程，可將過(guò)程分解成若干相互聯(lián)系的階段，在每個(gè)階段都要做出決策，從而使整個(gè)過(guò)程達(dá)到最優(yōu)的效果，全部過(guò)程的決策是一個(gè)決策序列，所以多階段決策問(wèn)題也稱為序貫決策問(wèn)題。

每個(gè)階段的決策依賴于該階段的狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移，一個(gè)決策序列就是在變化的狀態(tài)中產(chǎn)生出來(lái)的，故有“動(dòng)態(tài)”的含義。處理多階段決策問(wèn)題的方法稱為動(dòng)態(tài)規(guī)劃方法。動(dòng)態(tài)規(guī)劃問(wèn)題

動(dòng)態(tài)規(guī)劃(dynamicprogramming)是運(yùn)籌學(xué)的一個(gè)分支，是求解決策過(guò)程(decisionprocess)最優(yōu)化的數(shù)學(xué)方法。20世紀(jì)50年代初美國(guó)數(shù)學(xué)家R.E.Bellman等人在研究多階段決策過(guò)程(multistepdecisionprocess)的優(yōu)化問(wèn)題時(shí)，提出了著名的最優(yōu)化原理(principleofoptimality)，把多階段過(guò)程轉(zhuǎn)化為一系列單階段問(wèn)題，逐個(gè)求解，創(chuàng)立了解決這類過(guò)程優(yōu)化問(wèn)題的新方法——?jiǎng)討B(tài)規(guī)劃。多階段決策問(wèn)題的典型例子：

1.生產(chǎn)決策問(wèn)題：企業(yè)在生產(chǎn)過(guò)程中，由于需求是隨時(shí)間變化的，因此企業(yè)為了獲得全年的最佳生產(chǎn)效益，就要在整個(gè)生產(chǎn)過(guò)程中逐月或逐季度地根據(jù)庫(kù)存和需求決定生產(chǎn)計(jì)劃。

2.機(jī)器負(fù)荷分配問(wèn)題：某種機(jī)器可以在高低兩種不同的負(fù)荷下進(jìn)行生產(chǎn)。在高負(fù)荷下進(jìn)行生產(chǎn)時(shí)，產(chǎn)品的年產(chǎn)量g和投入生產(chǎn)的機(jī)器數(shù)量u1的關(guān)系為g=g(u1)12n狀態(tài)決策狀態(tài)決策狀態(tài)狀態(tài)決策多階段決策問(wèn)題

3.航天飛機(jī)飛行控制問(wèn)題：由于航天飛機(jī)的運(yùn)動(dòng)的環(huán)境是不斷變化的，因此就要根據(jù)航天飛機(jī)飛行在不同環(huán)境中的情況，不斷地決定航天飛機(jī)的飛行方向和速度（狀態(tài)），使之能最省燃料和實(shí)現(xiàn)目的（如軟著落問(wèn)題）。

4.不包含時(shí)間因素的線性規(guī)劃、非線性規(guī)劃等靜態(tài)決策問(wèn)題（本質(zhì)上是一次決策問(wèn)題）也可以適當(dāng)?shù)匾腚A段的概念，作為多階段的決策問(wèn)題用動(dòng)態(tài)規(guī)劃方法來(lái)解決。多階段決策問(wèn)題

5.最短路問(wèn)題：給定一個(gè)交通網(wǎng)絡(luò)圖如下，其中兩點(diǎn)之間的數(shù)字表示距離（或花費(fèi)），試求從A點(diǎn)到E點(diǎn)的最短距離（總費(fèi)用最小）。多階段決策問(wèn)題2511214106104131112396581052C1C3D1AB1B3B2D2EC2k=1k=2k=3k=4基本概念1、階段：

把一個(gè)問(wèn)題的過(guò)程，恰當(dāng)?shù)胤譃槿舾蓚€(gè)相互聯(lián)系的階段，以便于按一定的次序去求解。

描述階段的變量稱為階段變量（k)。k=1,2,3,…，n階段的劃分，一般是根據(jù)時(shí)間和空間的自然特征來(lái)進(jìn)行的，但要便于問(wèn)題轉(zhuǎn)化為多階段決策。2511214106104131112396581052C1C3D1AB1B3B2D2EC2k=1k=2k=3k=4基本概念2、狀態(tài)：表示每個(gè)階段開始所處的自然狀況或客觀條件。通常一個(gè)階段有若干個(gè)狀態(tài)，描述過(guò)程狀態(tài)的變量稱為狀態(tài)變量sk

(表示第k階段的狀態(tài)變量)，可以是一個(gè)數(shù)或數(shù)組。狀態(tài)變量的取值有一定的允許集合或范圍，此集合稱為可達(dá)狀態(tài)集合SK

。2511214106104131112396581052C1C3D1AB1B3B2D2EC2k=1k=2k=3k=4S1={A}S2={B1,B2,B3}S3={C1,C2,C3}S4={D1,D2}狀態(tài)應(yīng)滿足：（1）能描述問(wèn)題的變化過(guò)程。（2）具有無(wú)后效性：當(dāng)某階段狀態(tài)給定后，在這階段以后過(guò)程的發(fā)展不受這階段以前各狀態(tài)的影響。（3）能直接或間接地計(jì)算出來(lái)?；靖拍?/p>

3、決策：表示當(dāng)過(guò)程處于某一階段的某個(gè)狀態(tài)時(shí)，可以作出不同的決定，從而確定下一階段的狀態(tài)，這種決定稱為決策。

描述決策的變量，稱為決策變量。常用uk（sk）表示第k階段當(dāng)狀態(tài)為sk時(shí)的決策變量。

基本概念2511214106104131112396581052C1C3D1AB1B3B2D2EC2k=1k=2k=3k=4若s2=B2下段選C1,則u2(s2)=u2(B2)

=C1

基本概念在實(shí)際問(wèn)題中決策變量的取值往往在某一范圍之內(nèi)，此范圍稱為允許決策集合。

常用Dk（sk）表示第k階段從狀態(tài)sk出發(fā)的允許決策集合，顯然uk（sk）∈Dk（sk）。2511214106104131112396581052C1C3D1AB1B3B2D2EC2k=1k=2k=3k=4D2(s2)=D2(B2)={C1,C2,C3}u2(s2)∈D2（s2）u2(B2)∈D2（B2）

4、策略：相互連接的決策序列稱為一個(gè)策略。

從第k階段開始到第n階段結(jié)束稱為一個(gè)子策略

Pk，n=｛uk

,uk+1,…,un

｝

全策略

P1，n=｛u1,u2,…,un

｝

所有策略當(dāng)中有最優(yōu)值的策略稱為最優(yōu)策略pk,n*(p1,n*)?；靖拍罨靖拍?、狀態(tài)轉(zhuǎn)移方程：是確定過(guò)程由一個(gè)狀態(tài)到另一個(gè)狀態(tài)的演變過(guò)程，描述了狀態(tài)轉(zhuǎn)移規(guī)律。由sk轉(zhuǎn)變?yōu)閟k+1的狀態(tài)轉(zhuǎn)移方程：

sk+1=T(sk,uk)2511214106104131112396581052C1C3D1AB1B3B2D2EC2k=1k=2k=3k=4若s2=B2下段選C1,則s3=u2(s2)

=u2(B2)=C1

sk+1=uk(sk)

6、指標(biāo)函數(shù)和最優(yōu)值函數(shù)：用來(lái)衡量所實(shí)現(xiàn)過(guò)程優(yōu)劣的一種數(shù)量指標(biāo)，為指標(biāo)函數(shù)。階段指標(biāo)函數(shù)：Vk(sk,uk)

表示第

k

階段位于sk

狀態(tài)、決策為

uk

的指標(biāo)值。

策略指標(biāo)函數(shù)：各決策序列指標(biāo)值之和。（個(gè)別情況為乘積）基本概念V2(s2,u2)=V2(B2,u2)=d2(B2,C1)=62511214106104131112396581052C1C3D1AB1B3B2D2EC2k=1k=2k=3k=4基本概念指標(biāo)函數(shù)的最優(yōu)值，稱為最優(yōu)值函數(shù)。

在不同的問(wèn)題中，指標(biāo)函數(shù)的含義是不同的，它可能是距離、利潤(rùn)、成本、產(chǎn)量或資源消耗等。動(dòng)態(tài)規(guī)劃模型的指標(biāo)函數(shù)，應(yīng)具有可分離性，并滿足遞推關(guān)系。Vk,n(sk,pk,n):狀態(tài)為sk，采用策略pk,n時(shí)后部子策略的指標(biāo)函數(shù)。fk(sk)=optvk,n(sk,pk,n)：從第k段狀態(tài)，采用最優(yōu)策略pk,n*到過(guò)程終止時(shí)的最優(yōu)值函數(shù)。（opt:optimum—最優(yōu)化）所要求的是：

最優(yōu)解—最優(yōu)策略p1,n*

最優(yōu)值—最優(yōu)指標(biāo)f1(s1)基本概念基本思想1、動(dòng)態(tài)規(guī)劃思想是將問(wèn)題的過(guò)程分成幾個(gè)相互聯(lián)系的階段，恰當(dāng)?shù)倪x取狀態(tài)變量和決策變量及定義最優(yōu)值函數(shù)，從而把一個(gè)大問(wèn)題轉(zhuǎn)化成一組同類型的子問(wèn)題，然后逐個(gè)求解。從邊界條件開始，逐段遞推尋優(yōu)，在每一個(gè)子問(wèn)題的求解中，均利用了它前面的子問(wèn)題的最優(yōu)化結(jié)果，依次進(jìn)行，最后一個(gè)子問(wèn)題所得的最優(yōu)解，就是整個(gè)問(wèn)題的最優(yōu)解。因此，動(dòng)態(tài)規(guī)劃方法的關(guān)鍵在于正確地寫出基本的遞推關(guān)系式和恰當(dāng)?shù)倪吔鐥l件（簡(jiǎn)稱基本方程）。2、動(dòng)態(tài)規(guī)劃方法是既把當(dāng)前一段和未來(lái)一段分開，又把當(dāng)前效益和未來(lái)效益結(jié)合起來(lái)考慮的一種最優(yōu)化方法。因此，每段決策的選取是從全局來(lái)考慮的，與該段的最優(yōu)選擇答案一般是不同的.基本思想3、在求整個(gè)問(wèn)題的最優(yōu)策略時(shí)，由于初始狀態(tài)是已知的，而每段的決策都是該段狀態(tài)的函數(shù)，故最優(yōu)策略所經(jīng)過(guò)的各段狀態(tài)便可逐段變換得到，從而確定了最優(yōu)解。最優(yōu)化原理：作為整個(gè)過(guò)程的最優(yōu)策略具有這樣的性質(zhì)：無(wú)論過(guò)去的狀態(tài)和決策如何，相對(duì)于前面的決策所形成的狀態(tài)而言，余下的決策序列必然構(gòu)成最優(yōu)子策略?！币簿褪钦f(shuō)，一個(gè)最優(yōu)策略的子策略也是最優(yōu)的。最優(yōu)化原理2511214106104131112396581052C1C3D1AB1B3B2D2EC2k=1k=2k=3k=41.指標(biāo)函數(shù)為階段指標(biāo)和的形式

fk(sk)=opt{vk(sk,uk)+fk+1(sk+1)}（遞推公式）

uk∈D(uk)k=n,n-1,…,1

fn+1(sn+1)=0

（邊界條件）

2.指標(biāo)函數(shù)為階段指標(biāo)積的形式

fk(sk)=opt{vk(sk,uk)×fk+1(sk+1)}（遞推公式）

uk∈D(uk)k=n,n-1,…,1

fn+1(sn+1)=0（邊界條件）

基本方程動(dòng)態(tài)規(guī)劃四大要素一個(gè)方程動(dòng)態(tài)規(guī)劃的四大要素：狀態(tài)變量及其可能集合：

sk

∈

SK

決策變量及其允許集合：uk（sk）∈Dk（sk）狀態(tài)轉(zhuǎn)移方程：sk+1=T(sk,uk)指標(biāo)函數(shù)：vk

(sk,uk

)

一個(gè)方程：基本方程

fk(sk)=opt{vk(sk,uk)+fk+1(sk+1)}（遞推公式）

uk∈D(uk)k=n,n-1,…,1

fn+1(sn+1)=0

（邊界條件）

建立動(dòng)態(tài)規(guī)劃模型的步驟1、劃分階段k 按時(shí)間或空間先后順序，將過(guò)程劃分為若干相互聯(lián)系的階段。對(duì)于靜態(tài)問(wèn)題要人為地賦予“時(shí)間”概念，以便劃分階段。2、正確選擇狀態(tài)變量sk 一般地，狀態(tài)變量的選擇是從過(guò)程演變的特點(diǎn)中尋找。3、確定決策變量uk(sk)及允許決策集合Dk(sk)

建立動(dòng)態(tài)規(guī)劃模型的步驟4、確定狀態(tài)轉(zhuǎn)移方程

根據(jù)k階段狀態(tài)變量和決策變量，寫出k+1階段狀態(tài)變量，狀態(tài)轉(zhuǎn)移方程應(yīng)當(dāng)具有遞推關(guān)系。

sk+1=Tk(sk,uk

)Tk

—函數(shù)關(guān)系5、確定階段指標(biāo)函數(shù)和最優(yōu)指標(biāo)函數(shù)，建立動(dòng)態(tài)規(guī)劃基本方程動(dòng)態(tài)規(guī)劃基本方程:

fk(sk

)=Opt｛

Vk(sk

,uk)+fk+1(s

k+1)｝

fn+1(s

n+1)=0

Opt

最優(yōu)化（max,min）建立動(dòng)態(tài)規(guī)劃模型的步驟5、確定階段指標(biāo)函數(shù)和最優(yōu)指標(biāo)函數(shù)，建立動(dòng)態(tài)規(guī)劃基本方程動(dòng)態(tài)規(guī)劃基本方程:

fk(sk

)=Opt｛

Vk(sk

,uk)+fk+1(s

k+1)｝

fn+1(s

n+1)=0

Opt

最優(yōu)化（max,min）5、確定階段指標(biāo)函數(shù)和最優(yōu)指標(biāo)函數(shù)，建立動(dòng)態(tài)規(guī)劃基本方程：

fk(sk

)=Opt｛

Vk(sk

,uk)+fk+1(s

k+1)｝

fn+1(s

n+1)=0

Opt

最優(yōu)化（max,min）應(yīng)用舉例——最短路問(wèn)題2511214106104131112396581052C1C3D1AB1B3B2D2EC2例5.1試求下圖中從A地到E地的最短路徑：解：1、將問(wèn)題分為4個(gè)階段，階段變量k=1,2,3,4；2、狀態(tài)變量設(shè)為sk:表示第k階段所處的位置；3、決策變量設(shè)為uk:表示第k階段選擇的路線；4、狀態(tài)轉(zhuǎn)移方程為：sk+1=uk(sk)5、指標(biāo)函數(shù)為：階段指標(biāo)函數(shù)dk(sk,sk+1):表示從k階段到k+1階段的路程。最優(yōu)值函數(shù)fk(sk):表示從sk到E的最短路程。應(yīng)用舉例應(yīng)用舉例基本方程：

fk(sk

)=min｛

dk(sk

,sk+1)+fk+1(s

k+1)｝

f5(s

5)=f5(E)=02511214106104131112396581052C1C3D1AB1B3B2D2EC2k=1k=2k=3k=4基本方程：

fk

(sk

)=min｛

dk

(sk

,sk+1)+fk+1

(s

k+1)｝

f5

(s

5)=f5

(E)

=02511214106104131112396581052C1C3D1AB1B3B2D2EC2f5(E)=0應(yīng)用舉例2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f5(E)=0應(yīng)用舉例2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=5應(yīng)用舉例2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C1)=8f4(D1)=5應(yīng)用舉例2511214106104131112C3AB1B3B22511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C2)=7f4(D1)=5f3(C1)=8應(yīng)用舉例2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f3(C1)=8f3(C2)=7應(yīng)用舉例2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B1)=20f3(C2)=7f3(C1)=8應(yīng)用舉例2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2