管理運籌學(xué)--動態(tài)規(guī)劃

1、第8章 動態(tài)規(guī)劃 Dynamic Programming,華國偉北京交通大學(xué)物流管理系,內(nèi)容提要,1.多階段決策過程及實例2.動態(tài)規(guī)劃的基本概念和基本方程3.動態(tài)規(guī)劃的最優(yōu)性原理和最優(yōu)性定理4.動態(tài)規(guī)劃和靜態(tài)規(guī)劃的關(guān)系5.動態(tài)規(guī)劃應(yīng)用舉例,,重點： 理解動態(tài)規(guī)劃基本概念、最優(yōu)化原理和基本方程; 通過資源分配、生產(chǎn)與存儲和設(shè)備更新等問題,學(xué)習(xí) 應(yīng)用動態(tài)規(guī)劃解決多階段決策問題; 重點掌握動態(tài)規(guī)劃模型結(jié)構(gòu)、逆序算法原理

2、、資源 分配問題、生產(chǎn)與存儲問題. 難點為動態(tài)規(guī)劃中狀態(tài)變量、基本方程等的確定.,,動態(tài)規(guī)劃產(chǎn)生于20世紀(jì)50年代, 美國數(shù)學(xué)家貝爾曼(R. Bellman)等人提出. 動態(tài)規(guī)劃是求解某類問題的一種方法,是考察問題的一種途徑,而不是一種算法.必須對具體問題進(jìn)行具體分析,運用動態(tài)規(guī)劃的原理和方法,劃分階段,建立相應(yīng)的模型,然后再去求解.,,動態(tài)規(guī)劃是用來解決多階段決策過程最優(yōu)化的一種數(shù)量方法

3、.其特點在于,它可以把一個多階段決策問題變換為幾個相互聯(lián)系的同類型單階段最優(yōu)化問題,從而一個一個地去解決.,1. 多階段決策過程及實例,多階段決策過程（序貫決策過程）,1,2,n,決策,決策,決策,狀態(tài),狀態(tài),狀態(tài),狀態(tài),狀態(tài),收益,收益,收益,…,,2 多階段決策問題——舉例,(1) 時間階段,例1 機器負(fù)荷分配問題,其中：xi——各年度不同負(fù)荷機器的臺數(shù)（向量）； vi——產(chǎn)量,建模？求解？,,(2)

4、 空間階段圖中所示為從A到G的路線網(wǎng)絡(luò), 圖中數(shù)字表示相應(yīng)線路的長度, 如何求出從A到G的最短路線？,（窮舉法48條路線）,最短路的特性： 如果已有從起點到終點的一條最短路，那么從最短路線上中間任何一點出發(fā)到終點的路線仍然是最短路。（證明用反證法）,§1 動態(tài)規(guī)劃的研究對象和引例,動態(tài)系統(tǒng)： 包含隨時間變化的因素和變量的系統(tǒng)。,動態(tài)決策問題：,系統(tǒng)所處的狀態(tài)和時刻是進(jìn)行決策的重要因素.,找到不同時刻的最優(yōu)決策

5、以及整個過程的最優(yōu)策略.,,,,全過程的最優(yōu),,階段,1、 生產(chǎn)決策問題 企業(yè)在生產(chǎn)過程中，由于需求是隨時間變化的，因此企業(yè)為了獲得全年的最佳生產(chǎn)效益，就要在整個生產(chǎn)過程中逐月或逐季度地根據(jù)庫存和需求決定生產(chǎn)計劃。,多階段決策問題的典型例子,,2、機器負(fù)荷分配問題,某種機器,高負(fù)荷,低負(fù)荷,g=g(u1),,產(chǎn)品的年產(chǎn)量,,,,投入生產(chǎn)的機器數(shù)量,機器的年完好率為a ，0<a<1,h=h(u2),機器的年完好

6、率為b ，0< b<1,年終完好的機器？,,,,假定開始生產(chǎn)時完好的機器數(shù)量為s1。要求制定一個n年計劃，在每年開始時，決定如何重新分配完好的機器在兩種不同的負(fù)荷下生產(chǎn)的數(shù)量，使在n年內(nèi)產(chǎn)品的總產(chǎn)量達(dá)到最高。,,3、線性規(guī)劃、非線性規(guī)劃等靜態(tài)的規(guī)劃問題也可以通過適當(dāng)?shù)匾腚A段的概念，應(yīng)用動態(tài)規(guī)劃方法加以解決。,不包含時間因素的靜態(tài)決策問題（一次決策問題）也可以適當(dāng)?shù)匾腚A段的概念，作為多階段的決策問題用動態(tài)規(guī)劃方法來解決。,

7、4、最短路問題（引例）：給定一個交通網(wǎng)絡(luò)圖如前，其中兩點之間的數(shù)字表示距離（或花費），試求從A點到G點的最短距離（總費用最小）。,動態(tài)規(guī)劃的基本概念,1. 階段2. 狀態(tài)3. 決策4. 策略5. 狀態(tài)轉(zhuǎn)移方程6. 指標(biāo)函數(shù)和最優(yōu)值函數(shù),建模,,,§2 動態(tài)規(guī)劃的基本概念和定義,1、階段、階段變量,把所給問題的過程，適當(dāng)（按時間和空間）地分為若干個相互聯(lián)系的階段；描述階段的變量稱為階段變量，常用 k 表示。,,2、狀態(tài)

8、、狀態(tài)變量,每個階段開始所處的自然狀態(tài)或客觀條件,描述過程的狀況,通常一個階段有若干個狀態(tài).,描述過程狀態(tài)的變量稱為狀態(tài)變量，它可用一個數(shù)、一組數(shù)或一向量來描述, 常用 sk 表示第 k 階段的狀態(tài).,s2=?,,狀態(tài)允許集合，狀態(tài)變量的取值允許集合或范圍。,,在最優(yōu)控制中也稱為控制.,3、決策、決策變量,某一階段、某個狀態(tài),可以做出不同的決定(選擇),決定下一階段的狀態(tài),這種決定稱為決策.,決策變量, 描述決策的變量.,uk(sk),

9、 表示第 k 階段當(dāng)狀態(tài)為 sk 時的決策變量.,,允許決策集合，常用Dk(sk)表示第k階段從狀態(tài)sk出發(fā)的允許決策集合.,uk(sk) ? Dk(sk),D2(B1)?,,,系統(tǒng)當(dāng)前的狀態(tài)和決策,4、多階段決策過程,在每個階段進(jìn)行決策 ? 控制過程的發(fā)展；,其發(fā)展是通過一系列的狀態(tài)轉(zhuǎn)移來實現(xiàn)的；,系統(tǒng)過去的歷史狀態(tài)和決策,,,s2=T1(s1, u1),s3=T2(s1, u1, s2, u2),? ?,sk+1=Tk(s1,

10、u1, s2, u2 ,?, sk, uk),狀態(tài)轉(zhuǎn)移方程的一般形式,s1=A,u1=B1,s2=?,,能用動態(tài)規(guī)劃方法求解的多階段決策過程是一類特殊的多階段決策過程，即具有無后效性的多階段決策過程。,圖示如下：,5、無后效性或馬爾可夫性,如果某階段狀態(tài)給定后，則在這個階段以后過程的發(fā)展不受這個階段以前各階段狀態(tài)的影響；過程的過去歷史只能通過當(dāng)前的狀態(tài)去影響它未來的發(fā)展。,,構(gòu)造動態(tài)規(guī)劃模型時，要充分注意狀態(tài)變量是否滿足無后效性的要求

11、；,狀態(tài)轉(zhuǎn)移方程？,狀態(tài)具有無后效性的多階段決策過程的狀態(tài)轉(zhuǎn)移方程如下：,,,由每段的決策按順序排列組成的決策函數(shù)序列稱為 k 子過程策略。簡稱子策略，記為pk,n(sk)，即，,Pk,n(sk)={uk(sk),uk+1(sk+1), ?,un(sn)},6、策略,按順序排列的決策組成的集合。,由過程的第k ?終止?fàn)顟B(tài)為止的過程，稱為問題的后部子過程（k 子過程）。,,允許策略集合，可供選擇的策略范

12、圍，用 P 表示。,最優(yōu)策略，達(dá)到最優(yōu)效果的策略。,當(dāng) k =1時，此決策函數(shù)序列成為全過程的一個策略，簡稱策略，記為p1,n (s1)，即,P1,n(s1)={u1(s1), u2(s2), … , un(sn)},,7、指標(biāo)函數(shù)和最優(yōu)值函數(shù),指標(biāo)函數(shù)，用來衡量所實現(xiàn)過程優(yōu)劣的一種數(shù)量指標(biāo)，它是定義在全過程或所有后部子過程上確定的數(shù)量函數(shù)。用 Vk, n 表示。,Vk, n= Vk, n (sk, uk , sk+1, uk+1 ,

13、 ?, sn+1), k =1,2, ?,n,動態(tài)規(guī)劃模型的指標(biāo)函數(shù)，應(yīng)具有可分離性，并滿足遞推關(guān)系。,即Vk, n可以表示為 sk, uk,Vk+1, n 的函數(shù)。,,常見的指標(biāo)函數(shù)的形式是：,? 過程和它的任一子過程的指標(biāo)是它所包含的各階段的指標(biāo)和。即,無后效性的結(jié)果,其中V(sj, uj ) 表示第 j 階段的階段指標(biāo)。這時上式可寫成,Vk, n(sk ,uk ,…, sn+1) = vk(sk ,uk)+ Vk+1, n,

14、V5, 6= V5, 6 (s5, u5, V6, 6 ) =d5(s5,u5)+ V6, 6,,? 過程和它的任意子過程的指標(biāo)是它所包含的各階段的指標(biāo)的乘積。即,可改寫成,Vk, n(sk ,uk ,…, sn+1) = vk(sk ,uk) ?Vk+1, n(sk+1, uk+1, …, sn+1),指標(biāo)函數(shù)的最優(yōu)值，記為 fk (sk)。表示從第 k 階段的狀態(tài) sk 到第 n 階段的終止?fàn)顟B(tài)的采取最優(yōu)策略所得到的

15、指標(biāo)函數(shù)值。即,最優(yōu)值函數(shù)：,f6 (s6)=？,f6 (F1)=4,f6 (F2)=3,f5 (E1)=？,全過程的最優(yōu)值函數(shù)記為 f1 (s1),多階段決策過程的數(shù)學(xué)模型: (具有無后效性, 以和式為例),,小結(jié):,指標(biāo)函數(shù)形式: 和、積,無后效性,可遞推,Vk, n= Vk, n (sk, uk , sk+1, uk+1 , ?, sn+1),= ? k [sk , uk ,Vk+1, n (sk+1, uk+1 , ?,

16、sn+1)],解多階段決策過程問題，應(yīng)求出：,,§3 動態(tài)規(guī)劃的基本思想和基本方程,（窮舉法48條路線）,最短路的特性： 如果已有從起點到終點的一條最短路，那么從最短路線上中間任何一點出發(fā)到終點的路線仍然是最短路。（證明用反證法）,,,,k=5，出發(fā)點有 E1, E2, E3,u5(E1)=F1E1?F1?G,,u5(E2)=F2E2?F2?G,,k=6， F1 ? G，f6(F1)=4 F2 ? G

17、，f6(F2)=3,u5(E3)=F2E3?F2?G,,,,,,,,k=3 f3(C1)=13 u3(C1)=D1 f3(C2)=10 u3(C2)=D1f3(C3)=9 u3(C3)=D2f3(C4)=12 u3(C4)=D3,k=2 f2(B1)=13 u2(B1)=C2 f2(B2)=10 u2(B2)=C3,k=4 f4(D1)=7 u4(D1)=E2 f4(D2)=6 u

18、4(D2)=E2f4(D3)=8 u4(D3)=E2,u1(A)=B1,,最優(yōu)決策函數(shù)序列｛uk ｝：,最短路線為 A?B1?C2?D1?E2?F2?G,u1(A)=B1, u2(B1)=C2, u3(C2)=D1, u4(D1)=E2, u5(E2)=F2, u6(F2)=G,,求解的各個階段,我們利用了k 階段與 k+1 階段之間的遞推關(guān)系:,指標(biāo)函數(shù)是各階段指標(biāo)的和,,指標(biāo)函數(shù)是各階段指標(biāo)的

19、積,練習(xí),,最優(yōu)性原理(R. Bellman )：“一個過程的最優(yōu)策略具有這樣的性質(zhì)：即無論其初始狀態(tài)及初始決策如何，對于先前決策所形成的狀態(tài)而言，余下的諸決策仍構(gòu)成最優(yōu)策略?！币粋€最優(yōu)策略的子策略也是最優(yōu)的。,最優(yōu)策略的任何一部分子策略，也是它相應(yīng)初始狀態(tài)的最優(yōu)策略。每個最優(yōu)策略只能由最優(yōu)子策略構(gòu)成。,含義,動態(tài)規(guī)劃的理論基礎(chǔ),,動態(tài)規(guī)劃的最優(yōu)性定理：設(shè)階段數(shù)為 n 的多階段決策過程，其階段編號為k=0,1,...,n-1。允許策

20、略p*0, n-1= ( u*0, u*1, …, u*n-1 )是最優(yōu)策略的充要條件是: 對任意一個 k, 0 < k < n-1和 s0 ? S0，有,,,,,,推論：若允許策略 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)策略。（注意：

21、k 段狀態(tài) s*k ，是由 s0 和 p*0, k-1 所確定的）,最優(yōu)性原理,,最優(yōu)化原理為必要條件,最優(yōu)性定理為充要條件!最優(yōu)化原理為最優(yōu)性定理的推論!最優(yōu)性定理才是動態(tài)規(guī)劃的理論基礎(chǔ)!,,動態(tài)規(guī)劃(逆序法)小結(jié):,1.將問題的過程劃分成恰當(dāng)?shù)碾A段;對于靜態(tài)問題要人為地賦予“時間”概念, 以便劃分階段.2.選擇狀態(tài)變量 sk , 既能描述過程的變化又滿足無后效性;3.確定決策變量 uk 及每一階段的允許決策集合Dk( sk

22、);4.正確寫出狀態(tài)轉(zhuǎn)移方程; 狀態(tài)轉(zhuǎn)移方程應(yīng)當(dāng)具有遞推關(guān)系.5.正確寫出階段指標(biāo)函數(shù)和最優(yōu)指標(biāo)函數(shù)，建立動態(tài)規(guī)劃基本方程階段指標(biāo)函數(shù)是指第k 階段的收益，最優(yōu)指標(biāo)函數(shù)是指從第k 階段狀態(tài)出發(fā)到第n 階段末所獲得收益的最優(yōu)值，最后寫出動態(tài)規(guī)劃基本方程。,,逆序解法的基本方程,(1)指標(biāo)函數(shù)為“和”的形式,(2)指標(biāo)函數(shù)為“積”的形式,和、積函數(shù)的基本方程中邊界條件不一樣,,,,,求解時從邊界條件開始,逆（或順）

23、過程行進(jìn)方向,逐段遞推尋優(yōu). 每段決策的選取都是從全局考慮的,與該段的最優(yōu)選擇答案一般是不同的.在求整個問題的最優(yōu)策略時,由于初始狀態(tài)是已知的,每段的決策都是該段狀態(tài)的函數(shù),故最優(yōu)策略所經(jīng)過的各段狀態(tài)便可逐次變換得到,從而確定了最優(yōu)路線.,動態(tài)規(guī)劃和靜態(tài)規(guī)劃的關(guān)系,二者都屬于數(shù)學(xué)規(guī)劃的范圍，本質(zhì)上都是求極值的問題。都是用迭代法逐步求解。靜態(tài)規(guī)劃（如線性規(guī)劃）研究的問題是與時間無關(guān)的，每步迭代是整體改進(jìn)。動態(tài)規(guī)劃是用來解決多階段決

24、策過程最優(yōu)化的一種數(shù)量方法。把問題的整體，恰當(dāng)?shù)胤譃槿舾蓚€相互聯(lián)系的階段，按一定的次序去求解單階段決策問題。每步迭代是由當(dāng)前階段到“下”個階段。對于某些靜態(tài)的問題可以人為的引入時間因素，把它看作按階段進(jìn)行的一個動態(tài)規(guī)劃問題，從而把一個n 維決策問題變換為幾個一維最優(yōu)化問題，一個一個地去解決。,1.動態(tài)規(guī)劃的四大要素 ①決策變量及其允許集合 uk?Uk ②狀態(tài)變量及其可能集合 sk?Sk ③狀態(tài)轉(zhuǎn)移方程 xk+1=Tk (s

25、k,uk) ④階段指標(biāo) vk (sk,uk),動態(tài)規(guī)劃 非常 4+1,2. 動態(tài)規(guī)劃基本方程 fn+1(sn+1) = 0 (邊界條件) fk(sk) = opt u{vk (sk , uk ) + fk+1(sk+1)} k = n , n-1, … , 1,兩個變量+兩個方程,解：可列出靜態(tài)規(guī)劃問題的模型如下,§4 動態(tài)規(guī)劃與靜態(tài)規(guī)劃,,分階段：

26、,每一階段可使用的資金數(shù)為狀態(tài)變量sk。,狀態(tài)轉(zhuǎn)移方程,確定決策變量：,確定狀態(tài)變量：,分三個階段，即k=3，2，1。,通?？梢匀§o態(tài)規(guī)劃中的變量為決策變量。,,指標(biāo)函數(shù),基本方程,當(dāng)階段 k =3 時，有,,當(dāng)階段k=2時，有,當(dāng)階段k=1時，有,是凸函數(shù)，最大值點只能在[0,s1]的端點上取得，即,2階導(dǎo)數(shù)>0,（最優(yōu)決策）,,所以,最優(yōu)投資方案是全部資金投于第3個項目，可得最大收益200萬元。,例2 求解下面問題：,(考慮用

27、動態(tài)規(guī)劃的逆序法進(jìn)行求解。),解題思路？,,解：,1、將該問題劃分為三個階段，即k=1，2，3,2、確定狀態(tài)變量并可得狀態(tài)轉(zhuǎn)移方程：,3、指標(biāo)函數(shù),,4、基本方程,最優(yōu)值函數(shù),當(dāng)階段k=3時，有,最優(yōu)決策,當(dāng)階段k=2時，有,,因此最后可得：,當(dāng)階段k=1時，有,,例2’ 求解下面問題：,練習(xí)1,P212 8.5 (1),練習(xí)2,,,動態(tài)規(guī)劃的優(yōu)缺點,優(yōu)點: 最優(yōu)解是全局最優(yōu)解。 能得到一系列（包括子過程）的最優(yōu)解。 不需要對系統(tǒng)

28、狀態(tài)轉(zhuǎn)移方程、階段效應(yīng)函數(shù)等 的解析性質(zhì)作任何假設(shè)。,缺點： 沒有統(tǒng)一的標(biāo)準(zhǔn)模型和標(biāo)準(zhǔn)的算法可供使用。 應(yīng)用的局限性，要求滿足“無后效性”。 “維數(shù)災(zāi)難”問題。,,,,,,,,,,設(shè)有某種原料,總數(shù)量為a,用于生產(chǎn)n 種產(chǎn)品.若分配數(shù)量 xi 用于生產(chǎn)第 i 種產(chǎn)品, 其收益為 gi ( xi )，問應(yīng)如何分配, 才能使生產(chǎn) n 種產(chǎn)品的總收入最大？,§5 資源分配問題,5.1 資源平行分配問題—離散決策變量,靜

29、態(tài)規(guī)劃模型,,例3 某公司擬將5臺某種設(shè)備分配給所屬的甲、乙、丙三個工廠,各工廠若獲得這種設(shè)備,可以為公司提供的盈利如表. 問：這五臺設(shè)備如何分配給各工廠,才能使公司得到的盈利最大.,,如何劃分階段,,s1的可達(dá)狀態(tài)集合,s2的可達(dá)狀態(tài)集合,s3的可達(dá)狀態(tài)集合,,,,,,,,,決策變量 uk(sk),0? ? sk,3個階段,xk,狀態(tài)轉(zhuǎn)移方程？,,s1,s2,s3,3,2,1,,,,,x1,x2

30、,x3,,,,基本方程?,指標(biāo)函數(shù)gk(xk)?,s4,,解：將問題按工廠分為三個階段，甲、乙、丙分別編號為1，2，3。,決策變量xk::,分配給第 k 個工廠的設(shè)備數(shù)量,分配給第 k 個工廠至第 3 個工廠的設(shè)備數(shù)量。,狀態(tài)變量 sk :,,Dk ( sk )={ uk|0? xk ? sk },基本方程：,數(shù)量為 sk 的原料分配給第 k 個工廠至第 3 個工廠所得到的最大總收益,,,,狀態(tài)轉(zhuǎn)移方程:,sk+1 = sk - xk,

31、xk的取值范圍？,,x3*(0) = 0,x3*(1) = 1,x3*(2) = 2,x3*(3) = 3,k =3，s3=0,1,2,3,4,5，0? x3 ? s3,s3 = 0,s3 = 3,046111212,s3 = 2,s3 = 1,x3*(5) = 4,5,x3*(4) = 4,046111212,結(jié)果可寫成表格的形式:,s3 = 4,s3 = 5,,k =2，s3 = s2 - x2，s2

32、=0,1,2,3,4,5，0? x2 ? s2，有,x2*(0) = 0,s2 = 0,,,,,,x2*(1) =1,s2 = 1,s3 = s2 - x2，s2=0,1,2,3,4,5，0? x2 ? s2,,x2*(2) =2,s2 = 2,,x2*(3) =2,s2 = 3,,x2*(4) =1,2,s2 = 4,,,s2 = 5,x2*(5) =2,,結(jié)果列于下表：,k =1時, s2 = s1 - x1, s1 = 5,

33、 0? x1 ? s1,有,,,,,x1*(5) =0,2,,,結(jié)果可寫成表格的形式,最優(yōu)分配方案一：由 x1* = 0，根據(jù) s2 = s1- x1* = 5- 0 = 5，查表知 x2* = 2，由s3 = s2- x2* = 5 - 2 = 3，故 x3* = s3 =3。即得甲工廠分配0臺，乙工廠分配2臺，丙工廠分配3臺。,最優(yōu)分配方案？,最優(yōu)分配方案二：由 x1* = 2，根據(jù) s2 = s1 - x1* = 5- 2 =

34、3，查表知 x2*= 2，由 s3 = s2 - x2*= 3 - 2 =1，故 x3* = s3 =1。即得甲工廠分配2臺，乙工廠分配2臺，丙工廠分配1臺。,以上兩個分配方案所得到的總盈利均為21萬元。,問題： 如果原設(shè)備臺數(shù)是4臺，求最優(yōu)分配方案？ 如果原設(shè)備臺數(shù)是3臺，求最優(yōu)分配方案？ 如果原設(shè)備臺數(shù)是6臺，求最優(yōu)分配方案？,,例3 某公司擬將5臺某種設(shè)備分配給所屬的甲、乙、丙三個工廠,各工廠若獲得這種設(shè)備,

35、可以為公司提供的盈利如表. 問：這五臺設(shè)備如何分配給各工廠,才能使公司得到的盈利最大.,,,,Dk ( sk )={ uk|0? xk ? sk },,資源分配問題,資源平行分配問題—只合理分配資源, 不考慮回收 決策變量為離散值. 銷售點分配問題；投資分配問題；貨物分配問題 資源連續(xù)分配問題—考慮資源回收利用 決策變量為連續(xù)值,,資源連續(xù)分配問題,,5.2 資源連續(xù)分配問題,如此進(jìn)行 n 年,

36、 如何確定投入 A 的資源量 u1、…、un, 使總收入最大？,,此問題的靜態(tài)規(guī)劃問題模型為：,,,,S1,S2,S3,高負(fù)荷: 產(chǎn)量函數(shù) g = 8u1， 年完好率為 a=0.7，,,機器,例4 機器負(fù)荷分配問題,假定開始生產(chǎn)時完好機器的數(shù)量為1000臺。,低負(fù)荷: 產(chǎn)量函數(shù) h = 5y， 年完好率為 b=0.9。,試問每年如何安排機器在高低兩種負(fù)荷下

37、的生產(chǎn),可使5年內(nèi)生產(chǎn)的產(chǎn)品總產(chǎn)量最高?,投入生產(chǎn)的機器數(shù)量,,,狀態(tài)變量 sk,狀態(tài)轉(zhuǎn)移方程,決策變量 uk,第 k 年初擁有的完好機器臺數(shù),第 k 年高負(fù)荷下投入的機器數(shù),sk+1 = auk+ b(sk - uk) = 0.7uk+ 0.9 (sk -uk),0 ? uk ? sk,分析：,,第 k 年低負(fù)荷下投入的機器數(shù),sk – uk,,,,階段？,遞推方程？,指標(biāo)函數(shù),第k年度產(chǎn)量為,k = 5, 4, 3, 2, 1,

38、,,,sk+1,,,階段指標(biāo),f6(s6) = 0,則狀態(tài)轉(zhuǎn)移方程為,sk+1 = 0.7uk+ 0.9 (sk - uk) k = 1, 2, …, 5,解：設(shè)階段序數(shù) k 表示年度, sk為第 k 年初擁有的完好機器臺數(shù), 第 k 年度高負(fù)荷下投入的機器數(shù)為uk臺.,基本方程為,f4(s4) = 13.6s4,u*4 = s4,k = 4,u*5 = s5,k = 5,f5(s5) = 8s5,,,0,依次類推可得，,因

39、此最優(yōu)策略為,最高產(chǎn)量為23700。,,練習(xí)：1. 每年年初的完好機器數(shù)。 2. 如規(guī)定在第五年結(jié)束時完好機器數(shù)為500臺，該如何安排生產(chǎn)？,k = 4,k = 5,其他略,練習(xí) 1,,,生產(chǎn)與存儲問題,設(shè)某公司對某種產(chǎn)品要制訂一項n個階段的生產(chǎn)(或購買)計劃.已知它的初始庫存量為0,每階段生產(chǎn)(或購買)該產(chǎn)品的數(shù)量有上限的限制;每階段對該產(chǎn)品的需求量是已知的,公司保證供應(yīng);在n階段末的終結(jié)庫存量為0.問該公

40、司如何制訂每個階段的生產(chǎn)(或采購)計劃,從而使總成本最小.,固定成本為 3千元,單位產(chǎn)品成本為1千元,最大生產(chǎn)批量不超過6個單位,每個時期末未售出的產(chǎn)品,每單位需付存貯費0.5千元.,,按4個時期將問題分為4個階段。第k個時期內(nèi)的生產(chǎn)成本為：,第k時期末庫存量為vk時存貯費用為：,第k時內(nèi)的總成本為：,,,,生產(chǎn)與存儲問題的特征,§6 生產(chǎn)與存貯問題,生產(chǎn)周期分為 n 個階段，已知 最初庫存量: s1

41、 階段市場的需求: dk 生產(chǎn)的固定成本: K 單位產(chǎn)品的消耗費用: L 單位產(chǎn)品的階段庫存費用: h 階段生產(chǎn)能力為: B 倉庫容量: M,一個生產(chǎn)部門，如何在已知生產(chǎn)成本、庫存費用和各階段市場需求條件下，決定各階段產(chǎn)量，使計劃內(nèi)的費用總和為最小的問題。,問如何安排各階段產(chǎn)量,使計劃周期內(nèi)的費用總和最小.,不能超過階段 k 至階段 n 的需求總

42、量,sk ? dk+ dk+1+?+ dn，k =1, 2, ?, n,階段 k 的初始庫存量，s1已知，sn+1 = 0,0 ? sk ? min {M, dk+ dk+1+?+ dn},（k =1, 2, ?, n）,狀態(tài)變量 xk：,不能超過庫存容量M，,決策變量 uk：,不超過生產(chǎn)能力,階段 k 的產(chǎn)量,uk ? dk+dk+1+?+dn - sk,不小于該階段的需求和庫存量之差，,不超過 k?n 階段的總需求減去第 k 階段

43、初的庫存量，,dk-sk ? uk ? min{B, dk+dk+1+?+dn-sk},狀態(tài)轉(zhuǎn)移方程,為階段生產(chǎn)費用和庫存費用之和，即,階段 k 的生產(chǎn)費用,k 階段末的庫存費用,動態(tài)規(guī)劃基本方程,階段效益,fn+1（sn+1）= 0，k = 1, 2, ?, n,,,例5 已知 n = 3, K = 8, L = 2, h = 2, s1 = 1, M = 4, s4 = 0, B = 6, d1 = 3, d2 = 4, d

44、3 = 3, 求解生產(chǎn)與庫存問題.,解：遞推方程,f 4 ( s4 ) = 0，k = 1, 2, 3,,倉庫容量4,dk-sk ? uk ?min{B,dk+dk+1+?+dn-sk},0 ? sk ? min {M, dk+ dk+1+?+ dn},（k =1, 2, ?, n）,dk-sk ? uk ? min{B, dk+dk+1+?+dn-sk},,f3(s3)= 14-2s3 u3 =3-s3,s3：0

45、～3,,k =2,容量4,4+3,uk?dk-sk,4-s2?u2?min{B,d2+d3-s2}=min{6,7-s2},0 ? s2 ? min{M, d2+ d3} =min{4,7}=4,例5 已知 n = 3, K = 8, L = 2, h = 2, s1 = 1, M = 4, s4 = 0, B = 6, d1 = 3, d2 = 4, d3 = 3, 求解生產(chǎn)與庫存問題.,,4-s2 ? u2 ? min{6,7

46、-s2},f2 (s2 ) =min {4u2+2s2+ f3 (s2 + u2-4)},,,k =1,,例5 已知 n = 3, K = 8, L = 2, h = 2, s1 = 1, M = 4, s4 = 0, B = 6, d1 = 3, d2 = 4, d3 = 3, 求解生產(chǎn)與庫存問題.,dk-sk ? uk ? min{B, dk+dk+1+?+dn-sk},2 ? u1 ? 6,s1 = 1,,,,,最優(yōu)決策為,

47、{1，0，0，0},s2=u1-2=0,s3=s2+u2-d2=0+4-4=0,最優(yōu)路線為,最優(yōu)目標(biāo)函數(shù)值為42.,（狀態(tài)變量）,u*1 (1) = 2，u*2 (0) = 4， u*3 (0) = 3,,設(shè)備更新問題提法如下（以一臺機器為例）： n為設(shè)備計劃使用年數(shù)。 Ik(t) 為第k年（階段）機器役齡為t年的一臺機器運行（在使用一年）所得的收入。 Ok(t) 為第k年機器役齡為

48、t年的一臺機器運行（再使用一年）時所需運行的費用（或維修費用） 。 Ck(t) 為第k年機器役齡為t年的一臺機器更新時所需的凈費用（處理一臺役齡為t的舊設(shè)備，買進(jìn)一臺新設(shè)備的更新凈費用）。,§7 設(shè)備更新問題,,?為折扣因子,表示一年以后的收入是上一年的?單位. 要求在n年內(nèi)的每年年初作出決策,是繼續(xù)使用舊設(shè)備還是更換一臺新的,使n年內(nèi)總效益最大?,建立動態(tài)規(guī)劃模型如下：,階段k（k=1，2，…，n）表示

49、計劃使用該設(shè)備的年限數(shù)。,狀態(tài)變量sk: 第k年初,設(shè)備已使用過的年數(shù),即役齡.,決策變量xk: 是第k年初更新, 還是保留使用舊設(shè)備, 分別用R , K表示.,階段效益為：,狀態(tài)轉(zhuǎn)移方程為：,最優(yōu)指標(biāo)函數(shù)fk(sk): 表示第k年初, 使用一臺已用了sk年的設(shè)備, 到第n年末的最大收益.,實際上,例7：設(shè)某臺新設(shè)備的年效益及年均維修費用、更新凈費用如下表，試確定今后五年內(nèi)的更新策略，使總效益最大。（設(shè)?=1）,動態(tài)規(guī)劃的基本方程為,解

50、：n=5,狀態(tài)變量s5可取1，2，3，4,單位：萬元,賣掉役齡2年的設(shè)備，買入新設(shè)備的更新費用,狀態(tài)變量s4可取1，2，3,此時s3可取1或2,,由于狀態(tài)s2只能取1，所以有,,由于狀態(tài)s1只能取0，所以有,尋找最優(yōu)解，上述過程遞推回去。,,當(dāng)x*1(0)=K，由狀態(tài)轉(zhuǎn)移方程,本例的最優(yōu)策略是{K，R，R，R，K}，即第一年初購買的設(shè)備到第二、三、四年初各更換一次，用到第五年年末，總效益為17萬元。,s2=1，查f2(1)得x*2=R,

51、s3=1，查f3(1)得x*3=R,s4=1，查f4(1)得x*4=R,s5=1，查f5(1)得x*5=K,,,,,,,練習(xí)：現(xiàn)有資金5百萬元，可對三個項目進(jìn)行投資，投資額均為整數(shù)（單位為百萬元）。其中2#項目的投資不得超過3百萬元，1#和3#項目的投資均不得超過4百萬元，3#項目至少要投資1百萬元。每個項目投資五年后，預(yù)計可獲得的收益如下表所示。如何投資可望獲得最大收益？請用動態(tài)規(guī)劃方法求解。,,,,,,,,,,,,,,,,考研試題,

52、1. 下列關(guān)于動態(tài)規(guī)劃問題的說法不正確的是（ ）。A．應(yīng)用推理或逆推法可能會得出不同的最優(yōu)解B．狀態(tài)變量應(yīng)具有無后效性C．動態(tài)規(guī)劃模型中，階段是按時間或空間劃分的D．問題的階段數(shù)等于問題中的子問題的數(shù)目2. 用動態(tài)規(guī)劃方法求解多階段問題時，指標(biāo)函數(shù)應(yīng)滿足（ ）。A．定義在全過程和后部子過程上的數(shù)量函數(shù)B．具有可分離性，滿足遞推關(guān)系 C．嚴(yán)格單調(diào) D．以上A、B、C都是,,3. 下述的( )不能設(shè)為動態(tài)規(guī)劃中的狀態(tài)