《動態(tài)規(guī)劃MATLab》PPT課件

《《動態(tài)規(guī)劃MATLab》PPT課件》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、案例：最短路問題假設(shè)要從A城市到E城市鋪設(shè)一條輸油管道，中間需要經(jīng)過三個地區(qū)，每個地區(qū)都有若干個轉(zhuǎn)運站，構(gòu)成了許多不同的輸油路線，轉(zhuǎn)運站間的數(shù)字表示站間的運輸路徑的長度，由于地理條件等原因，某些地區(qū)之間不能直接鋪設(shè)相通的管道?，F(xiàn)需求出一條使總路徑最短的管道路線。動態(tài)規(guī)劃AB1B2B3C1C2C3D1D2E1動態(tài)規(guī)劃的基本概念一、階段對于一個多階段決策過程，可以根據(jù)問題的特點，把整個過程劃分為幾個相互聯(lián)系的階段，以便可以按一定的順序去求解。這個根據(jù)時間和空間的自然特征來劃分的次序稱為階段，描述階段的變量稱為階段變量，一般用k

2、表示。如案例中的多階段決策問題可劃分為四個階記為段，二、狀態(tài)狀態(tài)：表示系統(tǒng)每個階段開始時所處的自然狀況或客觀條件。如案例中，狀態(tài)就是某階段的出發(fā)位置，它既是該階段某支路的起點，又是前一階段某支路的終點。第一個階段有一個狀態(tài)即為點A，第二個階段有三個狀態(tài)狀態(tài)變量：描述狀態(tài)的變量。常用表示第k階段的狀態(tài)變量。如案例中第三個階段有3個狀態(tài)，則狀態(tài)可取三個值，即這三個點構(gòu)成的集合稱為第三個階段的允許狀態(tài)集，記為有時為了方便起見，也將階段的狀態(tài)編上號碼即有一般地，第k個階段的允許狀態(tài)集記為當(dāng)某個階段的狀態(tài)給定后，則這個階段以后過程的

3、發(fā)展不受這個階段及以前各階段狀態(tài)的影響。也是說，當(dāng)前的狀態(tài)只是以往歷史的一個總結(jié)，過程的過去歷史只能通過當(dāng)前的狀態(tài)去影響它未來的發(fā)展，這種性質(zhì)稱為無后效性。三、決策決策：各階段狀態(tài)確定后，確定下一個階段的狀態(tài)的各種選擇。決策變量：描述決策的變量。常用表示第k階段狀態(tài)處于時的決策變量，它是狀態(tài)變量的函數(shù)。允許決策集：決策變量的取值構(gòu)成的集合，表明決策的約束條件，常用表示第k階段系統(tǒng)處于狀態(tài)時的允許決策集合，即有如案例中，第二階段決策時，若從狀態(tài)出發(fā)，則可做出三種不同決策，其允許決策集合為若選定的下一個狀態(tài)是則四、策略策略：從

4、初始階段到最終階段，每個階段均有一決策，各階段決策形成一個決策序列，稱為系統(tǒng)的一個策略。此序列最優(yōu)策略：使系統(tǒng)達(dá)到最優(yōu)效果的策略。全過程策略：對于具有幾個階段的多階段決策問題，從第一個階段的某一狀態(tài)出發(fā)到終止階段的狀態(tài)做出的決策序列而形成的策略。記為即k后部子過程：從第k階段到終止階段狀態(tài)的過程。簡稱為k子過程。后部子過程策略：k后部子過程相應(yīng)的決策序列。簡稱為k子策略。記為即允許策略集：在實際問題中，可供選擇的策略所在的范圍，常記為P。五、狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程：描述系統(tǒng)由一個階段到下一個階段的狀態(tài)轉(zhuǎn)移規(guī)律。例如，設(shè)系

5、統(tǒng)第k階段的狀態(tài)變量的值給定，該階段的決策變量確定，則第k+1階段的狀態(tài)變量的值也就確定了，即的值隨和變化而變化，這種對應(yīng)關(guān)系我們記為的值的以上狀態(tài)轉(zhuǎn)移規(guī)律，即為狀態(tài)轉(zhuǎn)移方程。稱為狀態(tài)轉(zhuǎn)移函數(shù)。六、指標(biāo)函數(shù)與最優(yōu)指標(biāo)函數(shù)k階段指標(biāo)函數(shù)：第k階段狀態(tài)為決策變量取某個值后得到的一個反映這個局部策略效應(yīng)的數(shù)量指標(biāo)。也稱為k階段的效應(yīng)函數(shù)。全過程的指標(biāo)函數(shù)：常用表示。采用全過程的策略的數(shù)量指標(biāo)。其指標(biāo)函數(shù)值記為用表示第k階段狀態(tài)為采用策略時，后部子過程的指標(biāo)函數(shù)值。最優(yōu)指標(biāo)函數(shù)：指標(biāo)函數(shù)的最優(yōu)值。記為表示從第k階段的狀態(tài)開始到第n

6、階段的終止過程采取最優(yōu)策略所得到的指標(biāo)函數(shù)值，即在不同問題中，指標(biāo)函數(shù)的含義是不同的，它可能指距離、利潤、成本、產(chǎn)品的產(chǎn)量或資源消耗等。如案例中，指標(biāo)函數(shù)是距離，如第二階段狀態(tài)為時，表示由出發(fā)采用決策到下一個階段點的距離，表示從出發(fā)到F的總距離，而表示從B1出發(fā)到F的最短距離。該問題的總目標(biāo)是求即從A到終點F的最短距離。2動態(tài)規(guī)劃的基本原理下面我們結(jié)合案例的最短路問題來介紹動態(tài)規(guī)劃的基本思想與基本原理。窮舉法的計算量將非常大，顯然不適合。考慮最短路線的一個重要特征：若從起點A經(jīng)過B點和C點而達(dá)到終點D是一條最短路線，則由B

7、點出發(fā)經(jīng)過C點到達(dá)終點D點的這條子路線，對于從B點出發(fā)達(dá)到終點D點的所有可能選擇的不同路線來說，必定也是最短路線。在本例中，若找到了是由A到D的最短路線，則也應(yīng)是從B1出發(fā)到D點的所有可能選擇的不同路線中的最短路線。如果不是這樣，則從B1點到D點有另一條距離更短的路線存在，把它和原來的最短路線有A點到B1點的那部分連接起來，就會得到一條從A點到D點的新路線，且比原來的那條最短路線的距離還要短些，這就與假設(shè)矛盾。基于最短路線的這一特性，我們考慮尋找最短路線的方法，就是從最后一段開始，用由后向前逆向遞推的方法，逐步求出各點到終

8、點的最短路線，最后求得由起點到終點的最短路線。以本案例為例，我們按上述思想尋找從A到E的最短路線。AB1B2B3C1C2C3D1D2E第一步，從k=4出發(fā)，狀態(tài)變量可取狀態(tài)它們到E點的路長分別為第二步，k=3，狀態(tài)變量可取三個值這是經(jīng)過一個中途點到達(dá)終點E的兩級決策變量。從到E有兩條路線，需加以比較取其