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

運(yùn)籌帷幄之中決勝千里之外第七章動態(tài)規(guī)劃運(yùn)籌學(xué)教學(xué)要求：了解動態(tài)規(guī)劃的基本思想掌握一維離散動態(tài)規(guī)劃的建模和求解方法應(yīng)用會運(yùn)用動態(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)計劃。動態(tài)規(guī)則是將一個較復(fù)雜的多階段決策問題分解為若干相互關(guān)聯(lián)的較容易求解的子(單）決策問題。而每一個子決策問題都有多種選擇

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

順序遞推是由過程的始點(diǎn)向終點(diǎn)逐段遞推，其階段變量的設(shè)置與狀態(tài)變量的設(shè)置次序與逆序法相同，而最優(yōu)值函數(shù)fk(xk+1)表示第k階段末的結(jié)束狀態(tài)為xk+1時，從第1階段到第k階段所得到的最大收益，因此順序遞推是相對始點(diǎn)而言的收益，故一般選擇第k階段末(即第k+1階段初的狀態(tài))作為第k階段的狀態(tài)變量第二節(jié)動態(tài)規(guī)劃求解方法動態(tài)規(guī)劃用順序遞推(前向法)時的基本方程如下：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時，相對于始點(diǎn)的最優(yōu)指標(biāo)函數(shù)值而vk(xk+1,uk)表示第k階段狀態(tài)為xk+1取決策為uk時對本階段的階段效益值一般來說，當(dāng)過程給定終點(diǎn)時，用順序遞推法比較方便，若一個多階段決策問題，有一個固定的過程始點(diǎn)和一個固定的過程終點(diǎn)，則順序遞推和逆序遞推會得到相同的最優(yōu)結(jié)果第二節(jié)動態(tài)規(guī)劃求解方法4311344461697812553AB1B2B3C1C2C3D1D2E第二節(jié)動態(tài)規(guī)劃求解方法用順序遞推法求例1當(dāng)k=1時，由基本方程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é)動態(tài)規(guī)劃求解方法當(dāng)k=2時，f2(x3)=min[v2(x3,u2)+f1(x2)]當(dāng)x3=C1時，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é)動態(tài)規(guī)劃求解方法同理當(dāng)x3=c2時，

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

劃分階段

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

狀態(tài)變量

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

決策變量

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

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

sk+1=sk-wkxk

允許決策集合

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

確定邊界條件

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

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

狀態(tài)變量

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

決策變量

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

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

sk+1=sk+uk-dk

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

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

基本方程

確定邊界條件

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

劃分階段

將三個月分為三個階段，每個月為一個階段

狀態(tài)變量

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

決策變量

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

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

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

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

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

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

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

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

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

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