運籌動態(tài)規(guī)劃

運籌動態(tài)規(guī)劃第一頁，共四十二頁，2022年，8月28日動態(tài)規(guī)劃（DynamicProgramming）

R.Bellman50年代執(zhí)教于普林斯頓和斯坦福大學(xué)，后進(jìn)入蘭德（Rand）研究所。1957年發(fā)表“DynamicProgramming”一書，標(biāo)識動態(tài)規(guī)劃的正式誕生。

動態(tài)規(guī)劃是解決復(fù)雜系統(tǒng)優(yōu)化問題的一種方法。是解決動態(tài)系統(tǒng)多階段決策過程的基本方法之一。第二頁，共四十二頁，2022年，8月28日教學(xué)大綱:

理解動態(tài)規(guī)劃基本概念、最優(yōu)化原理和基本方程，通過資源分配和生產(chǎn)與存儲等問題,學(xué)習(xí)應(yīng)用動態(tài)規(guī)劃解決多階段決策問題。

重點:掌握動態(tài)規(guī)劃模型結(jié)構(gòu)、逆序法算法原理、資源分配、設(shè)備更新、生產(chǎn)于存貯等問題。難點為動態(tài)規(guī)劃中狀態(tài)變量等的確定。第三頁，共四十二頁，2022年，8月28日123451.多階段的決策問題引例1最短路問題A12345678E75632515142534463333第四頁，共四十二頁，2022年，8月28日例2：生產(chǎn)與投入問題例3：將一個單數(shù)C（C>0)分成n個部分C1,C2…,Cn之和，且Ci>0（i=1,…,n），問如何分割使其乘積為最大第五頁，共四十二頁，2022年，8月28日

包含隨時間變化的因素和變量的系統(tǒng)。系統(tǒng)在某個時刻的狀態(tài)，往往要依某種形式受過去某些決策的影響；將時間作為決策變量之一的決策問題稱為動態(tài)決策問題。如經(jīng)濟(jì)系統(tǒng),生產(chǎn)系統(tǒng)等。動態(tài)系統(tǒng)：

線性系統(tǒng)、非線性系統(tǒng)。動態(tài)系統(tǒng)的特點：動態(tài)決策問題：而系統(tǒng)的當(dāng)前狀態(tài)和決策又會影響系統(tǒng)今后的發(fā)展。動態(tài)規(guī)劃的研究對象第六頁，共四十二頁，2022年，8月28日即在系統(tǒng)發(fā)展的不同時刻（或階段）根據(jù)系統(tǒng)所處的狀態(tài)，不斷地做出決策；每個階段都要進(jìn)行決策,目的是使整個過程的決策達(dá)到最優(yōu)效果。動態(tài)決策問題的特點：系統(tǒng)所處的狀態(tài)和時刻是進(jìn)行決策的重要因素；找到不同時刻的最優(yōu)決策以及整個過程的最優(yōu)策略。多階段決策問題：是動態(tài)決策問題的一種特殊形式；在多階段決策過程中,系統(tǒng)的動態(tài)過程可以按照時間進(jìn)程分為狀態(tài)相互聯(lián)系而又相互區(qū)別的各個階段；第七頁，共四十二頁，2022年，8月28日多階段決策問題的典型例子：1.生產(chǎn)決策問題：企業(yè)在生產(chǎn)過程中，由于需求是隨時間變化的，因此企業(yè)為了獲得全年的最佳生產(chǎn)效益，就要在整個生產(chǎn)過程中逐月或逐季度地根據(jù)庫存和需求決定生產(chǎn)計劃。

2.機(jī)器負(fù)荷分配問題：某種機(jī)器可以在高低兩種不同的負(fù)荷下進(jìn)行生產(chǎn)。在高負(fù)荷下進(jìn)行生產(chǎn)時，產(chǎn)品的年產(chǎn)量g和投入生產(chǎn)的機(jī)器數(shù)量u1的關(guān)系為g=g(u1)12n狀態(tài)決策狀態(tài)決策狀態(tài)狀態(tài)決策第八頁，共四十二頁，2022年，8月28日

這時，機(jī)器的年完好率為a，即如果年初完好機(jī)器的數(shù)量為u，到年終完好的機(jī)器就為au,0<a<1。

在低負(fù)荷下生產(chǎn)時，產(chǎn)品的年產(chǎn)量h和投入生產(chǎn)的機(jī)器數(shù)量u2的關(guān)系為

h=h(u2)

假定開始生產(chǎn)時完好的機(jī)器數(shù)量為s1。要求制定一個五年計劃，在每年開始時，決定如何重新分配完好的機(jī)器在兩種不同的負(fù)荷下生產(chǎn)的數(shù)量，使在五年內(nèi)產(chǎn)品的總產(chǎn)量達(dá)到最高。

相應(yīng)的機(jī)器年完好率b,0<b<1。

第九頁，共四十二頁，2022年，8月28日

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

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

4

.線性規(guī)劃、非線性規(guī)劃等靜態(tài)的規(guī)劃問題也可以通過適當(dāng)?shù)匾腚A段的概念，應(yīng)用動態(tài)規(guī)劃方法加以解決，后面將詳細(xì)介紹。第十頁，共四十二頁，2022年，8月28日12345

5.最短路問題：給定一個交通網(wǎng)絡(luò)圖如下，其中兩點之間的數(shù)字表示距離（或花費），試求從A點到E點的最短距離（總費用最?。?。A12345678E75632515142534463333第十一頁，共四十二頁，2022年，8月28日12345A12345678E645877893389565621342.最優(yōu)化原理與動態(tài)規(guī)劃的數(shù)學(xué)模型2-1動態(tài)規(guī)劃的解題思想第十二頁，共四十二頁，2022年，8月28日

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

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

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

第十四頁，共四十二頁，2022年，8月28日即城市⑤到終點最短距離為5，其路徑為⑤→⑧→E。相應(yīng)決策為

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

即城市①到終點最短距離為9，其路徑為①→⑤→⑧→E。本段相應(yīng)決策為第十六頁，共四十二頁，2022年，8月28日同理有：第十七頁，共四十二頁，2022年，8月28日第四步k=1,只要一個狀態(tài)A，則：即從城市A到城市E的距離為17。本段決策為:

第十八頁，共四十二頁，2022年，8月28日再按計算順序反推可得最優(yōu)決策序列{}即：

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

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

第十九頁，共四十二頁，2022年，8月28日用動態(tài)規(guī)劃（逆序法求解的）基本特性：動態(tài)規(guī)劃方法是既把當(dāng)前一段和未來各段分開，又把當(dāng)前效益和未來效益結(jié)合起來考慮的一種最優(yōu)化方法。每段決策的選取都是從全局考慮的,與該段的最優(yōu)選擇答案一般是不同的。求解時從邊界條件開始，逆（或順）過程行進(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件（簡言之為基本方程）。從而把問題化成一族同類的子問題；第二十頁，共四十二頁，2022年，8月28日求解的各個階段,我們利用了k階段與k+1階段之間的遞推關(guān)系:在求整個問題的最優(yōu)策略時，由于初始狀態(tài)是已知的，每段的決策是該段狀態(tài)的函數(shù)，故沿最優(yōu)化策略所經(jīng)過的各段狀態(tài)便可確定了最優(yōu)路線。fk(sk)=min｛dk(sk,uk(sk))+fk+1(uk(sk))｝ukDk(sk)f4(s4)=0k=4,3,2,1第二十一頁，共四十二頁，2022年，8月28日一般情況,k階段與k+1階段的遞推關(guān)系式（動態(tài)規(guī)劃基本方程）邊界條件為第二十二頁，共四十二頁，2022年，8月28日但要便于把問題的過程能轉(zhuǎn)化為多階段決策的過程。狀態(tài)變量的取值有一定的允許集合或范圍，此集合稱為狀態(tài)允許集合。2-2動態(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ù)、一組數(shù)、一個向量第二十三頁，共四十二頁，2022年，8月28日在實際問題中決策變量的取值往往在某一范圍之內(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)第二十四頁，共四十二頁，2022年，8月28日

由每段的決策按順序排列組成的決策函數(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)，即第二十五頁，共四十二頁，2022年，8月28日系統(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)移來實現(xiàn)的；具體如下：第二十六頁，共四十二頁，2022年，8月28日12ks1u1s2u2s3skukSk+1能用動態(tài)規(guī)劃方法求解的多階段決策過程是一類特殊的多階段決策過程，即具有無后效性的多階段決策過程。圖示如下：第二十七頁，共四十二頁，2022年，8月28日如果狀態(tài)變量不能滿足無后效性的要求，應(yīng)適當(dāng)?shù)馗淖儬顟B(tài)的定義或規(guī)定方法。動態(tài)規(guī)劃中能處理的狀態(tài)轉(zhuǎn)移方程的形式。狀態(tài)具有無后效性的多階段決策過程的狀態(tài)轉(zhuǎn)移方程如下無后效性(馬爾可夫性)如果某階段狀態(tài)給定后，則在這個階段以后過程的發(fā)展不受這個階段以前各段狀態(tài)的影響；過程的過去歷史只能通過當(dāng)前的狀態(tài)去影響它未來的發(fā)展；構(gòu)造動態(tài)規(guī)劃模型時，要充分注意是否滿足無后效性的要求；狀態(tài)變量要滿足無后效性的要求；第二十八頁，共四十二頁，2022年，8月28日它是定義在全過程或所有后部子過程上確定的數(shù)量函數(shù)。動態(tài)規(guī)劃模型的指標(biāo)函數(shù)，應(yīng)具有可分離性，并滿足遞推關(guān)系。常見的指標(biāo)函數(shù)的形式是：費用、成本、利潤、路長等。用Vk,n

表示之。5.指標(biāo)函數(shù)和最優(yōu)值函數(shù)用來衡量所實現(xiàn)過程優(yōu)劣的一種數(shù)量指標(biāo)，稱為指標(biāo)函數(shù)；即Vk,n可以表示為sk,uk,Vk+1,n的函數(shù)。第二十九頁，共四十二頁，2022年，8月28日常見的指標(biāo)函數(shù)的形式是：

過程和它的任一子過程的指標(biāo)是它所包含的各階段的指標(biāo)和。即無后效性的結(jié)果。其中vj(sj

)

表示第j階段的階段指標(biāo)。這時上式可寫成第三十頁，共四十二頁，2022年，8月28日過程和它的任意子過程的指標(biāo)是它所包含的各階段的指標(biāo)的乘積。即則可改寫成第三十一頁，共四十二頁，2022年，8月28日

多階段決策過程的數(shù)學(xué)模型：（具有無后效性的多階段決策過程）

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

終止?fàn)顟B(tài)采取最優(yōu)策略所得到的指標(biāo)函數(shù)值。最優(yōu)值函數(shù)：即可遞推第三十二頁，共四十二頁，2022年，8月28日

多階段決策過程的數(shù)學(xué)模型：（具有無后效性）第三十三頁，共四十二頁，2022年，8月28日小結(jié):方程:狀態(tài)轉(zhuǎn)移方程概念:階段變量k﹑狀態(tài)變量sk﹑決策變量uk;指標(biāo):

動態(tài)規(guī)劃本質(zhì)上是多階段決策過程;

效益指標(biāo)函數(shù)形式:

和、積無后效性可遞推第三十四頁，共四十二頁，2022年，8月28日解多階段決策過程問題，求出

最優(yōu)策略，即最優(yōu)決策序列f1(s1)

最優(yōu)軌線，即執(zhí)行最優(yōu)策略時的狀態(tài)序列

最優(yōu)目標(biāo)函數(shù)值從k到終點最優(yōu)策略子策略的最優(yōu)目標(biāo)函數(shù)值第三十五頁，共四十二頁，2022年，8月28日將問題按時空特性恰當(dāng)?shù)貏澐譃槿舾蓚€階段

選擇狀態(tài)變量sk,既能描述過程的變化又滿足無后效性；確定決策變量uk及每一階段的允許決策集合Dk(sk)；正確寫出狀態(tài)轉(zhuǎn)移方程；正確地定義各階段的直接指標(biāo)函數(shù)和后部子過程的最優(yōu)指標(biāo)函數(shù)，并寫出其基本方程：動態(tài)規(guī)劃模型及其求解五要素：第三十六頁，共四十二頁，2022年，8月28日問如何分配投資數(shù)額才能使總效益最大?解：可列出靜態(tài)規(guī)劃問題的模型如下分階段：分三個階段，即k=1，2，3。確定決策變量：通?？梢匀§o態(tài)規(guī)劃中的變量為決策變量。確定狀態(tài)變量：狀態(tài)變量與決策變量有密切關(guān)系，狀態(tài)變量一般為累計量或隨遞推過程變化的量。例4某公司有資金10萬元，若投資于項目(i=1,2,3)的投資額為xi時，其效益分別為考慮效益函數(shù)的形式第三十七頁，共四十二頁，2022年，8月28日狀態(tài)轉(zhuǎn)移方程

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

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

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