第十章動態(tài)規(guī)劃DP課件

動態(tài)規(guī)劃DP

（DynamicProgramming）

動態(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)原理，研究了許多實際問題，從而創(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)計劃，在滿足市場需求的條件下，使一年的生產(chǎn)與存儲費(fèi)用最少。生產(chǎn)費(fèi)用為：件數(shù)的平方成正比，比例系數(shù)為0.005。

例2最短路問題

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

由上述例題可知，在實際生產(chǎn)、科學(xué)試驗、經(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)與存儲問題。

休息2511214106104131112396581052C1C3D1AB1B3B2D2EC2一、最短路徑問題求從A到E的最短路徑2511214106104131112396581052C1C3D1AB1B3B2D2EC2f5(E)=02511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f5(E)=02511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=52511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C1)=8f4(D1)=52511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C2)=7f4(D1)=5f3(C1)=82511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f3(C1)=8f3(C2)=72511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B1)=20f3(C2)=7f3(C1)=82511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B2)=14f3(C2)=7f3(C1)=8f2(B1)=212511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f2(B1)=21f2(B2)=142511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=212511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)A（A，B2）B22511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)A（A，B2）B2（B2，C1）C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)A（A，B2）B2（B2，C1）C1（C1，D1）D12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8