數學建模

動態規劃動態規劃問題實例動態規劃的基本概念與原理動態規劃應用舉例動態規劃是解決多階段決策過程最優化的一種方法。該方法是由美國數學家貝爾曼（R.E.Bellman)等人在20世紀50年代初提出的。他們針對多階段決策問題的特點，提出了解決這類問題的“最優化原理”，并成功地解決了生產管理、工程技術等方面的許多問題，從而建立了運籌學的一個新的分支，即動態規劃。Bellman在1957年出版了《DynamicProgramming》一書，是動態規劃領域中的第一本著作。動態規劃問題及實例動態規劃是解決多階段決策問題的一種方法，是現代企業管理中的一種重要決策方法，可用于最優路徑問題、資源分配問題、生產計劃和庫存問題、投資問題、裝載問題、排序問題及生產過程的最優控制等。動態規劃模型的分類：以“時間”角度可分成：離散型和連續型。從信息確定與否可分成：確定型和隨機型。從目標函數的個數可分成：單目標型和多目標型。一、多階段決策過程多階段決策過程是指這樣一類特殊的活動過程，他們可以按時間順序分解成若干相互聯系的階段，在每個階段都要做出決策，全部過程的決策是一個決策序列，所以多階段決策過程也稱為序貫決策過程。這種問題就稱為多階段決策問題。

二、多階段決策問題的特點過程可分為若干個相互聯系的階段；每一階段都對應著一組可供選擇的決策；每一決策的選定即依賴于當前面臨的狀態，又影響以后總體的效果。三、具體實例1、最短路線問題給定一個線路網絡，要從A向F鋪設一條輸油管道，各點間連線上的數字表示距離，問應選擇什么路線，可使總距離最短？2、生產與存儲問題：某工廠每月需供應市場一定數量的產品。供應需求所剩余產品應存入倉庫，一般地說，某月適當增加產量可降低生產成本，但超產部分存入倉庫會增加庫存費用，要確定一個每月的生產計劃，在滿足需求條件下，使一年的生產與存儲費用之和最小。動態規劃的基本概念與原理動態規劃的基本概念階段；狀態；決策和策略；狀態轉移方程；指標函數。一、基本概念階段：是指問題需要做出決策的步數。階段總數常記為n，相應的是n個階段的決策問題。階段的序號常記為k，稱為階段變量，k=1,2,…,n.k即可以是順序編號也可以是逆序編號，常用順序編號。狀態：各階段開始時的客觀條件，第k階段的狀態常用狀態變量表示，狀態變量取值的集合成為狀態集合，用表示。例如，案例1中，AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第1階段第2階段第3階段第4階段第5階段狀態1狀態2狀態3狀態4狀態5狀態6決策：是指從某階段的某個狀態出發，在若干個不同方案中做出的選擇。表示決策的變量，稱為決策變量，用表示。表示第k階段當狀態處于sk時的決策變量。例如：表示走到C階段,當處于C2路口時，下一步奔D1.時的允許決策集合記為，例如：決策變量允許的取值范圍稱為允許決策集合，第k階段狀態為狀態轉移方程：是從上一階段的某一狀態值轉變為下一階段某一狀態值的轉移規律，用表示。策略：一個按順序排列的決策組成的集合。由每段的決策按順序排列組成的決策函數序列稱為k子過程策略。簡稱子策略，記為。即當k=1時，此決策函數序列成為全過程的一個策略，簡稱策略，記為：在實際問題中，可供選擇的策略有一定的范圍，此范圍稱為允許策略集合，用P表示。指標函數：階段指標函數和過程指標函數。階段指標函數是指第k階段從狀態出發，采取決策時的效益，用表示。而過程指標函數是從第k階段的某狀態出發，采取子策略效益之和：最優指標函數：表示從第k階段狀態為時采用最佳策略到過程終止時的最佳效益。記為時所得到的階段其中opt可根據具體情況取max或min。基本方程：此為逐段遞推求和的依據，一般為：式中opt可根據題意取max或min.例如，案例1的基本方程為：最優性原理：最優策略的子策略必為最優。不管過去的狀態和決策如何，從眼下直到最后的諸決策必構成最優子策略。動態規劃的優點：可把一個N維優化問題化成N個一維優化問題求解。求得最優解以后，可得所有子問題的最優解。動態規劃的缺點：“一個”問題，“一個”模型，“一個”求解方法。且求解技巧要求比較高，沒有統一處理方法。狀態變量維數不能太高，一般要求小于6。動態規劃應用舉例例1最短路線問題基本思想：如果起點A經過B1,C1,D1,E1而到終點F，則由C1出發經D1,E1到F點這條子路線，是從C1到F的最短路線。所以，尋找最短路線，應該從最后一段開始找，然后往前遞推。狀態變量：各路線的位置決策變量：第k階段當狀態處于時，決定下一個狀態的位置狀態轉移方程：上一階段到下一階段的轉移規則指標函數：從狀態出發，采取決策時的路程距離最優指標函數：第k階段狀態為時且采用最佳走線策略，使從k位置及以后的路線最短。逆序遞推方程：（1）k=5時，狀態它們到F點的距離即為最短路。AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（2）k=4時，狀態它們到F點需經過中途點E，需一一分析從E到F的最短路：先說從D1到F的最短路有兩種選擇：經過E1,E2,比較最短。AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143這說明由D1到F的最短距離為7，其路徑為相應的決策為：這說明由D2到F的最短距離為5，其路徑為相應的決策為：AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143即D3到F的最短距離為5，其路徑為相應的決策為：（3）k=3時，狀態這說明由C1到F的最短距離為12，相應的決策為AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143即由C2到F的最短距離為10，相應的決策為即由C3到F的最短距離為8，相應的決策為即由C4到F的最短距離為9，相應的決策為AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（4）k=2時，狀態這說明由B1到F的最短距離為13，相應的決策為即由B2到F的最短距離為15，相應的決策為AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（1）k=1時，只有一個狀態點A,則即由A到F的最短距離為17，相應的決策為所以最優路線為：AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143再按計算順序反推可得最優決策序列：順序遞推方程：AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143例1：1階段2階段3階段4階段5階段行走方向AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143K=1時注意到：所以K=2時AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143K=3時AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143或類似地，可算出：最優策略：AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143或最短路徑：最短路長：注：順序解法與逆序解法無本質區別，一般來說，當初始狀態給定時用逆序解法，當終止狀態給定時用順序解法。若問題給定了一個初始狀態與一個終止狀態，則兩種方法均可使用。例2資源分配問題（離散型）例：設有6萬元資金用于4個工廠的擴建，已知每個工廠的利潤增長額同投資額的大小有關，見下表。問應如何確定對這四個工廠的投資額，使總利潤增長額最大？投資額(j)工廠(i)010020030040050060010204260758590202545576570733018396178909540284765748085

表1利潤增長額

（百元）解：把對四個工廠的投資依次看成4個階段的決策過程，確定對第k個工廠的投資額看成第k個階段的決策，k=1,2,3,4。圖示如下：狀態變量：可用于第k,k+1,…n個工廠的投資額。決策變量：第k階段對第k個工廠的投資額。允許決策集：工廠1工廠2工廠3工廠4投資x1投資x2投資x3投資x4狀態狀態狀態狀態轉移方程：其中階段指標函數：第k階段投資元時所產生的利潤。（見上表）最優指標函數：第k階段狀態為且采取最佳投資策略，從第k個工廠以及以后的最大總利潤。逆序法基本遞推方程：工廠1工廠2工廠3工廠4投資x1投資x2投資x3投資x4狀態狀態狀態投資額(j)工廠(i)010020030040050060040284765748085

表1利潤增長額

（百元）解：（1）k=4時考慮：若到最后一個，第4個工廠投資時，還有資金，若投資于第4個工廠的資金為，則最大利潤為工廠1工廠2工廠3工廠4投資x1投資x2投資x3投資x4狀態狀態狀態投資額(j)工廠(i)010020030040050060040284765748085

表1利潤增長額

（百元）（注意到此時=0）自然問：現在還有多少錢？即=？=0，100，200，300，400，500，600都有可能。下面分情況討論：工廠1工廠2工廠3工廠4投資x1投資x2投資x3投資x4狀態狀態狀態投資額(j)工廠(i)010020030040050060040284765748085

表1利潤增長額

（百元）時，時，其他種情況類似討論，我們把所有的結果匯總成一個表2。投資額(j)工廠(i)010020030040050060040284765748085

表1利潤增長額

（百元）01002003004005006000100200300400500600002802847028476502847657402847657480028476574808502847657480850100200300400500600表2

k=4時決策表投資額(j)工廠(i)010020030040050060010204260758590202545576570733018396178909540284765748085

表1利潤增長額

（百元）（2）k=3時到第三個工廠投資時，可利用的資金還有，若向第三個工廠投資（萬元），則自此即以后最大利潤為：

表1利潤增長額

（百元）投資額(j)工廠(i)010020030040050060030183961789095同樣問：=？，即現在還有多少錢？它是允許決策集上界。同理僅舉一例：投資額(j)工廠(i)010020030040050060030183961789095

表1利潤增長額

（百元）01002003004005006000100200300400500600002802847028476502847657402847657480028476574808502847657480850100200300400500600表2

k=4時決策表投資額(j)工廠(i)010020030040050060030183961789095表1利潤增長額（百元）所有情況討論結果匯總成下表：010020030040050060001002003004005006000+00+2818+00+4718+2839+00+6518+4739+2861+00+7418+6539+4761+2878+00+8018+7439+6561+7478+2890+00+8518+8039+7461+6578+4790+2895+0028476789108126000200300300300表3

k=3時決策表（3）k=2時僅舉一例：投資額(j)工廠(i)010020030040050060020254557657073表1利潤增長額（百元）010020030040050060001002003004005006000+00+2818+00+4718+2839+00+6518+4739+2861+00+7418+6539+4761+2878+00+8018+7439+6561+7478+2890+00+8518+8039+7461+6578+4790+2895+0028476789108126000200300300300表3

k=3時決策表關于的其它取值情況及相應的最優決策列于下表010020030040050060001002003004005006000+00+2825+00+4725+2845+00+6725+4745+2857+00+8925+6745+4757+2865+00+10825+8945+6757+4765+2870+00+12625+10845+8957+6765+4770+2873+002853739211413400100200100或200100200

表4k=2時決策表（4）k=1時，此時投資額(j)工廠(i)010020030040050060010204260758590表1利潤增長額（百元）010020030040050060001002003004005006000+00+2825+00+4725+2845+00+6725+4745+2857+00+8925+6745+4757+2865+00+10825+8945+6757+4765+2870+00+12625+10845+8957+6765+4770+2873+002853739211413400100200100或200100200表4k=2時決策表匯一表格：0100200300400500600600134134134133138113901340或100或200表5k=1時決策表此時對應最大值134的有三個值：

所對應的最優策略分別為：時，由狀態轉移方程知：所對應的010020030040050060001002003004005006000+00+2825+00+4725+2845+00+6725+4745+2857+00+8925+6745+4757+2865+00+10825+8945+6757+4765+2870+00+12625+10845+8957+6765+4770+2873+002853739211413400100200100或200100200表4k=2時決策表對應的

再由狀態轉移方程對應的

010020030040050060001002003004005006000+00+2818+00+4718+2839+00+6518+4739+2861+00+7418+6539+4761+2878+00+8018+7439+6561+7478+2890+00+8518+8039+7461+6578+4790+2895+0028476789108126000200300300300表3

k=3時決策表所對應的

再由狀態轉移方程對應的

0100200300400500600010020030040050060000280284702847650284765