1、第6章 動(dòng)態(tài)規(guī)劃應(yīng)用舉例,第1節(jié) 資源分配問(wèn)題,1.1 一維資源分配問(wèn)題,資源分配問(wèn)題可描述如下：設(shè)有某種原料，總數(shù)量為a，分配給n個(gè)使用者。已知第i個(gè)使用者得到數(shù)量xi的該種資源，可創(chuàng)造的收益為gi(xi)。問(wèn)應(yīng)如何分配該資源，才能使總收益最大。,用動(dòng)態(tài)規(guī)劃法處理這種問(wèn)題時(shí)，通常把給一個(gè)使用者分配資源的過(guò)程看成一個(gè)階段，按使用者分成先后的n個(gè)階段。即先給第1個(gè)使用者分配資源，為第一階段；再給第2個(gè)使用者分配，為第二階段；依此類(lèi)推，最后給第n個(gè)使用者分配，為第n階段。,按使用者劃分為n個(gè)階段，k=1,2,.,n； 取第k階段初（給第k個(gè)使用者分配資源時(shí)）資源的剩余量sk為狀態(tài)變量，s1=a；

2、取分配給第k個(gè)使用者的資源數(shù)量xk為決策變量，0 xksk (k=1,2,n-1)， xn= sn； 狀態(tài)轉(zhuǎn)移方程為sk+1=sk-xk； 指標(biāo)函數(shù)為Vk,n=gj(xj)； 基本方程為：,由于資源數(shù)量常常要求取整數(shù)，則狀態(tài)變量和決策變量也就取整數(shù)，所以求解時(shí)常采用列表的形式。,例2 某工業(yè)部門(mén)根據(jù)國(guó)家計(jì)劃安排，擬將五臺(tái)某種高效率的機(jī)器分配給所屬的甲、乙、丙三個(gè)工廠，各工廠得到不同數(shù)量的機(jī)器可獲得的收益如下表。問(wèn)應(yīng)如何分配機(jī)器，才能使各廠的總效益最大。,解：,分成3個(gè)階段，k=1,2,3；,sk為狀態(tài)變量，s1=5；,xk為決策變量，0 xksk，x3=s3；,狀態(tài)轉(zhuǎn)移方程sk+1= sk-x

3、k ；,當(dāng)k=3時(shí)：,當(dāng)k=2時(shí)：,當(dāng)k=1時(shí)：,總效益最大為21萬(wàn)元，分配方案為：,(1)甲0臺(tái), 乙2臺(tái), 丙3臺(tái)；(2)甲2臺(tái), 乙2臺(tái), 丙1臺(tái)。,1.2 二維資源分配問(wèn)題,二維資源分配問(wèn)題可描述如下：設(shè)有兩種原料，數(shù)量各為a和b，分配給n個(gè)使用者。已知第i個(gè)使用者得到兩種資源的數(shù)量各為xi和yi時(shí)，可創(chuàng)造的收益為gi(xi, yi)。問(wèn)應(yīng)如何分配該資源，才能使總收益最大。,與一維資源分配問(wèn)題類(lèi)似，把給一個(gè)使用者分配資源的過(guò)程看成一個(gè)階段，可按使用者分成先后的n個(gè)階段。由于要分配兩種資源，所以狀態(tài)變量要有兩個(gè)，決策變量也要有兩個(gè)。,按使用者劃分為n個(gè)階段，k=1,2,.,n； 取第k階

4、段初（給第k個(gè)使用者分配資源時(shí)）兩種資源各自的剩余量sk和tk為狀態(tài)變量, s1=a, t1=b； 取分配給第k個(gè)使用者兩種資源的數(shù)量xk和yk為決策變量，0 xksk, 0 xksk (k=1,n-1), xn= sn, yn= tn； 狀態(tài)轉(zhuǎn)移方程為：sk+1=sk-xk，tk+1=tk-yk； 指標(biāo)函數(shù)為Vk,n=gj(xj,yj) ； 基本方程為：,雖然建模過(guò)程和一維資源分配問(wèn)題沒(méi)多大區(qū)別，但求解模型卻極為困難。為此，需進(jìn)行簡(jiǎn)化處理。,1. 拉格朗日乘數(shù)法,引入拉格朗日乘數(shù)，將二維問(wèn)題化為,這是一個(gè)一維分配問(wèn)題。取定為某一值，求解得 xi*=xi() ， yi*=yi(xi(), )=

5、yi(),可證，若yi()=b，則對(duì)應(yīng)的xi*, yi*就是原問(wèn)題的最優(yōu)解。否則，就用插值法調(diào)整的值，漸進(jìn)地使yi()=b得到滿(mǎn)足。,2. 逐次逼近法,逐次逼近法的做法是，先保持一個(gè)變量不變，對(duì)另一個(gè)變量求最優(yōu)，然后交替地固定，以迭代的形式反復(fù)進(jìn)行，直到滿(mǎn)足某種要求為止。,先設(shè)x(0)=x1(0), x2(0), xn(0)為滿(mǎn)足xi(0)=a的一個(gè)可行解，固定x在x(0)，對(duì)y求解，則變?yōu)橐痪S問(wèn)題,用一維方法解得y(0)=y1(0), y2(0), yn(0)，再固定y在y(0)，對(duì)x求解一維問(wèn)題,解得x(1)=x1(1), x2(1), xn(1)，再固定x在x(1)，對(duì)y求解一維問(wèn)題。依

6、次輪換下去，得解序列x(k)、 y(k)。,由于gi(xi(0),yi(0)gi(xi(1),yi(0)gi(xi(1),yi(1)，故函數(shù)值序列g(shù)i(xi(k),yi(k)是單調(diào)上升的，但不一定收斂到整體的最優(yōu)解，一般只能收斂到某一局部最優(yōu)解。因此，在實(shí)際計(jì)算時(shí)，可選擇幾個(gè)初始點(diǎn)xi(0)進(jìn)行計(jì)算，然后從幾個(gè)局部最優(yōu)解中選出一個(gè)最好的。,3. 粗格子點(diǎn)法 （疏密法）,先將0 xa, 0yb分成網(wǎng)格，然后在格子點(diǎn)上進(jìn)行計(jì)算。為了使計(jì)算可行，可先用少數(shù)格子點(diǎn)進(jìn)行粗糙計(jì)算，在求出相應(yīng)最優(yōu)解后，再在最優(yōu)解附近的小范圍內(nèi)進(jìn)一步細(xì)分，求出在細(xì)分格子點(diǎn)上的最優(yōu)解。繼續(xù)細(xì)分下去，直至滿(mǎn)足要求為止。,第2節(jié)

7、生產(chǎn)與存儲(chǔ)問(wèn)題,2.1 生產(chǎn)計(jì)劃問(wèn)題,設(shè)某公司對(duì)某種產(chǎn)品要制定n個(gè)階段的生產(chǎn)計(jì)劃。已知它的初始庫(kù)存為0，每階段生產(chǎn)產(chǎn)品數(shù)量的上限為m；第k階段，對(duì)該產(chǎn)品的需求量為dk，生產(chǎn)產(chǎn)品量為xk時(shí)的生產(chǎn)費(fèi)用為ck(xk)，開(kāi)始時(shí)有庫(kù)存量vk需要支付的存儲(chǔ)費(fèi)用為hk(vk)；n階段末的終了庫(kù)存為0。問(wèn)該公司應(yīng)如何制定生產(chǎn)計(jì)劃，從而使總成本最小。,用動(dòng)態(tài)規(guī)劃的方法，劃分為n個(gè)決策階段；,狀態(tài)轉(zhuǎn)移方程為： vk+1= vk+xk-dk,k階段的產(chǎn)品生產(chǎn)量xk為決策變量，則,k階段開(kāi)始時(shí)的庫(kù)存量vk為狀態(tài)變量， v1=0；,在求解生產(chǎn)計(jì)劃問(wèn)題時(shí)，狀態(tài)變量vk的取值范圍要先確定下來(lái)，即要先給出可達(dá)狀態(tài)集。易推出：

8、,例 某工廠要對(duì)一種產(chǎn)品制定今后四個(gè)時(shí)期的生產(chǎn)計(jì)劃，據(jù)估計(jì)四個(gè)時(shí)期的需求量依次為2、3、2和4。假定該廠生產(chǎn)每批產(chǎn)品的固定成本為3萬(wàn)元，每單位產(chǎn)品的成本為1萬(wàn)元，若不生產(chǎn)就為0；每個(gè)時(shí)期生產(chǎn)能力的上限為6個(gè)單位，每單位產(chǎn)品存放每期的存儲(chǔ)費(fèi)用為0.5萬(wàn)元。還假定第一期開(kāi)始時(shí)和第四期結(jié)束時(shí)的庫(kù)存量都為0。試問(wèn)該廠應(yīng)如何安排各期的生產(chǎn)與庫(kù)存，才能在滿(mǎn)足需求的條件下，使總成本最小。,狀態(tài)變量vk的可達(dá)狀態(tài)集：,則有，v1=0，0v24，0v36，0v44。,解 分成四個(gè)階段，k=1,2,3,4；k階段初的庫(kù)存vk為狀態(tài)變量，v1=0；k階段的產(chǎn)品生產(chǎn)量xk為決策變量，,（d1=2, d2=3, d3=

9、2, d4=4）,k=4時(shí)：,k=3時(shí)：,k=2時(shí)：,k=2時(shí)：（續(xù)）,k=1時(shí)：,于是得，總成本最小為20.5萬(wàn)元。,x1*=5， x2*=0， x3*=6， x4*=0,再順序遞推出最優(yōu)計(jì)劃為：,即：第一個(gè)時(shí)期生產(chǎn)產(chǎn)品5個(gè)單位，第二個(gè)時(shí)期不安排生產(chǎn)，第三個(gè)時(shí)期生產(chǎn)產(chǎn)品6個(gè)單位，第四個(gè)時(shí)期不安排生產(chǎn)。,2.2 不確定性采購(gòu)問(wèn)題,某單位準(zhǔn)備在以后的n個(gè)時(shí)期內(nèi)采購(gòu)一批物資。各時(shí)期的價(jià)格不是確定的，而是按照某種已知的概率分布取值。試制定采購(gòu)策略，確定在哪一時(shí)期以什么價(jià)格采購(gòu)，能使采購(gòu)價(jià)的數(shù)學(xué)期望值最低。,這類(lèi)問(wèn)題也適合用動(dòng)態(tài)規(guī)劃法進(jìn)行處理,下面通過(guò)實(shí)例加以說(shuō)明。,例 某廠生產(chǎn)上須在近五周內(nèi)采購(gòu)一批

10、原料，而估計(jì)在未來(lái)五周的價(jià)格有波動(dòng)，其浮動(dòng)價(jià)格和概率策得如下表。試確定該廠應(yīng)在哪一周以什么價(jià)格購(gòu)入，能使其采購(gòu)價(jià)的數(shù)學(xué)期望值最小，并求出期望值。,解：,（1）按采購(gòu)周數(shù)分成5個(gè)階段，k=1,2,5；,（2）取第k階段(第k周)的實(shí)際價(jià)格yk為狀態(tài)變量；,（4）用fk(yk)表示：前k-1周未采購(gòu)，第k周狀態(tài)為yk時(shí)，從第k周到第5周按最優(yōu)策略所得到的采購(gòu)價(jià)的期望值。即fk(yk)為最優(yōu)值函數(shù)；,（5）用ykE表示：前k-1周未采購(gòu)，從第k周到第5周按最優(yōu)策略所得到的總的采購(gòu)價(jià)的期望值。,顯然，ykE=Efk (yk)=0.3fk(500)+0.3fk(600)+0.4fk(700),k=5時(shí)：

11、,f5(500)=500, f5(600)=600, f5(700)=700 (x5*=1) y5E=0.3*500+0.3*600+0.4*700=610,k=4時(shí)：,f4(500)=min500,610=500, (x4*=1), f4(600)=min600,610=600, (x4*=1), f4(700)=min700,610=610, (x4*=0), y4E=0.3*500+0.3*600+0.4*610=574,k=3時(shí)：,f3(500)=min500,574=500, (x3*=1), f3(600)=min600,574=574, (x3*=0), f3(700)=min7

12、00,574=574, (x3*=0), y3E=0.3*500+0.3*574+0.4*574=551.8,k=2時(shí)：,f2(500)=min500,551.8=500, (x2*=1), f2(600)=min600,551.8=551.8, (x2*=0), f2(700)=min700,551.8=551.8, (x2*=0), y2E=0.3*500+0.3*551.8+0.4*551.8=536.26,k=1時(shí)：,f1(500)=min500,536.26=500, (x1*=1), f1(600)=min600,536.26=536.26, (x1*=0), f1(700)=mi

13、n700,536.26=536.26, (x1*=0), y1E=0.3*500+0.3*536.26+0.4*536.26=525.382,最優(yōu)的采購(gòu)策略為：在一、二、三周時(shí)，價(jià)格為500時(shí)采購(gòu)，否則就等待；在第四周時(shí)，價(jià)格為500和600都要采購(gòu)，價(jià)格為700就等待；第五周時(shí)，無(wú)論什么價(jià)都要采購(gòu)。,由此可知，采購(gòu)價(jià)的期望值最小為525.382。,對(duì)于不確定性采購(gòu)問(wèn)題，還可考慮每期價(jià)格的概率分布不同、價(jià)格的概率分布為連續(xù)分布等情況，都可用與上例類(lèi)似的方法進(jìn)行求解。,第3節(jié) 背包問(wèn)題,一個(gè)人帶一個(gè)背包上山，其可攜帶物品重量的限度為a公斤。設(shè)有n種物品可供他選擇裝入背包，已知第i種物品每件重量為

14、wi公斤，上山過(guò)程中的效用是攜帶數(shù)量xi的函數(shù)ci(xi)。問(wèn)此人應(yīng)如何攜帶各種物品，才能使總效用最大。,用動(dòng)態(tài)規(guī)劃法處理這種問(wèn)題時(shí)，通常把一種物品決定帶多少件的過(guò)程看成一個(gè)階段，按物品種類(lèi)分成先后的n個(gè)階段。即先決定第1種物品帶多少件，為第一階段；再?zèng)Q定第2種物品，為第二階段；依此類(lèi)推，最后決定第n種物品，為第n階段。,按物品種類(lèi)劃分為n個(gè)階段，k=1,2,.,n； 取第k階段初（決定第k種物品帶多少件時(shí)）可攜帶重量的剩余量sk為狀態(tài)變量，s1=a； 取第k種物品攜帶的數(shù)量xk為決策變量，則有0 xksk /wk (k=1,2,n-1) ； 狀態(tài)轉(zhuǎn)移方程為sk+1=sk-wkxk； 指標(biāo)函數(shù)

15、為Vk,n=cj(xj)；,對(duì)背包問(wèn)題求解的難點(diǎn)在于，除第一階段外，其它階段的可達(dá)狀態(tài)集不容易給出，下面通過(guò)實(shí)例說(shuō)明給出可達(dá)狀態(tài)集的方法。,解：,按變量劃分為3個(gè)階段，k=1,2,3,取k階段時(shí)常數(shù)項(xiàng)(資源)的余量sk為狀態(tài)變量，s1=10,取xk為決策變量，0 xksk/wk,狀態(tài)轉(zhuǎn)移方程為 sk+1=sk-wkxk （w1=3, w2=4, w3=5）,指標(biāo)函數(shù)為 Vk,3=cjxj（c1=4, c2=5, c3=6）,由于s1=10，因而求解此問(wèn)題就是計(jì)算f1(10)。而,可見(jiàn)，要先計(jì)算f2(10), f2(7), f2(4), f2(1)。,于是，需計(jì)算f3(10), f3(7), f

16、3(6), f3(4), f3(3), f3(2), f3(1), f3(0) 。,f3(4)= f3(3)= f3(2)= f3(1)= f3(0)=0 (x3*=0),從而，有,最后，有,所以，最優(yōu)解為x1*=2, x2*=1, x3*=0，z*=13,二維背包問(wèn)題：一個(gè)人帶一個(gè)背包上山，其可攜帶物品重量的限度為a公斤，體積的限度為b立方米。設(shè)有n種物品可供他選擇裝入背包，已知第i種物品每件重量為wi公斤，每件體積為vi立方米，上山過(guò)程中的效用是攜帶數(shù)量xi的函數(shù)ci(xi)。問(wèn)此人應(yīng)如何攜帶各種物品，才能使總效用最大。,基本方程為：,二維背包問(wèn)題，其第k階段有兩個(gè)狀態(tài)變量，但決策變量仍只

17、有一個(gè)，所以求解難度并沒(méi)有實(shí)質(zhì)性增加。二維背包問(wèn)題的求解方法與一維背包問(wèn)題基本相同。,第4節(jié) 復(fù)合系統(tǒng)可靠性問(wèn)題,某種機(jī)器的工作系統(tǒng)由n個(gè)部件串聯(lián)組成，只要一個(gè)部件失靈，整個(gè)系統(tǒng)就不能工作。為提高系統(tǒng)可靠性，每個(gè)部件都裝備了備用件，并設(shè)計(jì)了備用件自動(dòng)投入裝置。已知，部件i裝備ui個(gè)配件時(shí)的可靠性為pi(ui)，一個(gè)備用件的費(fèi)用為ci，重量為wi；整個(gè)系統(tǒng)備用件的總費(fèi)用不超過(guò)c，總重量不超過(guò)w。問(wèn)應(yīng)如何選擇各部件的備用件數(shù)，使整個(gè)系統(tǒng)的可靠性最大。,按部件劃分為n個(gè)階段；取第k階段初費(fèi)用剩余量sk和重量剩余量tk為狀態(tài)變量，s1=c, t1=w； 取給部件k安裝的備用件數(shù)uk為決策變量，則有1u

18、kminsk /ck, tk /wk ； 狀態(tài)轉(zhuǎn)移方程為sk+1=sk-ckuk, tk+1=tk-wkuk 指標(biāo)函數(shù)為Vk,n=pj(uj)；,基本方程為：,該問(wèn)題的特點(diǎn)是，指標(biāo)函數(shù)為連乘形式，邊界條件當(dāng)然為1。另外，和背包問(wèn)題一樣，求解時(shí)要先順推出各階段的可達(dá)狀態(tài)集。,例 某廠設(shè)計(jì)的電子設(shè)備由三種元件D1、D2、D3組成。已知三種元件的價(jià)格和可靠性如下表所示，要求設(shè)計(jì)中使用元件的費(fèi)用不超過(guò)105元。問(wèn)應(yīng)如何設(shè)計(jì)，使設(shè)備的可靠性達(dá)到最大（不考慮重量限制）。,解：,按變量劃分為3個(gè)階段，k=1,2,3； sk為狀態(tài)變量，s1=105； uk為決策變量，1uksk/ck；狀態(tài)轉(zhuǎn)移方程sk+1=s

19、k-ckuk (c1=30, c2=15, c3=20)；指標(biāo)函數(shù)Vk,3= pj(uj) ( p1(u1) =1-0.1u1, p2(u2) =1-0.2u2, p3(u3) =1-0.5u3 )。,由于s1=105，而,則要先計(jì)算f2(75), f2(45), f2(15),于是計(jì)算f3(60), f3(45), f3(30), f3(15), f3(0) 。,從而得：,第5節(jié) 排序問(wèn)題,設(shè)有n個(gè)工件需要在機(jī)床A、B上加工，每個(gè)工件都必須先經(jīng)過(guò)A而后B兩道加工工序。以ai、bi分別表示工件i(1in)在機(jī)床A、B上的加工時(shí)間。問(wèn)應(yīng)如何在兩機(jī)床上安排各工件的加工順序，使在機(jī)床A上加工第一個(gè)工

20、件開(kāi)始到在機(jī)床B上加工完最后一個(gè)工件為止，所用的加工總時(shí)間最少？,加工工件在機(jī)床A上有加工順序問(wèn)題，在機(jī)床B上也有加工順序問(wèn)題?？梢宰C明：最優(yōu)加工順序在兩臺(tái)機(jī)床上可同時(shí)實(shí)現(xiàn)。因此，最優(yōu)排序方案可以只在機(jī)床A、B上加工順序相同的排序中尋找即可。 即使如此，所有可能的方案仍有n!個(gè)，這是一個(gè)不小的數(shù)，用窮舉法是不現(xiàn)實(shí)的。下面用動(dòng)態(tài)規(guī)劃法對(duì)排序問(wèn)題進(jìn)行研究。,當(dāng)加工順序排定之后，工件在A上沒(méi)有等待時(shí)間，而在B上則常常需要等待。因此，只有盡量減少在B上等待加工的時(shí)間，才能使總加工時(shí)間最短。,現(xiàn)以在機(jī)床A上更換工件的時(shí)刻作為階段的分界點(diǎn)，分成n個(gè)階段。第k階段時(shí)，Xk表示尚未在A上加工的工件集合，tk表示已在A上加工完的工件還需要在B上的加工時(shí)間，(Xk, tk)作為狀態(tài)。,令fk(Xk, tk)為從狀態(tài)(Xk, tk)出發(fā)，對(duì)還未在A上加工的剩余工件按最優(yōu)排序，完成全部加工任務(wù)還需要的時(shí)間，即為k-子過(guò)程最優(yōu)值函數(shù)。,fk(Xk, tk, i)