動(dòng)態(tài)規(guī)劃a課件

第八章動(dòng)態(tài)規(guī)劃8.1多階段決策問(wèn)題8.2動(dòng)態(tài)規(guī)劃的基本概念和基本方程8.3最優(yōu)性定理8.4動(dòng)態(tài)規(guī)劃的建模與求解方法8.5動(dòng)態(tài)規(guī)劃應(yīng)用舉例1第八章動(dòng)態(tài)規(guī)劃8.1多階段決策問(wèn)題1動(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)立了解決這類(lèi)過(guò)程優(yōu)化問(wèn)題的新方法——?jiǎng)討B(tài)規(guī)劃。1957年出版了他的名著DynamicProgramming，這是該領(lǐng)域的第一本著作。動(dòng)態(tài)規(guī)劃問(wèn)世以來(lái)，在經(jīng)濟(jì)管理、生產(chǎn)調(diào)度、工程技術(shù)和最優(yōu)控制等方面得到了廣泛的應(yīng)用。例如最短路線(xiàn)、庫(kù)存管理、資源分配、設(shè)備更新、排序、裝載等問(wèn)題，用動(dòng)態(tài)規(guī)劃方法比用其它方法求解更為方便。2動(dòng)態(tài)規(guī)劃(dynamicprogramming)是運(yùn)籌學(xué)的8.1多階段決策問(wèn)題多階段決策過(guò)程，是指這樣的一類(lèi)特殊的活動(dòng)過(guò)程，問(wèn)題可以按時(shí)間順序分解成若干相互聯(lián)系的階段，在每一個(gè)階段都要做出決策，全部過(guò)程的決策是一個(gè)決策序列。要使整個(gè)活動(dòng)的總體效果達(dá)到最優(yōu)的問(wèn)題，稱(chēng)為多階段決策問(wèn)題。決策:在多個(gè)可行方案中選擇或選定一個(gè)的過(guò)程或行為;策略:由一系列相互銜接的決策構(gòu)成的決策序列;策略集合:有可供選擇的策略構(gòu)成的集合;最優(yōu)策略:在預(yù)定標(biāo)準(zhǔn)下達(dá)到最好效果的策略.38.1多階段決策問(wèn)題多階段決策過(guò)程，是指這樣的一類(lèi)特殊的活靜態(tài)決策一次性決策動(dòng)態(tài)決策多階段決策決策s1s2vx輸入決策輸出決策效應(yīng)第一階段s1s2v1x1第二階段s3v2x2第三階段s4v3x34靜態(tài)決策一次性決策動(dòng)態(tài)決策多階段決策例1（最短路線(xiàn)問(wèn)題）給定一個(gè)線(xiàn)路網(wǎng)絡(luò)圖,兩點(diǎn)之間聯(lián)線(xiàn)上的數(shù)字表示兩點(diǎn)間的距離(或運(yùn)費(fèi)),試求一條由s到t的鋪管線(xiàn)路,使總距離最短.adbetcfs97578456465475例1（最短路線(xiàn)問(wèn)題）adbetcfs975784564654例2（資源分配問(wèn)題）某公司擬將50萬(wàn)元資金投放下屬A、B、C三個(gè)部門(mén)，各部門(mén)在獲得資金后的收益如表所示，求總收益最大的投資分配方案（投資數(shù)以10萬(wàn)元為單位）。投放資金(萬(wàn)元)01020304050收益（萬(wàn)元）

A01520252830B0010254570C010203040506例2（資源分配問(wèn)題）某公司擬將50萬(wàn)元資金投放下屬A、B、C例3（裝載問(wèn)題）已知貨物的單位重量ωi，單位體積υi及價(jià)值pi如表所示，船的最大載重能力為W＝5，最大裝載體積為V＝8，求最優(yōu)裝載方案。iωiυipi1123023480323657例3（裝載問(wèn)題）已知貨物的單位重量ωi，單位體積υi及8.2動(dòng)態(tài)規(guī)劃的基本概念和基本方程(1)動(dòng)態(tài)規(guī)劃的基本概念階段與階段變量:將所要研究的問(wèn)題,按時(shí)間或空間特征分成若干個(gè)互相聯(lián)系的階段.簡(jiǎn)稱(chēng)“階段”我們就是要按階段的順序來(lái)求解.描述階段的變量階段變量,常用字母k來(lái)表示;88.2動(dòng)態(tài)規(guī)劃的基本概念和基本方程(1)動(dòng)態(tài)規(guī)劃的基本概狀態(tài)、狀態(tài)變量和狀態(tài)集合各階段開(kāi)始時(shí)的客觀條件叫做狀態(tài).描述各階段狀態(tài)的變量叫做狀態(tài)變量,常用sk表示第ｋ階段的狀態(tài)變量；狀態(tài)變量sk的取值集合稱(chēng)為狀態(tài)集合,用Sk表示；動(dòng)態(tài)規(guī)劃中狀態(tài)具有以下性質(zhì):某階段狀態(tài)一旦確定以后過(guò)程的狀態(tài)變化不受這個(gè)狀態(tài)以前的影響,也就是說(shuō)某狀態(tài)以后的過(guò)程和以前無(wú)關(guān),只與當(dāng)前狀態(tài)有關(guān),我們稱(chēng)這種特性為“無(wú)后效性.”9狀態(tài)、狀態(tài)變量和狀態(tài)集合9決策、決策變量和策略當(dāng)個(gè)階段的狀態(tài)取定以后,就可以做出關(guān)于下一步的選擇,從而確定下一階段的狀態(tài),這種決定稱(chēng)為決策；表示決策的變量叫做決策變量,常用xk(sk)表示.第k階段當(dāng)狀態(tài)為sk時(shí)的決策變量；在實(shí)際問(wèn)題中決策變量的取值往往限制在一定的范圍內(nèi),我們稱(chēng)此范圍為允許決策集,常用Dk(sk)表示第k階段從狀態(tài)sk出發(fā)的允許決策集,因此有xk(sk)∈Dk(sk).各段決策確定后,整個(gè)問(wèn)題的決策序列就構(gòu)成了一個(gè)策略,用p1,n{x1(s1),x2(s2),…,xn(sn)}表示；10決策、決策變量和策略10使整個(gè)問(wèn)題達(dá)到最優(yōu)效果的的策略就是最優(yōu)策略.動(dòng)態(tài)規(guī)劃中本階段的狀態(tài)是上一階段的決策結(jié)果.如果給定了第k階段的狀態(tài)sk,本階段的決策就為xk(sk),則第k+1段的狀態(tài)xk+1也就完全確定了,它的關(guān)系可表示為:sk+1=Tk(sk,xk).由于它表示了由k到k=1段的狀態(tài)轉(zhuǎn)移規(guī)律,所以稱(chēng)為狀態(tài)轉(zhuǎn)移方程.T1s1s2v1(s1,x1)x1(s1)T2s3v2(s2,x2)x2(s2)Tksksk+1vk(sk,xk)xk(sk)Tnsnsn+1……vn(sn,xn)xn(sn)11使整個(gè)問(wèn)題達(dá)到最優(yōu)效果的的策略就是最優(yōu)策略.T1s1s2v1指標(biāo)函數(shù)與最優(yōu)值函數(shù)用于衡量所選定策略?xún)?yōu)劣的數(shù)量指標(biāo)稱(chēng)為指標(biāo)函數(shù).階段指標(biāo)函數(shù)vk(sk,xk)一個(gè)n段決策過(guò)程,從1到n叫作問(wèn)題的原過(guò)程,對(duì)于任意一個(gè)給定的k,從第k到n段的過(guò)程稱(chēng)為原過(guò)程的一個(gè)后部子過(guò)程.V1,n(s1,p1,n)表示初始狀態(tài)s1采用策略p1,n.時(shí)原過(guò)程指標(biāo)函數(shù)值.Vkn=(sk,xk,sk+1,xk+1,…,sn,xn)(k=1,2,…,n)V1n=(s1,x1,s2,x2,…,sn,xn)12指標(biāo)函數(shù)與最優(yōu)值函數(shù)12多段決策過(guò)程中從第k階段到最終階段的過(guò)程稱(chēng)為k-后部子過(guò)程，簡(jiǎn)稱(chēng)k-子過(guò)程。Tksksk+1vk(sk,xk)xk(xk)Tnsnsn+1…vn(sn,xn)xn(xn)13多段決策過(guò)程中從第k階段到最終階段的過(guò)程稱(chēng)為指標(biāo)函數(shù)應(yīng)具有三個(gè)條件1）指標(biāo)函數(shù)在全過(guò)程和所有后部子過(guò)程上有定義；2）指標(biāo)函數(shù)應(yīng)具有可分離性，滿(mǎn)足遞推公式Vkn=Ψ(sk,xk,Vk+1,n(sk+1,xk+1,…,sn,xn))3）函數(shù)Ψ是一個(gè)關(guān)于變量Vk+1,n單調(diào)遞增的函數(shù)。指標(biāo)函數(shù)Vkn達(dá)到最優(yōu)值，稱(chēng)為最優(yōu)值函數(shù)。fk(sk)=optVkn(sk,xk,sk+1,xk+1,…,sn,xn)

(k=1,2,…,n)

使指標(biāo)函數(shù)Vkn達(dá)到最優(yōu)值的策略是從k開(kāi)始的后部子過(guò)程的最優(yōu)策略，記作pkn*={xk*,..xn*},p1n*又是全過(guò)程的最優(yōu)策略，簡(jiǎn)稱(chēng)最優(yōu)策略。

14指標(biāo)函數(shù)應(yīng)具有三個(gè)條件14指標(biāo)函數(shù)的兩種基本形式：Ⅰ全過(guò)程和它的任一后部子過(guò)程的指標(biāo)函數(shù)等于各階段指標(biāo)函數(shù)之和Ⅱ全過(guò)程和它的任一后部子過(guò)程的指標(biāo)函數(shù)等于各階段指標(biāo)函數(shù)之積15指標(biāo)函數(shù)的兩種基本形式：Ⅱ全過(guò)程和它的任一后部子過(guò)程的指(2)最優(yōu)化原理Bellman最優(yōu)化原理“最優(yōu)策略具有的基本性質(zhì)是：無(wú)論初始狀態(tài)和初始決策如何，對(duì)于前面決策所造成的某一狀態(tài)而言，下余的決策序列必構(gòu)成最優(yōu)策略”。AMB16(2)最優(yōu)化原理Bellman最優(yōu)化原理AMB16最優(yōu)性原理的含意最優(yōu)策略的任何一部分子策略，也是相應(yīng)初始狀態(tài)的最優(yōu)策略。每個(gè)最優(yōu)策略只能由最優(yōu)子策略構(gòu)成。顯然，對(duì)于具有無(wú)后效性的多段決策過(guò)程而言，如果按照k后部子過(guò)程最優(yōu)的原則來(lái)求各階段狀態(tài)的最優(yōu)決策，那么這樣構(gòu)成的最優(yōu)決策序列或策略一定具有最優(yōu)性原理所揭示的性質(zhì)。17最優(yōu)性原理的含意17(3)動(dòng)態(tài)規(guī)劃基本方程多段決策過(guò)程的特點(diǎn)每個(gè)階段都要進(jìn)行決策相繼進(jìn)行的階段決策構(gòu)成的決策序列前一階段的終止?fàn)顟B(tài)又是后一階段的初始狀態(tài)階段最優(yōu)決策不能只從本階段的效應(yīng)出發(fā)，必須通盤(pán)考慮，整體規(guī)劃。階段k的最優(yōu)決策不應(yīng)該只是本階段效應(yīng)的最優(yōu)，而必須是本階段及其所有后續(xù)階段的總體最優(yōu)，即關(guān)于整個(gè)k后部子過(guò)程的最優(yōu)決策。18(3)動(dòng)態(tài)規(guī)劃基本方程18多段決策過(guò)程中所要求解的是，從起始狀態(tài)x1開(kāi)始，進(jìn)行一系列的決策，使目標(biāo)V達(dá)到最優(yōu)，最優(yōu)目標(biāo)值V*最優(yōu)策略----使得目標(biāo)達(dá)到最優(yōu)的決策序列。最優(yōu)路線(xiàn)----在采取最優(yōu)策略時(shí)，系統(tǒng)從s1開(kāi)始所經(jīng)過(guò)的狀態(tài)序列求解動(dòng)態(tài)規(guī)劃模型找到最優(yōu)策略、最優(yōu)路線(xiàn)和最優(yōu)目標(biāo)值。19多段決策過(guò)程中所要求解的是，從起始狀態(tài)x1開(kāi)始，進(jìn)行一系列的對(duì)于Ⅰ類(lèi)指標(biāo)函數(shù)設(shè)在階段k的狀態(tài)xk執(zhí)行了任意選定決策xk后的狀態(tài)是sk+1=Tk(sk,xk)。這時(shí)k-后部子過(guò)程就縮小為k+1后部子過(guò)程。根據(jù)最優(yōu)性原理，對(duì)k+1后部子過(guò)程應(yīng)采取最優(yōu)策略，由于無(wú)后效性，k后部子過(guò)程的目標(biāo)函數(shù)值為20對(duì)于Ⅰ類(lèi)指標(biāo)函數(shù)20給出邊界條件：合在一起即構(gòu)成動(dòng)態(tài)規(guī)劃的基本方程。21給出邊界條件：21Ⅰ類(lèi)指標(biāo)函數(shù)的基本方程（逆序）為II類(lèi)指標(biāo)函數(shù)的基本方程（逆序）為適用于初始狀態(tài)給定22Ⅰ類(lèi)指標(biāo)函數(shù)的基本方程（逆序）為II類(lèi)指標(biāo)函數(shù)的基本方程（逆Ⅰ類(lèi)指標(biāo)函數(shù)的基本方程（順序）為II類(lèi)指標(biāo)函數(shù)的基本方程（順序）為同理適用于終止?fàn)顟B(tài)給定23Ⅰ類(lèi)指標(biāo)函數(shù)的基本方程（順序）為II類(lèi)指標(biāo)函數(shù)的基本方程（順8.3最優(yōu)性定理248.3最優(yōu)性定理24動(dòng)態(tài)規(guī)劃的最優(yōu)性定理：設(shè)階段數(shù)為n的多階段決策過(guò)程，其階段編號(hào)為k=0,1,...,n-1。允許策略是最優(yōu)策略的充要條件是對(duì)任意一個(gè)k,0<k<n-1和s0S0，有它是由給定的初始狀態(tài)s0和子策略p0,k-1所確定的k段狀態(tài)。當(dāng)V是效益函數(shù)時(shí)，opt取max;當(dāng)V是損失函數(shù)時(shí)，opt取min.25動(dòng)態(tài)規(guī)劃的最優(yōu)性定理：設(shè)階段數(shù)為n的多階段決策過(guò)程，其階段編證明：必要性（）26證明：必要性（）26充分性（）設(shè)p0,n-1=(p0,k-1,pk,n-1)為任一策略，sk為由（s0，p0,k-1）所確定的k階段的起始狀態(tài)，則有（以最大化為例）27充分性（）設(shè)p0,n-1=(p0,k-1,推論：若允許策略p*0,n-1是最優(yōu)策略，則對(duì)任意的k,0<k<n-1,它的子策略p*k,n-1對(duì)于以

s*k=Tk-1(s*k-1,u*k-1)為起點(diǎn)的k到n-1子過(guò)程來(lái)說(shuō)，必是最優(yōu)策略。（注意：k段狀態(tài)s*k,是由s0和p*0,k+1所確定的）28推論：若允許策略p*0,n-1是最優(yōu)策略，則對(duì)任意的k,0<8.4動(dòng)態(tài)規(guī)劃的求解方法(1)基本求解過(guò)程動(dòng)態(tài)規(guī)劃建模遞推回溯(2)動(dòng)態(tài)規(guī)劃逆推解法(3)動(dòng)態(tài)規(guī)劃順推解法298.4動(dòng)態(tài)規(guī)劃的求解方法(1)基本求解過(guò)程29(1)基本求解過(guò)程動(dòng)態(tài)規(guī)劃建模①確定階段與階段變量k②明確狀態(tài)變量sk(無(wú)后效性)和狀態(tài)可能集合Sk。③確定決策變量xk(sk)和決策允許集合Dk(sk)。④確定狀態(tài)轉(zhuǎn)移方程sk+1=Tk(sk,xk)。⑤明確階段效應(yīng)和目標(biāo)，即寫(xiě)出指標(biāo)函數(shù)Vkn(具有三個(gè)性質(zhì))。30(1)基本求解過(guò)程30①確定階段與階段變量階段的劃分一般是按照決策進(jìn)行的時(shí)間或空間上的先后順序劃分的，階段數(shù)等于多段決策過(guò)程中從開(kāi)始到結(jié)束所需要作出決策的數(shù)目，階段變量用k表示。②明確狀態(tài)變量和狀態(tài)可能集合狀態(tài)變量必須包含在給定的階段上確定全部允許決策所需要的信息。狀態(tài)變量的確定決定了整個(gè)決策過(guò)程是不是具有無(wú)后效性，因而也決定著能不能用動(dòng)態(tài)規(guī)劃方法來(lái)求解。狀態(tài)可能集是關(guān)于狀態(tài)的約束條件，因此為了求解必須正確地確定狀態(tài)可能集。31①確定階段與階段變量31③確定決策變量和決策允許集合。與靜態(tài)問(wèn)題相同，決策變量應(yīng)能夠反映對(duì)問(wèn)題所作的決策，決策變量也應(yīng)有其相應(yīng)的約束條件，在建模時(shí)應(yīng)明確決策允許集合Dk(sk)。④確定狀態(tài)轉(zhuǎn)移方程。系統(tǒng)k階段從狀態(tài)sk出發(fā)作了決策xk(sk)之后的結(jié)果之一是系統(tǒng)狀態(tài)的轉(zhuǎn)移，這一結(jié)果直接影響系統(tǒng)往后的決策過(guò)程，因此必須明確狀態(tài)的轉(zhuǎn)移過(guò)程，即根據(jù)問(wèn)題的內(nèi)在關(guān)系，明確sk+1=Tk(sk,xk)中的函數(shù)Tk(sk,xk)

。32③確定決策變量和決策允許集合。32遞推運(yùn)用基本方程的遞推公式和邊界條件，從k=n開(kāi)始，由后向前逆推，從而逐步求得各階段的最優(yōu)決策和相應(yīng)的最優(yōu)值，最后求得f1(s1),將s1的值代入計(jì)算即得。回溯由s1和x1*，利用狀態(tài)轉(zhuǎn)移方程計(jì)算出s2，從而確定x2*，…，依此類(lèi)推，最后確定xn*，于是獲得最優(yōu)策略33遞推33(2)動(dòng)態(tài)規(guī)劃逆推解法例1某旅行者希望從s地起到t地，其間的道路系統(tǒng)如圖所示，圖上圓圈表示途徑的地方，稱(chēng)為節(jié)點(diǎn)，連結(jié)兩地的箭線(xiàn)表示道路，其上的數(shù)字表示該段道路長(zhǎng)度，箭頭表示通行的方向。試求s到t的最短路。adbetcfs975784564654734(2)動(dòng)態(tài)規(guī)劃逆推解法adbetcfs9757845646第一階段第二階段第三階段劃分階段k=1,2,3代表三個(gè)階段adbetcfs975784564654735第一階段第二階段狀態(tài)變量sk取為k階段所在地，則有：adbetcfs9757845646547邊界條件f4(t)=036狀態(tài)變量sk取為k階段所在地，則有：adbetcfs975k階段決策是決定下一步走到哪里，xk(sk)取為下一步的所在點(diǎn)。adbetcfs975784564654737k階段決策是決定下一步走到哪里，xk(sk)取為下一步的所在

adbetcfs9757845646547指標(biāo)函數(shù)：遞推方程：38 adbetcfs9757845646547指標(biāo)函數(shù)：由于第3階段末已到達(dá)t，往后的距離自然是零，因此f4(t)=0對(duì)3階段所有可能的狀態(tài)S3={d,e,f}計(jì)算f3()如下39由于第3階段末已到達(dá)t，往后的距離自然是零，因此f4(t)=也可以用表格方法計(jì)算如下t/tf3()x3()def5+07+04+0574tttv3(s3,x3)+f4(s4)f3(s3)x3(s3)adbetcfs975784564654740也可以用表格方法計(jì)算如下t/tf3()x3()d5+05tvadbetcfs975784564654747541adbetcfs975784564654747541對(duì)2階段所有可能的狀態(tài)s2={a,b,c}計(jì)算f2()如下42對(duì)2階段所有可能的狀態(tài)s2={a,b,c}計(jì)算f2()如下44343也可以用表格方法計(jì)算如下d/de/ef/ff2()x2()abc7+55+54+56+75+74+46+48109fddf2(s2)x2(s2)v2(s2,x2)+f3(s3)adbetcfs975784564654744也可以用表格方法計(jì)算如下d/de/ef/ff2()x2()aadbetcfs9757845646547475910845adbetcfs9757845646547475910845對(duì)1階段所有可能的狀態(tài)S1={s}計(jì)算f1()如下a/ab/bc/cf2()x2()s9+88+107+916c46對(duì)1階段所有可能的狀態(tài)S1={s}計(jì)算f1()如下a/a順序回溯求最優(yōu)策略、最優(yōu)路線(xiàn)和最優(yōu)目標(biāo)函數(shù)值47順序回溯求最優(yōu)策略、最優(yōu)路線(xiàn)和最優(yōu)47adbetcfs975784564654747591081648adbetcfs9757845646547475910816例2某公司有資金10萬(wàn)元，若投資項(xiàng)目i（i=1,2,3）的投資額為時(shí),其效益分別為:問(wèn)應(yīng)如何分配投資數(shù)額才能使總收益最大?可列出它的靜態(tài)模型:

[分析]:這是一個(gè)表面與時(shí)間沒(méi)有任何關(guān)系的問(wèn)題,但要用動(dòng)態(tài)規(guī)劃的方法去解則必須把它劃分為“時(shí)段”.本題可劃分為3各時(shí)段,每段只決定對(duì)一個(gè)投資項(xiàng)目的投資額.這樣把問(wèn)題分解為3階段決策問(wèn)題.49例2某公司有資金10萬(wàn)元，若投資項(xiàng)目i（i=1,2,解:50解:50當(dāng)k=2時(shí),

這是一個(gè)函數(shù)求極值問(wèn)題,利用微分方法可求得該函數(shù)有極小值.s0s2x251當(dāng)k=2時(shí),這是一個(gè)函數(shù)求極值問(wèn)題,利用微分方法可求得該函要討論的具體情況:52要討論的具體情況:52減函數(shù)53減函數(shù)535454例3用動(dòng)態(tài)規(guī)劃方法求解下列規(guī)劃問(wèn)題：解:(1)建模階段劃分：k=1,2,3狀態(tài)變量：階段初始時(shí)刻可分配資源，用s1,s2,s3表示，其中s1=6決策變量：每階段消耗資源量，用x1,x2,x3表示狀態(tài)轉(zhuǎn)移方程：指標(biāo)函數(shù)：55例3用動(dòng)態(tài)規(guī)劃方法求解下列規(guī)劃問(wèn)題：解:(1)建模55(2)遞推：56(2)遞推：565757(3)回溯：58(3)回溯：58(3)動(dòng)態(tài)規(guī)劃順推解法例1某旅行者希望從s地起到t地，其間的道路系統(tǒng)如圖所示，圖上圓圈表示途徑的地方，稱(chēng)為節(jié)點(diǎn)，連結(jié)兩地的箭線(xiàn)表示道路，其上的數(shù)字表示該段道路長(zhǎng)度，箭頭表示通行的方向。試求s到t的最短路。adbetcfs975784564654759(3)動(dòng)態(tài)規(guī)劃順推解法adbetcfs9757845646第一階段第二階段第三階段劃分階段k=1,2,3代表三個(gè)階段adbetcfs975784564654760第一階段第二階段狀態(tài)變量sk取為k階段所在地，則有：adbetcfs9757845646547邊界條件f0(s)=061狀態(tài)變量sk取為k階段所在地，則有：adbetcfs975k階段決策是決定到達(dá)所在點(diǎn)的路線(xiàn)，uk(sk)取為到達(dá)的sk的路線(xiàn)。adbetcfs975784564654762k階段決策是決定到達(dá)所在點(diǎn)的路線(xiàn)，uk(sk)取為到達(dá)的sk由于第0階段末已到達(dá)s，往前的距離自然是零，因此f0(s)=0對(duì)1階段所有可能的狀態(tài)S1={a,b,c}計(jì)算f1()如下63由于第0階段末已到達(dá)s，往前的距離自然是零，因此f0(s)=也可以用表格方法計(jì)算如下s/sf1()u1()abc9+08+07+0987sasbscv1(s1,u1)+f0(s)f1(s1)u1(s1)64也可以用表格方法計(jì)算如下s/sf1()u1()a9+09saadbetcfs9757845646547879065adbetcfs9757845646547879065對(duì)2階段所有可能的狀態(tài)s2={d,e,f}計(jì)算f2()如下66對(duì)2階段所有可能的狀態(tài)s2={d,e,f}計(jì)算f2()如下66767也可以用表格方法計(jì)算如下a/ab/bc/cf2()u2()def7+94+95+86+84+75+76+7111213cdceaf,cff2(s2)u2(s2)v2(s2,u2)+f1(s1)68也可以用表格方法計(jì)算如下a/ab/bc/cf2()u2()dadbetcfs9757845646547879131112069adbetcfs9757845646547879131112對(duì)3階段所有可能的狀態(tài)S3={t}計(jì)算f3(t)如下d/de/ef/ff3()u3()t5+117+124+1316ft70對(duì)3階段所有可能的狀態(tài)S3={t}計(jì)算f3(t)如下d/de逆序回溯求最優(yōu)策略、最優(yōu)路線(xiàn)和最優(yōu)目標(biāo)函數(shù)值71逆序回溯求最優(yōu)策略、最優(yōu)路線(xiàn)和最優(yōu)71adbetcfs975784564654787913111216072adbetcfs9757845646547879131112動(dòng)態(tài)規(guī)劃的優(yōu)點(diǎn)：可把一個(gè)N維優(yōu)化問(wèn)題化成N個(gè)一維優(yōu)化問(wèn)題求解。73動(dòng)態(tài)規(guī)劃的優(yōu)點(diǎn)：73動(dòng)態(tài)規(guī)劃的優(yōu)點(diǎn)：可把一個(gè)N維優(yōu)化問(wèn)題化成N個(gè)一維優(yōu)化問(wèn)題求解。DP方程中附加某些約束條件，可使求解更加容易。74動(dòng)態(tài)規(guī)劃的優(yōu)點(diǎn)：74動(dòng)態(tài)規(guī)劃的優(yōu)點(diǎn)：可把一個(gè)N維優(yōu)化問(wèn)題化成N個(gè)一維優(yōu)化問(wèn)題求解。DP方程中附加某些約束條件，可使求解更加容易。求得最優(yōu)解以后，可得所有子問(wèn)題的最優(yōu)解。75動(dòng)態(tài)規(guī)劃的優(yōu)點(diǎn)：75動(dòng)態(tài)規(guī)劃的缺點(diǎn)：“一個(gè)”問(wèn)題，“一個(gè)”模型，“一個(gè)”求解方法。且求解技巧要求比較高，沒(méi)有統(tǒng)一處理方法。76動(dòng)態(tài)規(guī)劃的缺點(diǎn)：768.5動(dòng)態(tài)規(guī)劃的其他應(yīng)用舉例（1）生產(chǎn)——庫(kù)存問(wèn)題（2）資源分配問(wèn)題（3）串聯(lián)系統(tǒng)可靠性問(wèn)題（4）設(shè)備更新問(wèn)題（5）二維背包問(wèn)題778.5動(dòng)態(tài)規(guī)劃的其他應(yīng)用舉例（1）生產(chǎn)——庫(kù)存問(wèn)題77（1）生產(chǎn)－庫(kù)存問(wèn)題生產(chǎn)計(jì)劃周期分為n個(gè)階段，即k=1~n；已知最初庫(kù)存量為s1；階段需求量為dk；單位產(chǎn)品的消耗費(fèi)用為L(zhǎng)k；單位產(chǎn)品的階段庫(kù)存費(fèi)用為hk；倉(cāng)庫(kù)容量為Mk；階段生產(chǎn)能力為Bk；生產(chǎn)的準(zhǔn)備費(fèi)用為：78（1）生產(chǎn)－庫(kù)存問(wèn)題生產(chǎn)計(jì)劃周期分為n個(gè)階段，即k=1~n問(wèn)應(yīng)如何安排各階段產(chǎn)量，使計(jì)劃期總費(fèi)用最小。這里狀態(tài)變量sk應(yīng)選為階段k的初始庫(kù)存量，計(jì)劃初期的庫(kù)存量s1是已知的，末期的庫(kù)存量通常也是給定的，為簡(jiǎn)單起見(jiàn)這里假定sn+1=0，于是問(wèn)題是始端末端固定的問(wèn)題。關(guān)于狀態(tài)xk的約束條件是即階段k的庫(kù)存既不能超過(guò)庫(kù)存容量，也不應(yīng)超過(guò)階段k至階段n的需求總量(dk+dk+1+…+dn)，否則將與sn+1=0的假設(shè)相違背。79問(wèn)應(yīng)如何安排各階段產(chǎn)量，使計(jì)劃期總費(fèi)用最小。這里狀態(tài)變量sk庫(kù)容量限制以后需求缺口本期需求缺口決策變量xk選為階段k的生產(chǎn)量。階段產(chǎn)量要在不超過(guò)生產(chǎn)能力Bk的條件下，充分滿(mǎn)足該階段的需求dk，同時(shí)還要滿(mǎn)足計(jì)劃末期的庫(kù)存量為0的要求。因此關(guān)于決策變量的約束條件就是期末庫(kù)存=期初庫(kù)存+生產(chǎn)量-本期需求80庫(kù)容量限制以后需求缺口本期需求缺口決策變量xk選為階段k的生階段k的生產(chǎn)費(fèi)用是庫(kù)存費(fèi)用按階段k末期的庫(kù)存量sk+1計(jì)算81階段k的生產(chǎn)費(fèi)用是庫(kù)存費(fèi)用按階段k末期的庫(kù)存量sk+1計(jì)算例3求解生產(chǎn)－庫(kù)存問(wèn)題。已知其n=3，ck=8，Lk=2，hk=1.5，s1=1，Mk=4，s4=0(計(jì)劃周期末期的庫(kù)存量為0)，Bk＝6，d1=3，d2=4，d3=3。解：82例3求解生產(chǎn)－庫(kù)存問(wèn)題。已知其n=3，ck=8，Lk=2838384840123f3()x3’0141431121222101013000850123f3()x3’01414311212221010130123456f2()x2’016+1419.5+1223+10304114+1417.5+1221+1024.5+024.56212+1415.5+1219+1022.5+022.55310+1413.5+1217+1020.5+020.5440+1411.5+1215+1018.5+0140860123456f2()x2’016+1419.5+1223+23456f!()x1’112+3015.5+24.519+22.522.5+20.526+14403或68723456f!()x1’112+3015.5+24.519+23456f!()u1’112+3015.5+24.519+22.522.5+20.526+14403或68823456f!()u1’112+3015.5+24.519+(2)資源分配問(wèn)題資源的多元分配

設(shè)有某種資源，總量為M，可以投入n種生產(chǎn)活動(dòng)。已知用于活動(dòng)k的資源為uk時(shí)的收益是gk(uk)，問(wèn)應(yīng)如何分配資源，使n種生產(chǎn)活動(dòng)的總收益最大。這種問(wèn)題就是資源的多元分配問(wèn)題。89(2)資源分配問(wèn)題資源的多元分配89資源的多元分配如果將n種活動(dòng)作為一個(gè)互相銜接的整體，對(duì)一種活動(dòng)的資源分配作為一個(gè)階段，每個(gè)階段確定對(duì)一種活動(dòng)的資源投放量。則該問(wèn)題成為一個(gè)多段決策問(wèn)題。狀態(tài)變量xk的選取原則是要能夠據(jù)此確定決策uk，以及滿(mǎn)足狀態(tài)轉(zhuǎn)移方程所要求的無(wú)后效性。在資源分配問(wèn)題中，決策變量選為對(duì)活動(dòng)k的資源投放量，因此狀態(tài)變量可以選擇為階段k初所擁有的資源量，即將要在第k種到第n種活動(dòng)間分配的資源量。90資源的多元分配90關(guān)于狀態(tài)變量xk的約束條件是0≤xk≤M關(guān)于決策變量uk的約束條件是0≤uk≤xk狀態(tài)轉(zhuǎn)移方程為xk+1=xk-uk顯然它滿(mǎn)足無(wú)后效性要求。階段效應(yīng)為對(duì)活動(dòng)k投放資源uk時(shí)的收益，vk(xk,uk)=gk(uk)目標(biāo)函數(shù)是為n種活動(dòng)投放資源后的總收益動(dòng)態(tài)規(guī)劃基本方程91關(guān)于狀態(tài)變量xk的約束條件是0≤xk≤M91例4某公司擬將50萬(wàn)元資金投放下屬A、B、C三個(gè)部門(mén)，各部門(mén)在獲得資金后的收益如表所示，用動(dòng)態(tài)規(guī)劃方法求總收益最大的投資分配方案（投資數(shù)以10萬(wàn)元為單位）。投放資金（萬(wàn)元）01020304050收益（萬(wàn)元）A01520252830B0010254570C0102030405092例4某公司擬將50萬(wàn)元資金投放下屬A、B、C三個(gè)部門(mén)，各部解:該問(wèn)題可以作為三段決策過(guò)程。對(duì)A、B、C三個(gè)部門(mén)分配資金分別形成1，2，3三個(gè)階段。xk表示給部門(mén)k分配資金時(shí)擁有的資金數(shù)。uk表示給部門(mén)k分配的資金數(shù)（以10萬(wàn)元為單位）。狀態(tài)轉(zhuǎn)移方程是xk+1=xk-uk。階段效應(yīng)如表所示。目標(biāo)函數(shù)是階段效應(yīng)求和。首先逆序求最優(yōu)目標(biāo)函數(shù)值集合和最優(yōu)決策集合。93解:該問(wèn)題可以作為三段決策過(guò)程。對(duì)A、B、C三個(gè)部門(mén)分配資從表可知g3()是單調(diào)遞增的函數(shù)，因此，當(dāng)u3=x3時(shí)達(dá)到最大。即：94從表可知g3()是單調(diào)遞增的函數(shù)，因此，當(dāng)u3=x3時(shí)達(dá)x3g3f3U3’000011010122020233030344040455050595x3g3f3U3’000011010122020233030k=2時(shí)，0≤x2≤50≤u2≤x2

96k=2時(shí)，0≤x2≤50≤u2≤x296k=2時(shí)，0≤x2≤50≤u2≤x2

0/x21/x2-12/x2-23/x2-34/x2-45/x2-5f2()U2’00+00010+100+010020+200+1010+020030+300+2010+1025+030040+400+3010+2025+1045+045450+500+4010+3025+2045+1070+070597k=2時(shí)，0≤x2≤50≤u2≤x20/x21/當(dāng)k=1時(shí)，有x1=5，0≤u1≤x1=598當(dāng)k=1時(shí)，有x1=5，0≤u1≤x1=598當(dāng)k=1時(shí)，有x1=5，0≤u1≤x1=50/51/42/33/24/15/0f1()U1’50+7015+4520+3025+2028+1030+070099當(dāng)k=1時(shí)，有x1=5，0≤u1≤x1=50/51/42/順序求最優(yōu)目標(biāo)函數(shù)值和最優(yōu)策略、最優(yōu)路線(xiàn)0/51/42/33/24/15/0f1()U1’50+7015+4520+3025+2028+1030+0700100順序求最優(yōu)目標(biāo)函數(shù)值和最優(yōu)策略、最優(yōu)路線(xiàn)0/51/42/33資源的多段分配將一種有消耗性的資源，多階段地在多種不同的生產(chǎn)活動(dòng)中投放的問(wèn)題稱(chēng)為資源的多段分配問(wèn)題，下面討論其中包含有兩個(gè)生產(chǎn)活動(dòng)的簡(jiǎn)單情況。設(shè)有某種資源，初始的擁有量是M。計(jì)劃在A，B兩個(gè)生產(chǎn)部門(mén)連續(xù)使用n個(gè)階段。已知在部門(mén)A投入資源uA時(shí)的階段收益是g(uA)，在部門(mén)B投入資源uB時(shí)的階段收益是h(uB)。又資源在生產(chǎn)中將有部分消耗，已知每生產(chǎn)一個(gè)階段后部門(mén)A，B中的資源完好率分別為a和b，0<(a,b)<1。求n階段間總收益最大的資源分配計(jì)劃。101資源的多段分配101n段決策過(guò)程狀態(tài)變量xk為階段k初擁有的資源量，0≤xk≤M，x1=M決策變量選為階段k在部門(mén)A的資源投放量，即uA=uk，這里顯然有uB=xk-uk，決策變量的約束條件是0≤uk≤xk即最多將所擁有的資源都投入部門(mén)A，其時(shí)uB=0階段k末部站A的剩余資源auk，部門(mén)B中則為b(xk-uk)，因此狀態(tài)轉(zhuǎn)移方程xk+1=T(xk,uk)是xk+1=auk+b(xk-uk)滿(mǎn)足無(wú)后效性階段效應(yīng)rk(xk,uk)即階段收益rk(xk,uk)=g(uk)+h(xk-uk)目標(biāo)函數(shù)是n個(gè)階段的總收益，即階段效應(yīng)求和。102n段決策過(guò)程102例5今有1000臺(tái)機(jī)床，要投放到A、B兩個(gè)生產(chǎn)部門(mén)，計(jì)劃連續(xù)使用3年。已知對(duì)A部門(mén)投入uA臺(tái)機(jī)器時(shí)的年收益是g(uA)=4(uA)2（元），機(jī)器完好率a=0.5，相應(yīng)的B部門(mén)的年收益是h(uB)=2(uB)2（元），完好率b=0.9。試求使3年間總收益最大的年度機(jī)器分配方案。解以每年作為一個(gè)階段，設(shè)狀態(tài)變量和決策變量都是連續(xù)取值的。K階段狀態(tài)變量xk取為該年度初完好的設(shè)備數(shù)，決策變量取為該年度投入A活動(dòng)的設(shè)備數(shù)，則有

0≤xk≤1000，

0≤uk≤xk狀態(tài)轉(zhuǎn)移方程為：xk+1=0.5uk+0.9(xk-uk)103例5今有1000臺(tái)機(jī)床，要投放到A、B兩個(gè)生產(chǎn)部門(mén)，計(jì)解以每年作為一個(gè)階段，設(shè)狀態(tài)變量和決策變量都是連續(xù)取值的。K階段狀態(tài)變量xk取為該年度初完好的設(shè)備數(shù)，決策變量取為該年度投入A活動(dòng)的設(shè)備數(shù)，則有

0≤xk≤1000，

0≤uk≤xk狀態(tài)轉(zhuǎn)移方程為：xk+1=0.5uk+0.9(xk-uk)動(dòng)態(tài)規(guī)劃基本方程104解以每年作為一個(gè)階段，設(shè)狀態(tài)變量和決策變量都是連續(xù)取值的逆序求條件最優(yōu)目標(biāo)函數(shù)值fk(xk)和條件最優(yōu)決策k=3時(shí)，0≤u3≤x3，注意到f4(x4)=0，有k=2時(shí)，0≤u2≤x2，有105逆序求條件最優(yōu)目標(biāo)函數(shù)值fk(xk)和條件最優(yōu)決策k=2時(shí)，k=1時(shí)，0≤u1≤x1，x2=0.5u1+0.9(x1-u1)，f2(x2)106k=1時(shí)，0≤u1≤x1，x2=0.5u1+0.9(x1-u(3)串聯(lián)系統(tǒng)可靠性問(wèn)題系統(tǒng)可靠性是指系統(tǒng)在規(guī)定的條件下能正常工作的概率，它是管理和工程技術(shù)設(shè)計(jì)中經(jīng)常要研究的問(wèn)題。這兒要研究的是串聯(lián)系統(tǒng)可靠性問(wèn)題。例如某種儀器設(shè)備由N個(gè)部件串聯(lián)構(gòu)成，凡其中有一個(gè)部件出現(xiàn)故障，則整個(gè)系統(tǒng)便不能正常工作。為了提高系統(tǒng)工作的可靠性，一種方法是可以在每個(gè)部件上裝有主要元件的相同性能的備用件，并且?guī)в袀溆迷詣?dòng)投入裝置。自然備用元件越多，系統(tǒng)的可靠性越高，但也會(huì)相應(yīng)增加系統(tǒng)重量、體積和費(fèi)用，有時(shí)也會(huì)降低工作精度。因此，在成本、重量、體積等一定的條件限制下，應(yīng)如何選擇各部件的備用元件數(shù)，使得整個(gè)系統(tǒng)的可靠性最大，就可以歸結(jié)為一個(gè)動(dòng)態(tài)規(guī)劃問(wèn)題。107(3)串聯(lián)系統(tǒng)可靠性問(wèn)題系統(tǒng)可靠性是指系統(tǒng)在規(guī)定的條件下例6某電氣設(shè)備由三個(gè)部件串聯(lián)而成，為提高該種設(shè)備在指定工作條件下正常工作的可靠性，需在每個(gè)部件上安裝一個(gè)、兩個(gè)或三個(gè)主要元件的相同備件。假設(shè)對(duì)部件i(i=1，2，3)配備j個(gè)備件后的可靠性Rij和所需費(fèi)用cij均已知，如表所示，若可用的總資金數(shù)量為1萬(wàn)元，問(wèn)如何配備各部件的備用元件數(shù)，才能使該設(shè)備在給定工作條件下的可靠性最大？備件數(shù)部件j=1j=2j=3Ci1（千元)vi1Ci2（千元）vi2Ci3（千元）vi3110.9030.9450.96230.7550.8860.97320.8030.9240.99108例6某電氣設(shè)備由三個(gè)部件串聯(lián)而成，為提高該種設(shè)備在指定解:以給不同的部件決定備件作為不同的階段，則該問(wèn)題是3階段決策問(wèn)題設(shè)狀態(tài)變量xk表示從第k個(gè)部件到第3個(gè)部件允許使用的總費(fèi)用（k=1,2,3）決策變量uk為第k部件配備的備用元件數(shù)（k=1，2，3）。則據(jù)題意有：x1=10千元，且每個(gè)部件都最少有一個(gè)備件，即uk≥1，若令sk表示為保障以后各部件均能獲得一個(gè)備件所需的資金數(shù)，則應(yīng)有：109解:以給不同的部件決定備件作為不同的階段，則該問(wèn)題是3階且據(jù)此可得：s1=6，s2=5，s3=2。從而可知：對(duì)uk有即當(dāng)期所耗資金加上k+1期往后所用資金sk+1不超過(guò)當(dāng)前擁有資金數(shù)。根據(jù)上述分析可以寫(xiě)出各階段的狀態(tài)可能集合和決策允許集合如下：

x1=10X2＝{9，7，5}X3＝{2，3，4，5，6}U1＝{1，2，3}U2(9)＝{1，2，3}U2(7)＝{1，2}U2(5)＝{1}U3(2)＝{1}U3(3)＝{1，2}U3(4)＝{1，2，3}U3(5)＝{1，2，3}U3(6)＝{1，2，3}110且據(jù)此可得：s1=6，s2=5，s3=2。即當(dāng)期所耗資金加上狀態(tài)轉(zhuǎn)移方程為：階段效應(yīng)為目標(biāo)函數(shù)為是階段效應(yīng)乘積的形式若以fk(xk)表示在階段k擁有資金xk時(shí)采用最優(yōu)決策序列所得的k階段往后的系統(tǒng)的可靠性，則動(dòng)態(tài)規(guī)劃基本方程為：111狀態(tài)轉(zhuǎn)移方程為：階段效應(yīng)為目標(biāo)函數(shù)為是階段效應(yīng)乘積的形式1/x3-22/x3-33/x3-4f3()U3’20.8×10.8130.8×10.92×10.92240.8×10.92×10.99×10.99360.8×10.92×10.99×10.9931121/x3-22/x3-33/x3-4f3()U3’20.8×1/x2-32/x2-53/x2-6f2()U2’90.75×0.990.8×0.990.97×0.920.8924370.75×0.990.8×0.80.7425150.75×0.80.611/x3-22/x3-33/x3-4f3()U3’20.8×10.8130.8×10.92×10.92240.8×10.92×10.99×10.99360.8×10.92×10.99×10.9931131/x2-32/x2-53/x2-6f2()U2’90.751/x2-32/x2-53/x2-6f2()U2’90.75×0.990.8×0.990.97×0.920.8924370.75×0.990.8×0.80.7425150.75×0.80.611/92/73/5f1()U1’100.9×0.89240.94×0.74250.96×0.60.803161

1141/x2-32/x2-53/x2-6f2()U2’90.75(4)設(shè)備更新問(wèn)題

設(shè)備更新問(wèn)題的一般提法隨著使用年限的增加，設(shè)備性能會(huì)變差，故障會(huì)增加，需要維修或更新。設(shè)備使用時(shí)間愈長(zhǎng)，積累效益愈高，但隨著設(shè)備陳舊，維修使用費(fèi)用也會(huì)提高，而且，設(shè)備使用年限愈久，處理價(jià)格愈低，更新費(fèi)用也要增加。因此，處于某個(gè)階段的各種設(shè)備，總是面臨著保留還是更新的問(wèn)題，這個(gè)問(wèn)題應(yīng)該從整個(gè)計(jì)劃期間的總回收額，而不應(yīng)從局部的某個(gè)階段的回收額來(lái)考慮。由于每個(gè)階段都面臨著保留還是更新的兩種選擇，因此，它是一個(gè)多階段的決策過(guò)程，可以用動(dòng)態(tài)規(guī)劃方法求解。115(4)設(shè)備更新問(wèn)題設(shè)備更新問(wèn)題的一般提法115今有一設(shè)備更新問(wèn)題如下：已知n為計(jì)算設(shè)備回收額的總期數(shù)；t為某個(gè)階段的設(shè)備役齡；γ(t)為從役齡為t的設(shè)備得到的階段收益；μ(t)為役齡為t的設(shè)備的階段使用費(fèi)用；s(t)是役齡為t的設(shè)備的處理價(jià)格；p為新設(shè)備的購(gòu)置價(jià)格；求n期內(nèi)使回收額最大的設(shè)備更新政策。116今有一設(shè)備更新問(wèn)題如下：116狀態(tài)變量選為設(shè)備的役齡t，即xk=t，決策只有兩種可能，即保留或更新，記為K（保留）或P（更新）。狀態(tài)轉(zhuǎn)移方程相應(yīng)的階段效應(yīng)即階段的回收額也有兩種可能117狀態(tài)變量選為設(shè)備的役齡t，即xk=t，相應(yīng)的階段效應(yīng)即階段的例7假定n＝6年，新設(shè)備購(gòu)買(mǎi)價(jià)格為10萬(wàn)元。役齡為t時(shí)的設(shè)備使用效益γ(t)，使用費(fèi)用μ(t)和處理價(jià)格s(t)如下表所示T0123456γ(t)萬(wàn)元27262624222018μ(t)萬(wàn)元15151616171718s(t)萬(wàn)元6554432118例7假定n＝6年，新設(shè)備購(gòu)買(mǎi)價(jià)格為10萬(wàn)元。T01234T0123456γ(t)萬(wàn)元27262624222018μ(t)萬(wàn)元15151616171718s(t)萬(wàn)元6554432γ(t)-μ(t)1211108530s(t)+28776654119T0123456γ(t)萬(wàn)元27262624222018μ(t0123456γ(t)-μ(t)1211108530s(t)+28776654t0123456f6(t)1211108654120t0123456γ(t)-μ(t)1211108530s(t0123456γ(t)-μ(t)1211108530s(t)+28776654t0123456f6(t)1211108654f5(t)23211817171615γ(t)-μ(t)+f6(t+1)23211814107s

(t)+2+1119181817171615121t0123456γ(t)-μ(t)1211108530s(t0123456γ(t)-μ(t)1211108530s(t)+28776654t0123456f6(t)1211108654f5(t)23211817171615γ(t)-μ(t)+f5(t+1)332927252118s

(t)+2+11292828272726