動態(tài)規(guī)劃Dynamic Programming

動態(tài)規(guī)劃DP （Dynamic Programming）   動態(tài)規(guī)劃是現(xiàn)代企業(yè)管理中一種重要的決策方法，它是解決多階段決策過程最優(yōu)化的一種數(shù)學(xué)方法。
動態(tài)規(guī)劃大約產(chǎn)生于五十年代，1951年美國數(shù)學(xué)家貝爾曼(R.Bellman)等人，根據(jù)一類多階段決策問題的特點(diǎn)，把多階段決策問題變換為一系列相互聯(lián)系的單階段問題。然后逐個加以解決。同時，他提出了解決這類問題的最優(yōu)原理，研究了許多實(shí)際問題，從而創(chuàng)建了解決最優(yōu)化問題的一種新的方法----動態(tài)規(guī)劃。
動態(tài)規(guī)劃的方法，在工程技術(shù)、企業(yè)管理、軍事等部門都有廣泛的應(yīng)用。在企業(yè)管理中，動態(tài)規(guī)劃可以用來解決最優(yōu)路徑問題、資源分配問題、生產(chǎn)調(diào)度問題、庫存問題、裝載問題、排序問題、設(shè)備更新問題、生產(chǎn)過程最優(yōu)控制問題。需要特別強(qiáng)調(diào)的是：動態(tài)規(guī)劃是求解一類問題的方法，是考察問題的一種途徑，而不是一種特殊的算法。因而不像線性規(guī)劃那樣有一個標(biāo)準(zhǔn)的數(shù)學(xué)表達(dá)式和明確定義的一組規(guī)則。故需要有豐富的想象去建模，創(chuàng)造性地去求解。
一、多段決策問題的提出 例1生產(chǎn)與存儲問題 某工廠每季度需供應(yīng)市場一定數(shù)量的產(chǎn)品（600，700，500，1200），未銷售完的產(chǎn)品存入倉庫（每件每季度1元），現(xiàn)要制定生產(chǎn)計(jì)劃，在滿足市場需求的條件下，使一年的生產(chǎn)與存儲費(fèi)用最少。生產(chǎn)費(fèi)用為：件數(shù)的平方成正比，比例系數(shù)為0.005。



例2最短路問題 設(shè)有一輛汽車由A城到B城，中間可經(jīng)過V1到V8城市，各城市的交通路線及距離如下圖所示，問應(yīng)選擇哪一條路線，可使總距離最短。


由上述例題可知，在實(shí)際生產(chǎn)、科學(xué)試驗(yàn)、經(jīng)濟(jì)活動的過程中，有一類活動的過程，由于其特殊性?？蓪⒃撨^程分為若干個相聯(lián)系的階段，在每個階段都要做出決策，全部過程的決策就形成一個決策序列，每一個階段的決策有許多種方案選擇，從而形成多種決策策略，在這些決策策略中選擇一個最優(yōu)的策略，使在預(yù)定的標(biāo)準(zhǔn)下達(dá)到最好效果，這就是多階段決策問題。  
二、多階段決策的有關(guān)概念





  三、動態(tài)規(guī)劃的基本思想和基本方程
以最短路線為例介紹動態(tài)規(guī)劃的思想。常識告訴我們，最短路線有一個重要特點(diǎn)：如果由起點(diǎn)A經(jīng)過B,C,D,E,F點(diǎn)到達(dá)終點(diǎn)G是一條最短的路線，則由點(diǎn)B出發(fā)經(jīng)過C,D,E,F點(diǎn)到達(dá)終點(diǎn)G的這條子路線。就必然是從點(diǎn)B出發(fā)到達(dá)終點(diǎn)的所有可能選擇的不同路線中最短的一條。此特點(diǎn)可用反正發(fā)來證明。
根據(jù)最短路線這一特點(diǎn)，我們就得到了尋找最短路線的方法，假設(shè)已求得從點(diǎn)B出發(fā)到達(dá)終點(diǎn)的最短路線，再選擇從A到B兩點(diǎn)間的一條最短路線，就求得了從起點(diǎn)A到終點(diǎn)G的一條最短路線。那么，如何求從點(diǎn)B出發(fā)到達(dá)終點(diǎn)的最短路線呢，再假設(shè)已求得從點(diǎn)C出發(fā)到達(dá)終點(diǎn)的最短路線，再選擇從B到C兩點(diǎn)間的一條最短路線，就求得了從起點(diǎn)B到終點(diǎn)G的一條最短路線。
以這樣的思路，只要能求出F到G的最短路，就可以求出E到G的最短路，從而遞推的求出，D,C,B,A 到G的最短路。所以動態(tài)規(guī)劃方法就是從終點(diǎn)逐段向始點(diǎn)方向?qū)ふ易顑?yōu)解的一種方法，即就是從最后一段開始，用由后向前逐步遞推的方法，求出各點(diǎn)到G點(diǎn)的最短路線，最后求得有A點(diǎn)到G點(diǎn)的最短路線。







四、動態(tài)規(guī)劃的最優(yōu)性原理 （R.Bellman原理） “作為整個過程的最優(yōu)策略具有這樣的性質(zhì)：無論過去的狀態(tài)和決策如何，對前面的決策所形成的狀態(tài)而言，余下的決策必須構(gòu)成最優(yōu)策略。”簡言之，一個最優(yōu)策略的子策略總是最優(yōu)的。
五、解法舉例 現(xiàn)利用動態(tài)規(guī)劃的基本方程求解例1中的生產(chǎn)與存儲問題。

























六、動態(tài)規(guī)劃的應(yīng)用

動態(tài)規(guī)劃Dynamic Programming