數(shù)學(xué)模型動態(tài)規(guī)劃

《數(shù)學(xué)模型動態(tài)規(guī)劃》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、.動態(tài)規(guī)劃動態(tài)規(guī)劃(dynamicprogramming)是運(yùn)籌學(xué)的一個重要分支，它是解決多階段決策問題的一種有效的數(shù)量化方法．動態(tài)規(guī)劃是由美國學(xué)者貝爾曼(R．Bellman）等人所創(chuàng)立的．1951年貝爾曼首先提出了動態(tài)規(guī)劃中解決多階段決策問題的最優(yōu)化原理，并給出了許多實際問題的解法．1957年貝爾曼發(fā)表了《動態(tài)規(guī)劃》一書，標(biāo)志著運(yùn)籌學(xué)這一重要分支的誕生．§1動態(tài)規(guī)劃的概念與原理一、動態(tài)規(guī)劃的基本概念引例:最短路線問題美國黑金石油公司（TheBlackGoldPetroleumCompany）最近

2、在阿拉斯加（Alaska）的北斯洛波（NorthSlope）發(fā)現(xiàn)了大的石油儲量。為了大規(guī)模開發(fā)這一油田，首先必須建立相應(yīng)的輸運(yùn)網(wǎng)絡(luò)，使北斯洛波生產(chǎn)的原油能運(yùn)至美國的3個裝運(yùn)港之一。在油田的集輸站（結(jié)點(diǎn)C）與裝運(yùn)港（結(jié)點(diǎn)P1、P2、P3）之間需要若干個中間站，中間站之間的聯(lián)通情況如圖1所示，圖中線段上的數(shù)字代表兩站之間的距離（單位：10千米）。試確定一最佳的輸運(yùn)線路，使原油的輸送距離最短。解：最短路線有一個重要性質(zhì)，即如果由起點(diǎn)A經(jīng)過B點(diǎn)和C點(diǎn)到達(dá)終點(diǎn)D是一條最短路線，則由B點(diǎn)經(jīng)C點(diǎn)到達(dá)終點(diǎn)D一定是

3、B到D的最短路（貝爾曼最優(yōu)化原理）。此性質(zhì)用反證法很容易證明，因為如果不是這樣，則從B點(diǎn)到D點(diǎn)有另一條距離更短的路線存在，不妨假設(shè)為B—P—D；從而可知路線A—B—P—D比原路線A—B—C—D距離短，這與原路線A—B—C—D是最短路線相矛盾，性質(zhì)得證。根據(jù)最短路線的這一性質(zhì)，尋找最短路線的方法就是從最后階段開始，由后向前逐步遞推求出各點(diǎn)到終點(diǎn)的最短路線，最后求得由始點(diǎn)到終點(diǎn)的最短路；即動態(tài)規(guī)劃的方法是從終點(diǎn)逐段向始點(diǎn)方向?qū)ふ易疃搪肪€的一種方法。按照動態(tài)規(guī)劃的方法，將此過程劃分為4個階段，即階段變量

4、；取過程在各階段所處的位置為狀態(tài)變量，按逆序算法求解。......CP3P2P1M11M12M21M22M23M31M32M33M34101286911107697511468643776534k=1k=2k=3k=4圖1當(dāng)時：由結(jié)點(diǎn)M31到達(dá)目的地有兩條路線可以選擇，即選擇P1或P2；故：選擇P2由結(jié)點(diǎn)M32到達(dá)目的地有三條路線可以選擇，即選擇P1、P2或P3；故：選擇P2由結(jié)點(diǎn)M33到達(dá)目的地也有三條路線可以選擇，即選擇P1、P2或P3；故：選擇P3由結(jié)點(diǎn)M34到達(dá)目的地有兩條路線可以選擇，即

5、選擇P2或P3；故：選擇P2當(dāng)時：由結(jié)點(diǎn)M21到達(dá)下一階段有三條路線可以選擇，即選擇M31、M32或M33；故：......選擇M32由結(jié)點(diǎn)M22到達(dá)下一階段也有三條路線可以選擇，即選擇M31、M32或M33；故：選擇M32或M33由結(jié)點(diǎn)M23到達(dá)下一階段也有三條路線可以選擇，即選擇M32、M33或M34；故：選擇M33或M34當(dāng)時：由結(jié)點(diǎn)M11到達(dá)下一階段有兩條路線可以選擇，即選擇M21或M22；故：選擇M22由結(jié)點(diǎn)M12到達(dá)下一階段也有兩條路線可以選擇，即選擇M22或M23；故：選擇M22當(dāng)時

6、：由結(jié)點(diǎn)C到達(dá)下一階段有兩條路線可以選擇，即選擇M11或M12；故：選擇M11從而通過順序（計算的反順序）追蹤（黑體標(biāo)示）可以得到兩條最佳的輸運(yùn)線路：C—M11—M22—M32—P2；C—M11—M22—M33—P3。最短的輸送距離是280千米。一個多階段決策過程最優(yōu)化問題的動態(tài)規(guī)劃模型通常包含以下要素。1、階段階段是過程中需要做出決策的決策點(diǎn)。描述階段的變量稱為階段變量，常用k來表示。階段的劃分一般是根據(jù)時間和空間的自然特征來進(jìn)行的，但要便于將問題的過程轉(zhuǎn)化為多階段決策的過程。階段變量一般用表示

7、。......2、狀態(tài)狀態(tài)（state）表示每個階段開始時過程所處的自然狀況。它應(yīng)能描述過程的特征并且無后效性，即當(dāng)某階段的狀態(tài)變量給定時，這個階段以后過程的演變與該階段以前各階段的狀態(tài)無關(guān)。通常還要求狀態(tài)是直接或間接可以觀測的。描述狀態(tài)的變量稱狀態(tài)變量（statevariable）。變量允許取值的范圍稱允許狀態(tài)集合(setofadmissiblestates)。用表示第階段的狀態(tài)變量，它可以是一個數(shù)或一個向量。用表示第階段的允許狀態(tài)集合。個階段的決策過程有個狀態(tài)變量，表示演變的結(jié)果。根據(jù)過程演變

8、的具體情況，狀態(tài)變量可以是離散的或連續(xù)的。為了計算的方便有時將連續(xù)變量離散化；為了分析的方便有時又將離散變量視為連續(xù)的。狀態(tài)變量簡稱為狀態(tài)。3決策當(dāng)一個階段的狀態(tài)確定后，可以作出各種選擇從而演變到下一階段的某個狀態(tài)，這種選擇手段稱為決策（decision），在最優(yōu)控制問題中也稱為控制（control）。描述決策的變量稱決策變量（decisionvariable），變量允許取值的范圍稱允許決策集合（setofadmissibledecisions）。用表示第階段處于狀態(tài)時的決策變量，