運籌學(xué) 第八章動態(tài)規(guī)劃

運籌學(xué)第八章動態(tài)規(guī)劃第1頁，共193頁，2023年，2月20日，星期四引言□動態(tài)規(guī)劃是解決多階段決策過程最優(yōu)化的一種方法?！踉摲椒ㄊ怯擅绹鴶?shù)學(xué)家貝爾曼（R.E.Bellman）等人在20世紀50年代初提出的。并成功地解決了生產(chǎn)管理、工程技術(shù)等方面的許多問題，從而建立了運籌學(xué)的一個新的分支，即動態(tài)規(guī)劃。Bellman在1957年出版了《DynamicProgramming》一書，是動態(tài)規(guī)劃領(lǐng)域中的第一本著作。第2頁，共193頁，2023年，2月20日，星期四□動態(tài)規(guī)劃與其他規(guī)劃方法的不同之處在于：

動態(tài)規(guī)劃是求解某類問題（多階段決策問題）的一種方法，是考察問題的一種途徑，而不是一種特定算法。

因此，它不像線性規(guī)劃那樣有一個標準的數(shù)學(xué)表達式和明確定義的一組（算法）規(guī)則，而必須對具體問題進行具體分析處理。因此，學(xué)習(xí)動態(tài)規(guī)劃時，除對基本概念和基本方法正確理解外，還應(yīng)在一定經(jīng)驗積累基礎(chǔ)上，以豐富的想像力去建立模型，用創(chuàng)造性的技巧去求解。第3頁，共193頁，2023年，2月20日，星期四提綱1

動態(tài)規(guī)劃實例2動態(tài)規(guī)劃的基本概念3動態(tài)規(guī)劃的基本思想與基本原理4逆序解法與順序解法第4頁，共193頁，2023年，2月20日，星期四學(xué)習(xí)目標：1明確什么是多階段的決策問題，特別要注意沒有明顯的時段背景的問題如何化歸為多階段的決策問題。1動態(tài)規(guī)劃實例第5頁，共193頁，2023年，2月20日，星期四P156例2機器負荷分配問題（時間階段問題）◎設(shè)有某種機器設(shè)備，用于完成兩類工作A和B。若第k年初完好機器的數(shù)量為xk，若以數(shù)量uk用于A，余下的（xk－uk）用于工作B，則該年的預(yù)期收入為g(uk)+h(xk－uk)。這里g(uk)和h(xk－uk)是已知函數(shù)，且g(0)=h(0)=0?！蛴謾C器設(shè)備在使用中會有損壞，設(shè)機器用于工作A時，一年后能繼續(xù)使用的完好機器數(shù)占年初投入量的70%；若用于工作B時，一年后能繼續(xù)使用的完好機器數(shù)占年初投入量的90%。則在下一年初能繼續(xù)用于A、B工作的設(shè)備數(shù)為xk+1=0.7uk+0.9(xk－uk)?！蛟O(shè)第1年初完好的機器總數(shù)為1000臺，問在連續(xù)5年內(nèi)每年應(yīng)如何分配用于A、B兩項工作的機器數(shù)，使5年的總收益為最大。1動態(tài)規(guī)劃實例第6頁，共193頁，2023年，2月20日，星期四□相應(yīng)的問題稱為多階段決策問題?！踹@是一個多階段決策過程?！踉撨^程可以分為相互聯(lián)系的若干階段，每一階段都需作出決策，從而形成全過程的決策。第1年x1=1000u1第2年x2=0.7u1+0.9(x1-u1)u2第3年x3=0.7u2+0.9(x2-u2)u3第4年u4第5年x5=0.7u4+0.9(x4-u4)u5x4=0.7u3+0.9(x3-u3)x6第7頁，共193頁，2023年，2月20日，星期四P156例1最短路線問題（空間階段的例子）設(shè)有一個旅行者從下圖中的A點出發(fā)，途中要經(jīng)過B、C、D等處，最后到達終點E。從A到E有很多條路線可以選擇，各點之間的距離如圖所示，問該旅行者應(yīng)選擇哪一條路線，使從A到達E的總的路程為最短。25375632455114633334C1C3D1AB1B3B2D2EC21234狀態(tài)1決策1狀態(tài)2狀態(tài)3狀態(tài)4狀態(tài)5決策2決策3決策4□可看成

4階段的決策問題。第8頁，共193頁，2023年，2月20日，星期四□從以上兩個例子，可以知道所謂多階段決策問題是指這樣的決策問題：其過程可分為若干個相互聯(lián)系的階段，每一階段都對應(yīng)著一組可供選擇的決策，每一決策的選定既依賴于當(dāng)前面臨的狀態(tài)，又影響以后總體的效果。

當(dāng)每一階段的決策選定以后，就構(gòu)成一個決策序列，稱為一個策略，它對應(yīng)著一個確定的效果。多階段決策問題就是尋找使此效果最好的策略。第9頁，共193頁，2023年，2月20日，星期四多階段決策過程的特點1.各階段的決策相互關(guān)聯(lián)□多階段決策過程最優(yōu)化的目的，是要達到整個活動過程的總體效果最優(yōu)，而不是某個階段“局部”的效果最優(yōu)。因此，各個階段決策的選取不是任意確定的。□前一個決策的選取決定了當(dāng)前狀態(tài)，當(dāng)前狀態(tài)進行決策后又影響到下一階段的狀態(tài)和決策，以至于影響總體效果。所以決策者在每個階段決策時，不應(yīng)僅考慮本階段最優(yōu)，還應(yīng)考慮對最終目標的影響，從而做出對全局而言是最優(yōu)的決策。□動態(tài)規(guī)劃就是符合這一要求的一種最優(yōu)化方法。第10頁，共193頁，2023年，2月20日，星期四2.各個階段的決策一般與“時間”有關(guān)□動態(tài)規(guī)劃方法與“時間”關(guān)系很密切，隨著時間過程的發(fā)展而決定各階段的決策，從而產(chǎn)生一個決策序列，這就是“動態(tài)”的意思。□但是，一些與時間無關(guān)的靜態(tài)問題，只要在問題中人為引入“時間”因素，也可將其看成是多階段的決策問題，用動態(tài)規(guī)劃方法去處理。第11頁，共193頁，2023年，2月20日，星期四學(xué)習(xí)目標：1準確、熟練地掌握動態(tài)規(guī)劃的基本概念、特別是狀態(tài)變量、決策變量、狀態(tài)轉(zhuǎn)移律、指標函數(shù)、基本方程等。2動態(tài)規(guī)劃的基本概念第12頁，共193頁，2023年，2月20日，星期四□為了便于求解和表示決策及過程的發(fā)展順序，而把所給問題恰當(dāng)?shù)貏澐譃槿舾蓚€相互聯(lián)系又有區(qū)別的子問題，稱之為多段決策問題的階段。一個階段，就是需要作出一個決策的子問題。□通常，階段是按決策進行的時間或空間上先后順序劃分的?！趺枋鲭A段的變量稱為階段變量，常記為k，k=1,2,…,n。□如本例可按空間分為4個階段來求解，

k=1,2,3,4。（1）階段（stage）第13頁，共193頁，2023年，2月20日，星期四□狀態(tài)：每階段初的客觀條件。描述各階段狀態(tài)的變量稱為狀態(tài)變量，常用xk表示第k階段的狀態(tài)。（2）狀態(tài)（state）□例1中，狀態(tài)就是某階段的出發(fā)位置。x1x2x3x4x5□按狀態(tài)變量的取值是連續(xù)還是離散，可將動態(tài)規(guī)劃問題分為離散型和連續(xù)型。第14頁，共193頁，2023年，2月20日，星期四□動態(tài)規(guī)劃中的狀態(tài)應(yīng)滿足無后效性（馬爾科夫性）：所謂無后效性指系統(tǒng)到達某個狀態(tài)前的過程的決策將不影響到該狀態(tài)以后的決策。［指系統(tǒng)從某個階段往后的發(fā)展，僅由本階段所處的狀態(tài)及其往后的決策所決定，與系統(tǒng)以前經(jīng)歷的狀態(tài)和決策（歷史）無關(guān)。過程的過去歷史只能通過當(dāng)前的狀態(tài)去影響它未來的發(fā)展］□例1中，當(dāng)某階段的狀態(tài)已選定某個點時，從這個點以后的路線只與該點有關(guān)，不受該點以前的路線的影響，所以滿足狀態(tài)的無后效性。第15頁，共193頁，2023年，2月20日，星期四□狀態(tài)集合：狀態(tài)變量xk的取值集合稱為狀態(tài)集合，狀態(tài)集合實際上是關(guān)于狀態(tài)的約束條件?！跬ǔＳ肧k表示狀態(tài)集合，xkSk。□第1階段S1={A}；□第2階段具有3個狀態(tài)B1、B2和B3，故S2={B1,B2,B3}。□……x1x2x3x4x5第16頁，共193頁，2023年，2月20日，星期四（3）決策（decision）□當(dāng)過程處于某一階段的某狀態(tài)時，可以做出不同的決定，從而確定下一階段的狀態(tài)，這種決定稱為決策。□描述決策的變量稱為決策變量，常用uk(

xk

)表示第k階段當(dāng)狀態(tài)處于xk時的決策變量，它是狀態(tài)變量的函數(shù)?！趵?中，從第2階段的狀態(tài)B1出發(fā)，可以選擇下一階段的C1、C2、C3?！跞缥覀儧Q定選擇C1，則可表示為：u2(B1)=C1。B1C1C2C3x2第17頁，共193頁，2023年，2月20日，星期四□決策集合：第k階段當(dāng)狀態(tài)處于xk時決策變量uk(xk)的取值范稱為決策集合，常用Dk(xk)表示?！趵?中，從第2階段的狀態(tài)B1出發(fā)，可以選擇下一階段的C1、C2、C3?！跫碊2(B1)={C1、C2、C3}；B1C1C2C3□決策集合實際上是決策的約束條件，uk(xk)∈Dk(xk)。第18頁，共193頁，2023年，2月20日，星期四□小結(jié)階段k、狀態(tài)xk、狀態(tài)集合Sk、決策uk(xk)、決策集合Dk(xk)。x1x2x3x4x5第19頁，共193頁，2023年，2月20日，星期四（4）狀態(tài)轉(zhuǎn)移律（方程）□狀態(tài)轉(zhuǎn)移律：從xk的某一狀態(tài)值出發(fā)，當(dāng)決策變量uk(xk)的取值決定后，下一階段狀態(tài)變量xk+1的取值也隨之確定。描述從xk轉(zhuǎn)變?yōu)閤k+1的規(guī)律稱為狀態(tài)轉(zhuǎn)移規(guī)律（方程）?！鯊牡?階段的狀態(tài)B1出發(fā)，如我們決定選擇C2（也即確定了下一階段的狀態(tài)）。B1C2第20頁，共193頁，2023年，2月20日，星期四B1C2□上例中，

u2(B1)=C2□狀態(tài)轉(zhuǎn)移律為：

xk+1=uk(xk

)□一般來說，下一階段狀態(tài)變量xk+1的取值是上階段的某一狀態(tài)變量xk和上階段決策變量uk(xk)的函數(shù)，記為

xk+1=Tk(xk,uk(xk))12nx1u1x2u2x3xnunxn+1第21頁，共193頁，2023年，2月20日，星期四（5）策略（policy）和子策略（subpolicy）□策略：由依次進行的n個階段決策構(gòu)成的決策序列就構(gòu)成一個策略，用p1n{u1(x1),u2(x2),…,un(xn)}表示。25375632455114633334C1C3D1AB1B3B2D2EC2□本例中，如p14{u1(A)=B1,u2(B1)=C2,u3(C2)=D1,

u4(D1)=E}表示其中一個策略，其總距離為2+5+6+3=16。第22頁，共193頁，2023年，2月20日，星期四□策略集合：在實際問題中，由于在各個階段可供選擇的決策有許多個，因此，它們的不同組合就構(gòu)成了許多可供選擇的決策序列（策略），由它們組成的集合，稱為策略集合，記作P1n?！鯊牟呗约现?，找出具有最優(yōu)效果的策略稱為最優(yōu)策略。第23頁，共193頁，2023年，2月20日，星期四□子策略：從k階段到第n階段，依次進行的階段決策構(gòu)成的決策序列稱為k部子策略，表示為pkn={uk(xk),uk+1(xk+1),…,un(xn)}□如從第3階段的C2狀態(tài)開始的一個子策略可表示：p34={u3(C2)=D1,u4(D1)=E}C2第24頁，共193頁，2023年，2月20日，星期四（6）指標函數(shù)□用來衡量策略或子策略或決策的效果的某種數(shù)量指標，就稱為指標函數(shù)?！跛嵌x在全過程或各子過程或各階段上的確定數(shù)量函數(shù)。對不同問題，指標函數(shù)可以是諸如費用、成本、產(chǎn)值、利潤、產(chǎn)量、耗量、距離、時間、效用，等等。階段指標函數(shù)過程指標函數(shù)第25頁，共193頁，2023年，2月20日，星期四①階段指標函數(shù)：是指第k階段從狀態(tài)xk出發(fā)，采取決策uk

時產(chǎn)生的效益，用vk(xk,uk)表示?！趵?中，指標函數(shù)是距離?！跞鐅2(B1,C2)表示由B1出發(fā)，采用決策到C2點的兩點間距離，即v2(B1,C2)=5。B1C2第26頁，共193頁，2023年，2月20日，星期四②過程指標函數(shù)：是指從第k階段的某狀態(tài)xk出發(fā)，采取子策略pkn時所得到的效益，記作

Vkn(xk,uk,xk+1,uk+1,…,xn)□例1中，如V34(C2,u3(C2)=D1,D1,u4(D1)=

E,E)=6+3=9C2第27頁，共193頁，2023年，2月20日，星期四□過程指標函數(shù)Vkn通常是描述所實現(xiàn)的全過程或k后部子過程效果優(yōu)劣的數(shù)量指標，它是由各階段的階段指標函數(shù)vk(xk,uk)累積形成的。（1）可分性：適于用動態(tài)規(guī)劃求解的問題的過程指標函數(shù)（即目標函數(shù)），必須具有關(guān)于階段指標的可分離形式，即對于后部子過程的指標函數(shù)可以表示為：

Vkn(xk,uk,xk+1,uk+1,···,xn)=

vk(xk,uk)

vk+1(xk+1,uk+1)···

vn(xn,un)式中，表示某種運算，可以是加、減、乘、除、開方等。第28頁，共193頁，2023年，2月20日，星期四□多階段決策問題中，常見的目標函數(shù)形式之一是取各階段效應(yīng)之和的形式，即:

□有些問題，如系統(tǒng)可靠性問題，其目標函數(shù)是取各階段效應(yīng)的連乘積形式，如：

總之，具體問題的目標函數(shù)表達形式需要視具體問題而定。Vkn=∑vi（xi,ui）i=kn(8.3a)Vkn=∏vi（xi,ui）i=kn(8.3b)第29頁，共193頁，2023年，2月20日，星期四（2）可遞推：過程指標函數(shù)Vkn要滿足遞推關(guān)系，即可遞推Vkn(

xk,uk,xk+1,uk+1,…,xn

)＝Φk[xk,uk,

V(k+1)n(xk+1,uk+1,…,xn)]＝vk(xk,uk)

vk+1(xk+1,uk+1)···

vn(xn,un)＝vk(xk,uk)V(k+1)n(

xk+1,uk+1,…,xn

)第30頁，共193頁，2023年，2月20日，星期四③最優(yōu)指標函數(shù)：表示從第k階段狀態(tài)為xk時采用最優(yōu)策略pkn*到過程終止時的最佳效益值。記為fk(xk)。

fk(xk)=Vkn(xk,pkn*)=optVkn(xk,pkn)□例1中，如f3(C2)=3+4=7。其中opt可根據(jù)具體情況取max或min。C2動態(tài)規(guī)劃的目標？◎最優(yōu)解：最優(yōu)策略p1n◎最優(yōu)值：最優(yōu)指標f1(A)第31頁，共193頁，2023年，2月20日，星期四□多階段決策問題的數(shù)學(xué)模型

綜上所述，適于應(yīng)用動態(tài)規(guī)劃方法求解的一類多階段決策問題的數(shù)學(xué)模型呈以下形式:

f1=opt

V1n(x1

,p1n)最優(yōu)指標函數(shù)

xk+1=Tk(xk,uk(xk))狀態(tài)轉(zhuǎn)移方程

uk∈Dk決策變量xk∈Sk

狀態(tài)變量

k=1,2,…,n

階段變量st.□上述數(shù)學(xué)模型說明了對于給定的多階段決策過程，求取一個(或多個)最優(yōu)策略或最優(yōu)決策序列{u1,u2,…,un

}，使之既滿足左式給出的全部約束條件，又使左式所示的目標函數(shù)取得極值，并且同時指出執(zhí)行該最優(yōu)策略時，過程狀態(tài)演變序列即是最優(yōu)路線。第32頁，共193頁，2023年，2月20日，星期四小結(jié):概念:階段變量k﹑狀態(tài)變量xk﹑決策變量uk;動態(tài)規(guī)劃本質(zhì)上是多階段決策過程;

效益指標函數(shù)形式:和、積無后效性可遞推方程:狀態(tài)轉(zhuǎn)移方程xk+1=Tk(xk,uk(xk))指標:

Vkn(xk,uk,xk+1,uk+1,…,xn)fk(xk)=Vkn(xk,pkn*)=optVkn(xk,pkn)Vkn(

xk,uk,xk+1,uk+1,…,xn

)＝Φk[xk,uk,

V(k+1)n(xk+1,uk+1,…,xn)]第33頁，共193頁，2023年，2月20日，星期四解多階段決策過程問題，求出

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

最優(yōu)軌線，即執(zhí)行最優(yōu)策略時的狀態(tài)序列{u1*,u2*,…,un*}{x1*,x2*,…,xn*}最優(yōu)目標函數(shù)值p1n∈P1nf1(x1)=V1n(x1

,p1n*)=optV1n(x1

,p1n)第34頁，共193頁，2023年，2月20日，星期四1.劃分階段2.正確選擇狀態(tài)變量3.確定決策變量及允許決策集合4.確定狀態(tài)轉(zhuǎn)移方程5.確定階段指標函數(shù)和最優(yōu)指標函數(shù)，建立動態(tài)規(guī)劃基本方程劃分階段是運用動態(tài)規(guī)劃求解多階段決策問題的第一步，在確定多階段特性后，按時間或空間先后順序，將過程劃分為若干相互聯(lián)系的階段。對于靜態(tài)問題要人為地賦予“時間”概念，以便劃分階段。建立動態(tài)規(guī)劃模型的步驟

選擇狀態(tài)變量既要能確切描述過程演變又要滿足無后效性，而且各階段狀態(tài)變量的取值能夠確定。通常選擇所求解問題的關(guān)鍵變量作為決策變量，同時要給出決策變量的取值范圍，即確定允許決策集合。根據(jù)k階段狀態(tài)變量和決策變量，寫出k+1階段狀態(tài)變量，狀態(tài)轉(zhuǎn)移方程應(yīng)當(dāng)具有遞推關(guān)系。階段指標函數(shù)是指第k階段的收益，最優(yōu)指標函數(shù)是指從第k階段狀態(tài)出發(fā)到第n階段末所獲得收益的最優(yōu)值，最后寫出動態(tài)規(guī)劃基本方程。第35頁，共193頁，2023年，2月20日，星期四以上五步是建立動態(tài)規(guī)劃數(shù)學(xué)模型的一般步驟。由于動態(tài)規(guī)劃模型與線性規(guī)劃模型不同，動態(tài)規(guī)劃模型沒有統(tǒng)一的模式，建模時必須根據(jù)具體問題具體分析，只有通過不斷實踐總結(jié)，才能較好掌握建模方法與技巧。下面我們看一個具體的例子P156例2機器負荷分配問題（時間階段問題）第36頁，共193頁，2023年，2月20日，星期四P156例2機器負荷分配問題（時間階段問題）◎設(shè)有某種機器設(shè)備，用于完成兩類工作A和B。若第k年初完好機器的數(shù)量為xk，若以數(shù)量uk用于A，余下的（xk－uk）用于工作B，則該年的預(yù)期收入為g(uk)+h(xk－uk)。其中g(shù)(uk)＝8uk，h(xk－uk)=5（xk－uk）?！蛴謾C器設(shè)備在使用中會有損壞，設(shè)機器用于工作A時，一年后能繼續(xù)使用的完好機器數(shù)占年初投入量的70%；若用于工作B時，一年后能繼續(xù)使用的完好機器數(shù)占年初投入量的90%。則在下一年初能繼續(xù)用于A、B工作的設(shè)備數(shù)為xk+1=0.7uk+0.9(xk－uk)?！蛟O(shè)第1年初完好的機器總數(shù)為1000臺，問在連續(xù)5年內(nèi)每年應(yīng)如何分配用于A、B兩項工作的機器數(shù)，使5年的總收益為最大。第37頁，共193頁，2023年，2月20日，星期四1.劃分階段按年度來劃分階段，k=1,2,3,4,52.正確選擇狀態(tài)變量狀態(tài)變量xk為第k年度初擁有的完好機器數(shù)量3.確定決策變量及允許決策集合決策變量uk為第k年度中分配于A工作的機器數(shù)量，則xk－uk為用于B工作的機器數(shù)量。第k階段決策集合Dk(xk)={uk|0≤uk≤xk}◎這里xk和uk均取連續(xù)變量，它們的非整數(shù)值可以這樣理解，如xk=0.6，就表示一臺機器在第k年度中正常工作時間只占6/10；uk=0.3，就表示一臺機器在該年度只有3/10的時間能正常用于A工作。第38頁，共193頁，2023年，2月20日，星期四4.確定狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程為xk+1=0.7uk+0.9(xk－uk)5.確定階段指標函數(shù)和最優(yōu)指標函數(shù)，建立動態(tài)規(guī)劃基本方程指標函數(shù)為V1,5

=∑vi（xi,ui）i=15

=∑g(ui)+h(xi－ui)i=15令最優(yōu)指標函數(shù)fk(xk)表示由資源量xk出發(fā)，從第k年開始到第5年結(jié)束時所取得的最大預(yù)期收入。因而有：

fk(xk

)=max{}Vk,5

=∑vi（xi,ui）i=k5

=∑8ui+5(xi－ui)i=k5

=∑8ui+5(xi－ui)i=15第39頁，共193頁，2023年，2月20日，星期四學(xué)習(xí)目標：1掌握最優(yōu)化原理的內(nèi)容2掌握逆序解法3動態(tài)規(guī)劃的基本思想與基本原理第40頁，共193頁，2023年，2月20日，星期四多階段決策過程的最優(yōu)化一般有三種思路求解1.全枚舉法或窮舉法：它的基本思想是列舉出所有可能發(fā)生的方案和結(jié)果，再對它們一一進行比較，求出最優(yōu)方案。可以計算：從A到E的路程可分為4個階段。第一段走法有3種，第二段走法有3種，第三段走法有2種，第四段走法僅1種，共有3×3×2×1＝18條可能的路線，分別算出各條路線的距離，最后進行比較，可知最優(yōu)路線是A→B3→C2→D2→E，最短距離是11。用窮舉法求最優(yōu)路線的計算工作量將會十分龐大，而且其中包含著許多重復(fù)計算。第41頁，共193頁，2023年，2月20日，星期四2.局部最優(yōu)路徑法：某人從k點出發(fā)，并不顧及全線是否最短，只是選擇當(dāng)前最短途徑，“逢近便走”，錯誤地以為局部最優(yōu)會致整體最優(yōu)，在這種想法指導(dǎo)下，所取決策必是A→B1→C2→D2→E，全程長度是14；顯然，這種方法的結(jié)果常是錯誤的。第42頁，共193頁，2023年，2月20日，星期四□小結(jié)：◎全枚舉法雖可找出最優(yōu)方案，但不是個好算法，◎局部最優(yōu)法則完全是個錯誤方法，◎只有動態(tài)規(guī)劃方法屬較科學(xué)有效的算法第43頁，共193頁，2023年，2月20日，星期四□作為一個全過程的最優(yōu)策略具有這樣的性質(zhì)：對于最優(yōu)策略過程中的任意狀態(tài)而言，無論其過去的狀態(tài)和決策如何，余下的諸決策必構(gòu)成一個最優(yōu)子策略。（一個最優(yōu)策略的子策略總是最優(yōu)的）3.貝爾曼最優(yōu)化原理（動態(tài)規(guī)劃方法）□作該原理的具體解釋是，若某一全過程最優(yōu)策略為：

p1n*(x1)={u1*(x1),···,uk*(xk),uk+1*(xk+1),···,un*(xn)}則對上述策略中所隱含的任一狀態(tài)（xk）而言，第k子過程上對應(yīng)于xk的最優(yōu)策略必然包含在上述全過程最優(yōu)策略p1n*中，即為pkn*(xk)={uk*(xk),uk+1*(xk+1),···,un*(xn)}第44頁，共193頁，2023年，2月20日，星期四C1D1AB3D2EC2□反證法進行證明□最優(yōu)性原理在最短路線中的應(yīng)用在最短路線中，若找到了A→B3→C2→D2→E是由A到E的最短路線，則B3→C2→D2→E必是由B3出發(fā)到E點的所有可能選擇的不同路線中的最短路線。（一個最優(yōu)策略的子策略總是最優(yōu)的）第45頁，共193頁，2023年，2月20日，星期四4.函數(shù)基本方程基于這個原理，提出了一種逆序遞推法；該法的關(guān)鍵在于給出一種遞推關(guān)系。一般把這種遞推關(guān)系稱為動態(tài)規(guī)劃的函數(shù)基本方程。對于求最小的加法的基本方程為（如例1）：

fk(xk

)=min{vk(xk,uk)+

fk+1(xk+1)}fn+1(xn+1)=0邊界條件uk∈Dk第46頁，共193頁，2023年，2月20日，星期四□用函數(shù)基本方程逆推求解是常用的方法：首先要有效地建立動態(tài)規(guī)劃模型，然后再遞推求解，最后得出結(jié)論?！跽_地建立一個動態(tài)規(guī)劃模型，是解決問題的關(guān)鍵。第47頁，共193頁，2023年，2月20日，星期四5.標號法（只適用于一類最優(yōu)路線問題的特殊解法）標號法是借助網(wǎng)絡(luò)圖通過分段標號來求出最優(yōu)路線的一種簡便、直觀的方法。通常標號法采取“逆序求解”的方法來尋找問題的最優(yōu)解，即從最后階段開始，逐次向階段數(shù)小的方向推算，最終求得全局最優(yōu)解。行進方向動態(tài)規(guī)劃尋優(yōu)途徑EA第48頁，共193頁，2023年，2月20日，星期四□標號法的一般步驟：

（1）給最后一段標號，該段各狀態(tài)（即各始點）到終點的距離用數(shù)字分別標在各點上方的方格內(nèi)，并用粗箭線連接各點和終點。

（2）向前遞推，給前一階段的各個狀態(tài)標號。每個狀態(tài)上方方格內(nèi)的數(shù)字表示該狀態(tài)到終點的最短距離。將剛標號的點沿著最短距離用粗箭線連接起來，表示出各剛標號的點到終點的最短路線。

（3）逐次向前遞推，直到將第一階段的狀態(tài)（即起點）標號，起點方格內(nèi)的數(shù)字就是起點到終點的最短距離，從起點開始連接終點的粗箭線就是最短路線。第49頁，共193頁，2023年，2月20日，星期四第（1）步k=5□

f5(x5)=f5(E)=

0這是邊界條件[0]Efk(xk)表示從第k階段狀態(tài)xk

到E點的的最短距離第50頁，共193頁，2023年，2月20日，星期四第（2）步k=4□狀態(tài)變量x4可取兩種狀態(tài)D1、D2。

◎由D1到終點E只有一條路線，路長為3，即f4(D1)=3?！蛲?，f4(D2)=4。[3]□表示由D1點至E點的最短路長為3。[4][0]D1第51頁，共193頁，2023年，2月20日，星期四第（3）步k=3□狀態(tài)變量x3可取三個值：C1、C2、C3。①由C1到終點E有2條路線，分別為經(jīng)過D1、D2到達E點（由D1、D2到達E點的最短路長在第一步已計算得出），需加以比較，取其中最短的。□路線1v3(C1,D1)+f4(D1)

=1+3=4□路線2v3(C1,D2)+f4(D2)

=4+4=8[3][4]□則由C1到終點E的最短距離

f3(C1)=min{v3(C1,D1)+f4(D1),

v3(C1,D2)+f4(D2)}=4[4]C1第52頁，共193頁，2023年，2月20日，星期四第（3）步k=3②由C2到終點E有2條路線，分別為經(jīng)過D1、D2到達E點（由D1、D2到達E點的最短路長在第一步已計算得出），需加以比較，取其中最短的?！趼肪€1v3(C2,D1)+f4(D1)

=6+3=9□路線2v3(C2,D2)+f4(D2)

=3+4=7[3][4]□則由C2到終點E的最短距離

f3(C2)=min{v3(C2,D1)+f4(D1),

v3(C2,D2)+f4(D2)}=7C2[7][4]第53頁，共193頁，2023年，2月20日，星期四第（3）步k=3③由C3到終點E有2條路線，分別為經(jīng)過D1、D2到達E點（由D1、D2到達E點的最短路長在第一步已計算得出），需加以比較，取其中最短的?！趼肪€1v3(C3,D1)+f4(D1)

=3+3=6□路線2v3(C3,D2)+f4(D2)

=3+4=7[3][4]□則由C3到終點E的最短距離

f3(C3)=min{v3(C3,D1)+f4(D1),

v3(C3,D2)+f4(D2)}=6C3[7][4][6]第54頁，共193頁，2023年，2月20日，星期四第（4）步k=2□狀態(tài)變量x2可取三個值：B1、B2、B3。①由B1到終點E，可分別經(jīng)過C1、C2、C3到達E點（由C1、C2、C3到E點的最短距離在第二步已計算出），需加以比較，取其中最短的。□路線1v2(B1,C1)+f3(C1)

=7+4=11□路線2v2(B1,C2)+f3(C2)

=5+7=12□路線3v2(B1,C3)+f3(C3)

=6+6=12[3][4]□則由B1到終點E的最短距離

f2(B1)=min{v2(B1,C1)+f3(C1),v2(B1,C2)+f3(C2)

v2(B1,C3)+f3(C3)}=11[4]B1[7][6][11]第55頁，共193頁，2023年，2月20日，星期四第（4）步k=2②由B2到終點E，可分別經(jīng)過C1、C2、C3到達E點（由C1、C2、C3到E點的最短距離在第二步已計算出），需加以比較，取其中最短的?！趼肪€1v2(B2,C1)+f3(C1)

=3+4=7□路線2v2(B2,C2)+f3(C2)

=2+7=9□路線3v2(B2,C3)+f3(C3)

=4+6=10[3][4]□則由B2到終點E的最短距離

f2(B2)=min{v2(B2,C1)+f3(C1),v2(B2,C2)+f3(C2)

v2(B2,C3)+f3(C3)}=7[4]B2[7][6][11][7]第56頁，共193頁，2023年，2月20日，星期四第（4）步k=2③由B3到終點E，可分別經(jīng)過C1、C2、C3到達E點（由C1、C2、C3到E點的最短距離在第二步已計算出），需加以比較，取其中最短的。□路線1v2(B3,C1)+f3(C1)

=5+4=9□路線2v2(B3,C2)+f3(C2)

=1+7=8□路線3v2(B3,C3)+f3(C3)

=5+6=11[3][4]□則由B3到終點E的最短距離

f2(B3)=min{v2(B3,C1)+f3(C1),v2(B3,C2)+f3(C2)

v2(B3,C3)+f3(C3)}=8[4]B3[7][6][11][7][8]第57頁，共193頁，2023年，2月20日，星期四第（5）步k=1□狀態(tài)變量x1只取一個值：A。由A到終點E，可分別經(jīng)過B1、B2、B3到達E點（由B1、B2、B3到E點的最短距離在第三步已計算出），需加以比較，取其中最短的?！踅?jīng)過B1點v1(A,B1)+f2(B1)

=2+11=13□經(jīng)過B2點v1(A,B2)+f2(B2)

=5+7=12□經(jīng)過B3點v1(A,B3)+f2(B3)

=3+8=11[3][4]□則由A到終點E的最短距離

f1(A

)=min{v1(A,B1)+f2(B1),v1(A,B2)+f2(B2)

v1(A,B3)+f2(B3)}=11[4]A[7][6][11][7][8][11]第58頁，共193頁，2023年，2月20日，星期四□從下圖反推可得到最優(yōu)路線。[3][4][4]A[7][6][11][7][8][11]□因此，由A到終點E的最優(yōu)解為：

A→B3→C2→D2→E□由點A到終點E的最優(yōu)值為11。第59頁，共193頁，2023年，2月20日，星期四□小結(jié)：在求解的各階段，都利用了第k階和第k+1段的如下關(guān)系：fk(xk

)=min{vk(xk,uk)+fk+1(xk+1)}(1)

f5(x5=E)=0(2)□上述遞推關(guān)系稱為動態(tài)規(guī)劃的基本方程?！跗渲校?）式稱為邊界條件。[3][4][4]A[7][6][11][7][8][11]第60頁，共193頁，2023年，2月20日，星期四動態(tài)規(guī)劃方法的優(yōu)點1.減少計算量動態(tài)規(guī)劃方法減少了計算量，而且隨著階段數(shù)的增加，計算量將大大減少。2.豐富了計算結(jié)果在動態(tài)規(guī)劃的解法中，得到的不僅僅是由A點出發(fā)到E點的最短路線及相應(yīng)距離，而且得到了從所有中間點出發(fā)到E點的最短路線及相應(yīng)距離。這對于許多實際問題來說是很有用的，有利于幫助分析所得的結(jié)果。第61頁，共193頁，2023年，2月20日，星期四動態(tài)規(guī)劃方法的基本思想1.將多階段決策過程劃分階段，恰當(dāng)?shù)剡x擇狀態(tài)變量、決策變量，定義最優(yōu)指標函數(shù)，從而把問題化成一簇同類型的子問題，然后逐個求解。2.求解時從邊界條件開始，逆過程方向行進，逐段遞推尋優(yōu)，在每一個子問題求解時，都要使用它前面已求出的子問題的最優(yōu)結(jié)果，最后一個子問題的最優(yōu)解，就是整個問題的最優(yōu)解。第62頁，共193頁，2023年，2月20日，星期四學(xué)習(xí)目標：1了解順序解法4逆序解法和順序解法第63頁，共193頁，2023年，2月20日，星期四□動態(tài)規(guī)劃的求解有兩種基本方法

◎逆序解法（后向動態(tài)規(guī)劃方法）如例1所使用的方法，尋優(yōu)的方向與多階段決策過程的實際行進方向相反，從最后一段開始計算逐段前推，求得全過程的最優(yōu)策略。◎順序解法（前向動態(tài)規(guī)劃方法）與逆序解法相反，順序解法的尋優(yōu)的方向與過程的行進方向相同，計算時從第一段開始逐段向后遞推，計算后一段要用到前一段的求優(yōu)結(jié)果，最后一段計算的結(jié)果就是全過程的最優(yōu)結(jié)果。第64頁，共193頁，2023年，2月20日，星期四□我們再次用例1來說明順序解法?！跤捎诖藛栴}的始點A與終點E都是固定的，計算由A點到E點的最短路線與由E點到A點的最短路線沒有什么不同。□若設(shè)

fk(xk+1)

表示從起點A到第k階段末狀態(tài)點xk+1的最短距離就可以由前向后逐步求出起點A到各階段末狀態(tài)點的最短距離，最后求出起點A到E點的最短距離及路線。動態(tài)規(guī)劃的目標：最優(yōu)指標

f4(E)第65頁，共193頁，2023年，2月20日，星期四第一步k=0□

f0(x1)=f0(A)=

0這是邊界條件[0]Afk(xk+1)表示從起點A到第k階段末狀態(tài)點xk+1的最短距離第66頁，共193頁，2023年，2月20日，星期四第二步k=1[2][3][5][0]□按f1(x2)的定義有

f1(B1)=v(B1,A)+f0(A)=2

f1(B2)=v(B2,A)+f0(A)=5

f1(B3)=v(B3,A)+f0(A)=3B1B2B3第67頁，共193頁，2023年，2月20日，星期四第三步k=2[2][3][5][0]□按f2(x3)的定義有

①

v(C1,B1)+f1(B1)=7+2=9

f2(C1)=min

v(C1,B2)+f1(B2)=3+5=8v(C1,B3)+f1(B3)=5+3=8□u2(C1)=B2或B3[8]C1□狀態(tài)轉(zhuǎn)移方程：

xk=Tk(xk+1,uk)第68頁，共193頁，2023年，2月20日，星期四第三步k=2[2][3][5][0]□按f2(x3)的定義有

②

v(C2,B1)+f1(B1)=5+2=7

f2(C2)=min

v(C2,B2)+f1(B2)=2+5=7v(C2,B3)+f1(B3)=1+3=4□u2(C2)=B3[8][4]C2第69頁，共193頁，2023年，2月20日，星期四第三步k=2[2][3][5][0]□按f2(x3)的定義有

③

v(C3,B1)+f1(B1)=6+2=8

f2(C3)=min

v(C3,B2)+f1(B2)=4+5=9v(C3,B3)+f1(B3)=5+3=8[8][4]□u2(C3)=B1或B3[8]C3第70頁，共193頁，2023年，2月20日，星期四第四步k=3[2][3][5][0]□按f3(x4)的定義有

①

v(D1,C1)+f2(C1)=1+8=9

f3(D1)=min

v(D1,C2)+f2(C2)=6+4=10v(D1,C3)+f2(C3)=3+8=11[8][4]□u3(D1)=C1[8][9]D1第71頁，共193頁，2023年，2月20日，星期四第四步k=3[2][3][5][0]□按f3(x4)的定義有

②

v(D2,C1)+f2(C1)=4+8=12

f3(D2)=min

v(D2,C2)+f2(C2)=3+4=7v(D2,C3)+f2(C3)=3+8=11[8][4]□u3(D2)=C2[8][9][7]D2第72頁，共193頁，2023年，2月20日，星期四第五步k=4[2][3][5][0]□按f4(x5)的定義有v(E,D1)+f3(D1)=3+9=12

f4(E)=min

v(E,D2)+f3(D2)=4+7=11[8][4]□u4(E)=D2[8][9][7][11]E第73頁，共193頁，2023年，2月20日，星期四[2][3][5][0][8][4][8][9][7]□即可得到最優(yōu)路線?！跻虼?，由A到終點E的最優(yōu)解為：

A→B3→C2→D2→E□由點A到終點E的最優(yōu)值為11。[11]第74頁，共193頁，2023年，2月20日，星期四課堂練習(xí)從A地到D地要鋪設(shè)一條煤氣管道,其中需經(jīng)過兩級中間站，兩點之間的連線上的數(shù)字表示距離，如圖所示。問應(yīng)該選擇什么路線，使總距離最短？AB1B2C1C2C3D24333321114第75頁，共193頁，2023年，2月20日，星期四解：整個計算過程分三個階段，從最后一個階段開始第一階段（C→D）：C

有三條路線到終點D。顯然有f3(C1)=1；

f3(C2)=3；

f3(C3)=4AB1B2C1C2C3D2433321114C1C2C3第76頁，共193頁，2023年，2月20日，星期四第二階段（B→C）：B到C

有六條路線。d(B1,C1)+f3(C1)3+1f2(B1)=mind(B1,C2)+f3(C2)=min3+3d(B1,C3)+f3(C3)1+44=min6=45AB1B2C1C2C3D24333321114B1B2第77頁，共193頁，2023年，2月20日，星期四

d(B2,C1)+f3(C1)2+1f2(B2)=mind(B2,C2)+f3(C2)=min3+3d(B2,C3)+f3(C3)1+43=min6=35AB1B2C1C2C3D24333321114B1B2第78頁，共193頁，2023年，2月20日，星期四第三階段（A→B）：A到B有二條路線。f1(A)=min=min｛6,7｝=6AB1B2C1C2C3D24333321114Ad(A,B1)＋f2(B1)d(A,B2)＋f2(B2)(最短路線為A→B1→C1→D)第79頁，共193頁，2023年，2月20日，星期四練習(xí)P156例2機器負荷分配問題（時間階段問題）◎設(shè)有某種機器設(shè)備，用于完成兩類工作A和B。若第k年初完好機器的數(shù)量為xk，若以數(shù)量uk用于A，余下的（xk－uk）用于工作B，則該年的預(yù)期收入為g(uk)+h(xk－uk)。其中g(shù)(uk)＝8uk

，h(xk－uk)=5（xk－uk）?！蛴謾C器設(shè)備在使用中會有損壞，設(shè)機器用于工作A時，一年后能繼續(xù)使用的完好機器數(shù)占年初投入量的70%；若用于工作B時，一年后能繼續(xù)使用的完好機器數(shù)占年初投入量的90%。則在下一年初能繼續(xù)用于A、B工作的設(shè)備數(shù)為xk+1=0.7uk+0.9(xk－uk)?！蛟O(shè)第1年初完好的機器總數(shù)為1000臺，問在連續(xù)5年內(nèi)每年應(yīng)如何分配用于A、B兩項工作的機器數(shù)，使5年的總收益為最大。第80頁，共193頁，2023年，2月20日，星期四□構(gòu)造動態(tài)規(guī)劃模型如下：

階段k：運行年份（k=1,2,···,6）,其中k=1表示第一年初，…，

依次類推；k=6表示第5年末（即第6年初）。

狀態(tài)變量xk：第k年初完好的機器數(shù)（k=1,2,···,4），其中x6表

示第5年末（即第6年初）的完好機器數(shù)。

決策變量uk：第k年度中分配于A工作的機器數(shù)量，則xk－uk為

用于B工作的機器數(shù)量。

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

)

決策允許集合：Dk(xk

)={uk|0≤uk≤xk

}

階段指標：vk(xk

,uk

)=8uk+5(xk－uk

)

終端條件：f6(x6)=0第81頁，共193頁，2023年，2月20日，星期四遞推方程：fk(xk

)=max{vk(xk,uk

)+fk+1(xk+1)}

dkDk(xk)

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

0≤dk≤xk

◎這里xk和uk均取連續(xù)變量，它們的非整數(shù)值可以這樣理解，如xk=0.6，就表示一臺機器在第k年度中正常工作時間只占6/10；uk=0.3，就表示一臺機器在該年度只有3/10的時間能正常用于A工作。第82頁，共193頁，2023年，2月20日，星期四f5(x5)

=max{8u5+5(x5－u5)+f6(x6

)}

0u5x5u5*=x5=max{3u5+5x5}

0u5x5=8x5f4(x4)

=max{8u4+5(x4－u4)+f5(x5)}

0u4x4=max{8u4+5(x4－u4)+8x5

}

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

xk+1=0.7uk+0.9(xk－uk

)=max{8u4+5(x4－u4)+8[0.7u4+0.9(x4－u4)

]}

0u4x4=max{1.4u4+12.2x4}

0u4x4u4*=x4=13.6x4第83頁，共193頁，2023年，2月20日，星期四f3(x3)

=max{8u3+5(x3－u3)+f4(x4)}

0u3x3=max{8u3+5(x3－u3)+13.6x4

}

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

xk+1=0.7uk+0.9(xk－uk

)=max{8u3+5(x3－u3)+13.6[0.7u3+0.9(x3－u3)

]}

0u3x3=max{0.28u3+17.22x3}

0u3x3u3*=x3=17.5x3第84頁，共193頁，2023年，2月20日，星期四f2(x2)

=max{8u2+5(x2－u2)+f3(x3)}

0u2x2=max{8u2+5(x2－u2)+17.5x3

}

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

xk+1=0.7uk+0.9(xk－uk

)=max{8u2+5(x2－u2)+17.5[0.7u2+0.9(x2－u2)

]}

0u2x2=max{－0.504u2+20.8x2}

0u2x2u2*=0=20.8x2第85頁，共193頁，2023年，2月20日，星期四f1(x1)

=max{8u1+5(x1－u1)+f2(x2)}

0u1x1=max{8u1+5(x1－u1)+20.8x2

}

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

xk+1=0.7uk+0.9(xk－uk

)=max{8u1+5(x1－u1)+20.8[0.7u1+0.9(x1－u1)

]}

0u1x1=max{－0.05u1+23.7x1}

0u1x1u1*=0=23.7x1第86頁，共193頁，2023年，2月20日，星期四由此可以得到：f1(x1)=23.7x1, u1*=0f2(x2)=20.8x2, u2*=0f3(x3)=17.5x3, u3*=x3f4(x4)=13.6x4, u4*=x4f5(x5)=8x5

u5*=x5用x1=1000代入，得到五年最大總收入為f1(x1)=f1(1000)=23700第87頁，共193頁，2023年，2月20日，星期四年度年初完好機器數(shù)用于工作A的數(shù)量用于工作B的數(shù)量1x1=1000u1*=02x2=0.7u1

+0.9(x1－u1)u2*=03x3=0.7u2

+0.9(x2－u2)u3*=x34x4=0.7u3

+0.9(x3－u3)u4*=x45x5=0.7u4

+0.9(x4－u4)u5*=x5x1－u1=1000x2=900x2－u2=900x3=810u3=810x3－u3=0x4=567u4=567x4－u4=0x5=397u5=397x5－u5=0第88頁，共193頁，2023年，2月20日，星期四例4某一警衛(wèi)部門共有12支巡邏隊，負責(zé)4個要害部位A、B、C、Dde警衛(wèi)巡邏。對每個部位可分別派出2～4支巡邏隊，并且由于派出巡邏隊隊數(shù)不同，各部位預(yù)期在一段時間內(nèi)可能造成的損失由差別，具體數(shù)字見表。問該警衛(wèi)部門分別派多少支巡邏隊，使總的預(yù)期損失為最小。ABCD218382434314352231410312125第89頁，共193頁，2023年，2月20日，星期四解把12支巡邏隊伍往4部位看成依次分4個階段（用k表示，k=1,2,3,4)(1)逆序解法每個階段初擁有的可派遣的巡邏隊數(shù)是前面階段決策的結(jié)果，用狀態(tài)變量來表示。各階段的決策變量就是對各部位派出的巡邏隊數(shù)，用表示，顯然個階段允許的決策集合為英每階段初擁有可派遣的巡邏隊