【正文】 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 最短路長度為 16 第二節(jié) 動態(tài)規(guī)劃求解方法 練習(xí)利用順序標(biā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é) 動態(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é) 動態(tài)規(guī)劃求解方法 利用順序標(biāo)號法求最長路徑 第二節(jié) 動態(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 最長路程為 19 第二節(jié) 動態(tài)規(guī)劃求解方法 ? 動態(tài)規(guī)劃計算的方法，不僅減少了計算量，而且還可以得到任一階段、任一狀態(tài)下的最優(yōu)子策略和相應(yīng)的最優(yōu)指標(biāo)值，也就是說，求出的 不只是一個最優(yōu)解，而是一族最優(yōu)解。 U 低 高 低 低 低 低 高 高 高 高 年初 第二年 第三年 第四年 第五年 即用最快的方法從 2*2*2*2*2=32種方案中找到最優(yōu)方案 一般先保守生產(chǎn) 后風(fēng)險生產(chǎn)可使產(chǎn)量最大 第一節(jié) 動態(tài)規(guī)劃原理和模型 例某運輸公司有 500輛運輸卡車，在超負(fù)荷運輸 (即每天滿載行駛 500km以上 )情況下，年利潤為 25萬元 /輛，這時卡車的年損壞率為 ，在低負(fù)荷運輸 (即每天行駛 300KM以下 )情況下，年利潤為 16萬元 /輛、年損壞率為 ，現(xiàn)在要求制訂一個 5年運輸計劃，問每年年初應(yīng)如何分配完好車輛在兩種不同負(fù)荷下運輸?shù)目ㄜ嚁?shù)量，使在 5年內(nèi)總利潤最大？ U 低 高 低 低 低 低 高 高 高 高 年初 第二年 第三年 第四年 第五年 第一節(jié) 動態(tài)規(guī)劃原理和模型 例 排序問題 ：有 5個零件需要在 A、 B兩臺機(jī)床上加工，每個零件都必須經(jīng)過先 A后 B的加工順序，加工時間如下表，問應(yīng)如何安排加工順序，使總的加工時間最少？ 零件號 機(jī)床 A 機(jī)床 B 1 3 6 2 9 2 3 4 7 4 5 3 5 7 4 第一節(jié) 動態(tài)規(guī)劃原理和模型 以上問題的一個共同特點是問題的過程可以分解成相互聯(lián)系的若干階段，在每個階段均需要作出決策，各個階段的決策取決于目前的狀態(tài)，它又將影響到以后的發(fā)展，當(dāng)各個階段的決策確定之后，就構(gòu)成一個決策序列，我們的目的就是要在決策系列中，尋找最優(yōu)的決策序列 二、動態(tài)規(guī)則的分類 離散確定性 離散隨機(jī)性 連續(xù)確定性 連續(xù)隨機(jī)性 第一節(jié) 動態(tài)規(guī)劃原理和模型 三、動態(tài)規(guī)則的基本概念 階段 將所給問題，按時間或空間特性分解成若干互相聯(lián)系的部分，用字母 K表示階段變量 第一節(jié) 動態(tài)規(guī)劃原理和模型 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 U 低 高 低 低 低 低 高 高 高 高 年初 第二年 第三年 第四年 第五年 4個階段 多種選擇 5個階段 2種選擇 狀態(tài) 狀態(tài)就是每個階段的起始位臵 ，它既是該階段某支路的起點，又是前一階段某支路的終點 ,通常一個階段包含若干個狀態(tài)，第 K階段的狀態(tài)就是該階段所有始點集合 狀態(tài)變量 ：描述各階段狀態(tài)的變量，用 sk表示 狀態(tài)集合 ：狀態(tài)變量 sk的取值集合 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 S1={A}, S2={B1,B2,B3} S3={C1,C2,C3} S4={D1,D2} 第一節(jié) 動態(tài)規(guī)劃原理和模型 決策 從一個階段給定狀態(tài)出發(fā)，到下階段某一狀態(tài)的選擇 決策變量 ：描述決策的變量，常用 uk(xk)表示第 k階段狀態(tài) xk的決策變量 第一節(jié) 動態(tài)規(guī)劃原理和模型 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 若第 2階段從狀態(tài) B1出發(fā)到第 3階段時選定的狀態(tài)為 C1,則有u2(B1)=C1 允許的決策集合 ：第 K階段某給定狀態(tài) xk的決策變量 uk(xk)的允許取值范圍 常用 Dk(xk)表示 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 D2(B1)={C1,C3} D2(B2)={C1,C2,C3} 第一節(jié) 動態(tài)規(guī)劃原理和模型 策略 由第一階段開始到最后階段終點的全過程的每一階段的決策 ui(xj)(i,j=1,2,3,..)組成的決策序列， 記為 P1,n(X)={u1(x1),u2(x2),… .un(xn)} 稱 Pk,n(X)={uk(xk),uk+1(xk+1),… .un(xn)}為由第 k階段開始到最后階段的一個子策略 第一節(jié) 動態(tài)規(guī)劃原理和模型 AB1C2D1E AB2C1D2E 均為策略 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 允許策略集合 ：可供選擇策略的范圍 最優(yōu)策略 ：允許策略集合中最優(yōu)的一個策略 在例 1中最優(yōu)策略為： AB1C3D2E 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 第一節(jié) 動態(tài)規(guī)劃原理和模型 狀態(tài)轉(zhuǎn)換方程 它是確定過程由某一階段的一個狀態(tài)到下一階段另一狀態(tài)的演變過程，用 sk+1=Tk(sk,uk)表示， 該方程描述了由第 k階段到第 k+1階段的狀態(tài)轉(zhuǎn)換規(guī)律，又稱狀態(tài)轉(zhuǎn)換函數(shù) 例 1中，前一階段的終點就是后一階段的起點，所以狀態(tài)轉(zhuǎn)換方程為： Sk+1=uk(sk) 第一節(jié) 動態(tài)規(guī)劃原理和模型 指標(biāo)函數(shù) 衡量多階段決策過程優(yōu)劣的一種數(shù)量指標(biāo)，一個 n階段決策過程，從 1到 n稱為問題的原過程 , 對于任意一個給定的 k，從第 k階段到第 n階段的過程稱為原過程的一個后部子過程， 用 V1,n(s1,p1,n)表示初始狀態(tài)為 s1，采用策略 p1,n時，原過程的指標(biāo)函數(shù)值 如 V1,4(A,P1,4) 而 Vk,n(sk,pk,n)表示在第 k 階段，狀態(tài)為 sk采用策略 pk,n時，后部子過程的指標(biāo)函數(shù)值， V2,4(B1,P2,4) 第一節(jié) 動態(tài)規(guī)劃原理和模型 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 ? 從第 k階段狀態(tài) sk 采用最優(yōu)策略 pk*,n到過程終止時的最佳效益值，稱為最優(yōu)指標(biāo)函數(shù) ? 記 ? fk(sk)=Vk,n(sk,pk*,n)=optimumpk,nVk,n(sk,pk,n) ? 在例 1中，每階段所走的距離為指標(biāo)函數(shù)， ? 如 V2,4(B1) 表示在第 2階段，狀態(tài)為 B1時，從 B1到 E的距離 ? 而 f2(B1)則表示從 B1到 E最短距離，本問題所要求的目標(biāo)是距離之和的最小值，即 f1(A) 第一節(jié) 動態(tài)規(guī)劃原理和模型 四、動態(tài)規(guī)劃貝爾曼的最優(yōu)化原理 最優(yōu)決策具有這樣的性質(zhì)：無論初始狀態(tài)及初始決策如何，對于先前決策所形成的狀態(tài)而言，其以后的所有決策應(yīng)構(gòu)成最優(yōu)策略 貝爾曼的最優(yōu)化原理 如果最短路線在第 k 階段通過狀態(tài) xk，則這條最短路線在由 xk 出發(fā)到達(dá)終點的這段線段，對于從 xk出發(fā)到終點的所有其它線路來說仍然是最優(yōu)的 第一節(jié) 動態(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é) 動態(tài)規(guī)劃原理和模型 例如：上例的最優(yōu)策略為： AB1C3D2E B1C3D2E仍然是從 B1出發(fā)到終點的所有線路中最短的一條 B1C1D1E 17 B1C1D2E 13 B1C3D2E 12 一、動態(tài)規(guī)劃求解的思想 逆序法 ：是從過程的最后一階段開始，用逆序遞推方法求解，逐步求出各階段各點到終點 E的最短路線，最后求得 A到 E點的最短路線 順序法 ：是從過程的第一階段開始，用順序遞推的方法求解，逐步求出各階段各點到起點最短路線，最后求得 A到 E點的最短路線。圖上節(jié)點表示地點，邊表示兩地之間的道路，邊上的數(shù)字表示兩地間的運輸費用，求運輸費用最低的運輸路線。 動態(tài)規(guī)則是將一個較復(fù)雜的多階段決策問題分解為若干相互關(guān)聯(lián)的較容易求解的子 (單）決策問題。運 籌 帷 幄 之 中 決 勝 千 里 之 外 第七章動態(tài)規(guī)劃 運籌學(xué) 教學(xué)要求： ?了解 動態(tài)規(guī)劃的基本思想 ?掌握 一維離散動態(tài)規(guī)劃的建模和求解方法應(yīng)用 ?會運用動態(tài)規(guī)劃方法解決一些基本應(yīng)用問題。 第一節(jié) 動態(tài)規(guī)劃原理和模型 在生產(chǎn)和經(jīng)營活動中，經(jīng)常遇到這樣的問題，它們包含若干個相互聯(lián)系的階段，而且，在每一階段都要做出決策，一個階段的決策除影響該階段本身的效果之外，還影響到下一階段的起始狀態(tài)，從而影響到整個過程的效果最優(yōu) 因此不但要考慮這一階段，還要把它看成是整個過程決策鏈中的一個鏈環(huán)，這種過程稱為多階段決策過程，如企業(yè)在生產(chǎn)過程中，由于需求是隨時間變化的，因此為了獲得全年的最佳效益，就要逐月或逐季度地根據(jù)庫存和需求決定生產(chǎn)計劃。 而每一個子決策問題都有多種選擇 當(dāng)一個子決策問題確定以后，將影響另一個子決策問題 從而影響到整個問題的決策 第一節(jié) 動態(tài)規(guī)劃原理和模型 例 最小費用問題： 某運輸公司擬將一批貨物從 A地運往 E地，其間的交通系統(tǒng)網(wǎng)絡(luò)如下圖所示。 A B1 B2 B3 C1 C2 C3 D1 D2 E 第 2階段 第 3階段 第 4階段 第 1階段 的狀態(tài) 第 2階段的狀態(tài) 第 1階段 4 3 11 3 4 4 4 6 1 6 9 7 8 12 5 5 3 第一節(jié)