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