資源描述：
《動態(tài)規(guī)劃ppt課件.ppt》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。
1、第十章動態(tài)規(guī)劃§1 多階段決策過程最優(yōu)化問題舉例§2 基本概念、基本方程與最優(yōu)化原理§3 動態(tài)規(guī)劃的應用(1)§4 動態(tài)規(guī)劃的應用(2)1劣墩唐役汽舉橢碟綏賃庫環(huán)恭愉族舟鉻浙俊錠舒輝閏脯絞沮榆如鍋捷寞呻第章動態(tài)規(guī)劃ppt課件第章動態(tài)規(guī)劃ppt課件§1 多階段決策過程最優(yōu)化問題舉例例1最短路徑問題下圖表示從起點A到終點E之間各點的距離。求A到E的最短路徑。2BACBDBCDEC412312312322164724838675611063751足筐墑漆敲宗梨讓宴居柯拓徊綠擻叛誠乞媚閩俞毖牲窖見祥汐寇辦撲磚哎第章動態(tài)規(guī)劃ppt課件第章
2、動態(tài)規(guī)劃ppt課件§1 多階段決策過程最優(yōu)化問題舉例用窮舉法的計算量:如果從A到E的站點有k個，除A、E之外每站有3個位置則總共有3k-1×2條路徑；計算各路徑長度總共要進行(k+1)3k-1×2次加法以及3k-1×2-1次比較。隨著k的值增加時，需要進行的加法和比較的次數(shù)將迅速增加；例如當k=20時，加法次數(shù)為4.2550833966227×1015次，比較1.3726075472977×1014次。若用1億次/秒的計算機計算需要約508天。3型器瘋油禾攝嫉站淫朵烷聽帶亦肖噪她稅狼皆簿目鑼緘腋釬棧互沃懈源實第章動態(tài)規(guī)劃ppt課
3、件第章動態(tài)規(guī)劃ppt課件§1 多階段決策過程最優(yōu)化問題舉例討論：1、以上求從A到E的最短路徑問題，可以轉化為四個性質完全相同，但規(guī)模較小的子問題，即分別從Di、Ci、Bi、A到E的最短路徑問題。第四階段：兩個始點D1和D2，終點只有一個；表10-1分析得知：從D1和D2到E的最短路徑唯一。4階段4本階段始點（狀態(tài)）本階段各終點（決策）到E的最短距離本階段最優(yōu)終點（最優(yōu)決策)ED1D2106106EE篷襖砰郵融繕浩納顴兄餾移溯鯉醛神始餡庶酣警量沈下材娠咯蕪佰審莖蜒第章動態(tài)規(guī)劃ppt課件第章動態(tài)規(guī)劃ppt課件5第三階段：有三個始點C
4、1，C2，C3，終點有D1，D2，對始點和終點進行分析和討論分別求C1，C2，C3到D1，D2的最短路徑問題：表10-2分析得知：如果經過C1，則最短路為C1-D2-E；如果經過C2，則最短路為C2-D2-E；如果經過C3，則最短路為C3-D1-E。§1 多階段決策過程最優(yōu)化問題舉例階段3本階段始點（狀態(tài)）本階段各終點（決策）到E的最短距離本階段最優(yōu)終點（最優(yōu)決策)D1D2C1C2C38+10=187+10=171+10=116+6=125+6=116+6=12121111D2D2D1株嘻撒陷墟訃劣霧謠隙馬掄努齲僥探鑒抉搭萎渠鞭
5、油固翌熬官帛即鐐肩忌第章動態(tài)規(guī)劃ppt課件第章動態(tài)規(guī)劃ppt課件6第二階段：有4個始點B1,B2,B3,B4，終點有C1,C2,C3。對始點和終點進行分析和討論分別求B1,B2,B3,B4到C1,C2,C3的最短路徑問題：表10-3分析得知：如果經過B1，則走B1-C2-D2-E；如果經過B2，則走B2-C3-D1-E；如果經過B3，則走B3-C3-D1-E；如果經過B4，則走B4-C3-D1-E?！? 多階段決策過程最優(yōu)化問題舉例階段2本階段始點（狀態(tài)）本階段各終點（決策）到E的最短距離本階段最優(yōu)終點（最優(yōu)決策)C1C2C3B
6、1B2B3B42+12=144+12=164+12=167+12=191+11=127+11=188+11=195+11=166+11=172+11=133+11=141+11=1212131412C2C3C3C3蚌中孵踏晦商項衰迎緞廄蹭頁鵬炕佯速甥緬畸袋柏重鞠吶前請糙腋牲絹盛第章動態(tài)規(guī)劃ppt課件第章動態(tài)規(guī)劃ppt課件7第一階段：只有1個始點A，終點有B1,B2,B3,B4。對始點和終點進行分析和討論分別求A到B1,B2,B3,B4的最短路徑問題：表10-4最后，可以得到：從A到E的最短路徑為A?B4?C3?D1?E距離為14
7、.§1 多階段決策過程最優(yōu)化問題舉例階段1本階段始點(狀態(tài))本階段各終點（決策）到E的最短距離本階段最優(yōu)終點(最優(yōu)決策)B1B2B3B4A4+12=163+13=163+14=172+12=1414B4須喜蜂票殉瑯刻位靴峻訴呼牛錘塵然件偉脅檢亞計窟鈣寐稻邏集鵬砂冉騁第章動態(tài)規(guī)劃ppt課件第章動態(tài)規(guī)劃ppt課件8以上計算過程及結果，可用圖2表示，可以看到，以上方法不僅得到了從A到D的最短路徑，同時，也得到了從圖中任一點到E的最短路徑。以上過程，僅用了22次加法，計算效率遠高于窮舉法。BACBDBCDEC41231231233216
8、472483867516106010612111112131414127512§1 多階段決策過程最優(yōu)化問題舉例乾稱素冪橢痘金抿秀捂督艷僳灑女芬誡瀉瓊條酉企盲銹塊僅屏凈簧抬終促第章動態(tài)規(guī)劃ppt課件第章動態(tài)規(guī)劃ppt課件9一、基本概念：1、階段k：表示決策順序的
