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