動態(tài)規(guī)劃肖健華

動態(tài)規(guī)劃肖健華1第1頁，課件共40頁，創(chuàng)作于2023年2月動態(tài)規(guī)劃（dynamicprogramming）是運(yùn)籌學(xué)的一個分支，是求解多階段決策過程的最優(yōu)化數(shù)學(xué)分支。動態(tài)規(guī)劃的“動態(tài)性”主要體現(xiàn)在研究對象的時序性上。2第2頁，課件共40頁，創(chuàng)作于2023年2月所謂多階段決策問題是指這樣一類活動過程：它可以分解為若干個相互聯(lián)系的階段，在每一階段分別對應(yīng)著一組可供選取的決策集合，即構(gòu)成過程的每個階段都需要進(jìn)行一次決策的決策問題。將各階段的決策綜合起來構(gòu)成一個決策序列，稱為一個策略。3第3頁，課件共40頁，創(chuàng)作于2023年2月動態(tài)規(guī)劃模型的分類決策過程的演變是否確定：確定性動態(tài)規(guī)劃和隨機(jī)性動態(tài)規(guī)劃狀態(tài)變量的取值是否連續(xù)：連續(xù)性動態(tài)規(guī)劃和離散性動態(tài)規(guī)劃動態(tài)規(guī)劃分為四大類：連續(xù)確定性離散確定性連續(xù)隨機(jī)性離散隨機(jī)性4第4頁，課件共40頁，創(chuàng)作于2023年2月§7.1動態(tài)規(guī)劃的基本理論動態(tài)規(guī)劃三個例子最短路線問題資源分配問題靜態(tài)非線性規(guī)劃問題的動態(tài)求解5第5頁，課件共40頁，創(chuàng)作于2023年2月例1：最短路線問題設(shè)有一個旅行者從下圖中的A點出發(fā)，途中要經(jīng)過B、C、D等處，最后到達(dá)終點E。從A到E有很多條路線可以選擇，各點之間的距離如圖中所示，問該旅行者應(yīng)選擇哪一條路線，使從A到E的總路線最短？6第6頁，課件共40頁，創(chuàng)作于2023年2月例2：資源分配問題7第7頁，課件共40頁，創(chuàng)作于2023年2月例3：靜態(tài)非線性規(guī)劃問題的動態(tài)求解8第8頁，課件共40頁，創(chuàng)作于2023年2月7.1.1多階段決策過程的數(shù)學(xué)描述多階段決策問題的示意圖下圖表明：多階段決策過程可分為若干個相互聯(lián)系的階段，每一個都要求作出相應(yīng)的決策，以使整個過程達(dá)到最佳的活動效果。9第9頁，課件共40頁，創(chuàng)作于2023年2月任何一個階段(Stage，即決策點)都是由輸入(Input)、決策(Decision)、階段指標(biāo)函數(shù)(PayoffFunction)和輸出(Output)構(gòu)成的，其中輸入輸出也稱為狀態(tài)(State)，輸入稱為輸入狀態(tài)，輸出稱為輸出狀態(tài)。前一個階段的輸出狀態(tài)為后一個階段的輸入狀態(tài)。10第10頁，課件共40頁，創(chuàng)作于2023年2月7.1.2動態(tài)規(guī)劃的基本概念1.階段：是過程中需要作出決策的決策點，描述階段的變量稱為階段變量，常用k表示，具有N個階段的決策過程，其階段變量k=1,2,…,N2.狀態(tài)：是動態(tài)規(guī)劃中最關(guān)鍵的一個參數(shù)，第k階段的狀態(tài)變量用Sk表示，它既反映前面各階段決策的結(jié)局，又是本階段作出決策的出發(fā)點和依據(jù)。Sk應(yīng)包含該階段之前決策過程的全部信息，做到從該階段后做出的決策同之前的狀態(tài)決策相互獨立。這種性質(zhì)在本書中被稱為無后效性或健忘性。11第11頁，課件共40頁，創(chuàng)作于2023年2月12第12頁，課件共40頁，創(chuàng)作于2023年2月4.狀態(tài)轉(zhuǎn)移律13第13頁，課件共40頁，創(chuàng)作于2023年2月5.策略與子策略14第14頁，課件共40頁，創(chuàng)作于2023年2月6.指標(biāo)函數(shù)15第15頁，課件共40頁，創(chuàng)作于2023年2月16第16頁，課件共40頁，創(chuàng)作于2023年2月17第17頁，課件共40頁，創(chuàng)作于2023年2月7.最優(yōu)指標(biāo)函數(shù)18第18頁，課件共40頁，創(chuàng)作于2023年2月7.1.3動態(tài)規(guī)劃的數(shù)學(xué)模型一、動態(tài)規(guī)劃問題的解題思路動態(tài)規(guī)劃問題的復(fù)雜性在于各階段之間的相互聯(lián)系，由此使得各階段局部最優(yōu)不能保證全局最優(yōu)。用動態(tài)規(guī)劃方法解題的基本思路：將一個n階段的決策問題轉(zhuǎn)化為依次求解n個具有遞推關(guān)系的單階段決策問題，從而簡化計算過程。19第19頁，課件共40頁，創(chuàng)作于2023年2月兩種基本求解方法動態(tài)規(guī)劃問題的求解有兩種基本方法。逆序解法：從問題的最后一個階段開始，逆多階段決策的實際過程反向?qū)?yōu)。順序解法：從問題的最初階段開始，同多階段決策的實際過程順序?qū)?yōu)。20第20頁，課件共40頁，創(chuàng)作于2023年2月將一個多階段的決策問題轉(zhuǎn)化為依次求解多個單階段的決策問題時，一個重要特征是將前面的解傳遞，并納入下一階段一并考慮，即做到求解的各階段具有遞推性。21第21頁，課件共40頁，創(chuàng)作于2023年2月二、動態(tài)規(guī)劃的數(shù)學(xué)模型：最優(yōu)化原理思路：從某一狀態(tài)出發(fā)，尋找最優(yōu)選擇時，它是從下述所有可能的組合中進(jìn)行優(yōu)化選取的：將本階段決策的指標(biāo)效益值加上從下階段開始采取最優(yōu)策略時的指標(biāo)效益值。這是一種遞推關(guān)系式，按逆序算法時可以從最后一個階段反推到過程的開始。22第22頁，課件共40頁，創(chuàng)作于2023年2月最優(yōu)化原理美國的貝爾曼（Bellman）由上述思路提出求解動態(tài)規(guī)劃的最優(yōu)化原理：作為整個過程的最優(yōu)策略具有這樣的性質(zhì)，無論過去的狀態(tài)和決策如何，對先前決策形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略。23第23頁，課件共40頁，創(chuàng)作于2023年2月動態(tài)規(guī)劃的基本方程24第24頁，課件共40頁，創(chuàng)作于2023年2月25第25頁，課件共40頁，創(chuàng)作于2023年2月邊界條件26第26頁，課件共40頁，創(chuàng)作于2023年2月為構(gòu)造和求解動態(tài)規(guī)劃的數(shù)學(xué)模型，需要明確模型中有關(guān)階段的劃分、狀態(tài)變量、決策變量、允許決策集合和狀態(tài)轉(zhuǎn)移方程的確定等，并注意以下各點。27第27頁，課件共40頁，創(chuàng)作于2023年2月（1）狀態(tài)變量的確定是構(gòu)造動態(tài)規(guī)劃模型中最關(guān)鍵的一步，要求：①狀態(tài)變量首先應(yīng)描述反映研究過程的演變特征；②狀態(tài)變量應(yīng)包含到達(dá)這個狀態(tài)前的足夠信息，并無后效性；③狀態(tài)變量還應(yīng)具有可知性，即規(guī)定的狀態(tài)變量的值可通過直接或間接的方法測知。注：狀態(tài)變量可以是連續(xù)的或離散的，單個數(shù)據(jù)或多個數(shù)據(jù)。28第28頁，課件共40頁，創(chuàng)作于2023年2月（2）決策變量是對過程進(jìn)行控制的手段，復(fù)雜的問題中決策變量也可以是多維的向量，它的取值可能是離散的，也可能是連續(xù)的，允許決策集合相當(dāng)于線性規(guī)劃問題的約束條件。29第29頁，課件共40頁，創(chuàng)作于2023年2月30第30頁，課件共40頁，創(chuàng)作于2023年2月31第31頁，課件共40頁，創(chuàng)作于2023年2月§7.2確定性動態(tài)規(guī)劃確定性動態(tài)規(guī)劃是階段的輸出狀態(tài)完全由其輸入狀態(tài)和決策所決定的動態(tài)規(guī)劃。確定性動態(tài)規(guī)劃解決的問題可能包含經(jīng)濟(jì)管理的方方面面，可以說最短路線問題，可以是資源配置問題，也可以是其他的規(guī)劃問題。32第32頁，課件共40頁，創(chuàng)作于2023年2月7.2.1最短路線問題例1：33第33頁，課件共40頁，創(chuàng)作于2023年2月7.2.2資源分配問題

所謂資源分配問題是指：將數(shù)量一定的某些資源（例如資金、機(jī)器設(shè)備、原材料、物資、勞力等）恰當(dāng)?shù)胤峙浣o若干個使用者，而使總的目標(biāo)函數(shù)值為最優(yōu)。資源分配問題本身是線性規(guī)劃或非線性規(guī)劃的一類靜態(tài)問題人為引入時間因素，將其視為按階段進(jìn)行的多階段決策問題，再按動態(tài)規(guī)劃方法求解。34第34頁，課件共40頁，創(chuàng)作于2023年2月35第35頁，課件共40頁，創(chuàng)作于2023年2月36第36頁，課件共40頁，創(chuàng)作于2023年2月37第37頁，課件共40頁，創(chuàng)作于2023年2月38第38頁，課件共40頁，創(chuàng)作于2023年2月例