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

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

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

(k=1,2,…,n)

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

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

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

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

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

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

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

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

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

0≤xk≤1000，

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

0≤xk≤1000，

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

設(shè)備更新問題的一般提法隨著使用年限的增加，設(shè)備性能會變差，故障會增加，需要維修或更新。設(shè)備使用時間愈長，積累效益愈高，但隨著設(shè)備陳舊，維修使用費用也會提高，而且，設(shè)備使用年限愈久，處理價格愈低，更新費用也要增加。因此，處于某個階段的各種設(shè)備，總是面臨著保留還是更新的問題，這個問題應(yīng)該從整個計劃期間的總回收額，而不應(yīng)從局部的某個階段的回收額來考慮。由于每個階段都面臨著保留還是更新的兩種選擇，因此，它是一個多階段的決策過程，可以用動態(tài)規(guī)劃方法求解。115(4)設(shè)備更新問題設(shè)備更新問題的一般提法115今有一設(shè)備更新問題如下：已知n為計算設(shè)備回收額的總期數(shù)；t為某個階段的設(shè)備役齡；γ(t)為從役齡為t的設(shè)備得到的階段收益；μ(t)為役齡為t的設(shè)備的階段使用費用；s(t)是役齡為t的設(shè)備的處理價格；p為新設(shè)備的購置價格；求n期內(nèi)使回收額最大的設(shè)備更新政策。116今有一設(shè)備更新問題如下：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è)備購買價格為10萬元。役齡為t時的設(shè)備使用效益γ(t)，使用費用μ(t)和處理價格s(t)如下表所示T0123456γ(t)萬元27262624222018μ(t)萬元15151616171718s(t)萬元6554432118例7假定n＝6年，新設(shè)備購買價格為10萬元。T01234T0123456γ(t)萬元27262624222018μ(t)萬元15151616171718s(t)萬元6554432γ(t)-μ(t)1211108530s(t)+28776654119T0123456γ(t)萬元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