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