【正文】 變量sk+1的值也就隨之確定，從而 sk+1的值隨 sk和 uk的值變化而變化，記為sk+1=Tk(sk, uk)，稱為狀態(tài)轉(zhuǎn)移方程。 動(dòng)態(tài)規(guī)劃的最優(yōu)性原理 ? 利用最優(yōu)性原理，可以把多階段決策問題的求解過程看成是一個(gè)連續(xù)的遞推過程，由后向前逐步推算（因條件不同，也可能由前向后推算）。 ? 上述遞推關(guān)系式即為極小化的泛函方程，且指標(biāo)函數(shù)為和的形式，當(dāng)其中的加號(hào)改為乘號(hào)時(shí)，即轉(zhuǎn)化為積的形式。 ?設(shè)有 N個(gè)點(diǎn)，以 1, 2, …, N 記之，任兩點(diǎn) i, j之間的長度為 Cij, 當(dāng) i, j間有一弧直接連接時(shí)， 0≤Cij+∞, 當(dāng) i, j間不直接連接它們的弧時(shí)， Cij=+∞. 今設(shè) N為終點(diǎn)，求任一點(diǎn) i至終點(diǎn) N的最短距離。 函數(shù)空間迭代法求解步驟如下： 1176。直到 fk(i) = fk+1(i) = …=f(i) 為止， i=1,2,…,N 函數(shù)空間迭代法 ?可以證明： (1)由上述步驟確定的函數(shù)序列 {fk(i)} 不超過 N1步單調(diào)下降收斂于問題的最優(yōu)函數(shù) f(i) (2)若 0≤Cij+∞（ i,j=1,2,…,N ） ,則收斂步驟 P有下列估計(jì)： 12lg )1lg(2lg )1lg( ????? NPN 策略空間迭代法 ?策略空間的迭代就是先給出初始策略{u1(i)}，然后按某種方式求得新策略{u2(i)}, {u3(i)},… ，直至最終求出最優(yōu)策略。在此策略下作方程組 fk(i) = Ci, uk(i) + fk[uk(i)], i=1,2,…,N 1 fk(N)=0 求解 fk(i)，這里 Ci, uk(i)為已知值 3176。 , 3176。 ③ 2 6 3 ① 1 2 3 ⑤ 3 4 5 ② ④ 2 函數(shù)空間與策略空間迭代法 [解 ]先用函數(shù)空間迭代法求解。 ,4176。 5動(dòng)態(tài)規(guī)劃的解法及應(yīng)用舉例 ? 一維資源分配問題 例 1用逆推法解 max z=x1x22x3 x1+x2+x3=C (C0) xi≥0, i=1,2,3 動(dòng)態(tài)規(guī)劃的解法及應(yīng)用舉例 ?例 2用動(dòng)態(tài)規(guī)劃解下列問題（ P332） max z=8x1 + 7x2 2x1 + x2≤8 5x1 + 2x2≤15 x1, x2為非負(fù)整數(shù) 動(dòng)態(tài)規(guī)劃的解法及應(yīng)用舉例 ? [解 ]用逆序解法，將問題分為兩個(gè)階段，對應(yīng) ? 狀態(tài)變量： vj, wj分別為第 j階段，第一、第二約束可供分配的右端數(shù)值 ? 決策變量： x1,x2，于是 ? f2*(v2,w2)=max{7x2}=7min{[v2], [w2/2]} 0≤x2≤v2 0 ≤2x2 ≤w2 x2取整數(shù) ? f1*(v1,w1)=max{8x1+ f2*(v12x1,w15x1)} 0≤2x1≤v1 0 ≤5x1 ≤w1 x1取整數(shù) ? 而 v1=8, w1=15,所以 動(dòng)態(tài)規(guī)劃的解法及應(yīng)用舉例 ? f1*(8,15)=max{8x1+ 7min([82x1],[(155x1)/2])} 0≤2x1≤8 0 ≤5x1 ≤15 x1取整數(shù) ? 由于 x1 ≤min([8/2],[15/5])=3, 因而 ? f1*(8,15)=max{8x1+ 7min([82x1],[(155x1)/2])} x1=0,1,2,3 =max{8x1+ 7[(155x1)/2]}=49 x1=0,1,2,3 ? x1*=0 ? 由 v2=v12x1=8, w2=w15x1=15, 得 ? x2*= min{[8], [15/2]}=7 ? ∴ 最優(yōu)解為 x1*=0, x2*= 7, z*=49 動(dòng)態(tài)規(guī)劃的解法及應(yīng)用舉例 ? 167。 1中的例 2，將資源分配劃分為三個(gè)階段，分配給生產(chǎn)產(chǎn)品 A， B，C的數(shù)量設(shè)為 x1,x2,x3，其狀態(tài) (資源剩余量 )s1=4, s2=s1x1, s3=s2x2, sn+1=s4=0. ?現(xiàn)列表計(jì)算如下： 動(dòng)態(tài)規(guī)劃的解法及應(yīng)用舉例 ?由上述表知，最大總收益等于 35，最優(yōu)決策序列是 ?x1*=1, x2*=2, x3*=1 動(dòng)態(tài)規(guī)劃的解法及應(yīng)用舉例 ? 例 3 資源連續(xù)分配問題： ? 設(shè)有數(shù)量為 s1的某種資源，可投入生產(chǎn) A和 B兩種產(chǎn)品，第一年若以數(shù)量 u1投入生產(chǎn) A，剩下的s1u1投入生產(chǎn) B，其收入為 g(u1)+h(s1u1)，這里g(0)=h(0)=0，在 A、 B生產(chǎn)后，資源的回收率分別為 0a1, 0b1, 則在第一年生產(chǎn)后，回收的資源量合計(jì)為 s2=au1+b(s1u1)。 ? 狀態(tài)轉(zhuǎn)移方程為 sk+1=auk+b(skuk) ? 最優(yōu)值函數(shù) fk(sk)表示當(dāng)資源量為 sk時(shí)，從第k階段至第 n階段采取最優(yōu)分配方案進(jìn)行生產(chǎn)后所得到的最大總收入。 ?當(dāng) g(u), h(u)為凸函數(shù)，且 h(0)=g(0)=0時(shí)，可以證明：在每個(gè)階段上 u(i)的最優(yōu)決策總是取其上限或下限，因此，對于解的結(jié)構(gòu)來說，它與 g(u), h(u)是線性情況是類似的。 狀態(tài)轉(zhuǎn)移方程： Xk+1=Xkxk Yk+1=Ykyk 動(dòng)態(tài)規(guī)劃的解法及應(yīng)用舉例 ? 允許決策集合： Dk(Xk,Yk)={(xk,yk)|0≤xk≤Xk,0≤yk≤Yk} ? 令 fk(Xk,Yk)表示當(dāng)狀態(tài)為 (Xk,Yk)時(shí)分別用于第 k種生產(chǎn)到 n種生產(chǎn)所得到的最大收入，則由最優(yōu)性原理，得： fn(Xn,Yn)=g(Xn,Yn) fk(Xk,Yk)=max {gk(xk,yk) + fk+1(Xkxk, Ykyk)}, k=n1,…,2,1 0≤xk≤Xk 0≤yk≤Yk 動(dòng)態(tài)規(guī)劃的解法及應(yīng)用舉例 ?由此遞推關(guān)系式可求得 f1(a,b)，即為所求問題的最大收入。 動(dòng)態(tài)規(guī)劃的解法及應(yīng)用舉例 ? 令 hi(xi)=hi(xi,λ) = max[gi(xi,yi) –λyi] yi≥0 于是問題變?yōu)? max[h1(x1)+h1(x1)+…+h n(xn)] 滿足條件 x1+x2+…+x n=a xi≥0, i=1,2,…,n )0),(lim,( ??? iiiiy yyxgi可設(shè)為了使此式有意義 動(dòng)態(tài)規(guī)劃的解法及應(yīng)用舉例 ?這是一個(gè)一維分配問題，可用對一維的方法求解，這里由于 λ是參數(shù)，因此，最優(yōu)解 xi*是參數(shù) λ的函數(shù)，相應(yīng)的 yi*也是 λ的函數(shù)，即 xi=xi*(λ), yi=yi*(λ)為其解。 ?設(shè)有 n個(gè)工件需要在機(jī)床 A、 B上加工，每個(gè)工件都必須經(jīng)過先 A而后 B的兩道加工工序，工件 i(1≤i≤n)在 A、 B上的加工時(shí)間分別設(shè)為 ai, bi, 問應(yīng)如何在兩機(jī)床上安排各工件的加工順序，使在機(jī)床 A上加工第一個(gè)工件開始到在機(jī)床 B上將最后一個(gè)工件加工完為止，所用的加工時(shí)間最少？ 排序問題 ?當(dāng)機(jī)床 B上的加工順序與機(jī)床 A不同時(shí)，意味著在 A上加工完畢的某些工件不能在 B上立即加工，而需等到另一個(gè)或一些工件加工完畢之后才能加工，這樣使機(jī)床 B的等待加工時(shí)間加長，從而使總的加工時(shí)間加長了。 排序問題 ? X：表示在 A上等待加工的按取定順序排列。因此，只考慮在 A、B上具有相同的加工順序 。 ?? ?n i by1 * )(???nii by1* )(????ni iby1* )(? 動(dòng)態(tài)規(guī)劃的解法及應(yīng)用舉例 ?(2)逐次逼近法 ?這是另一種降維方法，先保持一個(gè)變量不變，對另一個(gè)變量實(shí)現(xiàn)最優(yōu)化，然后交替地固定變量，以迭代的形式反復(fù)進(jìn)行，直到獲得某種要求為止。為了能使計(jì)算可行，可以采用拉長計(jì)算時(shí)間減少存儲(chǔ)量的辦法來實(shí)現(xiàn)，以求得它的解或近似解。 設(shè)狀態(tài)變量為 (Xk,Yk), Xk,Yk分別表示分配用于第 k種生產(chǎn)至 n種生產(chǎn)的兩種物資的數(shù)量 (資源剩余量 )。 動(dòng)態(tài)規(guī)劃的解法及應(yīng)用舉例 ? 下面以簡單的例子 n=3, a=, b=, g(y)=, h(y)=的步驟。 ? 設(shè) sk為狀態(tài)變量，表示在第 k階段（第 k年）可投入 A、 B兩種生產(chǎn)的資源量。將不同數(shù)量的這種原料分配給各種產(chǎn)品時(shí)產(chǎn)生收益如下表（單位：萬元），試確定使總收益最大的分配法。 函數(shù)空間與策略空間迭代法 ?注意：在求解這類問題中，若網(wǎng)絡(luò)中出現(xiàn)負(fù)權(quán)邊，由于有可能出現(xiàn)負(fù)圈，故上述方法不太適用。 先選取一不構(gòu)成回路的初始策略 {u1(i)}： u1(1)=3， u1(2)=3， u1(3)=5， u1(4)=5 然后根據(jù)策略空間迭代法步驟中的 2176。 策略空間迭代法 ?可以證明：若初始策略 {u1(i)}不構(gòu)成回路，則以后迭代所得的策略 {uk(i)}也不構(gòu)成回路（即解是唯一的），且{fk(i)}一致收斂于泛函方程的解。令 k=k+1 4176。選一無回路的初始策略 {u1(i), i=1,2,…,N 1}, u1(i)表示在此策略下由 i點(diǎn)到達(dá)的下一個(gè)點(diǎn)。 fk(i) = min(Cij + fk1(j)), i=1,2,…,N 1 j fk(N)=0 3176。 下面用兩種迭代法來求解。 167。 ? 為了利用最優(yōu)性原理求解多階段決策問題，還要導(dǎo)出一些遞推公式，便于運(yùn)算。 3最優(yōu)性原理和泛函方程 ? 一、動(dòng)態(tài)規(guī)劃的最優(yōu)性原理 20世紀(jì) 50年代， 類多階段決策問題，提出了最優(yōu)性原理。 動(dòng)態(tài)規(guī)劃的基本概念 ?(4)策略 (Policy) ?策略是一個(gè)按順序排列的決策序列，用 pk,n(sk)={uk(sk), uk+1(sk+1), … u n(sn)} 表示從第 k階段 sk狀態(tài)開始到終止的決策序列，稱為 k子過程策略；當(dāng) k=1時(shí)，即為全過程的一個(gè)策略，簡稱策略。 動(dòng)態(tài)規(guī)劃的基本概念 ? (3)決策 (Decision) ? 決策表示當(dāng)過程處于某一階段的某個(gè)狀態(tài)時(shí)，可以作出不同的決定（或選擇），從而確定下一階段的狀態(tài)，這種決定稱為決策。描述階段的變量稱為階段變量，用 k表示。 原料的分配量 產(chǎn)品種類 （噸） A B C 0 0 0 0 1 10 6 8 2 17 17 11 3 20 18 167。在多階段決策問題中，既然引入了階段的概念，也就與時(shí)間密不可分，決策過程從一個(gè)狀態(tài)到另一個(gè)狀態(tài)，隨著時(shí)間的變化在變化，也就有了“動(dòng)態(tài)”的含義。 1多階段決策問題及實(shí)例 ? 所謂多階段決策問題，是指一類活動(dòng)過程，它可以分為互相聯(lián)系的若干個(gè)階段，在每一階段都需要作出決策，從而使整個(gè)過程達(dá)到最優(yōu)的活動(dòng)效果。然而動(dòng)態(tài)規(guī)劃目前還存在以下弱點(diǎn)： 1）動(dòng)態(tài)規(guī)劃沒有一個(gè)統(tǒng)一的算法，它必須針對各種問題的性質(zhì)，利用最優(yōu)性原理