動(dòng)態(tài)規(guī)劃模型舉例ppt課件-在線瀏覽
2025-06-23 12:08本頁面
【正文】 ，如反應(yīng)器、蒸餾塔、吸收器等，前一設(shè)備的輸出為后一設(shè)備的輸入。 （ 2）發(fā)射一枚導(dǎo)彈去擊中運(yùn)動(dòng)的目標(biāo)，由于目標(biāo)的行動(dòng)是不斷改變的，因此應(yīng)當(dāng)如何根據(jù)目標(biāo)運(yùn)動(dòng)的情況，不斷地決定導(dǎo)彈飛行的方向和速度，使之最快地命中目標(biāo)。隨著使用時(shí)間的增加則變得故障多，油耗高，維修費(fèi)用增加，經(jīng)濟(jì)效益差。另外，每次更新都要付出更新費(fèi)用。 動(dòng)態(tài)規(guī)劃模型是解決這類問題的有力工具。 例 13 最短路問題。 6/3/2022 4 解： 用窮舉法當(dāng)然可以解決這個(gè)問題。顯然當(dāng)路段很多時(shí)，計(jì)算工作量將是很大的。因?yàn)榉駝t，若 D1到 G的最短路是另一條路線 L2，則把 A— B1— C2— D1與 L2連接起來，就會(huì)得到一條不同于 L的從 A到 G的最短路。 6/3/2022 6 具體實(shí)施如下：從 A到 G要走 6個(gè)路段，是一個(gè) 6階段決策問題，記 k=1， 2， … ， 6。設(shè) xk到終點(diǎn) G的最短距離為 fk（ xk），則 k=6時(shí)， f (F1)=4, f (F2)=3,顯然 u (F1)=G, u (F2)=G, k=5時(shí)， f5(E1)=min = min =7 表明 E1到 G的最短路是 E1— F1— G，即 E1的最優(yōu)決策為 u (E1)= 。同法計(jì)算出 f5(E3)=9， u5（ E3） =F2， ,532 45m i n)(),( )(),(m i n)(262251612525 ???????????????????FfFEdFfFEdEf,)(,8)(,)(,6)(,)(,75272m i n)(),()(),(m i n)(42343422424214252141511414EDuDfEDuDfEDuEfEDdEfEDdDfk????????????????????????? 時(shí)，6/3/2022 8 k=3 時(shí)， k=2時(shí) , f2(B1)=13,u2(B1)=C2 f2(B2)=16,u2(B2)=C3 k=1時(shí) , f1(A)=18 ,u1(A)=B1, 于是從 A到 G的最短距離為 f1(A)=18，而最短路線則由A開始順次找出最優(yōu)決策來確定，即 u1(A)=B1， u2(B1)=C2, u3(C2)=D1， u4(D1)=E2， u5(E2)=F2， u6(F2)=G，最短路線為A—— B1—— C2—— D1 —— E2—— F2—— G。 當(dāng)按（ 1）式由 k=6逆推至 k=1時(shí)，就得到了最短距離，而最短路線由順推的最優(yōu)決策確定。 ???????????? ????0)(1,5,6,) ] ,(),([)(77111)(mi nxfkXxxfxxdxfkkkkkkkxDukkkkk?k k6/3/2022 10 需要指出，上例只是最短路問題的一種形式，實(shí)際問題中可以有多種形式，如： 1）路線數(shù)目不定，如圖 3，求任一點(diǎn)（如 B）到 E的最短路線（不論它由幾段組成）； 2）有向路網(wǎng)，如圖 4，求 V1到 V6的有向最短路； 3）旅行商問題，如圖 3，求從 A點(diǎn)出發(fā)，經(jīng)每點(diǎn)一次又回到 A點(diǎn)的最短路 。通常按時(shí)間或空間劃分階段，描述階段的變量稱為 階段變量 ，記為 。各階段的狀態(tài)通常用 狀態(tài)變量 描述。 個(gè)階段的決策過程有 個(gè)狀態(tài)。即：如果某階段的狀態(tài)給定，則此階段以后過程的發(fā)展不受以前狀態(tài)的影響，未來狀態(tài)只依賴于當(dāng)前狀態(tài)。描述決策的變量稱為 決策變量 。用 表示第 階段處于狀態(tài) 時(shí)的決策變量，它是 的函數(shù)，用 表示 的允許決策集合。由第 階段的狀態(tài) 開始到終止?fàn)顟B(tài)的后部子過程的策略記為 在實(shí)際問題中，可供選擇的策略有一定范圍，稱為允許策略集合 。 )( kk xuk kx kx)( kk xD kxk kx)}(,),(),({)( 11 nnkkkkkk xuxuxuxp ????6/3/2022 13 （ 5）狀態(tài)轉(zhuǎn)移方程 如果第 個(gè)階段狀態(tài)變量為 ，作出的決策為 ，那么第 階段的狀態(tài)變量 也被完全確定。指標(biāo)函數(shù)的最優(yōu)值稱為 最優(yōu)值函數(shù) 。 稱此為動(dòng)態(tài)規(guī)劃逆序求解的基本方程 (貝爾曼方程 )。 ?????????????????1,1,),(,0)() ] ,())(,([m i n)(11111)(?nnkuxTxxfxfxuxvxfkkkknnkkkkkkxDukkkkk6/3/2022 15 例 14 生產(chǎn)計(jì)劃問題。 解： 決策變量是第 k周的生產(chǎn)量，記作 uk（ k=1， 2， … ， n）。按照最短路
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1