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

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

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