1、2020/9/5,1,2020/9/5,1,第七章 動態(tài)規(guī)劃Dynamic Programming，DP,美國數(shù)學家貝爾曼 (Richard Bellman, 19201984),創(chuàng)始時間,上個世紀50年代,創(chuàng)始人,動態(tài)規(guī)劃是運籌學的主要分支之一, 是現(xiàn)代企業(yè)管理中的一種重要決策方法, 它是解決多階段決策過程的一種最優(yōu)化方法,2020/9/5,2,本章主要內(nèi)容,多階段決策過程及其問題舉例 最短路問題 動態(tài)規(guī)劃的基本概念和基本方程 動態(tài)規(guī)劃應用舉例 資源分配問題 背包問題 生產(chǎn)庫存問題 ,2020/9/5,3,7.1 多階段決策過程及其問題舉例,動態(tài)規(guī)劃研究的問題多階段決策問題 在時間或空間上可

2、以劃分為若干階段，每一階段都需要根據(jù)現(xiàn)階段的情況做出決策 決策者每段決策時，不僅要考慮本階段目標最優(yōu)，還應考慮之后各階段的目標最優(yōu)，最終達到整個決策活動的總體目標最優(yōu) 當各個階段的決策確定后，就構(gòu)成了一個決策序列 各階段的決策一般與時間有關，故稱“動態(tài)”。但某些“靜態(tài)”問題可通過引進“時間”因素，用動態(tài)規(guī)劃方法來處理,2020/9/5,4,動態(tài)規(guī)劃分類： 離散確定性動態(tài)規(guī)劃 離散隨機性動態(tài)規(guī)劃 連續(xù)確定性動態(tài)規(guī)劃 連續(xù)隨機性動態(tài)規(guī)劃,2020/9/5,5,例1 最短路徑問題,第一階段 第二階段 第三階段 第四階段 求從 A 到 H 的最短路徑,2020/9/5,6,2020/9/5,6,第一種

3、方法稱做枚舉法（窮舉法）：基本思想是列舉出所有可能發(fā)生的方案和結(jié)果，再對它們進行比較，求出最優(yōu)方案。這里，從 A 到 H 的路程共有7條可能的路線，分別算出各條路線的距離，最后進行比較，可得最優(yōu)路線 當節(jié)點很多時，用窮舉法求最優(yōu)路線的計算工作量將會十分龐大，而且其中包含著許多重復計算 第二種方法熟稱貪心算法，亦即“局部最優(yōu)路徑”法，只選擇當前最短途徑，“逢近便走”，錯誤地以為局部最優(yōu)會致整體最優(yōu)。在這種想法指導下，所取決策必是 A C G H，距離為 4+5+8=17,2020/9/5,7,d(sk, uk)：第 k 階段，采取策略 uk 所發(fā)生的距離 fk(sk)：第 k 階段，在 sk 狀

4、態(tài)時到終點 H 的最短距離,動態(tài)規(guī)劃的基本思想：如果起點 A 經(jīng)過 B, E 而到 H最優(yōu)，則由 B 出發(fā)經(jīng) E 到 H 這條子路線，必為從 B 到 H 的最短路線。所以，尋找最短路線，應該從最后一段開始找，然后往前遞推 假設 sk：第 k 階段初所處的節(jié)點,uk(sk)：在 sk 狀態(tài)時第 k 階段所作的決定,2020/9/5,8,2020/9/5,9,f3(E)=3,2020/9/5,10,f3(F)=5,2020/9/5,11,f3(G)=8,2020/9/5,12,f2(B)=13,2020/9/5,13,f2(C)=10,2020/9/5,14,f2(D)=8,2020/9/5,15

5、,f1(A)=14,2020/9/5,16,狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài),A （ AC） C （CE） E （EH） H 從A到H的最短路徑：距離為14，路線為ACEH,2020/9/5,17,2020/9/5,17,多階段決策過程及實例：標號法,4,3,7,5,9,7,6,8,13,10,9,12,13,16,18,從G到A的解法稱為逆序解法,注：因為從A到G的最短路與從G到A的最短路是一樣的，因此也可以從A出發(fā)來找。從A到G的解法稱為順序解法,2020/9/5,18,2020/9/5,18,綜上可見，全枚舉法雖可找出最優(yōu)方案，但不是好算法；局部最優(yōu)法則完全是個錯誤方

6、法；只有動態(tài)規(guī)劃方法屬于科學有效的算法。它的基本思想是，把一個比較復雜的問題分解為一系列同類型的更易求解的子問題,2020/9/5,19,7.2 動態(tài)規(guī)劃的基本概念和基本方程,(一) 基本概念和基本方程,(1) 階段：k = 1, , n,(2) 狀態(tài)變量 sk ：第 k 階段的自然狀況,(3) 決策變量 uk(sk) ：第 k 階段的決定 Dk(sk) ：決策變量的取值范圍,2020/9/5,20,(4) 狀態(tài)轉(zhuǎn)移方程 sk1 T (sk, uk)：描述第 k 階段與第 k+1 階段的狀態(tài)變量的關系,(5) 指標 v (sk ,uk) ：第 k 階段在狀態(tài) sk 下采取決策 uk 得到的 結(jié)

7、果（距離、得益、成本等） 指標函數(shù)是指各階段指標的累計。即 V (sk,uk, , sn,un, sn+1)=vk(sk,uk)*vk+1(sk+1,uk+1)*vn(sn,un) 它表示從第 k 階段的狀態(tài) sk 開始到第 n 階段的終止狀態(tài)的指標累計。式中*表示某種運算符，一般為加法或乘積運算,(6) 最優(yōu)指標函數(shù) fk (sk) ：它表示從第 k 階段的狀態(tài) sk 開始到 第 n 階段終止的過程中，采取最優(yōu)策略得到的指標函數(shù)值,2020/9/5,21,2020/9/5,21,逆推公式,或,多階段決策問題中，常見的目標函數(shù)形式之一是取各階段效益之和的形式。有些問題，如系統(tǒng)可靠性問題，其目標

8、函數(shù)是取各階段效益的連乘積形式?？傊?，具體問題的目標函數(shù)表達形式需要視具體問題而定,Max 或 Min,2020/9/5,22,對例1,(1) 階段：k1,2,3,(2) 狀態(tài)變量 sk ：第 k 階段初所處的位置, 狀態(tài)集合 Sk, 如 S2 =B , C, D,(3) 決策變量 uk ：在第 k 段 sk 狀態(tài)時的路徑選擇,(4) 狀態(tài)轉(zhuǎn)移方程 ：sk1 uk (sk),2020/9/5,23,(5) 指標： vk (sk ，uk) 為第 k 階段采取決策 uk 時到下一狀態(tài)的距離 指標函數(shù),(6) 最優(yōu)指標函數(shù)： fk (sk)：第 k 階段，在 sk 狀態(tài)時到終點 H 的最短距離,20

9、20/9/5,24,2020/9/5,24,（二）貝爾曼最優(yōu)化原理 最優(yōu)策略具有這樣的性質(zhì)：不論初始狀態(tài)與初始策略如何，對于先前決策所造成的狀態(tài)而言，余下所有決策必構(gòu)成最優(yōu)決策。即：最優(yōu)策略的子策略也是最優(yōu)的！,2020/9/5,25,（三）解法步驟 首先將問題劃分為若干個階段，然后選擇狀態(tài)變量與決策變量，并寫出轉(zhuǎn)移方程和指標函數(shù)，列出基本方程 反向條件優(yōu)化 正向求最優(yōu)解,2020/9/5,26,7.3 應用舉例,例2 資源分配問題() 例3 資源分配問題() 例4 背包問題 例5 生產(chǎn)庫存問題 例6 可靠性問題 例7 機器負荷分配問題 ,2020/9/5,27,例 2 資源分配問題(),某公

10、司準備將 5 臺設備分配給所屬的三個子工廠，各工廠獲得設備后的可盈利情況如表所示。問：如何分配這五臺設備，才能使公司獲得的收益最大？,2020/9/5,28,分析,(1) 階段：k =1，2，3,(3) 決策變量 uk ：對第 k 階段的分配數(shù),(2) 狀態(tài)變量 sk ：可分配給第 k 個至第 3 個企業(yè)的 設備數(shù)（亦即第 k 階段初可供分配的設備數(shù)）,(4) 狀態(tài)轉(zhuǎn)移方程： sk1 sk - uk,(5) 指標函數(shù) gk (uk) ：分配 uk 臺設備給第 k 個工廠所產(chǎn)生 的收益 (6) 最優(yōu)指標函數(shù) fk (sk) ：第 k 至 第 3 階段采取最優(yōu) 分配策略可產(chǎn)生的最大收益,2020/

11、9/5,29,逆推公式：,其中,2020/9/5,30,2020/9/5,30,k=3, S3 = 0,1,2,3,4,5, f3(s3) maxg3(u3)+0,2020/9/5,31,2020/9/5,31,k=2, S2 = 0,1,2,3,4,5, f2(s2) maxg2(u2)+ f3(s3),S3=S2-u3,2020/9/5,32,2020/9/5,32,k=1, S1 = 5, f1(s1) max g1(u1)+ f2(s2),得到兩種方案： u1*0，u2*2，u3*3: 工廠1分配0臺，工廠2 分配2臺，工廠3分配3臺 u1*2，u2*2，u3*1: 工廠1分配2臺，工

12、廠2 分配2臺，工廠3分配1臺 總盈利均為21萬元,同理得到另一組最優(yōu)解,2020/9/5,33,一般分配問題,某種資源的總量為 a，用于 n 種生產(chǎn) 若分配 uk 于第 k 種生產(chǎn)時，收益為 gk(xk),問：應如何分配才能使總收入最大？ 該問題的數(shù)學模型為,Max z = g1 (u1 )+ g2 (u2 )+ gn (un),s.t. u1 +u2 +un= a uk0,2020/9/5,34,分析,(1) 階段：k =1，2，., n,(3) 決策變量 uk ：對第 k 階段的分配數(shù),(2) 狀態(tài)變量 sk ：第 k 階段初可供分配的資源數(shù),(4) 狀態(tài)轉(zhuǎn)移方程： sk1 sk - u

13、k,(5) 指標函數(shù) gk (uk) ：uk 臺設備分配給第 k 種生產(chǎn)所產(chǎn)生 的收益 (6) 最優(yōu)指標函數(shù) fk (sk) ：第 k 至 n 階段采取最優(yōu)分配策 略可產(chǎn)生的最大收益,2020/9/5,35,逆推公式：,2020/9/5,36,例3 資源分配問題(),某工廠要進行A,B,C三種新產(chǎn)品的試制，為提高三種產(chǎn)品研制成功的概率，決定調(diào)撥經(jīng)費2百萬，并要求資金集中使用，也即以百萬為單位進行分配，其增加研發(fā)費與新產(chǎn)品不成功概率的關系如表所示。問：如何分配資金，可使三種產(chǎn)品都研制不成功的概率最??？,2020/9/5,37,分析,(1) 階段：k = 1，2，3,(3) 決策變量 uk ：對第

14、 k 階段分配金額,(2) 狀態(tài)變量 sk ：第 k 階段初的可用金額,(4) 狀態(tài)轉(zhuǎn)移方程： sk1 sk - uk,(5) 最優(yōu)指標函數(shù) fk (sk) ：第 k 至 3 階段采取最優(yōu) 分配策略時的最小不成功概率的值,2020/9/5,38,逆推公式：,其中 gk (uk) 是階段函數(shù),2020/9/5,39,k=3, S3 = 0,1,2, f3(s3) ming3(u3)*1,2020/9/5,40,k=2, S2 = 0,1,2, f2(s2) ming2(u2)*f3(s3),2020/9/5,41,k=1, S1 = 2, f1(s1) max g1(u1)* f2(s2),得到

15、方案：u1*1，u2*0，u3*1: 產(chǎn)品 A分配 1百萬，產(chǎn)品 B分配0，產(chǎn)品 C分配1百萬，f *=0.06,2020/9/5,42,例4 背包問題 某卡車載重能力為10噸，現(xiàn)要裝三種產(chǎn)品，已知每件產(chǎn)品的重量和利潤如表。又規(guī)定產(chǎn)品3至多裝2件。問：如何安排運輸可使總利潤最大？,2020/9/5,43,階段：k=1,2,3 狀態(tài)變量 sk：第 k 階段初的可裝載能力 決策變量 uk：第 k 階段的裝載件數(shù) 狀態(tài)轉(zhuǎn)移方程： （tk 為 k 產(chǎn)品的單件重量） 最優(yōu)指標函數(shù) fk(sk)：第k-3階段采取最優(yōu)策略時的最大利潤 遞推公式： k=3,2,1 f4(s4)=0,動態(tài)規(guī)劃方法求解,2020

16、/9/5,44,物品1,物品2,物品3,k=1,k=2,k=3,k=4,s1=10,s2,s3,s4,階段,狀態(tài)變量： 裝載前背包的容量,決策變量： 裝載的件數(shù),u1,u2,u3,決策允許集合： 裝載件數(shù)的范圍,0u1s1/t1 u1為整數(shù),狀態(tài)轉(zhuǎn)移方程：背包容量和裝載件數(shù)的關系,階段指標： vk(sk,uk)=rkuk 在背包中第k種物品的價值,最優(yōu)指標： fk(sk)=maxrkuk+fk+1(sk+1),終端條件：,f4(s4)=0,s2s1-t1u1,s3=s2-t2u2,s4=s3-t3u3,0u2s2/t2 u2為整數(shù),0u3mins3/t3, 2 u3為整數(shù),2020/9/5,4

17、5,k =3,C的單件重量為t3=2,2020/9/5,46,k=2：裝載物品B，f2(s2),B的單件重量為t2=3,2020/9/5,47,k=1：裝載物品A， f1(u1),最優(yōu)解：物品A裝0件，物品B裝2件，物品C裝2件 最大價值為400元,A的單件重量為t1=4,2020/9/5,48,例5 生產(chǎn)庫存問題 某廠在年末估計，來年4個季度市場對該廠某產(chǎn)品的需求量均為 dk=3 (k=1, 2, 3, 4)，而該廠每季度生產(chǎn)此產(chǎn)品的能力為 bk=5 (k=1, 2, 3, 4) 每季度生產(chǎn)該產(chǎn)品的固定成本為 F=13 (不生產(chǎn)時則為 0)，該產(chǎn)品的單位生產(chǎn)成本為 C=2 如果當季度產(chǎn)品不能

18、售出，則需發(fā)生庫存費用 g=1/件，倉庫能貯存產(chǎn)品的最大數(shù)量 Ek=4 (k=1, 2, 3, 4) 年初年末庫存為 0，而每個季度可以銷售的產(chǎn)品是本季度初的庫存及本季度的產(chǎn)量 試問：在滿足市場需求的前提下，如何安排 4 個季度的生產(chǎn)使生產(chǎn)和庫存的總費用最小?,2020/9/5,49,分析,(1) 階段：k = 1, 2, 3, 4,(2) 狀態(tài)變量 sk ：第 k 季度初的庫存量,(3) 決策變量 uk ：第 k 個季度的產(chǎn)量,(4) 轉(zhuǎn)移方程： sk1 sk +uk - dk,(5) 最優(yōu)指標函數(shù) fk (sk) ：第 k 至第 4 個季度采取最優(yōu)策略 時的最小總費用,2020/9/5,5

19、0,逆推公式：,dk=3: 需求 bk=5: 生產(chǎn)能力 F=13: 固定成本 C=2: 單位生產(chǎn)成本 g=1: 單位庫存費用 Ek=4: 倉庫儲存能力,2020/9/5,51,2020/9/5,52,k = 4,2020/9/5,53,k = 3,2020/9/5,54,k = 2,2020/9/5,55,k = 1,2020/9/5,56,可用總費用為 C，總重量為 W ck 為第 k 個部件裝配一個備用件的費用,wk 為第 k 個部件裝配一個備用件的重量,Pk 第 k 個部件的故障概率,某機器工作系統(tǒng)由 n 個部件組成，這些部件正常工作關系為串聯(lián)。為提高系統(tǒng)工作的可靠性，考慮對每個部件都配

20、備備用件。備用件越多，可靠性越大，但系統(tǒng)的成本、重量、體積都會變大。已知：,例6 可靠性問題,問：在這兩個限制條件下，應如何選用部件的備用件個數(shù)，使得正常工作的可靠性最大？,2020/9/5,57,設 uk 為第 k 個部件裝配備用件的個數(shù)， dk(sk, uk) 為第 k 個部件裝配 uk 個備用件時機器正常工作的概率,2020/9/5,58,動態(tài)規(guī)劃模型,(1) 階段：k = 1, 2, , n,(3) 決策變量 uk ：第 k 個部件上裝的備用件個數(shù),(4) 狀態(tài)轉(zhuǎn)移： sk+1 = sk - ckuk tk+1 = tk - wkuk,(5) 最優(yōu)指標函數(shù) fk (sk , tk)：第

21、 k 至第 n 個部件，采取最優(yōu)策略時機器正常工作的概率,tk ：第 k 至第 n 個部件允許的總重量,2020/9/5,59,2020/9/5,60,某系統(tǒng)由 A, B, C 三個部分串聯(lián)而成，已知： A、B、C 相互獨立 各部分的單件故障率分別為 P1=0.4， P2=0.2， P3=0.5 每個部分的單件價格為：A 部分單價 c1=1 萬元； B 部分單價 c2=2 萬元；C 部分單價 c3=3 萬元 可投資購置部件的金額為10萬元 問：A, B, C 三部分各應購置多少部件才能使系統(tǒng)的總可靠率最大？（假設每部分至少購置一件）,2020/9/5,61,階段：購置 A、B、C 分別為階段1

22、、2、3 狀態(tài)變量 sk：第 k 階段初可用來購買部件的費用 決策變量 uk：第 k 階段購置的件數(shù) 狀態(tài)轉(zhuǎn)移方程：sk+1 = sk - ckuk 指標函數(shù)：第 k 階段本身的可靠率 最優(yōu)指標函數(shù) fk(sk) ：第 k 階段尚有資金 sk 時可能獲得 的最高可靠率 遞推方程 fk(sk)= max dk(sk, uk)fk+1(sk+1) k=3,2,1 f4(s4)=1,2020/9/5,62,第3階段 此時 C 應至少配備 1 個部件，故 s2c3=3 同時 A, B 部件已經(jīng)至少配備 1個部件，故 s210-c1-c2=7,總費用：10 (萬元) 單價：c1=1, c2=2, c3=

23、3 故障率：P1=0.4, P2=0.2, P3=0.5,2020/9/5,63,第2階段 此時 B、C 應至少各配制 1 個部件，故 s2c2+c3=2+3=5 同時 A 部件已經(jīng)至少配備 1個部件，故 s2101=9,總費用：10 (萬元) 單價：c1=1, c2=2, c3=3 故障率：P1=0.4, P2=0.2, P3=0.5,2020/9/5,64,第1階段,總費用：10 (萬元) 單價：c1=1, c2=2, c3=3 故障率：P1=0.4, P2=0.2, P3=0.5,2020/9/5,65,例7 機器負荷分配問題（其它情形之一）,某廠有 120 臺同一規(guī)格完好的機器，每臺機

24、床全年在高負荷下工作可創(chuàng)利 9 萬元，但機器的報廢率高，每年將有 的機器報廢；在低負荷下工作可創(chuàng)利 6 萬元，每年將有 的機器報廢 試擬定連續(xù) 3 年的分配計劃，使得總利潤最大,2020/9/5,66,階段：k1、2、3 狀態(tài)變量 sk：第 k 階段完好的機器數(shù)量 決策變量 uk：第 k 階段用于高負荷工作的機器數(shù)量 狀態(tài)轉(zhuǎn)移方程： 指標函數(shù)： 最優(yōu)指標函數(shù) fk(sk)：第 k 階段尚有機器數(shù)量為 sk 時可能獲得總收益 遞推方程：,2020/9/5,67,采用反向動態(tài)規(guī)劃法，從第3階段算起：,2020/9/5,68,例8 不確定采購問題（其它情形之二）,某廠 5 周內(nèi)需采購一批原料，價格波

25、動見右表 試求：在哪周，以什么價格購進，期望價格最低？,2020/9/5,69,(1) 階段：k =1, 2, 3, 4, 5,(5) 最優(yōu)指標函數(shù) fk( sk)：第 k 到第 5 周采用最優(yōu)采購策略時 的最低期望價格,2020/9/5,70,2020/9/5,71,k=4 f4( s4)= min s4, S4E,k=3 S3E = 0.3 f4 (500)+ 0.3 f4 (600)+ 0.4 f4 (700) =0.3500+ 0.3600+ 0.4610 =574,2020/9/5,72,k=2 S2E = 0.3 f3 (500)+ 0.3 f3 (600)+ 0.4 f3 (700) = 0.3500+ 0.3574+ 0.4574 = 551.8,2020/9/5,73,k=1 S1E = 0.3 f2 (500)+ 0.3 f2 (600)+ 0.4 f2 (700) = 0.3500+ 0.3551.8+ 0.4551.8 = 536.26,2020/9/5,74,最優(yōu)策略：第 1- 3周，價格為500