【正文】 ) A B2 B1 B3 C1 C3 D1 D2 E 5 2 14 12 6 10 10 4 3 12 11 13 9 6 5 8 10 5 2 1 C2 829 53m i n)(),( )(),(m i n)(2421141113 ???????????????????DfDCdDfDCdCfEDC ?? 111C25 A B2 B1 B3 C1 C3 D1 D2 E 5 2 14 12 6 10 10 4 3 12 11 13 9 6 5 8 10 5 2 1 C2 725 56m i n)(),( )(),(m i n)(2422141223 ???????????????????DfDCdDfDCdCf(最短路線為 ) EDC ??22考慮經(jīng)過 的兩條路線 2C26 A B2 B1 B3 C1 C3 D1 D2 E 5 2 14 12 6 10 10 4 3 12 11 13 9 6 5 8 10 5 2 1 C2 12210 58m i n)(),()(),(m i n)(2423141333 ??????????????????? DfDCdDfDCdCf(最短路線為 ) EDC ??23考慮經(jīng)過 的兩條路線 3C27 A B2 B1 B3 C1 C3 D1 D2 E 5 2 14 12 6 10 10 4 3 12 11 13 9 6 5 8 10 5 2 1 C2 201210714812m i n)(),()(),()(),(m i n)(33312321131112 ?????????????????????????????CfCBdCfCBdCfCBdBf(最短路線為 ) EDCB ???111第二階段（ B → C）： B 到 C 有 9 條路線。 首先考慮經(jīng)過 的 3條路線 1B28 A B2 B1 B3 C1 C3 D1 D2 E 5 2 14 12 6 10 10 4 3 12 11 13 9 6 5 8 10 5 2 1 C2 1412471086m i n)(),()(),()(),(m i n)(33322322131222 ?????????????????????????????CfCBdCfCBdCfCBdBf(最短路線為 ) EDCB ???112考慮經(jīng)過 的 3條路線 2B29 A B2 B1 B3 C1 C3 D1 D2 E 5 2 14 12 6 10 10 4 3 12 11 13 9 6 5 8 10 5 2 1 C2 191211712813m i n)(),()(),()(),(m i n)(33332323131332 ?????????????????????????????CfCBdCfCBdCfCBdBf(最短路線為 ) EDCB ???223考慮經(jīng)過 的 3條路線 3B30 A B2 B1 B3 C1 C3 D1 D2 E 5 2 14 12 6 10 10 4 3 12 11 13 9 6 5 8 10 5 2 1 C2 19191145202m i n)(),()(),()(),(m i n)(3232221211 ?????????????????????????????BfBAdBfBAdBfBAdAf(最短路線為 ) EDCBA ????112第一階段（ A → B）： A 到 B 有 3 條路線。 （最短距離為 19） 31 動(dòng)態(tài)規(guī)劃是用來解決多階段決策過程最優(yōu)化的一種數(shù)量方法。其特點(diǎn)在于， 它可以把一個(gè) n 維決策問題變換為幾個(gè)一維最優(yōu)化問題 ，從而一個(gè)一個(gè)地去解決。 需指出： 動(dòng)態(tài)規(guī)劃是求解某類問題的一種方法，是考察問題的一種途徑，而不是一種算法 。必須對(duì)具體問題進(jìn)行具體分析，運(yùn)用動(dòng)態(tài)規(guī)劃的原理和方法，建立相應(yīng)的模型，然后再用動(dòng)態(tài)規(guī)劃方法去求解。 二 . 動(dòng)態(tài)規(guī)劃的原理 最優(yōu)化原理： 作為整個(gè)過程的最優(yōu)策略具有這樣的性質(zhì)：無論過去的狀態(tài)和決策如何，相對(duì)于前面的決策所形成的狀態(tài)而言，余下的決策序列必然構(gòu)成最優(yōu)子策略。也就是說， 一個(gè)最優(yōu)策略的子策略也是最優(yōu)的 。 32 動(dòng)態(tài)規(guī)劃方法的關(guān)鍵：在于正確地寫出 基本的遞推關(guān)系式 和 恰當(dāng)?shù)倪吔鐥l件 （簡稱 基本方程 ）。 要做到這一點(diǎn)，就必須將問題的過程分成幾個(gè)相互聯(lián)系的 階段 ，恰當(dāng)?shù)倪x取 狀態(tài)變量 和 決策變量 及定義 最優(yōu)值函數(shù) ，從而把一個(gè)大問題轉(zhuǎn)化成一組同類型的子問題，然后逐個(gè)求解。 即從邊界條件開始，逐段遞推尋優(yōu)，在每一個(gè)子問題的求解中，均利用了它前面的子問題的最優(yōu)化結(jié)果，依次進(jìn)行，最后一個(gè)子問題所得的最優(yōu)解，就是整個(gè)問題的最優(yōu)解。 33 動(dòng)態(tài)規(guī)劃適用于求解哪一類問題？ ? 每個(gè)階段的最優(yōu)決策過程只與本階段的初始狀態(tài)有關(guān)，而與以前各階段的決策（即為了到達(dá)本階段的初始狀態(tài)而采用哪組決策路線無關(guān)）。換言之，本階段之前的狀態(tài)與決策，只是通過系統(tǒng)在本階段所處的初始狀態(tài)來影響本階段及以后各個(gè)階段的決策?；蛘哒f，系統(tǒng)過程的歷史只能通過系統(tǒng)現(xiàn)階段的狀態(tài)去影響系統(tǒng)的未來。 ? 具有這種性質(zhì)的狀態(tài)稱為無后效性（即馬爾科夫性）狀態(tài)。 ? 動(dòng)態(tài)規(guī)劃方法只適用于求解具有無后效性狀態(tài)的多階段決策問題。 34 練習(xí) 1： A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 E3 F1 F2 G 5 3 1 3 6 8 7 6 3 6 8 5 3 3 8 4 2 2 2 1 3 3 3 5 2 5 6 6 4 最優(yōu)路線為： A → B1 → C2 → D1 → E2 → F2 → G 路長 ＝ 18 求從 A到 G的最短路徑 3 35 ? ? ? ? ? ?? ? ? ? 532 45m i n,m i n262251612525 ???????????????????FfFEdFfFEdEfk=5， 出發(fā)點(diǎn) E E E3 ? ? ? ?? ? ? ? 73543m i n,m i n2621161155 ???????????????????FfFEdFfFEdu5(E1)= F1 E1 F1 G A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 E3 F1 F2 G 5 3 1 3 6 8 7 6 6 8 3 5 3 3 8 4 2 2 1 2 3 3 3 5 5 2 6 6 4 3 )( 15 Efu5(E2)= F2 E2 F2 G ? ? ? ? ? ?? ? ? ? 936 46m i n,m i n262351613535 ???????????????????FfFEdFfFEdEfu5(E3)= F2 E3 F2 G k=6, F1 G, f6(F1)=4 F2 G,f6(F2)=3 36 k=4， f4(D1)=7 u4(D1)=E2 f4(D2)=6 u4(D2)=E2 f4(D3)=8 u4(D3)=E2 k=2, f2(B1)=13 u2(B1)=C2 f2(B2)=16 u2(B2)=C3 f3(C1)=13 u3(C1)=D1 f3(C2)=10 u3(C2)=D1 f3(C3)=9 u3(C3)=D1 f3(C4)=12 u3(C4)=D3 k=3, = min f1(A)= min d1(A,B1)+ f2(B1) d1(A,B2)+ f2(B2) 5+13 3+16 =18 k=1, u1(A)=B1 u2(B1)=C2 u3(C2)=D1 u4(D1)=E2 37 增加研制費(fèi) （ 萬元 ） 新產(chǎn)品成功的概率 甲 乙 丙 0 1 2 例 3：有一工廠研制甲、乙、丙三種新產(chǎn)品，估計(jì)這三種新研制成功的概率分別為： 、 、 。由于工廠急于推出新產(chǎn)品，決定再加撥 2萬元研制費(fèi)，以提高新產(chǎn)品研制成功的概率。據(jù)估計(jì)，把增加的研制費(fèi)用于各種新產(chǎn)品研制時(shí)，研制成功的概率見下表?，F(xiàn)把這批研制費(fèi)分配給各新產(chǎn)品（不分配、分配給 1萬元或分配給 2萬元），使這三種新產(chǎn)品都研制成功的概率最大。應(yīng)怎樣分配。 38 ? 解： 1. 劃分階段 根據(jù)問題的性質(zhì)，按照時(shí)間、空間、變量劃分為若干階段，這是用多階段決策過程描述一個(gè)實(shí)際問題的第一步。一個(gè)階段表示需要做出一次決策的子問題，建立動(dòng)態(tài)規(guī)劃模型要求每個(gè)階段問題具有同一模式。描述階段的變量稱為階段變量，常用自然數(shù) k表示。 可劃分為 3個(gè)階段求解，對(duì)甲產(chǎn)品增加研制費(fèi)記為第1階段，對(duì)乙產(chǎn)品增加研制費(fèi)記為第 2階段，對(duì)丙產(chǎn)品增加研制費(fèi)記為第 3階段， k=1， 2， 3。 39 ? 2. 確定狀態(tài)變量及相應(yīng)的取值范圍 多階段決策過程的進(jìn)展，可用各階段的狀態(tài)演變來描述。狀態(tài)必須包含表示系統(tǒng)情況和確定決策所需要的全部信息，使其能反映過程的演變特征。同時(shí)還要狀態(tài)滿足無后效性，即若已知過程現(xiàn)在處于某一階段的某一狀態(tài)，則該階段以后過程的演變，不再受以前各階段狀態(tài)的影響。確定狀態(tài)變量之后，根據(jù)具體問題的性質(zhì)，找出狀態(tài)變量在各階段的取值范圍。 把有可能提供的研制費(fèi)用作狀態(tài)變量，記為 s