動(dòng)態(tài)規(guī)劃matlabppt課件(參考版)
2025-05-09 12:08本頁(yè)面
【正文】 作業(yè)：用 LINGO軟件求解下列最短路問題。 Data: W=3 5 7 7 6 9 5 2 3 8 3 5 4 3 6 9 4 3。 for(nodes(i)|iLTn:d(i)=min(arcs(i,j):w(i,j)+d(j)))。 Endsets n=size(nodes)。 3 應(yīng)用 LINGO軟件求解動(dòng)態(tài)規(guī)劃 解： LINGO程序如下： Model: Sets: Nodes/a,b1,b2,b3,c1,c2,c3,d1,d2,e/:d。 動(dòng)態(tài)規(guī)劃的基本方程是遞推逐段求解的根據(jù)。 求解時(shí)從邊界條件開始， 逆方向逐 段遞推尋優(yōu)。 動(dòng)態(tài)規(guī)劃方法存在的不足之處： （ 1）靜態(tài)規(guī)劃模型轉(zhuǎn)化為動(dòng)態(tài)規(guī)劃模型十分困難； （ 2）狀態(tài)變量的“無(wú)后效性”條件難以滿足。 這種在圖上直接計(jì)算的方法稱為 標(biāo)號(hào)法 。 反推可得最優(yōu)決策序列 再按計(jì)算順序 即 所以得最短路線為 注 1： 從本案例的計(jì)算過程可以看出，在各階段，都 利用了第 k階段和第 k+1階段的如下關(guān)系： ? ?55 0fs ?這種遞推關(guān)系稱為 動(dòng)態(tài)規(guī)劃的基本方程 ， 稱為邊界條件。 從 到 E有兩條路線， 需加以比較取其中最短的， 即 11CD?,E? ? ?3 1 1 .u C D?? ? ? ? ? ?? ? ? ?3 2 1 4 1323 2 2 4 2, 44m in m in 633,d C D f DfCd C D f D??? ?????? ? ?? ? ? ??? ????1C這說明由 到 E的最短距離為 7， 其路徑為 相應(yīng)的決策為 同理 2C 22 ,C D E??? ?3 2 2 .u C D?? ? ? ? ? ?? ? ? ?3 3 1 4 1333 3 2 4 2, 64m in m in 1 093,d C D f DfCd C D f D??? ?????? ? ?? ? ? ??? ????即 到終點(diǎn) E的最短距離為 6， 其路徑為 相應(yīng)的決策為 即 3C 31CD?,E?? ? ? ?2 2 2 2 21 1 , ,f B u B C??? ? ? ?2 1 2 1 21 2 , ,f B u B C??? ?3 3 1 .u C D?到終點(diǎn) E的最短距離為 10 。 以本案例為例，我們按上述思想尋找從 A到 E的最 短路線。 如果不是這樣， 則從 B1點(diǎn)到 D點(diǎn)有另一條距離更短的 路線存在， 把它和原來(lái)的最短路線有 A點(diǎn)到 B1點(diǎn)的那 部分連接起來(lái)， 就會(huì)得到一條從 A點(diǎn)到 D點(diǎn)的新路線， 且比原來(lái)的那條最短路線的距離還要短些 ， 這就與 假設(shè)矛盾。 考慮最短路線的一個(gè)重要特征： 若從起點(diǎn) A經(jīng)過 B點(diǎn)和 C點(diǎn)而達(dá)到終點(diǎn) D是一條最短路線， 則由 B點(diǎn)出 發(fā)經(jīng)過 C點(diǎn)到達(dá)終點(diǎn) D點(diǎn)的這條子路線，對(duì)于從 B點(diǎn) 出發(fā)達(dá)到終點(diǎn) D點(diǎn)的所有可能選擇的不同路線來(lái)說， 必定也是最短路線。 2 動(dòng)態(tài)規(guī)劃的基本原理 下面我們結(jié)合案例的最短路問題來(lái)介紹動(dòng)態(tài) 規(guī)劃的基本思想與基本原理。 如 案例中， 指標(biāo)函數(shù)是距離， 如第二
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1