運(yùn)籌學(xué) 第八章動(dòng)態(tài)規(guī)劃

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

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

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

動(dòng)態(tài)規(guī)劃實(shí)例2動(dòng)態(tài)規(guī)劃的基本概念3動(dòng)態(tài)規(guī)劃的基本思想與基本原理4逆序解法與順序解法第4頁，共193頁，2023年，2月20日，星期四學(xué)習(xí)目標(biāo)：1明確什么是多階段的決策問題，特別要注意沒有明顯的時(shí)段背景的問題如何化歸為多階段的決策問題。1動(dòng)態(tài)規(guī)劃實(shí)例第5頁，共193頁，2023年，2月20日，星期四P156例2機(jī)器負(fù)荷分配問題（時(shí)間階段問題）◎設(shè)有某種機(jī)器設(shè)備，用于完成兩類工作A和B。若第k年初完好機(jī)器的數(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(jī)器設(shè)備在使用中會有損壞，設(shè)機(jī)器用于工作A時(shí)，一年后能繼續(xù)使用的完好機(jī)器數(shù)占年初投入量的70%；若用于工作B時(shí)，一年后能繼續(xù)使用的完好機(jī)器數(shù)占年初投入量的90%。則在下一年初能繼續(xù)用于A、B工作的設(shè)備數(shù)為xk+1=0.7uk+0.9(xk－uk)。◎設(shè)第1年初完好的機(jī)器總數(shù)為1000臺，問在連續(xù)5年內(nèi)每年應(yīng)如何分配用于A、B兩項(xiàng)工作的機(jī)器數(shù)，使5年的總收益為最大。1動(dòng)態(tài)規(guī)劃實(shí)例第6頁，共193頁，2023年，2月20日，星期四□相應(yīng)的問題稱為多階段決策問題。□這是一個(gè)多階段決策過程?！踉撨^程可以分為相互聯(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è)有一個(gè)旅行者從下圖中的A點(diǎn)出發(fā)，途中要經(jīng)過B、C、D等處，最后到達(dá)終點(diǎn)E。從A到E有很多條路線可以選擇，各點(diǎn)之間的距離如圖所示，問該旅行者應(yīng)選擇哪一條路線，使從A到達(dá)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日，星期四□從以上兩個(gè)例子，可以知道所謂多階段決策問題是指這樣的決策問題：其過程可分為若干個(gè)相互聯(lián)系的階段，每一階段都對應(yīng)著一組可供選擇的決策，每一決策的選定既依賴于當(dāng)前面臨的狀態(tài)，又影響以后總體的效果。

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

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

xk

)表示第k階段當(dāng)狀態(tài)處于xk時(shí)的決策變量，它是狀態(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時(shí)決策變量uk(xk)的取值范稱為決策集合，常用Dk(xk)表示?！趵?中，從第2階段的狀態(tài)B1出發(fā)，可以選擇下一階段的C1、C2、C3?！跫碊2(B1)={C1、C2、C3}；B1C1C2C3□決策集合實(shí)際上是決策的約束條件，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）□策略：由依次進(jìn)行的n個(gè)階段決策構(gòu)成的決策序列就構(gòu)成一個(gè)策略，用p1n{u1(x1),u2(x2),…,un(xn)}表示。25375632455114633334C1C3D1AB1B3B2D2EC2□本例中，如p14{u1(A)=B1,u2(B1)=C2,u3(C2)=D1,

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

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

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日，星期四□過程指標(biāo)函數(shù)Vkn通常是描述所實(shí)現(xiàn)的全過程或k后部子過程效果優(yōu)劣的數(shù)量指標(biāo)，它是由各階段的階段指標(biāo)函數(shù)vk(xk,uk)累積形成的。（1）可分性：適于用動(dòng)態(tài)規(guī)劃求解的問題的過程指標(biāo)函數(shù)（即目標(biāo)函數(shù)），必須具有關(guān)于階段指標(biāo)的可分離形式，即對于后部子過程的指標(biāo)函數(shù)可以表示為：

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

vk(xk,uk)

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

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

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

總之，具體問題的目標(biāo)函數(shù)表達(dá)形式需要視具體問題而定。Vkn=∑vi（xi,ui）i=kn(8.3a)Vkn=∏vi（xi,ui）i=kn(8.3b)第29頁，共193頁，2023年，2月20日，星期四（2）可遞推：過程指標(biāo)函數(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)指標(biāo)函數(shù)：表示從第k階段狀態(tài)為xk時(shí)采用最優(yōu)策略pkn*到過程終止時(shí)的最佳效益值。記為fk(xk)。

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

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

f1=opt

V1n(x1

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

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

uk∈Dk決策變量xk∈Sk

狀態(tài)變量

k=1,2,…,n

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

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

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

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)策略時(shí)的狀態(tài)序列{u1*,u2*,…,un*}{x1*,x2*,…,xn*}最優(yōu)目標(biāo)函數(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.確定階段指標(biāo)函數(shù)和最優(yōu)指標(biāo)函數(shù)，建立動(dòng)態(tài)規(guī)劃基本方程劃分階段是運(yùn)用動(dòng)態(tài)規(guī)劃求解多階段決策問題的第一步，在確定多階段特性后，按時(shí)間或空間先后順序，將過程劃分為若干相互聯(lián)系的階段。對于靜態(tài)問題要人為地賦予“時(shí)間”概念，以便劃分階段。建立動(dòng)態(tài)規(guī)劃模型的步驟

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

=∑vi（xi,ui）i=15

=∑g(ui)+h(xi－ui)i=15令最優(yōu)指標(biāo)函數(shù)fk(xk)表示由資源量xk出發(fā)，從第k年開始到第5年結(jié)束時(shí)所取得的最大預(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í)目標(biāo)：1掌握最優(yōu)化原理的內(nèi)容2掌握逆序解法3動(dòng)態(tài)規(guī)劃的基本思想與基本原理第40頁，共193頁，2023年，2月20日，星期四多階段決策過程的最優(yōu)化一般有三種思路求解1.全枚舉法或窮舉法：它的基本思想是列舉出所有可能發(fā)生的方案和結(jié)果，再對它們一一進(jìn)行比較，求出最優(yōu)方案?？梢杂?jì)算：從A到E的路程可分為4個(gè)階段。第一段走法有3種，第二段走法有3種，第三段走法有2種，第四段走法僅1種，共有3×3×2×1＝18條可能的路線，分別算出各條路線的距離，最后進(jìn)行比較，可知最優(yōu)路線是A→B3→C2→D2→E，最短距離是11。用窮舉法求最優(yōu)路線的計(jì)算工作量將會十分龐大，而且其中包含著許多重復(fù)計(jì)算。第41頁，共193頁，2023年，2月20日，星期四2.局部最優(yōu)路徑法：某人從k點(diǎn)出發(fā)，并不顧及全線是否最短，只是選擇當(dāng)前最短途徑，“逢近便走”，錯(cuò)誤地以為局部最優(yōu)會致整體最優(yōu)，在這種想法指導(dǎo)下，所取決策必是A→B1→C2→D2→E，全程長度是14；顯然，這種方法的結(jié)果常是錯(cuò)誤的。第42頁，共193頁，2023年，2月20日，星期四□小結(jié)：◎全枚舉法雖可找出最優(yōu)方案，但不是個(gè)好算法，◎局部最優(yōu)法則完全是個(gè)錯(cuò)誤方法，◎只有動(dòng)態(tài)規(guī)劃方法屬較科學(xué)有效的算法第43頁，共193頁，2023年，2月20日，星期四□作為一個(gè)全過程的最優(yōu)策略具有這樣的性質(zhì)：對于最優(yōu)策略過程中的任意狀態(tài)而言，無論其過去的狀態(tài)和決策如何，余下的諸決策必構(gòu)成一個(gè)最優(yōu)子策略。（一個(gè)最優(yōu)策略的子策略總是最優(yōu)的）3.貝爾曼最優(yōu)化原理（動(dòng)態(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□反證法進(jìn)行證明□最優(yōu)性原理在最短路線中的應(yīng)用在最短路線中，若找到了A→B3→C2→D2→E是由A到E的最短路線，則B3→C2→D2→E必是由B3出發(fā)到E點(diǎn)的所有可能選擇的不同路線中的最短路線。（一個(gè)最優(yōu)策略的子策略總是最優(yōu)的）第45頁，共193頁，2023年，2月20日，星期四4.函數(shù)基本方程基于這個(gè)原理，提出了一種逆序遞推法；該法的關(guān)鍵在于給出一種遞推關(guān)系。一般把這種遞推關(guān)系稱為動(dòng)態(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ù)基本方程逆推求解是常用的方法：首先要有效地建立動(dòng)態(tài)規(guī)劃模型，然后再遞推求解，最后得出結(jié)論?！跽_地建立一個(gè)動(dòng)態(tài)規(guī)劃模型，是解決問題的關(guān)鍵。第47頁，共193頁，2023年，2月20日，星期四5.標(biāo)號法（只適用于一類最優(yōu)路線問題的特殊解法）標(biāo)號法是借助網(wǎng)絡(luò)圖通過分段標(biāo)號來求出最優(yōu)路線的一種簡便、直觀的方法。通常標(biāo)號法采取“逆序求解”的方法來尋找問題的最優(yōu)解，即從最后階段開始，逐次向階段數(shù)小的方向推算，最終求得全局最優(yōu)解。行進(jìn)方向動(dòng)態(tài)規(guī)劃尋優(yōu)途徑EA第48頁，共193頁，2023年，2月20日，星期四□標(biāo)號法的一般步驟：

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

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

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

f5(x5)=f5(E)=

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

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

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

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

=4+4=8[3][4]□則由C1到終點(diǎn)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到終點(diǎn)E有2條路線，分別為經(jīng)過D1、D2到達(dá)E點(diǎn)（由D1、D2到達(dá)E點(diǎn)的最短路長在第一步已計(jì)算得出），需加以比較，取其中最短的?！趼肪€1v3(C2,D1)+f4(D1)

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

=3+4=7[3][4]□則由C2到終點(diǎn)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到終點(diǎn)E有2條路線，分別為經(jīng)過D1、D2到達(dá)E點(diǎn)（由D1、D2到達(dá)E點(diǎn)的最短路長在第一步已計(jì)算得出），需加以比較，取其中最短的?！趼肪€1v3(C3,D1)+f4(D1)

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

=3+4=7[3][4]□則由C3到終點(diǎn)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可取三個(gè)值：B1、B2、B3。①由B1到終點(diǎn)E，可分別經(jīng)過C1、C2、C3到達(dá)E點(diǎn)（由C1、C2、C3到E點(diǎn)的最短距離在第二步已計(jì)算出），需加以比較，取其中最短的。□路線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到終點(diǎn)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到終點(diǎn)E，可分別經(jīng)過C1、C2、C3到達(dá)E點(diǎn)（由C1、C2、C3到E點(diǎn)的最短距離在第二步已計(jì)算出），需加以比較，取其中最短的?！趼肪€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到終點(diǎn)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到終點(diǎn)E，可分別經(jīng)過C1、C2、C3到達(dá)E點(diǎn)（由C1、C2、C3到E點(diǎn)的最短距離在第二步已計(jì)算出），需加以比較，取其中最短的?！趼肪€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到終點(diǎn)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只取一個(gè)值：A。由A到終點(diǎn)E，可分別經(jīng)過B1、B2、B3到達(dá)E點(diǎn)（由B1、B2、B3到E點(diǎn)的最短距離在第三步已計(jì)算出），需加以比較，取其中最短的?！踅?jīng)過B1點(diǎn)v1(A,B1)+f2(B1)

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

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

=3+8=11[3][4]□則由A到終點(diǎn)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到終點(diǎn)E的最優(yōu)解為：

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

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

fk(xk+1)

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

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

f0(x1)=f0(A)=

0這是邊界條件[0]Afk(xk+1)表示從起點(diǎn)A到第k階段末狀態(tài)點(diǎn)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到終點(diǎn)E的最優(yōu)解為：

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

有三條路線到終點(diǎn)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機(jī)器負(fù)荷分配問題（時(shí)間階段問題）◎設(shè)有某種機(jī)器設(shè)備，用于完成兩類工作A和B。若第k年初完好機(jī)器的數(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(jī)器設(shè)備在使用中會有損壞，設(shè)機(jī)器用于工作A時(shí)，一年后能繼續(xù)使用的完好機(jī)器數(shù)占年初投入量的70%；若用于工作B時(shí)，一年后能繼續(xù)使用的完好機(jī)器數(shù)占年初投入量的90%。則在下一年初能繼續(xù)用于A、B工作的設(shè)備數(shù)為xk+1=0.7uk+0.9(xk－uk)。◎設(shè)第1年初完好的機(jī)器總數(shù)為1000臺，問在連續(xù)5年內(nèi)每年應(yīng)如何分配用于A、B兩項(xiàng)工作的機(jī)器數(shù)，使5年的總收益為最大。第80頁，共193頁，2023年，2月20日，星期四□構(gòu)造動(dòng)態(tài)規(guī)劃模型如下：

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

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

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

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

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

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

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

)

決策允許集合：Dk(xk

)={uk|0≤uk≤xk

}

階段指標(biāo)：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，就表示一臺機(jī)器在第k年度中正常工作時(shí)間只占6/10；uk=0.3，就表示一臺機(jī)器在該年度只有3/10的時(shí)間能正常用于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日，星期四年度年初完好機(jī)器數(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支巡邏隊(duì)，負(fù)責(zé)4個(gè)要害部位A、B、C、Dde警衛(wèi)巡邏。對每個(gè)部位可分別派出2～4支巡邏隊(duì)，并且由于派出巡邏隊(duì)隊(duì)數(shù)不同，各部位預(yù)期在一段時(shí)間內(nèi)可能造成的損失由差別，具體數(shù)字見表。問該警衛(wèi)部門分別派多少支巡邏隊(duì)，使總的預(yù)期損失為最小。ABCD218382434314352231410312125第89頁，共193頁，2023年，2月20日，星期四解把12支巡邏隊(duì)伍往4部位看成依次分4個(gè)階段（用k表示，k=1,2,3,4)(1)逆序解法每個(gè)階段初擁有的可派遣的巡邏隊(duì)數(shù)是前面階段決策的結(jié)果，用狀態(tài)變量來表示。各階段的決策變量就是對各部位派出的巡邏隊(duì)數(shù)，用表示，顯然個(gè)階段允許的決策集合為英每階段初擁有可派遣的巡邏隊(duì)