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

1、1動態(tài)規(guī)劃動態(tài)規(guī)劃動態(tài)規(guī)劃動態(tài)規(guī)劃(dynamic(dynamicprogramming)programming)是運(yùn)籌學(xué)的一個重要分支，它是解決多是運(yùn)籌學(xué)的一個重要分支，它是解決多階段決策問題的一種有效的數(shù)量化方法動態(tài)規(guī)劃是由美國學(xué)者貝爾曼階段決策問題的一種有效的數(shù)量化方法動態(tài)規(guī)劃是由美國學(xué)者貝爾曼(R(RBellmanBellman）等人所創(chuàng)立的）等人所創(chuàng)立的19511951年貝爾曼首先提出了動態(tài)規(guī)劃中解決多年貝爾曼首先提出了動態(tài)規(guī)

2、劃中解決多階段決策問題的最優(yōu)化原理，并給出了許多實(shí)際問題的解法階段決策問題的最優(yōu)化原理，并給出了許多實(shí)際問題的解法19571957年貝爾曼年貝爾曼發(fā)表了發(fā)表了《動態(tài)規(guī)劃動態(tài)規(guī)劃》一書，標(biāo)志著運(yùn)籌學(xué)這一重要分支的誕生一書，標(biāo)志著運(yùn)籌學(xué)這一重要分支的誕生11動態(tài)規(guī)劃的概念與原理動態(tài)規(guī)劃的概念與原理一、動態(tài)規(guī)劃的基本概念一、動態(tài)規(guī)劃的基本概念引例引例:最短路線問題最短路線問題美國黑金石油公司（美國黑金石油公司（TheTheBlackBlack

3、GoldGoldPetroleumPetroleumCompanyCompany）最近在阿拉）最近在阿拉斯加（斯加（AlaskaAlaska）的北斯洛波（）的北斯洛波（NthNthSlopeSlope）發(fā)現(xiàn)了大的石油儲量。為了大規(guī)）發(fā)現(xiàn)了大的石油儲量。為了大規(guī)模開發(fā)這一油田，首先必須建立相應(yīng)的輸運(yùn)網(wǎng)絡(luò)，使北斯洛波生產(chǎn)的原油能模開發(fā)這一油田，首先必須建立相應(yīng)的輸運(yùn)網(wǎng)絡(luò)，使北斯洛波生產(chǎn)的原油能運(yùn)至美國的運(yùn)至美國的3個裝運(yùn)港之一。在油田的集輸

4、站（結(jié)點(diǎn)個裝運(yùn)港之一。在油田的集輸站（結(jié)點(diǎn)C）與裝運(yùn)港（結(jié)點(diǎn)）與裝運(yùn)港（結(jié)點(diǎn)P1、P2、P3）之間需要若干個中間站，中間站之間的聯(lián)通情況如圖）之間需要若干個中間站，中間站之間的聯(lián)通情況如圖1所示，圖所示，圖中線段上的數(shù)字代表兩站之間的距離（單位：中線段上的數(shù)字代表兩站之間的距離（單位：1010千米）千米）。試確定一最佳的輸。試確定一最佳的輸運(yùn)線路，使原油的輸送距離最短。運(yùn)線路，使原油的輸送距離最短。解：最短路線有一個重要性質(zhì)，即如果由起

5、點(diǎn)解：最短路線有一個重要性質(zhì)，即如果由起點(diǎn)A經(jīng)過經(jīng)過B點(diǎn)和點(diǎn)和C點(diǎn)到達(dá)終點(diǎn)到達(dá)終點(diǎn)D是一條最短路線，則由是一條最短路線，則由B點(diǎn)經(jīng)點(diǎn)經(jīng)C點(diǎn)到達(dá)終點(diǎn)點(diǎn)到達(dá)終點(diǎn)D一定是一定是B到D的最短路的最短路（貝爾曼最優(yōu)化原理）（貝爾曼最優(yōu)化原理）。此性質(zhì)用反證法很容易證明，因?yàn)槿绻皇沁@樣，則。此性質(zhì)用反證法很容易證明，因?yàn)槿绻皇沁@樣，則從B點(diǎn)到點(diǎn)到D點(diǎn)有另一條距離更短的路線存在，不妨假設(shè)為點(diǎn)有另一條距離更短的路線存在，不妨假設(shè)為B—P—D；從而可

6、；從而可知路線知路線A—B—P—D比原路線比原路線A—B—C—D距離短，這與原路線距離短，這與原路線A—B—C—D是最短路線相矛盾，性質(zhì)得證。最短路線相矛盾，性質(zhì)得證。根據(jù)最短路線的這一性質(zhì)，尋找最短路線的方法就是從最后階段開始，根據(jù)最短路線的這一性質(zhì)，尋找最短路線的方法就是從最后階段開始，由后向前逐步遞推求出各點(diǎn)到終點(diǎn)的最短路線，最后求得由始點(diǎn)到終點(diǎn)的最由后向前逐步遞推求出各點(diǎn)到終點(diǎn)的最短路線，最后求得由始點(diǎn)到終點(diǎn)的最短路；即動態(tài)規(guī)劃

7、的方法是從終點(diǎn)逐段向始點(diǎn)方向?qū)ふ易疃搪肪€的一種方法。短路；即動態(tài)規(guī)劃的方法是從終點(diǎn)逐段向始點(diǎn)方向?qū)ふ易疃搪肪€的一種方法。按照動態(tài)規(guī)劃的方法，將此過程劃分為按照動態(tài)規(guī)劃的方法，將此過程劃分為4個階段，即階段變量個階段，即階段變量；取；取4321?k過程在各階段所處的位置為狀態(tài)變量過程在各階段所處的位置為狀態(tài)變量，按逆序算法求解。，按逆序算法求解。kx3選擇選擇M3232105637610min)(2133????????????????M

8、xf由結(jié)點(diǎn)由結(jié)點(diǎn)M2222到達(dá)下一階段也有三條路線可以選擇，即選擇到達(dá)下一階段也有三條路線可以選擇，即選擇M3131、M3232或M3333；故：；故：選擇選擇M3232或M333310553769min)(2233????????????????Mxf由結(jié)點(diǎn)由結(jié)點(diǎn)M2323到達(dá)下一階段也有三條路線可以選擇，即選擇到達(dá)下一階段也有三條路線可以選擇，即選擇M3232、M3333或M3434；故：；故：選擇選擇M3333或M34349365

9、4311min)(2333????????????????Mxf當(dāng)時：時：2?k由結(jié)點(diǎn)由結(jié)點(diǎn)M1111到達(dá)下一階段有兩條路線可以選擇，即選擇到達(dá)下一階段有兩條路線可以選擇，即選擇M2121或M2222；故：；故：選擇選擇M222216106108min)(1122???????????Mxf由結(jié)點(diǎn)由結(jié)點(diǎn)M1212到達(dá)下一階段也有兩條路線可以選擇，即選擇到達(dá)下一階段也有兩條路線可以選擇，即選擇M2222或M2323；故：；故：選擇選擇M2

10、22219911109min)(1222???????????Mxf當(dāng)時：時：1?k由結(jié)點(diǎn)由結(jié)點(diǎn)C到達(dá)下一階段有兩條路線可以選擇，即選擇到達(dá)下一階段有兩條路線可以選擇，即選擇M1111或M1212；故：；故：選擇選擇M11112819101612min)(11???????????Cxf從而通過順序（計(jì)算的反順序）追蹤（黑體標(biāo)示）可以得到兩條最佳的從而通過順序（計(jì)算的反順序）追蹤（黑體標(biāo)示）可以得到兩條最佳的輸運(yùn)線路：輸運(yùn)線路：C—M1

11、111—M2222—M3232—P2；C—M1111—M2222—M3333—P3。最短的輸送距離是。最短的輸送距離是280280千米。千米。一個多階段決策過程最優(yōu)化問題的動態(tài)規(guī)劃模型通常包含以下要素。一個多階段決策過程最優(yōu)化問題的動態(tài)規(guī)劃模型通常包含以下要素。1、階段、階段階段是過程中需要做出決策的決策點(diǎn)。描述階段的變量稱為階段變量，階段是過程中需要做出決策的決策點(diǎn)。描述階段的變量稱為階段變量，常用常用k來表示。階段的劃分一般是根據(jù)時