【正文】 =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ī)劃的解法及應(yīng)用舉例 ? 167。 1例 2 多階段資源分配問題 ? 某工廠生產(chǎn) A, B和 C三種產(chǎn)品，都要使用某種原材料，原材料共有 4噸。將不同數(shù)量的這種原料分配給各種產(chǎn)品時產(chǎn)生收益如下表（單位：萬元），試確定使總收益最大的分配法。 原料分配量 產(chǎn)品種類 （噸） A B C 0 0 0 0 1 10 6 8 2 17 17 11 3 20 18 動態(tài)規(guī)劃的解法及應(yīng)用舉例 ?下面求167。 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ī)劃的解法及應(yīng)用舉例 ?由上述表知，最大總收益等于 35，最優(yōu)決策序列是 ?x1*=1, x2*=2, x3*=1 動態(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)后，回收的資源量合計為 s2=au1+b(s1u1)。 第二年將資源數(shù)量 s2中的 u2和 s2u2分別投入生產(chǎn) A和 B，又得到收入為 g(u2)+h(s2u2)，如此繼續(xù)進行 n年，問如何決定每年投入 A生產(chǎn)的資源量，才能使總的收入最大？ 動態(tài)規(guī)劃的解法及應(yīng)用舉例 ? 此問題等價于下列規(guī)劃問題： max Z=g(u1)+h(s1u1)+g(u2)+h(s2u2)+…+ g(u n) + h(snun) s2=au1+b(s1u1) s3=au2+b(s2u2) ……………… sn=aun1+b(sn1un1) 0≤ui≤si, i=1,2,…,n 動態(tài)規(guī)劃的解法及應(yīng)用舉例 ? 下面用動態(tài)規(guī)劃的方法來處理。 ? 設(shè) sk為狀態(tài)變量，表示在第 k階段（第 k年）可投入 A、 B兩種生產(chǎn)的資源量。 ? uk為決策變量，它表示在第 k階段用于 A生產(chǎn)的資源量，則 skuk表示用于 B生產(chǎn)的資源量。 ? 狀態(tài)轉(zhuǎn)移方程為 sk+1=auk+b(skuk) ? 最優(yōu)值函數(shù) fk(sk)表示當資源量為 sk時，從第k階段至第 n階段采取最優(yōu)分配方案進行生產(chǎn)后所得到的最大總收入。 動態(tài)規(guī)劃的解法及應(yīng)用舉例 ? 因此可寫出動態(tài)規(guī)劃的遞推關(guān)系式為： fn(sn)=max {g(un) + h(snun)} 0≤un≤sn fk(sk)=max {g(uk) + h(skuk) + fk+1(auk+b(skuk))}, 0≤uk≤sk k=n1,…,2,1 ? 最后求出 f1(s1)即為所求問題的最大總收入。 動態(tài)規(guī)劃的解法及應(yīng)用舉例 ? 下面以簡單的例子 n=3, a=, b=, g(y)=, h(y)=的步驟。 先計算 f3(s3),得 f3(s3)=max { + (s3u3)} 0≤u3≤s3 = max { + }= 0≤u3≤s3 u3*=s3 動態(tài)規(guī)劃的解法及應(yīng)用舉例 ? 而 f2(s2)=max {g(u2) + h(s2u2) + f3(au2+b(s2u2))} 0≤u2≤s2 = max { + }= 0≤u2≤s2 u2*=s2 f1(s1)=max {g(u1) + h(s1u1) + f2(au1+b(s1u1))} 0≤u1≤s1 = max { }= 0≤u1≤s1 u1*=0 動態(tài)規(guī)劃的解法及應(yīng)用舉例 上述結(jié)果可列表如下： 實際階段 投入 A的量 投入 B的量 收入 剩余量 1 0 s1 2 s1 0 3 0 總收入 動態(tài)規(guī)劃的解法及應(yīng)用舉例 ?上面的例子較簡單，但當 n很大時，且g(u), h(u)是復(fù)雜函數(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ī)劃的解法及應(yīng)用舉例 ? 二維 (兩種 )資源分配問題 ?設(shè)有兩種資源數(shù)量各為 a和 b，需要分配于 n種生產(chǎn)，若第一種物資以數(shù)量 xi，第二種以數(shù)量 yi投入第 i種生產(chǎn)時，得到的收益為 gi(xi,yi)，問應(yīng)如何分配這兩種物資于 n種生產(chǎn)使總收入最大？ 動態(tài)規(guī)劃的解法及應(yīng)用舉例 ?這個問題可化為下述數(shù)學(xué)規(guī)劃問題： max Z=g1(x1,y1)+g2(x2,y2)+…+g n(xn,yn) x1+x2+…+x n=a y1+y2+…+y n=b xi≥0, yi≥0 i=1,2,…,n 動態(tài)規(guī)劃的解法及應(yīng)用舉例 ? 用動態(tài)規(guī)劃的方法求解。 設(shè)狀態(tài)變量為 (Xk,Yk), Xk,Yk分別表示分配用于第 k種生產(chǎn)至 n種生產(chǎn)的兩種物資的數(shù)量 (資源剩余量 )。 決策變量為 (xk,yk), xk,yk分別表示分配用于第 k種生產(chǎn)的兩種物資的數(shù)量。 狀態(tài)轉(zhuǎn)移方程： Xk+1=Xkxk Yk+1=Ykyk 動態(tài)規(guī)劃的解法及應(yīng)用舉例 ? 允許決策集合： 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ī)劃的解法及應(yīng)用舉例 ?由此遞推關(guān)系式可求得 f1(a,b)，即為所求問題的最大收入。由于狀態(tài)變量為二維情形，其計算量比一般問題成平方增長，其計算量和記憶容量都顯著增加。為了能使計算可行，可以采用拉長計算時間減少存儲量的辦法來實現(xiàn)，以求得它的解或近似解。 動態(tài)規(guī)劃的解法及應(yīng)用舉例 ? (1)Lagrange乘子法 引入 Lagrange乘子 λ，將上述問題化為 max{g1(x1,y1) +g2(x2,y2) +…+g n(xn,yn) –λ(y1+y2+…+y n)} 滿足條件 x1+x2+…+x n=a xi≥0, yi≥0 i=1,2,…,n 其中 λ作為一個固定的參數(shù)。 動態(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è)為了使此式有意義 動態(tài)規(guī)劃的解法及應(yīng)用舉例 ?這是一個一維分配問題，可用對一維的方法求解，這里由于 λ是參數(shù)，因此，最優(yōu)解 xi*是參數(shù) λ的函數(shù)，相應(yīng)的 yi*也是 λ的函數(shù)，即 xi=xi*(λ), yi=yi*(λ)為其解。如果 ，則可證明 {xi*, yi*}為原問題的最優(yōu)解；如果 ，可調(diào)整 λ的值 (利用插值法逐漸確定 λ)，直到滿足 為止。 ?? ?n i by1 * )(???nii by1* )(????ni iby1* )(? 動態(tài)規(guī)劃的解法及應(yīng)用舉例 ?(2)逐次逼近法 ?這是另一種降維方法，先保持一個變量不變，對另一個變量實現(xiàn)最優(yōu)化，然后交替地固定變量，以迭代的形式反復(fù)進行，直到獲得某種要求為止。 逐次逼近法 ? 先設(shè) x(0)={x1(0), x2(0),…,x n(0)}為滿足x1(0)+x2(0)+…+x n(0)=a的一個可行解，固定 x在 x(0)，求 max{g1(x1(0),y1) +g2(x2(0),y2) +…+g n(xn(0),yn)} 滿足條件 y1+y2+…+y n=b yi≥0 i=1,2,…,n 的解，設(shè)這個解為 y(0)={y1(0), y2(0),…,y n(0)} 逐次逼近法 ?然后再固定 y為 y(0), 求 max{g1(x1,y1(0)) +g2(x2,y2(0)) +…+g n(xn,yn(0))} 滿足條件 x1+x2+…+x n=a xi≥0 i=1,2,…,n 的解，設(shè)其解為 x(1)={x1(1), x2(1),…,x n(1)}， 逐次逼近法 ?再固定 x為 x(1),對 y求解，這樣依次輪換下去得到一系列的解 {x(k)},{y(k)}，(k=0,1,2,…), 顯然，函數(shù)值 g1(x1(k),y1(k)) +g2(x2(k),y2(k)) +…+g n(xn(k),yn(k))是單調(diào)上升的，通常它收斂到一個局部最優(yōu)解，因此，在實際計算中，可選擇幾個初始點 x(0)進行計算，從中選出一個最好的解作為近似最優(yōu)解。 ?設(shè)有 n個工件需要在機床 A、 B上加工，每個工件都必須經(jīng)過先 A而后 B的兩道加工工序，工件 i(1≤i≤n)在 A、 B上的加工時間分別設(shè)為 ai, bi, 問應(yīng)如何在兩機床上安排各工件的加工順序，使在機床 A上加工第一個工件開始到在機床 B上將最后一個工件加工完為止，所用的加工時間最少？ 排序問題 ?當機床 B上的加工順序與機床 A不同時，意味著在 A上加工完畢的某些工件不能在 B上立即加工，而需等到另一個或一些工件加工完畢之后才能加工，這樣使機床 B的等待加工時間加長，從而使總的加工時間加長了?？梢宰C明： 最優(yōu)加工順序可以在 A、 B上加工順序相同時實現(xiàn)。因此，只考慮在 A、B上具有相同的加工順序 。 排序問題 ?當加工順序取定之后，工件在 A上加工時沒有等待時間，而在 B上常常等待，且第 i個工件在 A上加工完畢以后，在 B上要經(jīng)過若干時間才能加工完，因此對同一個工件來說，在 A、 B上總是出現(xiàn)加工完畢的時間差。 排序問題 ? X：表示在 A上等待加工的按取定順序