動態(tài)規(guī)劃模型

《動態(tài)規(guī)劃模型》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、第2講動態(tài)規(guī)劃模型動態(tài)規(guī)劃是運籌學的一個分支，它是解決多階段決策過程最優(yōu)化問題的一種數(shù)學方法。1951年美國數(shù)學家貝爾曼（R.Bellman）等人，根據(jù)一類多階段決策問題的特點，提出了解決這類問題的“最優(yōu)性原理”，研究了許多實際問題，從而創(chuàng)建了解決最優(yōu)化問題的一種新方法——動態(tài)規(guī)劃。動態(tài)規(guī)劃可以用來解決最優(yōu)路徑問題、資源分配問題、生產(chǎn)調(diào)度問題、庫存問題、裝載問題、排序問題、設(shè)備更新問題、生產(chǎn)過程最優(yōu)控制問題。下面，以最短路徑問題為例，說明動態(tài)規(guī)劃的基本思想方法和特點。（一）、最短路徑問題1、問題提出如圖1-10所示（P56），從地

2、要鋪設(shè)一條管道到地，中間必須經(jīng)過五個中間站，第一站可以在兩地中任選一個，類似的，第二、三、四、五站可供選擇的地點分別是連接兩點間的距離用圖上兩點連線上的數(shù)字表示，兩點間沒有連線的表示相應(yīng)兩點不能鋪設(shè)管道，現(xiàn)要選擇一條從到的鋪管線路，使總距離最短。2、問題分析解決最短路徑問題，最容易想到的方法是窮舉法，即列出所有可能發(fā)生的方案和結(jié)果，再針對題目的要求對它們一一進行比較，求出最優(yōu)方案。這種方法，在變量（或節(jié)點）的數(shù)目較小時有效；在變量數(shù)目很大時，計算量將會變得十分龐大，行不通。因此，需要根據(jù)問題的特性，尋求一種簡便的算法。最短路徑問題

3、有一個特性：如果最短路徑在第站通過點，則這一線路在由出發(fā)到達終點的那一部分線路，對于從點終點的所有可能選擇的不同線路來說，必定也是距離最短的。這就是最優(yōu)性原理。這就啟發(fā)我們從最后一段開始，采用從后向前逐步遞推的方法，求出各點到的最短線路，最后求得從到的最短線路。（歸結(jié)為一句話：最有策略的子策略仍然是最優(yōu)策略）3、問題求解為求解方便，將整個過程分為6個階段，用表示。（1）時，設(shè)表示由到的最短距離，表示由到的最短距離，有，（2）時，從出發(fā)，有兩種選擇，到或，如果表示到的最短距離，表示到的距離，則再用表示相應(yīng)的選擇或決策，則。得到由出發(fā)

4、到的最短線路是。從出發(fā)，也有兩種選擇，到或，如果的定義與中相似，則。得到由出發(fā)到的最短線路是。從出發(fā)，同樣有。得到由出發(fā)到的最短線路是。（3）時，分別以為出發(fā)點來計算，有，由出發(fā)的最短線路是。，由出發(fā)的最短線路是，由出發(fā)的最短線路是。（4）時，分別以為出發(fā)點來計算，有，由出發(fā)的最短線路是。，由出發(fā)的最短線路是。，由出發(fā)的最短線路是。，由出發(fā)的最短線路是。（5）時，分別以為出發(fā)點來計算，有，由出發(fā)的最短線路是。，由出發(fā)的最短線路是。（6）時，出發(fā)點只有，有，由出發(fā)的最短線路是，距離為18。綜上所述，動態(tài)規(guī)劃方法的基本思想是，把一個復(fù)

5、雜的問題分解為一系列同一類型更容易求解的子問題，使計算過程單一化，便于應(yīng)用計算機。求解過程分為兩個階段，先按照整體最優(yōu)的思想逆序地求出各個可能狀態(tài)的最優(yōu)決策。然后，再順序地求出整個問題的最優(yōu)策略和最優(yōu)路線。由于把最優(yōu)化應(yīng)用到每個子問題上，于是，就系統(tǒng)地刪去了所有中間非最優(yōu)的方案組合，使計算工作量比直接枚舉法大大減少。（二）、基本概念和基本方程1、動態(tài)規(guī)劃的基本概念（1）階段和階段變量用動態(tài)規(guī)劃求解多階段決策系統(tǒng)問題時，要根據(jù)具體情況，將系統(tǒng)適當?shù)胤殖扇舾蓚€階段，以便分階段決策。通常階段是按照決策進行的時間或空間上的先后次序劃分的，

6、描述階段的變量稱為階段變量。由系統(tǒng)的最后階段向初始階段求最優(yōu)解的過程，稱為動態(tài)規(guī)劃的逆推解法。（2）狀態(tài)和狀態(tài)變量狀態(tài)表示系統(tǒng)在某階段所處的“起點”位置或狀態(tài)。各階段的狀態(tài)可用狀態(tài)變量來描述，階段的狀態(tài)變量記為。第階段所有可能狀態(tài)的全體，可用狀態(tài)集合來描述。上例中（3）決策、決策變量和策略從一個階段的某個狀態(tài)出發(fā)，到達下一階段，都有若干種選擇。把過程從一個狀態(tài)演變到下一階段某一狀態(tài)所作的選擇或決定稱為決策。描述決策的變量稱為決策變量，記為。表示從第階段的狀態(tài)出發(fā)所作的決策。并用表示第階段從出發(fā)的所有決策的集合。由每階段的決策組成的

7、決策序列稱為全過程策略或策略，表示為。由系統(tǒng)的第階段出發(fā)到終點的決策過程稱為全過程的后部子過程，相應(yīng)的策略稱為子策略。表示為。對于每一實際的多階段決策過程，可供選擇的策略有一定的范圍限制，這個范圍稱為允許集合。允許集合中達到最優(yōu)效果的策略稱為最優(yōu)策略。（4）狀態(tài)轉(zhuǎn)移方程由第階段的狀態(tài)，采用決策變到第階段的狀態(tài)的過程稱為狀態(tài)轉(zhuǎn)移，并記為該式表達了從階段到階段的狀態(tài)轉(zhuǎn)移規(guī)律，故稱為狀態(tài)轉(zhuǎn)移方程。（5）階段效益多階段決策過程中，在階段的狀態(tài)執(zhí)行決策轉(zhuǎn)到狀態(tài)，不僅帶來系統(tǒng)狀態(tài)的轉(zhuǎn)移，而且也將對整個決策的結(jié)果或效益產(chǎn)生影響。用表示在第階段中

8、，從狀態(tài)出發(fā)，采取策略，轉(zhuǎn)移到的效益，稱為階段效益。（6）最優(yōu)策略與最優(yōu)效益對于多階段決策問題，自然都存在很多策略，而且每個策略都對應(yīng)一種結(jié)果，把這些結(jié)果統(tǒng)稱為效益。根據(jù)不同的實際問題，效益可以是利潤、距離、產(chǎn)量或資源的消耗量等。顯然一個多階段決策