【正文】 d3(C1,D2)+ f4(D2)=8+3=11 又因?yàn)槿羧^程最短路徑經(jīng)過 C1,，則從 C1到終點(diǎn) E應(yīng)是一切可能路徑中最短路徑，即： d3(C1,D1)+f4(D1)=9+5=14 d3(C1,D2)+f4(D2)=8+3=11 f3(C1)=min =11 最小費(fèi)用路線為 C1－ D2－ E 相應(yīng)的最優(yōu)決策 u3(C1)=D2 第二節(jié) 動(dòng)態(tài)規(guī)劃求解方法 同理，對(duì)于 C2，有： 最小費(fèi)用路線為 C2－ D1－ E 相應(yīng)的最優(yōu)決策 u3(C2)=D1 d3(C2,D1)+f4(D1)=7+5=12 d3(C2,D2)+f4(D2)=12+3=15 f3(C2)=min =12 最小費(fèi)用路線為 C3－ D2－ E 相應(yīng)的最優(yōu)決策 u3(C3)=D2 d3(C3,D2)+f4(D2)=5+3=8 f3(C3)=min =8 第二節(jié) 動(dòng)態(tài)規(guī)劃求解方法 4 3 11 3 4 4 4 6 1 6 9 7 8 12 5 5 3 A B1 B2 B3 C1 C2 C3 D1 D2 E 第二節(jié) 動(dòng)態(tài)規(guī)劃求解方法 (3) k=2，第二階段，有三種初始狀態(tài) S2={B1,B2,B3} 最小費(fèi)用路線為 B1C3－ D2－ E 相應(yīng)的最優(yōu)決策 u2(B1)=C3 d2(B1,C1)+f3(C1)=3+11=14 d2(B1,C3)+f3(C3)=4+8=12 f2(B1)=min =12 最小費(fèi)用路線為 B2C3－ D2－ E 相應(yīng)的最優(yōu)決策 u2(B2)=C3 d2(B2,C1)+f3(C1)=4+11=15 d2(B2,C2)+f3(C2)=4+15=19 d2(B2,C3)+f3(C3)=6+8=14 f2(B2)=min =14 最小費(fèi)用路線為 B3C1－ D2－ E 相應(yīng)的最優(yōu)決策 u2(B3)=C1 d2(B3,C1)+f3(C1)=1+11=12 d2(B3,C3)+f3(C3)=6+8=14 f2(B3)=min =12 第二節(jié) 動(dòng)態(tài)規(guī)劃求解方法 最小費(fèi)用路線為 AB1C3－ D2－ E 相應(yīng)的最優(yōu)決策 u1(A)=B1 所以整個(gè)問題的最小費(fèi)用路線為 AB1C3D2E 最優(yōu)策略為 {u1(A)=B1,u2(B1)=C3,u3(C3)=D2,u4(D2)=E} 每一階段的求解都利用了第 k階段和第 k+1階段的如下關(guān)系求解： fk(sk)=min{dk(sk,uk)+fk+1(sk+1)},k=4,3,2,1 f5(s5)=0 這種關(guān)系稱為動(dòng)態(tài)規(guī)劃的基本方程， dk(sk,uk)表示第 k階段由狀態(tài) sk點(diǎn)出發(fā)，采用策略 uk到下一階 段 sk+1點(diǎn)時(shí)的兩點(diǎn)間的距離 (4) S1={A} d1(A,B1)+f2(B1)=4+12=16 d2(A,B2)+f2(B2)=3+14=17 d3(A,B3)+f2(B2)=11+12=22 f1(A)=min =16 第二節(jié) 動(dòng)態(tài)規(guī)劃求解方法 第二節(jié) 動(dòng)態(tài)規(guī)劃求解方法 逆序標(biāo)號(hào)法求最短路徑 4 3 11 3 4 4 4 6 1 6 9 7 8 12 5 5 3 A B1 B2 B3 C1 C2 C3 D1 D2 E 4 3 11 3 4 4 4 6 1 6 9 7 8 12 5 5 3 A B1 B2 B3 C1 C2 C3 D1 D2 E 0 5 3 10 13 8 12 14 16 16 由上圖可知，最優(yōu)策略為： AB1C3D2E 最短路長(zhǎng)度為 16 第二節(jié) 動(dòng)態(tài)規(guī)劃求解方法 練習(xí) 利用逆序標(biāo)號(hào)法求最短路徑 2 4 3 7 7 3 5 6 6 8 4 6 3 5 3 4 3 A B1 B2 B3 C1 C2 C3 D1 D2 E 8 7 2 第二節(jié) 動(dòng)態(tài)規(guī)劃求解方法 2 4 3 7 7 3 5 6 6 8 4 6 3 5 3 4 3 A B1 B2 B3 C1 C2 C3 D1 D2 E 8 7 2 0 4 3 8 7 6 14 11 13 15 所以最短路徑為： AB2C1D2E 最短路程為： 15 第二節(jié) 動(dòng)態(tài)規(guī)劃求解方法 利用逆序標(biāo)號(hào)法求最長(zhǎng)路徑 2 4 3 7 7 3 5 6 6 8 4 6 3 5 3 4 3 A B1 B2 B3 C1 C2 C3 D1 D2 E 8 7 2 第二節(jié) 動(dòng)態(tài)規(guī)劃求解方法 2 4 3 7 7 3 5 6 6 8 4 6 3 5 3 4 3 A B1 B2 B3 C1 C2 C3 D1 D2 E 8 7 2 0 4 3 9 8 6 16 13 16 19 所以最長(zhǎng)路徑為： AB3C2D2E 最長(zhǎng)路程為 19 第二節(jié) 動(dòng)態(tài)規(guī)劃求解方法 順序遞推 (前向法 ) 順序遞推是由過程的始點(diǎn)向終點(diǎn)逐段遞推，其階段變量的設(shè)臵與狀態(tài)變量的設(shè)臵次序與逆序法相同，而最優(yōu)值函數(shù) fk(xk+1)表示第 k階段末的結(jié)束狀態(tài)為 xk+1時(shí)，從第 1階段到第 k階段所得到的最大收益，因此順序遞推是相對(duì)始點(diǎn)而言的收益，故一般選擇第 k階段末 (即第 k+1階段初的狀態(tài) )作為第 k階段的狀態(tài)變量 第二節(jié) 動(dòng)態(tài)規(guī)劃求解方法 動(dòng)態(tài)規(guī)劃用順序遞推 (前向法 )時(shí)的基本方程如下： fk(xk+1)=min[vk(xk+1,uk)+fk1(xk)],k=1,2,… n 始端條件 f0(x1)=0 其狀態(tài)轉(zhuǎn)換方程為： Xk=T’k(xk+1,uk) 上式中， fk(xk+1)是指第 k階段狀態(tài)為 xk+1時(shí)，相對(duì)于始點(diǎn)的最優(yōu)指標(biāo)函數(shù)值 而 vk(xk+1,uk)表示第 k階段狀態(tài)為 xk+1取決策為 uk時(shí)對(duì)本階段的階段效益值 一般來說，當(dāng)過程給定終點(diǎn)時(shí)，用順序遞推法比較方便，若一個(gè)多階段決策問題，有一個(gè)固定的過程始點(diǎn)和一個(gè)固定的過程終點(diǎn)，則順序遞推和逆序遞推會(huì)得到相同的最優(yōu)結(jié)果 第二節(jié) 動(dòng)態(tài)規(guī)劃求解方法 4 3 11 3 4 4 4 6 1 6 9 7 8 12 5 5 3 A B1 B2 B3 C1 C2 C3 D1 D2 E 第二節(jié) 動(dòng)態(tài)規(guī)劃求解方法 用順序遞推法求例 1 當(dāng) k=1時(shí)，由基本方程 f1(x2)=min[v1(x2,u1)+f0(x1)] 而 f0(x1)=0 且 x2有三種可能的取值： B1,B2,B3，故有 f1(B1)=min[d(B1,A)+f0(A)]=4 f1(B2)=min[d(B2,A)+f0(A)]=3 f1(B3)= min[d(B3,A)+f0(A)]=11 第二節(jié) 動(dòng)態(tài)規(guī)劃求解方法 當(dāng) k=2時(shí)， f2(x3)=min[v2(x3,u2)+f1(x2)] 當(dāng) x3=C1時(shí)， u2有三種取值。故有 d2(C1,B1)+f1(B1) f2(c1)=min{ d2(C1,B2)+f1(B2) } d2(C1,B3)+f1(B3) 3+4 =min{ 4+3 }=7 1+11 故 C1到 A的最佳路徑為 C1B1A或 C1B2A 第二節(jié) 動(dòng)態(tài)規(guī)劃求解方法 同理當(dāng) x3=c2時(shí)， f2(C2)=min{d2(c2,B2)+f1(B2)}=7 即 C2到 A的最佳路徑為： C2B2A 當(dāng) x3=C3時(shí)， d2(C3,B1)+f1(B1) f2(C3)=min{d2(c3,B2)+f1(B2)} =8 即 C3到 A的最佳路徑為 C3B1A 第二節(jié) 動(dòng)態(tài)規(guī)劃求解方法 當(dāng) k=3時(shí)， f3(x4)=min{v3(x4,u3)+f2(x3)] 因 x4有 D1， D2兩種狀態(tài)， 最佳路徑 D1C2B2A d3(D1,C1)+f2(C1)=9+7=16 d3(D1,C2)+f2(C2)=8+7=15 f3(D1)=min =15 最佳路徑 D2C3B1A d3(D2,C1)+f2(C1)=7+7=16 d3(D2,C2)+f2(C2)=12+7=15 d3(D3,C3)+f2(C3)=5+8=13 f3(D2)=min =13 第二節(jié) 動(dòng)態(tài)規(guī)劃求解方法 當(dāng) k=4時(shí)， f4(x5)=min[v4(x5,u4)+f3(x4)] 因?yàn)?x5=E，只有一種狀態(tài)， u4有兩種選擇 最短距離為 f4(E)=16 與逆序法的結(jié)果相同 最佳路徑 ED2C3B1A d4(E,D1)+f3(D1)=5+15=20 d4(E,D2)+f3(D2)=3+13=16 f4(E)=min =16 第二節(jié) 動(dòng)態(tài)規(guī)劃求解方法 用順序標(biāo)號(hào)法求最短路徑 第二節(jié) 動(dòng)態(tài)規(guī)劃求解方法 4 3 11 3 4 4 4 6 1 6 9 7 8 12 5 5 3 A B1 B2 B3 C1 C2 C3 D1 D2 E 4 3 11 3 4 4 4 6 1 6 9 7 8 12 5 5 3 A B1 B2 B3 C1 C2 C3 D1 D2 E 0 4 3 11 7 7 8 15 13 16 由上圖可知，最優(yōu)策略為： AB1C3D2E 最短路長(zhǎng)度為 16 第二節(jié) 動(dòng)態(tài)規(guī)劃求解方法 練習(xí)利用順序標(biāo)號(hào)法求最短路徑 2 4 3 7 7 3 5 6 6 8 4 6 3 5 3 4 3 A B1 B2 B3 C1 C2 C3 D1 D2 E 8 7 2 第二節(jié) 動(dòng)態(tài)規(guī)劃求解方法 2 4 3 7 7 3 5 6 6 8 4 6 3 5 3 4 3 A B1 B2 B3 C1 C2 C3 D1 D2 E 8 7 2 0 2 4 3 7 9 10 11 13 15 所以最優(yōu)路徑為： AB2C1D1E 最短路程為 15 第二節(jié) 動(dòng)態(tài)規(guī)劃求解方法 利用順序標(biāo)號(hào)法求最長(zhǎng)路徑 第二節(jié) 動(dòng)態(tài)規(guī)劃求解方法 2 4 3 7 7 3 5 6 6 8 4 6 3 5 3 4 3 A B1 B2 B3 C1 C2 C3 D1 D2 E 8 7 2 2 4 3 7 7 3 5 6 6 8 4 6 3 5 3 4 3 A B1 B2 B3 C1 C2 C3 D1 D2 E 8 7 2 0 2 4 3 9 11 10 14 16 19 所以最優(yōu)路徑為： AB3C2D2E 最長(zhǎng)路程為 19 第二節(jié) 動(dòng)態(tài)規(guī)劃求解方法 ? 動(dòng)態(tài)規(guī)劃計(jì)算的方法，不僅減少了計(jì)算量，而且還可以得到任一階段、任一狀態(tài)下的最優(yōu)子策略和相應(yīng)的最優(yōu)指標(biāo)值，也就是說，求出的 不只是一個(gè)最優(yōu)解，而是一族最優(yōu)解。 ? 動(dòng)態(tài)規(guī)則方法是既把當(dāng)前的一段和未來的各段分開，又把當(dāng)前效益和未來效益結(jié)合起來考慮的一種最優(yōu)化方法，因此每階段的選擇都是從全局來考慮的。 第二節(jié) 動(dòng)態(tài)規(guī)劃求解方法 5 4 3 5 1 3 5 4 1 F C 2 C 1 E 1 E 2 E 3 D 1 D 3 D 4 D 5 D 2 A 2 7 6 2 B 1 B 2 B 3 B 4 4 7 3 2 6 3 4 5 2 3 9 3 4 1 7 1 5 2 4 現(xiàn)要從 A地出發(fā)，鋪設(shè)一條天然氣管道到 F地，中間要