動態(tài)規(guī)劃(生產(chǎn)和存儲問題)

1、動態(tài)規(guī)劃（生產(chǎn)和存儲問題）一、動態(tài)規(guī)劃法的發(fā)展及其研究內(nèi)容動態(tài)規(guī)劃是運籌學(xué)的一個分支，是求解決策過程最優(yōu)化的數(shù)學(xué)方法。20世紀(jì)50年代初美國數(shù)學(xué)家 R.E.BELLMAN等人在研究多階段決策過程的優(yōu)化問題時，提出了著名的最優(yōu)化原理，把多階段問題轉(zhuǎn)化為一系列的單階段問題，逐個求解創(chuàng)立了解決這類過程優(yōu)化問題的新方法動態(tài)規(guī)劃。 1957 年出版的他的名著Dynamic Proggramming ，這是該領(lǐng)域的第一本著作。動態(tài)規(guī)劃問世以來，在經(jīng)濟管理生產(chǎn)調(diào)度工程技術(shù) 和最優(yōu)控制等方面得到了廣泛的應(yīng)用。例如最短路線庫存 管理資源分配設(shè)備更新組合排序裝載等問題，采 用動態(tài)規(guī)劃法求解比用其他方法更為簡便。二

2、、動態(tài)規(guī)劃法基本概念一個多階段決策過程最優(yōu)化問題的動態(tài)規(guī)劃模型通常包括以下幾個要素：1 階段階段（ stage ）是對整個過程的自然劃分。通常根據(jù)時間順序或是空間特征來劃分階段，對于與時間，空間無關(guān)的“靜態(tài)”優(yōu)化問題，可以根據(jù)其自然特征，人為的賦予“時段”概念，將靜態(tài)問題動態(tài)化，以便按階段的順序解優(yōu)化問題。階段變量一般用 k=1.2 .n.表示。1. 狀態(tài)狀態(tài) (state) 是我們所研究的問題(也叫系統(tǒng))在過個階段的初始狀態(tài)或客觀條件。它應(yīng)能描述過程的特征并且具有無后效性，即當(dāng)某階段的狀態(tài)給定時，這個階段以后的過程的演變與該階段以前各階段的狀態(tài)無關(guān)。通常還要求狀態(tài)是可以直接或者是間接可以觀測

3、的。描述狀態(tài)的變量稱為狀態(tài)變量(State Virable )用 s 表示，狀態(tài)變量的取值集合稱為狀態(tài)集合，用 S 表示。 變量允許取值的范圍稱為允許狀態(tài)集合(set of admissble states). 用x(k) 表示第 k 階段的狀態(tài)變量，它可以是一個數(shù)或者是一個向量。用X(k) 表示第 k 階段的允許狀態(tài)集合。n 個階段的決策過程有n+1 個狀態(tài)變量，x(n+1) 是x(n) 的演變的結(jié)果。根據(jù)演變過程的具體情況，狀態(tài)變量可以是離散的或是連續(xù)的。為了計算方便有時將連續(xù)變量離散化，為了分析的方便有時又將離散的變量視為連續(xù)的。2 決策當(dāng)一個階段的狀態(tài)確定后，可以做出各種選擇從而演變到

4、下一階段的某個狀態(tài)，這種選擇手段稱為決策( decision ) ， 在最優(yōu)控制問題中也稱為控制( control )描述決策的變量稱為決策變量(decision virable ) 。變 量 允 許 取 值 的 范 圍 稱 為 允 許 決 策 集 合 ( set ofadmissble decisions ）。用"£（'（*）表示第 k 階段處于 階段x（k）的決策變量，它是x（k）的函數(shù)，用 心（9） 表示x（k）的允許決策集合決策變量簡稱決策。4.策略決策組成的系列稱為策略（policy ）。由初始狀態(tài) x1開始的全過程的策略記作 丫）.匕（，）一 "

5、;G），人（武2）八:%（"（如 .由第k階段的狀態(tài)x（k）開始到終止?fàn)顟B(tài)的后部子 過程的策略以（*（"）,- 8初二"（必初/"3"）人立，.,n.1.可供選擇的策略有一定的范圍，稱為允許策略集合(set of admissble polices），用431）,小武初等表示。5 .狀態(tài)轉(zhuǎn)移方程在確定性過程中，一旦某階段的狀態(tài)和決策為已知， 下階段的狀態(tài)偏完全可以確定。用狀態(tài)轉(zhuǎn)移方程（state transfer equations ）表示這種演變規(guī)律，寫作：上（左 + 1）=7 （?。?。）,聲（#）， k=l 2E6 .階段指標(biāo)函數(shù)對于k階段

6、的狀態(tài)x（k）,當(dāng)執(zhí)行了決策“D）時，除帶來系統(tǒng)狀態(tài)的轉(zhuǎn)移之外，還產(chǎn)生第k階段的局部利益，它是總效益的一部分，稱為階段指標(biāo)函數(shù)（ stageeffective fuction ）,記作凡爾* >, ”心（左）.7 .過程指標(biāo)函數(shù)用來衡量策略或者是子策略執(zhí)行效果的數(shù)量指標(biāo)稱為 過程指標(biāo)函數(shù) （process effective fuction ）,它定義在所 有k后部子過程上，常用用 匕表示，即% =彳欣1»以或（*+1）,A打）k=1,2,n.當(dāng)k=1時，就是全過程指標(biāo)函數(shù)。如果狀態(tài)x（k）和子策略勺/WQ）給定,那么匕也就被 確定了，所以匕是x（k）和'（幻）的函數(shù)，

7、記為： 九（K（k）+43k）常見的過程指標(biāo)函數(shù)是連和 形式或連積形式：匕=X，（M，）M（x（/）X = 12人 11匕=11（爪）必（式'），* 二 12A7=A*8 .最優(yōu)指標(biāo)函數(shù)過程指標(biāo)函數(shù)=h（工/式尸）的最優(yōu)值稱為最優(yōu)指標(biāo)函數(shù)(optimum effective fuction ),記為 f(x(k).米取了 最優(yōu)子策略尸；3初三2:U "(*()之后, 后部子過程所獲 得的總效益，表示為:八W公)=opi*(x(k),八(*(初W=12 Aopt是optimization的縮寫，意為最優(yōu)化，可以根據(jù)具體問題去max或min三動態(tài)規(guī)劃法的最優(yōu)性原理和基本函數(shù)方程在

8、動態(tài)規(guī)劃中起核心作用的是最優(yōu)性原理：”作為整個過程的最優(yōu)策略具有這樣的性質(zhì)，無論過去的狀態(tài)和決策如 何，相對于前面決策所形成的狀態(tài)而言，余下的決策系列必 須構(gòu)成最優(yōu)子策略?！眲討B(tài)規(guī)劃解法的關(guān)鍵在于給由一種遞推關(guān)系，一般把這種關(guān)系稱為基本函數(shù)方程，匕(式),尸切*伏)=(武行，以(n#) +外田(工出+1),A)注意到無后效性，最優(yōu)指標(biāo)函數(shù)為):卬環(huán)(X姆匕(M*)-w7 匕(丫(牡 (Y)+ 廉+1 (x( +('(± +1)=Of>tMx(k+ opt VMx(k 匕心(M* + I) “上UHJ-平電(式初"*式初)+/(1+1)當(dāng)k=n時，由于x(n+1

9、)是整個決策過程的終止?fàn)顟B(tài)，以后不再做出決策，因此， *35 +(十I) = °這樣就得到了可以用來遞推的基本函數(shù)方程：/“的)二4")+/(刈4 + 1), k f LA 工中f(x(n+1)=0.類似的，可以得到乘法形式的基本函數(shù)方程：/(父(外)="比"(),«()/(x(女+ 1),斤二認(rèn)月一LA 1f(x(n+1)=1.四、建立動態(tài)規(guī)劃模型的基本步驟1 .階段；2 .狀態(tài)變量及可能狀態(tài)集合；3 .決策變量及允許決策集合；4 .狀態(tài)轉(zhuǎn)移方程；5 .階段指數(shù)函數(shù)；6 .基本函數(shù)方程；建立動態(tài)規(guī)劃模型基本上是上面6個步驟，按上述順序逐步確定

10、16的內(nèi)容。五、動態(tài)規(guī)劃法的遞推方向及求解形式1.遞推解法基本方程：/(£#)二則匕(x(后),/(式/)+/(即 + 1), % wl,A.f(x(n+1)=0狀態(tài)轉(zhuǎn)移方程為r(A +1) = 7 (x(A),t(-r() * k ”, 一 1,A J,計算步驟是，利用終端條件從k=n開始由后向前遞推基本方程，求得各階段的最優(yōu)決策和最優(yōu)函數(shù)，最后算由 f(x(1) 時就得到了最優(yōu)決策系列"MM。),上="k)412A M再按照狀態(tài)轉(zhuǎn)移方程* *兇+1)=(武桂«邛)從k=i開始確定*rx(£b序列，丫，卜二修，用為最優(yōu)軌跡線，噌 x伏)，才二

11、12A，北)為最優(yōu)策略。2. 順推解法使用順推解法時，一些概念的含義須做相應(yīng)調(diào)整。狀態(tài)變量x(k)表示第k階段末系統(tǒng)的形態(tài)狀況，最優(yōu)值函數(shù)f(x(k)表示從第一階段到第 k階段總效益的最優(yōu)值，狀 態(tài)轉(zhuǎn)移方程為x(k -1) = T1Hk)M (jr),k = 12A、基本函數(shù)方程為- optrk (x(kuk(x(A) + f(xk -1) ， k = 1,2.Af(x(0)=0 或 13. 求解形式求解動態(tài)規(guī)劃問題，一般有兩種形式：解析形式和表格形式，解析形式是利用函數(shù)的解析表達式，在每個階段用經(jīng)典求極值的方法得到最優(yōu)解。表格形式是指各階段的計算過程均在表格中進行，這種形式便于分析和比較，操

12、作過程直觀且簡練，適用于沒有解析表達式的離散型問題。4. 動態(tài)規(guī)劃的適用條件適用動態(tài)規(guī)劃的問題通常應(yīng)滿足如下3 點：最優(yōu)化原理（最優(yōu)子結(jié)構(gòu)性質(zhì)）。如果問題的最優(yōu)解所包含的子問題的解也是最優(yōu)的，就稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，即滿足最優(yōu)化原理。由于對于有些問題的某些遞歸式來講并不一定能保證最優(yōu)化原則，因此在求解問題時有必要對它進行驗證。若不能保持最優(yōu)原則，則不可以應(yīng)用動態(tài)規(guī)劃法求解。在得到最優(yōu)解的遞歸式之后，需要執(zhí)行回溯以構(gòu)造最優(yōu)解。無后效性。應(yīng)用動態(tài)規(guī)劃法的一個重要條件就是將各階段按照一定的次序排好，階段i 的狀態(tài)只能由階段i+1 的狀態(tài)來確定，與其他狀態(tài)沒有關(guān)系，尤其是于未發(fā)生的狀態(tài)沒有關(guān)系。

13、 換言之， 每個狀態(tài)都是 “過去歷史的一個完整總結(jié)”。這就是無后效性。子問題的重疊性。子問題的重疊性是指在利用遞歸算法自頂向下對問題進行求解時，每次產(chǎn)生的問題并不總是新問題，有些子問題可能會被重復(fù)計算多次。動態(tài)規(guī)劃法正是利用子問題的這種重疊性質(zhì)，對每一個問題只計算一次，然后將其計算結(jié)果保持起來，當(dāng)再次需要計算已經(jīng)計算過的子問題時，只要簡單的查看一下以往的計算結(jié)果，從而獲得較高的解題效率。子問題的的重疊性并不是動態(tài)規(guī)劃適用的必要條件，但是如果該性質(zhì)無法滿足，動態(tài)規(guī)劃算法同其他算法相比就無優(yōu)勢可言了。5. 解決問題的步驟利用動態(tài)規(guī)劃法求解問題的算法通常包含如下幾個步驟。分析。對原始的問題進行分析，

14、找到問題的最優(yōu)解的結(jié)構(gòu)特征。分解。將所給問題按時間或空間特征分解成相互關(guān)聯(lián)的階段，并確定出計算局部最優(yōu)解的遞推關(guān)系，這是利用動態(tài)規(guī)劃法解決問題的關(guān)鍵和難點所在。需要注意的是，分解后的各個階段一定是有序的或者是可以排序的，即無后向性。否則問題就無法用動態(tài)規(guī)劃求解。階段之間相互聯(lián)系方式是通過狀態(tài)和狀態(tài)轉(zhuǎn)移體現(xiàn)的。每個階段通常包含若干個狀態(tài)，可以描述問題發(fā)展到這個階段時所處在的一種客觀情況。每個階段的狀態(tài)都由以前階段的狀態(tài)以某種方式 “變化” 來的， 這樣的 “變化” 稱為狀態(tài)轉(zhuǎn)移。狀態(tài)轉(zhuǎn)移是導(dǎo)出狀態(tài)的途徑，也是聯(lián)系各階段的方式。解決。對于每個階段通過自底向上的方法求得局部最優(yōu)解。由于這一步驟通常是

15、通過遞推實現(xiàn)的，因此，需要遞推終止條件或邊界條件。(4合并。將各個階段求生的解合并為原問題的解，即構(gòu)造一個最優(yōu)解。動態(tài)規(guī)劃的主要難點在于理論的設(shè)計，特別是遞推關(guān)系的建立，一旦設(shè)計完成，實現(xiàn)部分就會非常簡單。整個求解過程就可以使用一個最優(yōu)決策表的二維數(shù)組來描述，其中行表示決策的階段，列表示問題狀態(tài)，表格需要填寫的數(shù)據(jù)一般對應(yīng)此問題的在某階段某個狀態(tài)下的最優(yōu)值，如最短路徑，最長公共子序列，最大價值等。填表的過程就是根據(jù)遞推關(guān)系從 1 行 1 列開始，以行或者列優(yōu)先的順序，依次填寫表格。最后根據(jù)整個表格的數(shù)據(jù)通過簡單的取舍或者運算求得問題的最優(yōu)解?？傊?，動態(tài)規(guī)劃算法的關(guān)鍵在于解決冗余，是一個以空間換

16、時間的技術(shù)，所以它的空間復(fù)雜度要大于其他的算法。六、動態(tài)規(guī)劃問題在問題中的具體實現(xiàn)例如：動態(tài)規(guī)劃規(guī)劃在生產(chǎn)存儲中的運用生產(chǎn) 存儲問題是生產(chǎn)活動中經(jīng)常遇到的問題。大批量生產(chǎn)可以降低成本，但當(dāng)產(chǎn)量大于銷量時就會造成產(chǎn)品積壓而增加庫存費用；單純按市場要求安排生產(chǎn)也會因為開工不足或加班加點造成生產(chǎn)成本增加。因此合理利用存貯資源調(diào)節(jié) 產(chǎn)量，滿足要求是十分有意義的。生產(chǎn)與存貯問題是一個生 產(chǎn)部門如何在已知生產(chǎn)成本，存貯費用和各階段市場要求的 條件下，決定各個生產(chǎn)階段的產(chǎn)量，使得計劃期內(nèi)的費用之 和最小?，F(xiàn)設(shè)有一個生產(chǎn)部門，生產(chǎn)計劃周期為n個階段，已知最初庫存量為x1,階段需求量為 dk,單位產(chǎn)品的消耗費用

17、是lk ,單位產(chǎn)品的階段庫存費用為hk,倉庫容量為m1階段心產(chǎn)量=0生產(chǎn)能力為bk,生產(chǎn)固定成本為問如何安排現(xiàn)階段的產(chǎn)量，使計劃期內(nèi)的費用綜合為最??？該問題本身就是一個多階段決策問題，設(shè)狀態(tài)變量為xk為k階段初的庫存量，由于計劃期初的庫存量 x1已知，計 劃期末的庫存量通常也是給定的， 為簡單起見，假定x(n+1)=0 ,于是狀態(tài)變量 xk 的約束條件是：0MHa W"上 + + d力/ = 1 打決策變量uk選為階段k的產(chǎn)量，它滿足的約束條件是：工/ < Tmin場 & 十 4計,一十 一 口 * q + d* / = 1 -t n狀態(tài)轉(zhuǎn)移方程為 工+工 + % 一它

18、滿足無后效性的要求。階段效用由兩階段組成，一部分為生產(chǎn)費用，另一部分 為存貯費用，即：（0 + 兒（4 d*）= 0門（工+*?。?I Ct + Lku 上 + 陽（h* + w* ak） 4 H。nR = 2 rM/皿）動態(tài)規(guī)劃基本方程為：a 九 Ct* 一4 > + 九門 Ct“iui 0九5）= mintui Icj + 工/曜+ 兒4 + M* 一心）+ fa）如 羊0七、設(shè)計題目：某機床廠根據(jù)合同，在一至四月份為客戶生產(chǎn)某種機床。工廠每月的生產(chǎn)能力為10臺，機床可以庫存，存儲費用為每臺每月 0.2 萬元，每月需要的數(shù)量及每臺機床的生產(chǎn)成本如下表。試確 定每月的生產(chǎn)量，要求既能滿

19、足每月的需求，又能使生產(chǎn)成 本和存儲費用之和達到最小。表 需求量及生廣成本月份1234需求（日）67126生產(chǎn)成本（萬元/臺）77.287.61 .構(gòu)造動態(tài)規(guī)劃模型階段變量k把每個月作為一個階段，k=1,2,3,4狀態(tài)變量不選擇每個階段的庫存量為狀態(tài)變量工工,可滿足無后效性,由已知條件可知：x1=x5=0,單位為臺決策變量”設(shè)每個階段的生產(chǎn)量為決策變量也，由已知條件得0W也w10臺，狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程為：工.= / +也-（d 是第k階段的市 場需求量）階段指標(biāo)第k階段的指標(biāo)費用：八（皿，收）=0.2 4 +y（i）丸（以0） i=1,2,3,4.或匕（工上，肛）=0.2 * +0=0）

20、其中 y1=7, y2=7.2 , y3=8, y4=7.6 ,單位為萬元2 .建立基本方程設(shè)最優(yōu)值函數(shù) 五"是從第k階段的*狀態(tài)生發(fā)到過程終結(jié)的最小費用，按動態(tài)規(guī)劃方法的逆序解基本方程又：人（"=嚷匕（也，H”）+人 5Q（k=4,3,2,1 ）F5（x5）=03 .逆序逆推計算k=4時按照問題的各種約束條件，確定狀態(tài)變量x4的取值范圍。按窮舉法的思路，在量化的精度內(nèi)，確定狀態(tài)變量x4的全部可能取值。狀態(tài)轉(zhuǎn)移方程 x5=x4+u4-d4又 x5=0 , d4=6 所以有 x4+u4=6又因為每個月的最大生產(chǎn)能力為10臺。第1, 2, 3月的需求量為 6, 7, 12 臺，

21、故 x4=0, 1, 2, 3, 4, 4 臺對x4的的確定取值，分別求生決策變量u4的取值范圍當(dāng) x4=0, u4=6;x4=3,u4=3x4=1, u4=5;x4=4, u4=2x4=2, u4=4;x4=5, u4=1由此可知x4與u4是一一對應(yīng)的，即對于每個確定的狀態(tài)，只有一種決策，故這唯一決策的結(jié)果是最優(yōu)的。利用第四階段的基本方程進行計算：F4(x4)=minv4(x4,u4)+f5(x5)=minv4(x4,u4)=v4(x4,u4)=0.2x4+7.6u4 (u4>0)或=0.2x4(u4=0)計算結(jié)果列表 1表1 k=4 時V,九十i (丸+i >晨+"1

22、5c06045.6045.615038.2038.224030.8030.833023.4023.4420160165108.608.6k=3時因為d3=12, d4=6, x1=x5=0, d1=7.每月的最大生產(chǎn)能力為 10臺，故2三x3三7當(dāng) x3=2, u3=10 x3=3, u3=10, 9x3=4, u3=10, 9, 8 x3=5, u3=10, 9, 8, 7 x3=6, u3=10, 9, 8, 7, 6 x3=7, u3=10, 9, 8, 7, 6, 5狀態(tài)變量x3的一個取值，對應(yīng)決策變量u3的六個可能取值,要求分別計算由各個 u3取值相應(yīng)的指標(biāo)函數(shù)值，再挑選其中的最小值

23、為這個狀態(tài)的最優(yōu)指標(biāo)函數(shù)值，f3(0).下面利用第三階段的基本方程進行計算。F3 (x3) =min【v3(x3,u3)+f4(x4)其中 v3(x3,u3)=0.2x3+8u3(u3>0)或 v3(x3,u3)=0.2x3 (u3=0)狀態(tài)轉(zhuǎn)移方程x4=x3+u3-12 計算結(jié)果位于表2表2表2 k=3 時*匕九/(力+i)七+九/小210080.445.6126310180.638.2118.89072.645.6118.2410280.830.8111.69172.838.21118064.845.6110.451038123.4104.4927330.8103.8816538.2

24、103.2705745.6102.6610481.21697.29373.223.496.68265.230.8967157.238.295.46049.245.694.8710581.48.6909473.41689.48365.423.488.87257.430.888.26149.438.287.65041.445.687k=2 時確定x2的取值范圍因為x1=0, 0三u1三10,且d1=6,且x3蘭2因止匕0三x2三4即x2=0,1,2,3,4.對于x2的每個確定值，分別求生 u2的可能取值X2=0時，u2=10, 9X2=1時，u2=10, 9, 8X2=2時，u2=10, 9, 8

25、, 7X2=3時，u2=10, 9, 8, 7, 6X2=4時，u2=10, 9, 8, 7, 6, 5基本方程 f2(x2)=minv2(x2,u2)+f3(x3)其中 v2(x2,u2)=0.2x2+7.2u2 (u2>0) 或 v2(x2,u2)=0.2x2 (u2=0)狀態(tài)方程x3=x2+u2-3注：對上面的u2取值解釋。本來x2=0時，u2可取值為10, 9, 8, 7.但由于每個月的最大生產(chǎn)能力為10臺且d3=12,所以x3必須大于2臺，因此u2取值只能為10, 9.同理對于x3取其他可能值，也應(yīng)考慮到x3必須大于2臺,計算結(jié)果如下表3.表 3 k=2匕fi+t < X14-I)匕+人)010372118.2190.29264.8126190.8110472.2110.4182.69365118.2183.28257.8126183.6210572.4102.61759465.2110.4175.68358118.2176.27250.8126176.8310672.