第七章-動(dòng)態(tài)規(guī)劃優(yōu)秀文檔

運(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ī)劃原理和模型例1、最小費(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)輸路線。AB1B2B3C1C2C3D1D2E第2階段第3階段第4階段第1階段的狀態(tài)第2階段的狀態(tài)第1階段4311344461697812553第一節(jié)動(dòng)態(tài)規(guī)劃原理和模型例2、機(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稱完好率,a<0<1)，另外有u2臺(tái)機(jī)器用于低負(fù)荷生產(chǎn)，產(chǎn)品的年產(chǎn)量為s2=g(u2)，年終完好機(jī)器數(shù)為bu2(0<b<1)，試制定一個(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)輸卡車(chē)，在超負(fù)荷運(yùn)輸(即每天滿載行駛500km以上)情況下，年利潤(rùn)為25萬(wàn)元/輛，這時(shí)卡車(chē)的年損壞率為0.3，在低負(fù)荷運(yùn)輸(即每天行駛300KM以下)情況下，年利潤(rùn)為16萬(wàn)元/輛、年損壞率為0.1，現(xiàn)在要求制訂一個(gè)5年運(yùn)輸計(jì)劃，問(wèn)每年年初應(yīng)如何分配完好車(chē)輛在兩種不同負(fù)荷下運(yùn)輸?shù)目ㄜ?chē)數(shù)量，使在5年內(nèi)總利潤(rùn)最大？U低高低低低低高高高高年初第二年第三年第四年第五年第一節(jié)動(dòng)態(tài)規(guī)劃原理和模型例3、排序問(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ī)床B136292347453574第一節(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ī)則的分類(lèi)離散確定性離散隨機(jī)性連續(xù)確定性連續(xù)隨機(jī)性第一節(jié)動(dòng)態(tài)規(guī)劃原理和模型三、動(dòng)態(tài)規(guī)則的基本概念1、階段將所給問(wèn)題，按時(shí)間或空間特性分解成若干互相聯(lián)系的部分，用字母K表示階段變量第一節(jié)動(dòng)態(tài)規(guī)劃原理和模型AB1B2B3C1C2C3D1D2E4311344461697812553U低高低低低低高高高高年初第二年第三年第四年第五年4個(gè)階段多種選擇5個(gè)階段2種選擇決勝千里之外但同時(shí)要求必須及時(shí)滿足需求。(2)k=3第三階段將一種或多種有限的資源，分配給若干個(gè)使用者，而使目標(biāo)達(dá)到最優(yōu)第一節(jié)動(dòng)態(tài)規(guī)劃原理和模型d2(B2,C2)+f3(C2)=4+15=19f2(x2)=max{v2(x2,u2)+f3(x3)}0≤u2≤x2第一節(jié)動(dòng)態(tài)規(guī)劃原理和模型f1(B1)=min[d(B1,A)+f0(A)]=4順序法：是從過(guò)程的第一階段開(kāi)始，用順序遞推的方法求解，逐步求出各階段各點(diǎn)到起點(diǎn)最短路線，最后求得A到E點(diǎn)的最短路線。f2(x2)=max{v2(x2,u2)+f3(x3)}0≤u2≤x2第一節(jié)動(dòng)態(tài)規(guī)劃原理和模型即C3到A的最佳路徑為C3-B1-ASk+1=uk(sk)設(shè)部件i上裝有zi個(gè)備用元件時(shí)，它正常工作的概率是pi(zi)。第一節(jié)動(dòng)態(tài)規(guī)劃原理和模型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的取值集合AB1B2B3C1C2C3D1D2E4311344461697812553S1={A},S2={B1,B2,B3}S3={C1,C2,C3}S4={D1,D2}第一節(jié)動(dòng)態(tài)規(guī)劃原理和模型3、決策從一個(gè)階段給定狀態(tài)出發(fā)，到下階段某一狀態(tài)的選擇決策變量：描述決策的變量，常用uk(xk)表示第k階段狀態(tài)xk的決策變量第一節(jié)動(dòng)態(tài)規(guī)劃原理和模型AB1B2B3C1C2C3D1D2E4311344461697812553若第2階段從狀態(tài)B1出發(fā)到第3階段時(shí)選定的狀態(tài)為C1,則有u2(B1)=C1允許的決策集合：第K階段某給定狀態(tài)xk的決策變量uk(xk)的允許取值范圍常用Dk(xk)表示AB1B2B3C1C2C3D1D2E4311344461697812553D2(B1)={C1,C3}D2(B2)={C1,C2,C3}第一節(jié)動(dòng)態(tài)規(guī)劃原理和模型4、策略由第一階段開(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ī)劃原理和模型A-B1-C2-D1-EA-B2-C1-D2-E均為策略AB1B2B3C1C2C3D1D2E4311344461697812553允許策略集合：可供選擇策略的范圍最優(yōu)策略：允許策略集合中最優(yōu)的一個(gè)策略在例1中最優(yōu)策略為：A-B1-C3-D2-EAB1B2B3C1C2C3D1D2E4311344461697812553第一節(jié)動(dòng)態(tài)規(guī)劃原理和模型5、狀態(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ī)劃原理和模型6、指標(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ī)劃原理和模型AB1B2B3C1C2C3D1D2E4311344461697812553從第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ī)劃原理和模型4311344461697812553AB1B2B3C1C2C3D1D2E第一節(jié)動(dòng)態(tài)規(guī)劃原理和模型例如：上例的最優(yōu)策略為：A-B1-C3-D2-EB1-C3-D2-E仍然是從B1出發(fā)到終點(diǎn)的所有線路中最短的一條B1-C1-D1-E17B1-C1-D2-E13B1-C3-D2-E12一動(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ī)劃求解方法4311344461697812553AB1B2B3C1C2C3D1D2E第二節(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)策略u(píng)4(D1)=Ef4(D2)=d4(D2,E)=3最優(yōu)策略u(píng)4(D2)=E第二節(jié)動(dòng)態(tài)規(guī)劃求解方法因此，最優(yōu)化問(wèn)題是在考慮上述限制條件下，應(yīng)如何選擇各部件的備用元件數(shù)，使整個(gè)系統(tǒng)的工作可靠性最大？建立狀態(tài)轉(zhuǎn)移方程sk+1=sk-wkxk當(dāng)一個(gè)子決策問(wèn)題確定以后，將影響另一個(gè)子決策問(wèn)題但備用元件多了，整個(gè)系統(tǒng)的成本、重量、體積均相應(yīng)加大，工作精度也降低。第一節(jié)動(dòng)態(tài)規(guī)劃原理和模型現(xiàn)有一臺(tái)效益函數(shù)為r(t)的設(shè)備，其維修費(fèi)用為u(t)，更新費(fèi)用為c(t)，需要在n年內(nèi)的每年年初做出決策，是繼續(xù)使用舊設(shè)備還是更新一臺(tái)新設(shè)備，使n年總效益最大？第二節(jié)動(dòng)態(tài)規(guī)劃求解方法d2(B1,C3)+f3(C3)=4+8=12Xk=T’k(xk+1,uk)背包問(wèn)題：一位旅行者攜帶背包旅游，已知他的背包所能承受的重量為w千克，現(xiàn)有n種物品可供他選擇裝入包中，第i種物品的單件重量為wi千克，其價(jià)值是攜帶數(shù)量xi的函數(shù)pi(xi)。例2、機(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稱完好率,a<0<1)，另外有u2臺(tái)機(jī)器用于低負(fù)荷生產(chǎn)，產(chǎn)品的年產(chǎn)量為s2=g(u2)，年終完好機(jī)器數(shù)為bu2(0<b<1)，試制定一個(gè)五年計(jì)劃，使產(chǎn)品產(chǎn)量最高。f5(x5)=max{v5(x5,u5)+f6(x6)}0≤u5≤x5Yk+1=yk-zkwk4311344461697812553AB1B2B3C1C2C3D1D2E第二節(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-D1-E和C1-D2-E，對(duì)于C1-D1-E，其最短路徑應(yīng)為：從C1-D1的距離d3(C1,D1)，再加上D1-E的最短距離f4(D1),故有C1-D1-E：d3(C1,D1)+f4(D1)=9+5=14C1-D2-E:d3(C1,D2)+f4(D2)=8+3=11又因?yàn)槿羧^(guò)程最短路徑經(jīng)過(guò)C1,，則從C1到終點(diǎn)E應(yīng)是一切可能路徑中最短路徑，即：d3(C1,D1)+f4(D1)=9+5=14d3(C1,D2)+f4(D2)=8+3=11f3(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)=D1d3(C2,D1)+f4(D1)=7+5=12d3(C2,D2)+f4(D2)=12+3=15f3(C2)=min=12最小費(fèi)用路線為C3－D2－E相應(yīng)的最優(yōu)決策u3(C3)=D2d3(C3,D2)+f4(D2)=5+3=8f3(C3)=min=8第二節(jié)動(dòng)態(tài)規(guī)劃求解方法4311344461697812553AB1B2B3C1C2C3D1D2E第二節(jié)動(dòng)態(tài)規(guī)劃求解方法(3)k=2，第二階段，有三種初始狀態(tài)S2={B1,B2,B3}最小費(fèi)用路線為B1-C3－D2－E相應(yīng)的最優(yōu)決策u2(B1)=C3d2(B1,C1)+f3(C1)=3+11=14d2(B1,C3)+f3(C3)=4+8=12f2(B1)=min=12最小費(fèi)用路線為B2-C3－D2－E相應(yīng)的最優(yōu)決策u2(B2)=C3d2(B2,C1)+f3(C1)=4+11=15d2(B2,C2)+f3(C2)=4+15=19d2(B2,C3)+f3(C3)=6+8=14f2(B2)=min=14最小費(fèi)用路線為B3-C1－D2－E相應(yīng)的最優(yōu)決策u2(B3)=C1d2(B3,C1)+f3(C1)=1+11=12d2(B3,C3)+f3(C3)=6+8=14f2(B3)=min=12第二節(jié)動(dòng)態(tài)規(guī)劃求解方法最小費(fèi)用路線為A-B1-C3－D2－E相應(yīng)的最優(yōu)決策u1(A)=B1所以整個(gè)問(wèn)題的最小費(fèi)用路線為A-B1-C3-D2-E最優(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,1f5(s5)=0這種關(guān)系稱為動(dòng)態(tài)規(guī)劃的基本方程，dk(sk,uk)表示第k階段由狀態(tài)sk點(diǎn)出發(fā)，采用策略u(píng)k到下一階段sk+1點(diǎn)時(shí)的兩點(diǎn)間的距離(4)S1={A}d1(A,B1)+f2(B1)=4+12=16d2(A,B2)+f2(B2)=3+14=17d3(A,B3)+f2(B2)=11+12=22f1(A)=min=16第二節(jié)動(dòng)態(tài)規(guī)劃求解方法第二節(jié)動(dòng)態(tài)規(guī)劃求解方法1、逆序標(biāo)號(hào)法求最短路徑4311344461697812553AB1B2B3C1C2C3D1D2E4311344461697812553AB1B2B3C1C2C3D1D2E0531013812141616由上圖可知，最優(yōu)策略為：A-B1-C3-D2-E最短路長(zhǎng)度為16第二節(jié)動(dòng)態(tài)規(guī)劃求解方法練習(xí)利用逆序標(biāo)號(hào)法求最短路徑24377356684635343AB1B2B3C1C2C3D1D2E872第二節(jié)動(dòng)態(tài)規(guī)劃求解方法24377356684635343AB1B2B3C1C2C3D1D2E87204387614111315所以最短路徑為：A-B2-C1-D2-E最短路程為：15第二節(jié)動(dòng)態(tài)規(guī)劃求解方法利用逆序標(biāo)號(hào)法求最長(zhǎng)路徑24377356684635343AB1B2B3C1C2C3D1D2E872第二節(jié)動(dòng)態(tài)規(guī)劃求解方法24377356684635343AB1B2B3C1C2C3D1D2E87204398616131619所以最長(zhǎng)路徑為：A-B3-C2-D2-E最長(zhǎng)路程為19第二節(jié)動(dòng)態(tài)規(guī)劃求解方法順序遞推(前向法)

順序遞推是由過(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)+fk-1(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ì)本階段的階段效益值一般來(lái)說(shuō)，當(dāng)過(guò)程給定終點(diǎn)時(shí)，用順序遞推法比較方便，若一個(gè)多階段決策問(wèn)題，有一個(gè)固定的過(guò)程始點(diǎn)和一個(gè)固定的過(guò)程終點(diǎn)，則順序遞推和逆序遞推會(huì)得到相同的最優(yōu)結(jié)果第二節(jié)動(dòng)態(tài)規(guī)劃求解方法4311344461697812553AB1B2B3C1C2C3D1D2E第二節(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)]=4f1(B2)=min[d(B2,A)+f0(A)]=3f1(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í)，u1有三種取值。故有d2(C1,B1)+f1(B1)f2(c1)=min{d2(C1,B2)+f1(B2)}d2(C1,B3)+f1(B3)3+4=min{4+3}=71+11故C1到A的最佳路徑為C1-B1-A或C1-B2-A第二節(jié)動(dòng)態(tài)規(guī)劃求解方法同理當(dāng)x3=c2時(shí)，

f2(C2)=min{d2(c2,B2)+f1(B2)}=7即C2到A的最佳路徑為：C2-B2-A當(dāng)x3=C3時(shí)，d2(C3,B1)+f1(B1)f2(C3)=min{d2(c3,B2)+f1(B2)}=8即C3到A的最佳路徑為C3-B1-A第二節(jié)動(dòng)態(tài)規(guī)劃求解方法當(dāng)k=3時(shí)，f3(x4)=min{v3(x4,u3)+f2(x3)]因x4有D1，D2兩種狀態(tài)，最佳路徑D1-C2-B2-Ad3(D1,C1)+f2(C1)=9+7=16d3(D1,C2)+f2(C2)=8+7=15f3(D1)=min=15最佳路徑D2-C3-B1-Ad3(D2,C1)+f2(C1)=7+7=16d3(D2,C2)+f2(C2)=12+7=15d3(D3,C3)+f2(C3)=5+8=13f3(D2)=min=13第二節(jié)動(dòng)態(tài)規(guī)劃求解方法當(dāng)k=4時(shí)，f4(x5)=min[v4(x5,u4)+f3(x4)]因?yàn)閤5=E，只有一種狀態(tài)，u4有兩種選擇最短距離為f4(E)=16與逆序法的結(jié)果相同最佳路徑E-D2-C3-B1-Ad4(E,D1)+f3(D1)=5+15=20d4(E,D2)+f3(D2)=3+13=16f4(E)=min=16第二節(jié)動(dòng)態(tài)規(guī)劃求解方法用順序標(biāo)號(hào)法求最短路徑第二節(jié)動(dòng)態(tài)規(guī)劃求解方法4311344461697812553AB1B2B3C1C2C3D1D2E4311344461697812553AB1B2B3C1C2C3D1D2E04311778151316由上圖可知，最優(yōu)策略為：A-B1-C3-D2-E最短路長(zhǎng)度為16第二節(jié)動(dòng)態(tài)規(guī)劃求解方法練習(xí)利用順序標(biāo)號(hào)法求最短路徑24377356684635343AB1B2B3C1C2C3D1D2E872第二節(jié)動(dòng)態(tài)規(guī)劃求解方法24377356684635343AB1B2B3C1C2C3D1D2E87202437910111315所以最優(yōu)路徑為：A-B2-C1-D1-E最短路程為15第二節(jié)動(dòng)態(tài)規(guī)劃求解方法利用順序標(biāo)號(hào)法求最長(zhǎng)路徑第二節(jié)動(dòng)態(tài)規(guī)劃求解方法24377356684635343AB1B2B3C1C2C3D1D2E87224377356684635343AB1B2B3C1C2C3D1D2E872024391110141619所以最優(yōu)路徑為：A-B3-C2-D2-E最長(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)值，也就是說(shuō)，求出的不只是一個(gè)最優(yōu)解，而是一族最優(yōu)解。動(dòng)態(tài)規(guī)則方法是既把當(dāng)前的一段和未來(lái)的各段分開(kāi)，又把當(dāng)前效益和未來(lái)效益結(jié)合起來(lái)考慮的一種最優(yōu)化方法，因此每階段的選擇都是從全局來(lái)考慮的。第二節(jié)動(dòng)態(tài)規(guī)劃求解方法現(xiàn)要從A地出發(fā)，鋪設(shè)一條天然氣管道到F地，中間要經(jīng)過(guò)4站，每站都有幾條路可供選擇，并且已知各地間的距離(單位：百米)，如下圖所示，問(wèn)應(yīng)選擇哪條路徑使總的鋪設(shè)路徑最短？第二節(jié)動(dòng)態(tài)規(guī)劃求解方法由上圖可以得出最優(yōu)的決策路徑為：A-B4-C2-D5-E1-F最短的鋪設(shè)路徑為900米第二節(jié)動(dòng)態(tài)規(guī)劃求解方法現(xiàn)要從A地出發(fā)，鋪設(shè)一條天然氣管道到G地，中間要經(jīng)過(guò)5站，每站都有幾條路可供選擇，并且已知各地間的距離(單位：百米)，如下圖所示，問(wèn)應(yīng)選擇哪條路徑使總的鋪設(shè)路徑最短？第二節(jié)動(dòng)態(tài)規(guī)劃求解方法由上圖可以得出最優(yōu)的決策路徑為：A-B1-C2-D1-E2-F2-G最短的鋪設(shè)路徑為1800米第二節(jié)動(dòng)態(tài)規(guī)劃求解方法許多問(wèn)題用動(dòng)態(tài)規(guī)劃研究求解比線性規(guī)劃、非線性規(guī)劃更有效，特別是離散性問(wèn)題，很難用解析數(shù)學(xué)的方法，而用動(dòng)態(tài)規(guī)劃就迎刃而解了，但動(dòng)態(tài)規(guī)劃也存在如下不足：1．沒(méi)有統(tǒng)一的處理方法，求解時(shí)要根據(jù)問(wèn)題的性質(zhì)，結(jié)合多種數(shù)學(xué)技巧。因此，實(shí)踐經(jīng)驗(yàn)及創(chuàng)造性思維將起重要的引導(dǎo)作用。2．當(dāng)變量個(gè)數(shù)太多時(shí)，導(dǎo)致問(wèn)題無(wú)法解決。有些問(wèn)題由于涉及的函數(shù)沒(méi)有理想的性質(zhì)使問(wèn)題只能用動(dòng)態(tài)規(guī)劃描述，而不能用動(dòng)態(tài)規(guī)劃方法求解。第一節(jié)動(dòng)態(tài)規(guī)劃原理和模型例某運(yùn)輸公司有500輛運(yùn)輸卡車(chē)，在超負(fù)荷運(yùn)輸(即每天滿載行駛500km以上)情況下，年利潤(rùn)為25萬(wàn)元/輛，這時(shí)卡車(chē)的年損壞率為0.3，在低負(fù)荷運(yùn)輸(即每天行駛300KM以下)情況下，年利潤(rùn)為16萬(wàn)元/輛、年損壞率為0.1，現(xiàn)在要求制訂一個(gè)5年運(yùn)輸計(jì)劃，問(wèn)每年年初應(yīng)如何分配完好車(chē)輛在兩種不同負(fù)荷下運(yùn)輸?shù)目ㄜ?chē)數(shù)量，使在5年內(nèi)總利潤(rùn)最大？U低高低低低低高高高高年初第二年第三年第四年第五年第一節(jié)動(dòng)態(tài)規(guī)劃原理和模型首先將五年計(jì)劃，以時(shí)間為特征分為5個(gè)階段：k=1,2,3,4,5以狀態(tài)變量xk表示第k年初完好卡車(chē)的數(shù)據(jù)，同時(shí)也是第k-1年末的完好卡車(chē)的數(shù)量，用決策變量uk表示第k年度分配給超負(fù)荷運(yùn)輸?shù)目ㄜ?chē)數(shù)量，則分配給低負(fù)荷運(yùn)輸卡車(chē)的數(shù)量為xk-uk這里xk,uk均視作連續(xù)變量，它們的非整數(shù)值可以這樣理解：xk=0.6表示一輛卡車(chē)在第k年度中有60%的時(shí)間處在完好狀態(tài)；uk=0.7表示一輛卡車(chē)在第k年度中有70%時(shí)間在超負(fù)荷運(yùn)輸?shù)谝还?jié)動(dòng)態(tài)規(guī)劃原理和模型依題意xk+1=(1-0.3)uk+(1-0.1)(xk-uk)kk以vk(xk,uk)表示第k年度的階段效益(利潤(rùn))Vk(xk,uk)=25uk+16(xk-uk)=16xk+9uk以fk(xk)表示由第k年度初狀態(tài)(完好車(chē)輛數(shù))為xk，采用最優(yōu)策略時(shí)到第5年末這段時(shí)間內(nèi)所產(chǎn)生的最大利潤(rùn)值故基本方程：fk(xk)=max{vk(xk,uk)+fk+1(xk+1)}f6(x6)=0邊界條件：第6年度不計(jì)運(yùn)輸量其利潤(rùn)為0第一節(jié)動(dòng)態(tài)規(guī)劃原理和模型當(dāng)k=5時(shí)，f5(x5)=max{v5(x5,u5)+f6(x6)}0≤u5≤x5=max{16x5+9u5+0}0≤u5≤x5決策變量u5是指在第5年初分給超負(fù)荷運(yùn)輸?shù)目ㄜ?chē)數(shù)量，最大為x5(第5年度初完好的車(chē)輛數(shù))，最少為0，因此對(duì)f5=16x5+9u5求極值顯然為u5=x5時(shí)，達(dá)到極大點(diǎn)故有最優(yōu)決策：u5*=x5,f5(x5)=16x5+9u5*=25x5第一節(jié)動(dòng)態(tài)規(guī)劃原理和模型當(dāng)k=4時(shí)，f4(x4)=max{v4(x4,u4)+f5(x5)}0≤u4≤x4=max{16x4+9u4+25x5}0≤u4≤x4=max{16x4+9u444)}4+4u4}同理，只有當(dāng)u4=x4時(shí)，函數(shù)f44+4u4才能達(dá)到極值u4*=x4f4(x44第一節(jié)動(dòng)態(tài)規(guī)劃原理和模型當(dāng)k=3時(shí)，f3(x3)=max{v3(x3,u3)+f4(x4)}0≤u3≤x3=max{16x3+9u34}0≤u3≤x3=max{16x3+9u333)}33}同理，只有當(dāng)u3=x3時(shí)，函數(shù)f333才能達(dá)到極值u3*=x3f3(x33第一節(jié)動(dòng)態(tài)規(guī)劃原理和模型當(dāng)k=2時(shí)，f2(x2)=max{v2(x2,u2)+f3(x3)}0≤u2≤x2=max{16x2+9u23}0≤u2≤x2=max{16x2+9u222)}22}由圖可知，只有當(dāng)u2=0時(shí)，函數(shù)f222才能達(dá)到極值u2*=0f2(x22第一節(jié)動(dòng)態(tài)規(guī)劃原理和模型已知企業(yè)產(chǎn)品的生產(chǎn)費(fèi)用、存儲(chǔ)費(fèi)用和市場(chǎng)的需求量，在其生產(chǎn)能力和存儲(chǔ)能力許可的前提下，怎樣制定各個(gè)時(shí)期的生產(chǎn)計(jì)劃，既能完成交貨任務(wù)，又使總支出最小。決策變量xk表示第k年初更新，還是繼續(xù)使用舊設(shè)備，分別用R和K表示。第二節(jié)動(dòng)態(tài)規(guī)劃求解方法動(dòng)態(tài)規(guī)則方法是既把當(dāng)前的一段和未來(lái)的各段分開(kāi)，又把當(dāng)前效益和未來(lái)效益結(jié)合起來(lái)考慮的一種最優(yōu)化方法，因此每階段的選擇都是從全局來(lái)考慮的。而f2(B1)則表示從B1到E最短距離，本問(wèn)題所要求的目標(biāo)是距離之和的最小值，即f1(A)第一節(jié)動(dòng)態(tài)規(guī)劃原理和模型練習(xí)利用逆序標(biāo)號(hào)法求最短路徑在生產(chǎn)和經(jīng)營(yíng)活動(dòng)中，經(jīng)常遇到這樣的問(wèn)題，它們包含若干個(gè)相互聯(lián)系的階段，而且，在每一階段都要做出決策，一個(gè)階段的決策除影響該階段本身的效果之外，還影響到下一階段的起始狀態(tài)，從而影響到整個(gè)過(guò)程的效果最優(yōu)稱Pk,n(X)={uk(xk),uk+1(xk+1),….d2(C1,B1)+f1(B1)因此，整個(gè)系統(tǒng)正常工作的可靠性，可以用它的正常工作的概率來(lái)衡量?，F(xiàn)有一臺(tái)效益函數(shù)為r(t)的設(shè)備，其維修費(fèi)用為u(t)，更新費(fèi)用為c(t)，需要在n年內(nèi)的每年年初做出決策，是繼續(xù)使用舊設(shè)備還是更新一臺(tái)新設(shè)備，使n年總效益最大？建立狀態(tài)轉(zhuǎn)移方程sk+1=sk-wkxk決策變量第k階段內(nèi)的部件生產(chǎn)量，記為uk問(wèn)如何分配，才能使生產(chǎn)n種產(chǎn)品的總收入最大？。在第四階段，有兩個(gè)初始狀態(tài)：D1，D2，而全過(guò)程的最短路徑究竟是經(jīng)過(guò)D1，D2中哪一點(diǎn)，目前無(wú)法肯定，因此只能將各種可能都考慮，最小費(fèi)用路線為C1－D2－E相應(yīng)的最優(yōu)決策u3(C1)=D2當(dāng)k=1時(shí)，f1(x1)=max{v1(x1,u1)+f2(x2)}0≤u1≤x1=max{16x1+9u12}0≤u1≤x1=max{16x1+9u111)}11}同理，當(dāng)u1=0時(shí)，函數(shù)f1才能達(dá)到極值故u1*=0f1(x11因有x1=500故f1(x1)=f1P1,5(x1)={u1*,u2*,u3*,u4*,u5*}={0,0,x3,x4,x5}第一節(jié)動(dòng)態(tài)規(guī)劃原理和模型P1,5(x1)={u1*,u2*,u3*,u4*,u5*}={0,0,x3,x4,x5}x211*=0.9*500=450u2*=0x322*=0.9*450-0=405u3*=405X433*=0.9*405-0.2*405=283.5輛u4x544u5*=x5X655一般來(lái)說(shuō)，當(dāng)多階段決策問(wèn)題的始點(diǎn)給定時(shí)(本列x1=500)用逆序遞推法比較方便第一節(jié)動(dòng)態(tài)規(guī)劃原理和模型背包問(wèn)題：一位旅行者攜帶背包旅游，已知他的背包所能承受的重量為w千克，現(xiàn)有n種物品可供他選擇裝入包中，第i種物品的單件重量為wi千克，其價(jià)值是攜帶數(shù)量xi的函數(shù)pi(xi)。問(wèn)旅行者應(yīng)如何選擇攜帶物品的件數(shù)，使總價(jià)值最大？

劃分階段

將可裝入物品按排序，每階段裝一種物品，共劃分為n個(gè)階段，

狀態(tài)變量

表示在第k階段開(kāi)始時(shí)，背包中允許裝入前k種物品的總重量，記為sk

決策變量

裝入第k種物品的件數(shù)xk

建立狀態(tài)轉(zhuǎn)移方程

sk+1=sk-wkxk

允許決策集合

確定指標(biāo)函數(shù)

確定邊界條件

背包所能承受的重量為w千克第三節(jié)動(dòng)態(tài)規(guī)劃在經(jīng)濟(jì)和管理中的應(yīng)用生產(chǎn)計(jì)劃問(wèn)題已知企業(yè)產(chǎn)品的生產(chǎn)費(fèi)用、存儲(chǔ)費(fèi)用和市場(chǎng)的需求量，在其生產(chǎn)能力和存儲(chǔ)能力許可的前提下，怎樣制定各個(gè)時(shí)期的生產(chǎn)計(jì)劃，既能完成交貨任務(wù)，又使總支出最小。例某中轉(zhuǎn)倉(cāng)庫(kù)要按月在月初供應(yīng)一定數(shù)量的某種部件給總裝車(chē)間，由于生產(chǎn)條件的變化，生產(chǎn)車(chē)間在各月份中生產(chǎn)每單位這種部件所需耗費(fèi)的工時(shí)不同，各月份的生產(chǎn)量于當(dāng)月的月底前，全部要存入倉(cāng)庫(kù)以備后用。已知總裝車(chē)間的各個(gè)月份的需求量以及在加工車(chē)間生產(chǎn)該部件每單位數(shù)量所需工時(shí)，倉(cāng)庫(kù)容量H=9和開(kāi)始庫(kù)存量2，要求最終庫(kù)存量為0，要制定一個(gè)半年的逐月生產(chǎn)計(jì)劃，既滿足需要和倉(cāng)庫(kù)容量的限制，又使生產(chǎn)這種部件的總耗費(fèi)工時(shí)數(shù)最少。第三節(jié)動(dòng)態(tài)規(guī)劃在經(jīng)濟(jì)和管理中的應(yīng)用劃分階段

按月份劃分階段，每個(gè)月為一個(gè)階段，k=1,2,……,n.

狀態(tài)變量

第k階段開(kāi)始時(shí)（即本階段需求送出之前，上階段產(chǎn)品送入之后）部件庫(kù)存量，記為sk

決策變量

第k階段內(nèi)的部件生產(chǎn)量，記為uk

建立狀態(tài)轉(zhuǎn)移方程

sk+1=sk+uk-dk

最優(yōu)指標(biāo)函數(shù)

fk(sk)表示在第k階段開(kāi)始的庫(kù)存量為sk時(shí)，從第k階段到最后一階段生產(chǎn)部件的最小累計(jì)工時(shí)數(shù)。

基本方程

確定邊界條件

so=開(kāi)始庫(kù)存量，sn=0第三節(jié)動(dòng)態(tài)規(guī)劃在經(jīng)濟(jì)和管理中的應(yīng)用貨物存儲(chǔ)問(wèn)題考慮下面三個(gè)月的庫(kù)存問(wèn)題，在每月初，公司必須決定在本月內(nèi)，應(yīng)生產(chǎn)多少產(chǎn)品。在一個(gè)月內(nèi)生產(chǎn)x單位的產(chǎn)品，所需成本為c(x)，其中c(0)=0，當(dāng)x>0時(shí)，c(x)=3+2x。每月最多生產(chǎn)4個(gè)單位，每月的需求是隨機(jī)的，或?yàn)?或?yàn)?單位。如果生產(chǎn)的數(shù)量大于需求，就出現(xiàn)庫(kù)存。每個(gè)月末檢查庫(kù)存，1個(gè)單位的庫(kù)存費(fèi)用是1元。因?yàn)閹?kù)存能力有限，每月末的庫(kù)存量不能超過(guò)3單位。但同時(shí)要求必須及時(shí)滿足需求。在第3個(gè)月末要把現(xiàn)有的庫(kù)存以每單位2元的價(jià)格售出。在第1月的月初，公司有1單位的庫(kù)存。如何制定生產(chǎn)策略使三個(gè)月內(nèi)的期望費(fèi)用最小。第三節(jié)動(dòng)態(tài)規(guī)劃在經(jīng)濟(jì)和管理中的應(yīng)用

劃分階段

將三個(gè)月分為三個(gè)階段，每個(gè)月為一個(gè)階段

狀態(tài)變量

sk表示第k個(gè)月初的庫(kù)存數(shù)

決策變量

xk表示第k月生產(chǎn)的單位數(shù)

建立狀態(tài)轉(zhuǎn)移方程

，其中為一隨機(jī)需求量或?yàn)?或?yàn)?

最優(yōu)指標(biāo)函數(shù)

fk(sk)表示第k個(gè)月初的庫(kù)存是時(shí)，第k個(gè)月至第3個(gè)月內(nèi)的最小期望費(fèi)用。第三節(jié)動(dòng)態(tài)規(guī)劃在經(jīng)濟(jì)和管理中的應(yīng)用設(shè)備更新問(wèn)題在企業(yè)中，經(jīng)常遇到設(shè)備陳舊或部分損壞需要更新的問(wèn)題。從經(jīng)濟(jì)上分析，一種設(shè)備應(yīng)該使用多少年后進(jìn)行更新最合算。這就是要研究的問(wèn)題。一般來(lái)說(shuō)，一臺(tái)新設(shè)備出故障少，維護(hù)費(fèi)用低，帶來(lái)的經(jīng)濟(jì)效益就高；隨著使用年限的增加，新設(shè)備逐漸變舊，維護(hù)費(fèi)用增加，效用降低。在適當(dāng)?shù)臅r(shí)候，就要賣(mài)掉舊設(shè)備，購(gòu)買(mǎi)新設(shè)備。當(dāng)然，設(shè)備越舊越不值錢(qián)，購(gòu)買(mǎi)新設(shè)備又需要一定數(shù)額的購(gòu)買(mǎi)費(fèi)，這就是設(shè)備的更新決策問(wèn)題?，F(xiàn)有一臺(tái)效益函數(shù)為r(t)的設(shè)備，其維修費(fèi)用為u(t)，更新費(fèi)用為c(t)，需要在n年內(nèi)的每年年初做出決策，是繼續(xù)使用舊設(shè)備還是更新一臺(tái)新設(shè)備，使n年總效益最大？第三節(jié)動(dòng)態(tài)規(guī)劃在經(jīng)濟(jì)和管理中的應(yīng)用

rk(t)：在第k年設(shè)備已使用過(guò)t年，再使用1年的效益

uk(t)：在第k年設(shè)備已使用過(guò)t年，再使用1年的維修費(fèi)用

ck(t)：在第k年賣(mài)掉一臺(tái)已使用過(guò)t年的設(shè)備，買(mǎi)進(jìn)一臺(tái)新設(shè)備的更新費(fèi)用

a：折扣因子，表示一年以后的單位收入價(jià)值相當(dāng)于現(xiàn)在的a單位

fk(t)：已使用了t年的舊設(shè)備，從第k年開(kāi)始在以后繼續(xù)使用到規(guī)定的第n年未知幾年內(nèi)的總回收額