【文章內(nèi)容簡(jiǎn)介】 路線。 （ 3） 逐次向前遞推，直到將第一階段的狀態(tài)（即起點(diǎn)）標(biāo) 號(hào)， 起點(diǎn)方格內(nèi)的數(shù)字就是起點(diǎn)到終點(diǎn)的最短距離 ，從起點(diǎn)開(kāi)始 連接終點(diǎn)的粗箭線就是最短路線。 50 第（ 1）步 k=5 □ f5( x5 ) = f5( E ) = 0 這是 邊界條件 [0] E fk( xk ) 表示從第 k 階段狀態(tài) xk 到 E 點(diǎn)的的最短距離 51 第（ 2）步 k=4 □ 狀態(tài)變量 x4 可取兩種狀態(tài) D D2。 ◎ 由 D1到終點(diǎn) E只有一條路線，路長(zhǎng)為 3，即 f4( D1 ) = 3。 ◎ 同理， f4( D2 ) = 4 。 [3] □ 表示由 D1點(diǎn)至 E 點(diǎn)的最短路長(zhǎng) 為 3。 [4] [0] D1 第（ 3）步 k=3 □ 狀態(tài)變量 x3 可取三個(gè)值： C C C3。 ① 由 C1到終點(diǎn) E有 2條路線，分別為經(jīng)過(guò) D D2到達(dá) E點(diǎn)（由 D D2到達(dá) E點(diǎn)的最短路長(zhǎng)在第一步已計(jì)算得出），需加以比較，取其中最短的。 □ 路線 1 v3(C1, D1)+ f4(D1) = 1+3=4 □ 路線 2 v3(C1, D2)+ f4(D2) = 4+4=8 [3] [4] □ 則由 C1到終點(diǎn) E的最短距離 f3( C1 ) = min{v3(C1, D1)+ f4(D1), v3(C1, D2)+ f4(D2) } = 4 [4] C1 第（ 3）步 k=3 ② 由 C2到終點(diǎn) E有 2條路線，分別為經(jīng)過(guò) D D2到達(dá) E點(diǎn)（由 D D2到達(dá) E點(diǎn)的最短路長(zhǎng)在第一步已計(jì)算得出），需加以比較，取其中最短的。 □ 路線 1 v3(C2, D1)+ f4(D1) = 6+3=9 □ 路線 2 v3(C2, D2)+ f4(D2) = 3+4=7 [3] [4] □ 則由 C2到終點(diǎn) E的最短距離 f3( C2 ) = min{v3(C2, D1)+ f4(D1), v3(C2, D2)+ f4(D2) } = 7 C2 [7] [4] 第（ 3）步 k=3 ③ 由 C3到終點(diǎn) E有 2條路線，分別為經(jīng)過(guò) D D2到達(dá) E點(diǎn)（由 D D2到達(dá) E點(diǎn)的最短路長(zhǎng)在第一步已計(jì)算得出），需加以比較，取其中最短的。 □ 路線 1 v3(C3, D1)+ f4(D1) = 3+3=6 □ 路線 2 v3(C3, D2)+ f4(D2) = 3+4=7 [3] [4] □ 則由 C3到終點(diǎn) E的最短距離 f3( C3 ) = min{v3(C3, D1)+ f4(D1), v3(C3, D2)+ f4(D2) } = 6 C3 [7] [4] [6] 第（ 4）步 k=2 □ 狀態(tài)變量 x2 可取三個(gè)值： B B B3。 ① 由 B1到終點(diǎn) E，可分別經(jīng)過(guò) C C C3到達(dá) E點(diǎn)（由 C C C3到 E點(diǎn) 的最短距離在第二步已計(jì)算出），需加以比較，取其中最短的。 □ 路線 1 v2(B1, C1)+ f3(C1) = 7+4=11 □ 路線 2 v2(B1, C2)+ f3(C2) = 5+7=12 □ 路線 3 v2(B1, C3)+ f3(C3) = 6+6=12 [3] [4] □ 則由 B1到終點(diǎn) E的最短距離 f2( B1 ) = min{v2(B1, C1)+ f3(C1), v2(B1, C2)+ f3(C2) v2(B1, C3)+ f3(C3) } = 11 [4] B1 [7] [6] [11] 第（ 4）步 k=2 ② 由 B2到終點(diǎn) E，可分別經(jīng)過(guò) C C C3到達(dá) E點(diǎn)（由 C C C3到 E點(diǎn) 的最短距離在第二步已計(jì)算出），需加以比較，取其中最短的。 □ 路線 1 v2(B2, C1)+ f3(C1) = 3+4=7 □ 路線 2 v2(B2, C2)+ f3(C2) = 2+7=9 □ 路線 3 v2(B2, C3)+ f3(C3) = 4+6=10 [3] [4] □ 則由 B2到終點(diǎn) E的最短距離 f2( B2 ) = min{v2(B2, C1)+ f3(C1), v2(B2, C2)+ f3(C2) v2(B2, C3)+ f3(C3) } = 7 [4] B2 [7] [6] [11] [7] 第（ 4）步 k=2 ③ 由 B3到終點(diǎn) E，可分別經(jīng)過(guò) C C C3到達(dá) E點(diǎn)（由 C C C3到 E點(diǎn) 的最短距離在第二步已計(jì)算出），需加以比較，取其中最短的。 □ 路線 1 v2(B3, C1)+ f3(C1) = 5+4=9 □ 路線 2 v2(B3, C2)+ f3(C2) = 1+7=8 □ 路線 3 v2(B3, C3)+ f3(C3) = 5+6=11 [3] [4] □ 則由 B3到終點(diǎn) E的最短距離 f2( B3 ) = min{v2(B3, C1)+ f3(C1), v2(B3, C2)+ f3(C2) v2(B3, C3)+ f3(C3) } = 8 [4] B3 [7] [6] [11] [7] [8] 第（ 5）步 k=1 □ 狀態(tài)變量 x1 只取一個(gè)值： A。 由 A到終點(diǎn) E，可分別經(jīng)過(guò) B B B3到達(dá) E點(diǎn)（由 B B B3到 E點(diǎn) 的最短距離在第三步已計(jì)算出），需加以比較，取其中最短的。 □ 經(jīng)過(guò) B1點(diǎn) v1(A, B1)+ f2(B1) = 2+11=13 □ 經(jīng)過(guò) B2點(diǎn) v1(A, B2)+ f2(B2) = 5+7=12 □ 經(jīng)過(guò) B3點(diǎn) v1(A, B3)+ f2(B3) = 3+8=11 [3] [4] □ 則由 A到終點(diǎn) E的最短距離 f1( A ) = min{v1(A, B1)+ f2(B1), v1(A, B2)+ f2(B2) v1(A, B3)+ f2(B3) } = 11 [4] A [7] [6] [11] [7] [8] [11] 59 □ 從下圖 反推 可得到最優(yōu)路線。 [3] [4] [4] A [7] [6] [11] [7] [8] [11] □ 因此，由 A到終點(diǎn) E的 最優(yōu)解 為： A→ B3→C2→D2→E □ 由點(diǎn) A到終點(diǎn) E的 最優(yōu)值 為 11。 60 □ 小結(jié)： 在求解的各階段，都利用了第 k階和第 k+1段的如下關(guān) 系： fk( xk ) = min{ vk( xk, uk ) + fk+1( xk+1 ) } (1) f5( x5 = E ) = 0 (2) □ 上述遞推關(guān)系 稱(chēng)為 動(dòng)態(tài)規(guī)劃的 基本方程。 □ 其中（ 2）式稱(chēng) 為 邊界條件。 [3] [4] [4] A [7] [6] [11] [7] [8] [11] 61 動(dòng)態(tài)規(guī)劃方法的優(yōu)點(diǎn) 動(dòng)態(tài)規(guī)劃方法減少了計(jì)算量，而且隨著階段數(shù)的增加，計(jì) 算量將大大減少。 在動(dòng)態(tài)規(guī)劃的解法中，得到的不僅僅是由 A點(diǎn)出發(fā)到 E點(diǎn)的 最短路線及相應(yīng)距離， 而且得到了從所有中間點(diǎn)出發(fā)到 E點(diǎn)的最 短路線及相應(yīng)距離 。這對(duì)于許多實(shí)際問(wèn)題來(lái)說(shuō)是很有用的，有 利于幫助分析所得的結(jié)果。 62 動(dòng)態(tài)規(guī)劃方法的基本思想 1. 將多階段決策過(guò)程劃分階段，恰當(dāng)?shù)剡x擇狀態(tài)變量、決策變 量，定義最優(yōu)指標(biāo)函數(shù)，從而把問(wèn)題化成一簇同類(lèi)型的子問(wèn) 題，然后逐個(gè)求解。 2. 求解時(shí)從邊界條件開(kāi)始，逆過(guò)程方向行進(jìn)，逐段遞推尋優(yōu)， 在每一個(gè)子問(wèn)題求解時(shí)，都要使用它前面已求出的子問(wèn)題的 最優(yōu)結(jié)果，最后一個(gè)子問(wèn)題的最優(yōu)解，就是整個(gè)問(wèn)題的最優(yōu) 解。 63 學(xué)習(xí)目標(biāo)： 1 了解順序解法 4 逆序解法和順序解法 64 □ 動(dòng)態(tài)規(guī)劃的求解有 兩種基本方法 ◎逆序解法（后向動(dòng)態(tài)規(guī)劃方法） 如例 1所使用的方法，尋優(yōu)的方向與多階段決策過(guò)程的實(shí)際 行進(jìn)方向相反，從最后一段開(kāi)始計(jì)算逐段前推，求得全過(guò)程的 最優(yōu)策略。 ◎順序解法（前向動(dòng)態(tài)規(guī)劃方法） 與逆序解法相反，順序解法的尋優(yōu)的方向與過(guò)程的行進(jìn)方向 相同，計(jì)算時(shí)從第一段開(kāi)始逐段向后遞推，計(jì)算后一段要用到 前一段的求優(yōu)結(jié)果，最后一段計(jì)算的結(jié)果就是全過(guò)程的最優(yōu)結(jié) 果。 65 □ 我們?cè)俅斡美?1來(lái)說(shuō)明順序解法。 □ 由于此問(wèn)題的始點(diǎn) A與終點(diǎn) E都是固定的，計(jì)算由 A點(diǎn)到 E點(diǎn) 的最短路線與由 E點(diǎn)到 A點(diǎn)的最短路線沒(méi)有什么不同。 □ 若設(shè) fk( xk+1 ) 表示從起點(diǎn) A到第 k階段末狀態(tài)點(diǎn) xk+1的最短距離 就可以由前向后逐步求出起點(diǎn) A到各階段末狀態(tài)點(diǎn)的最短距 離，最后求出起點(diǎn) A到 E點(diǎn)的最短距離及路線。 動(dòng)態(tài)規(guī)劃的目標(biāo)： 最優(yōu)指標(biāo) f4( E ) 66 第一步 k=0 □ f0( x1 ) = f0( A ) = 0 這是 邊界條件 [0] A fk( xk+1 ) 表示從起點(diǎn) A到第 k階段 末狀態(tài)點(diǎn) xk+1的最短距離 第二步 k=1 [2] [3] [5] [0] □ 按 f1( x2 ) 的定義有 f1( B1 ) = v( B1, A ) + f0( A ) = 2 f1( B2 ) = v( B2, A ) + f0( A ) = 5 f1( B3 ) = v( B3, A ) + f0( A ) = 3 B1 B2 B3 第三步 k=2 [2] [3] [5] [0] □ 按 f2( x3 ) 的定義有 ① v( C1, B1 ) + f1( B1 ) = 7+2 = 9 f2( C1 ) = min v( C1, B2 ) + f1( B2 ) = 3+5 = 8 v( C1, B3 ) + f1( B3 ) = 5+3 = 8 □ u2( C1 ) = B2 或 B3 [8] C1 □ 狀態(tài)轉(zhuǎn)移方程： xk=Tk( xk+1, uk ) 第三步 k=2 [2] [3] [5] [0] □ 按 f2( x3 ) 的定義有 ② v( C2, B1 ) + f1( B1 ) = 5+2 = 7 f2( C2 ) = min v( C2, B2 ) + f1( B2 ) = 2+5 = 7 v( C2, B3 ) + f1( B3 ) = 1+3 = 4 □ u2( C2 ) = B3 [8] [4] C2 第三步 k=2 [2] [3] [5] [0] □ 按 f2( x3 ) 的定義有 ③ v( C3, B1 ) + f1( B1 ) = 6+2 = 8 f2( C3 ) = min v( C3, B2 ) + f1(