動(dòng)態(tài)規(guī)劃matlabppt課件-在線瀏覽
2025-06-23 12:08本頁(yè)面
【正文】 ? ? ?12B C D??在本例中， 若找到了 是由 A到 D的最短路線， 則 也應(yīng)是從 B1 出 發(fā)到 D點(diǎn)的所有可能選擇的不同路線中的最短路線。 基于最短路線的這一特性， 我們考慮尋找 最短路線的方法， 就是從最后一段開始， 用由后向前 逆向遞推的方法， 逐步求出各點(diǎn)到終點(diǎn)的最短路線， 最后求得由起點(diǎn)到終點(diǎn)的最短路線。 A B1 B2 B3 C1 C2 C3 D1 D2 E 35967752383543 3496? ? ? ? ? ?? ? ? ?3 1 1 4 1313 1 2 4 2, 34m in m in 753,d C D f DfCd C D f D??? ?????? ? ?? ? ? ??? ????第一步， 從 k=4出發(fā)， 狀態(tài)變量 4s 12,DD? ? ? ?4 1 4 24 , 3f D f D??3s1C1 2 3, , ,C C C可取狀態(tài) 它們到 E點(diǎn)的路長(zhǎng)分別為 第二步， k=3， 狀態(tài)變量 可取三個(gè)值 這是經(jīng)過一個(gè)中途點(diǎn)到達(dá)終點(diǎn) E的兩級(jí)決策變量。 其路徑為 相應(yīng)的決策為 類似地， k=2時(shí) ? ? ? ?1 1 11 5 ,f A u A B??? ? ? ?2 3 2 3 29,f B u B C??k=1時(shí)， 出發(fā)點(diǎn)只有一個(gè) A點(diǎn)， 則 ? ? ? ? ? ? ? ?1 1 2 1 2 3 2 2 4 2, , ,u A B u B C u C D u D E? ? ? ?1 2 2 .A B C D E? ? ? ?? ? ? ? ? ?? ?11m i n 4 , 3 , 2 , 1kk k k k k k kuf s d s u f s k??? ? ?， ，? ?55 0fs ?? ?,ku即從起點(diǎn) A到終點(diǎn) E的最短距離為 15。 上述最短路線的計(jì)算過程也可用圖直觀表示出 來，如圖： A B1 B2 B3 C1 C2 C3 D1 D2 E 356333346(15)(9)(11)(12)(10)(6)(7)(3)(4)(0)這里，每個(gè)節(jié)點(diǎn)上方的括號(hào)內(nèi)的數(shù)字， 表示該點(diǎn)到 E點(diǎn)的最短距離， 連接各點(diǎn)到 E點(diǎn)的線表示最短路徑。 動(dòng)態(tài)規(guī)劃方法相對(duì)于窮舉法來說有以下優(yōu)點(diǎn)： （ 1）減少了計(jì)算量； （ 2）豐富了計(jì)算結(jié)果。 動(dòng)態(tài)規(guī)劃的 基本思想 總結(jié)： 先將多階段決策的過程劃分成幾個(gè)相互聯(lián)系 的階段， 恰當(dāng)?shù)剡x取狀態(tài)變量、決策變量， 定義最 優(yōu)指標(biāo)函數(shù)， 從而把問題化成一族同類型的子問題， 然后逐個(gè)求解。 在每一個(gè)子問題求解時(shí)， 都要使用它 前面已求出的子問題的最優(yōu)結(jié)果， 最后一個(gè)子問題 的最優(yōu)解， 就是整個(gè)問題的最優(yōu)解。 動(dòng)態(tài)規(guī)劃基本方程可表述為： ku,ks( , )k k kd s u11()11( ) ( ( , ) ( ) ) , , 1 , , 1( ) 0k k kk k k k k k ku D s
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1