第五章動(dòng)態(tài)規(guī)劃

Dynamicprogramming§1.引言

研究多階段決策問(wèn)題美國(guó)數(shù)學(xué)家貝爾曼（R.E.Bellman）1951年提出動(dòng)態(tài)規(guī)劃。1957年出版DynamicProgramming應(yīng)用：最優(yōu)調(diào)度、資源分配最優(yōu)路徑、最優(yōu)控制設(shè)備更新、庫(kù)存問(wèn)題投資問(wèn)題、排序問(wèn)題動(dòng)態(tài)規(guī)劃所解決問(wèn)題的特征動(dòng)態(tài)規(guī)劃方法適用于多階段決策問(wèn)題。多階段決策過(guò)程可表述如下：狀態(tài)狀態(tài)狀態(tài)狀態(tài)狀態(tài)決策決策決策12n特點(diǎn)：過(guò)程分若干階段，每階段都要決策，每階段的決策依賴于當(dāng)前的狀態(tài)，決定當(dāng)前階段的效益， 又決定了下一階段的狀態(tài)?！?.多階段決策問(wèn)題例1.（最優(yōu)路徑問(wèn)題）某產(chǎn)品從A城運(yùn)至F城，其間要經(jīng)過(guò)若干個(gè)城鎮(zhèn)和若干條道路，路線結(jié)構(gòu)如圖所示，圖中給出了每段道路的運(yùn)費(fèi)（元），試選擇一條合理的運(yùn)輸路線，使總運(yùn)費(fèi)最??？1234分析：方案①：A→B1→C1→E1→F運(yùn)費(fèi)：26元方案②:A→B3→C3→E3→F運(yùn)費(fèi)：22元方案③:A→B2→C1→E2→F運(yùn)費(fèi)：18元最優(yōu)方案：方案③例2、多階段資源分配問(wèn)題

若某機(jī)器的工作系統(tǒng)有N個(gè)部件串聯(lián)組成，只要一個(gè)部件失靈，則整個(gè)系統(tǒng)就不能正常工作。為了提高系統(tǒng)的可靠性，可在每一個(gè)部件上裝有主要元件的備用件，并設(shè)計(jì)成并聯(lián)系統(tǒng)。顯然，備用元件越多，整個(gè)系統(tǒng)正常工作的可能性越大，但系統(tǒng)的成本，重量，體積均相應(yīng)增大，工作精度也降低，在考慮上述限制條件下，應(yīng)如何選用各部件的備用元件數(shù)，使整個(gè)系統(tǒng)的工作可靠性最大？設(shè)部件i(i=1,2,…,N)上裝有zi個(gè)備用元件時(shí)，它正常工作的概率為Pi(zi),因此整個(gè)系統(tǒng)正常工作的概率為P=

pi(zi)設(shè)裝一個(gè)部件i備用元件費(fèi)用為ci，重量為wi，要求總費(fèi)用不超過(guò)c，總重量不超過(guò)w，則這個(gè)問(wèn)題的數(shù)學(xué)模型為例3、復(fù)合系統(tǒng)工作可靠性問(wèn)題，且為整數(shù)。例4、生產(chǎn)庫(kù)存問(wèn)題

現(xiàn)有一生產(chǎn)部門，生產(chǎn)周期分為n個(gè)階段，即k=1~n,已知最初庫(kù)存量為s1，階段產(chǎn)品需求量為dk，生產(chǎn)的固定成本為K，單位產(chǎn)品的消耗費(fèi)用為c，單位產(chǎn)品的階段庫(kù)存費(fèi)用為h，倉(cāng)庫(kù)容量為M，階段生產(chǎn)能力為bk，問(wèn)應(yīng)如何安排各階段產(chǎn)量，使計(jì)劃期內(nèi)的費(fèi)用總和最小。

例5、排序問(wèn)題

設(shè)有n個(gè)工件，要在A,B機(jī)床上加工,各工件必須經(jīng)過(guò)先A后B的兩道加工工序,以ai,bi分別表示工件i(1≤i≤n)在A,B上的加工時(shí)間,問(wèn)應(yīng)如何在兩機(jī)床上安排各工件加工的順序,使所用的加工總時(shí)間最少？§3.基本概念1.階段和階段變量階段：過(guò)程的劃分，包括時(shí)間、空間的劃分，階段數(shù):n階段變量：描述階段的變量用k表示，k=1,2,…..,n2.狀態(tài)和狀態(tài)變量狀態(tài)：描述過(guò)程的必要信息。狀態(tài)應(yīng)具有無(wú)后效性:若給定了某階段狀態(tài)，則在這階段以后過(guò)程的發(fā)展不受這階段以前各階段狀態(tài)的影響.狀態(tài)變量：描述狀態(tài)的變量，用s表示。3.決策和決策變量決策：決定（選擇），從一個(gè)階段的狀態(tài)到下一個(gè)階段狀態(tài)的選擇。決策變量：描述決策的變量，用u表示.4.策略策略：決策按順序構(gòu)成的序列，用p表示。7.多階段過(guò)程對(duì)于動(dòng)態(tài)系統(tǒng)，12kn8.多階段決策過(guò)程多階段決策過(guò)程就是在各個(gè)階段都要進(jìn)行決策。12kn數(shù)學(xué)描述§4動(dòng)態(tài)規(guī)劃的基本方程4.1最優(yōu)性原理4.2基本方程或求解的過(guò)程是一個(gè)逆推過(guò)程.基本方程的解法······12kn······逆推找決策劃分階段順序定策略構(gòu)造模型的過(guò)程1)劃分階段2)正確選擇狀態(tài)變量3)選擇決策變量uk4)確定狀態(tài)轉(zhuǎn)移方程sk+1=Tk(sk,uk)5)確定最優(yōu)值函數(shù)fk(sk)6)建立函數(shù)基本方程式逆推解法基本方程：若改變最優(yōu)值函數(shù)的意義，可得到基本方程的另一種表述形式。12knnn-1n-k+110最優(yōu)路徑問(wèn)題

§5多階段資源分配問(wèn)題基本方程為：基本方程為：注：二者形式有差異，本質(zhì)相同。該結(jié)論的證明見(jiàn)課本P168引理5.3.1和引理5.3.2及定理5.3.1.原基本方程：又可改寫為如下形式：資源總量S1，兩種生產(chǎn)方式A和B，兩種產(chǎn)量函數(shù)g(y)和h(y),回收率分別為a,b,進(jìn)行5階段的生產(chǎn).關(guān)鍵詞：例：令顯然，原問(wèn)題即求f3(12).階段k,狀態(tài)變量為y，決策變量xk,階段指標(biāo)為xk,最優(yōu)值函數(shù)為fk(y).§6用最優(yōu)化原理求解非線性規(guī)劃問(wèn)題遞歸公式為：推廣：用最優(yōu)化原理求解某些非線性規(guī)劃問(wèn)題.基本方程：注：若目標(biāo)函數(shù)為乘積形式，gi(x)應(yīng)為非負(fù)?！?旅行售貨員問(wèn)題和最優(yōu)線路問(wèn)題例1旅行售貨員問(wèn)題基本方程：例2、最優(yōu)線路問(wèn)題基本方程：【前向最優(yōu)性原理】動(dòng)態(tài)規(guī)劃的順序解法假設(shè)階段序數(shù)k和狀態(tài)變量sk的定義不變，而改變決策變量uk的定義，則這時(shí)的狀態(tài)轉(zhuǎn)移不是由sk、uk去確定sk+1，而是反過(guò)來(lái)由sk+1、uk去確定sk，這時(shí)狀態(tài)轉(zhuǎn)移方程為sk=Tkr

(sk+1,uk)順序解法的基本方程為：順序解法用順序解法求習(xí)題（A）第3題12kn用順序解法求習(xí)題（A）第3題12kn

例1投資問(wèn)題現(xiàn)有資金5百萬(wàn)元,可對(duì)三個(gè)項(xiàng)目進(jìn)行投資,投資額均為整數(shù)(單位為百萬(wàn)元),其中2號(hào)項(xiàng)目的投資不得超過(guò)3百萬(wàn)元,1號(hào)和3號(hào)項(xiàng)目的投資均不得超過(guò)4百萬(wàn)元，3號(hào)項(xiàng)目至少要投資1百萬(wàn)元。每個(gè)項(xiàng)目投資5年后,預(yù)計(jì)可獲得的收益見(jiàn)下表,問(wèn)如何投資可望獲得最大的收益。

01234103610122051012---3--481115投資額u收益wk項(xiàng)目k§8.動(dòng)態(tài)規(guī)劃應(yīng)用舉例[解]sk——留給第k,(k+1),…,n項(xiàng)目的資金(狀態(tài)變量)uk——對(duì)k項(xiàng)目的投資額wk(sk,uk)——對(duì)k項(xiàng)目投資uk后的收益wk(uk)fk(sk)——應(yīng)用剩余資金sk對(duì)k,(k+1),…,n項(xiàng)目投資可獲得的最大收益問(wèn)題即求f1(5)。狀態(tài)轉(zhuǎn)移方程為sk+1=sk-ukfk(sk)=max{wk(sk,uk)+fk+1(sk+1)}k=3,2,1f4(s4)=0基本方程當(dāng)k=3時(shí)uk=skf3(1)=4f3(2)=8f3(3)=11f3(4)=15當(dāng)k=2時(shí),有(注意：項(xiàng)目3至少投資1百萬(wàn)元,2號(hào)項(xiàng)目的投資不得超過(guò)3百萬(wàn)元)s212345D2(sk){0}{0,1}{0,1,2}{0,1,2,3}{0,1,2,3}f2(1)=w2(1,0)+f3(1)=4為了獲得最大收益，必須將5百萬(wàn)元資金全部用于投資。fk(sk)=max{wk(sk,uk)+fk+1(sk+1)}k=3,2,1f4(s4)=0f2(2)=maxw2(2,1)+f3(1)w2(2,0)+f3(2)=max5+40+8=9f2(3)=maxw2(3,2)+f3(1)w2(3,1)+f3(2)w2(3,0)+f3(3)=max10+45+80+11=14f2(4)=maxw2(4,3)+f3(1)w2(4,2)+f3(2)w2(4,1)+f3(3)w2(4,0)+f3(4)=max12+410+85+110+15=1812+810+115+15w2(5,3)+f3(2)w2(5,2)+f3(3)w2(5,1)+f3(4)f2(5)=max=max=21當(dāng)k=1時(shí)，有s1=5D1(s1)={0,1,2,3,4}f1(5)=maxw1(5,4)+f2(1)w1(5,3)+f2(2)w1(5,2)+f2(3)w1(5,1)+f2(4)w1(5,0)+f2(5)=max12+410+96+143+180+21=21應(yīng)用順序跟蹤，可知，最優(yōu)方案有兩個(gè)：方案Ⅰ——u1*=0,u2*=2,u3*=3方案Ⅱ——u1*=1,u2*=2,u3*=2最大收益為21百萬(wàn)元。例2、一維“背包”問(wèn)題

問(wèn)題：有一徒步旅行者，已知他所能承受的旅行背包的重量不超過(guò)a(kg)。今有n種物品可供他選擇裝入背包，這n種物品分別編號(hào)為1,2,…,n，其中第j種物品的單位重量為aj(kg)，其使用價(jià)值為cj。問(wèn)這位旅行者如何選擇這n種物品的件數(shù)，使總的價(jià)值最大？其數(shù)學(xué)模型為：，整數(shù)sj—旅行者背包中允許裝入前j種物品的總重量uj—裝入第j種物品的件數(shù)sj-1=sj–ajujfj(sj)——允許裝入物品的總重量不超過(guò)sj，并采用最優(yōu)策略裝前j種物品時(shí)的(最大)使用價(jià)值(j=1,2,…,n)fj(sj)=max{cjuj+fj-1（sj–ajuj）}uj≤sj/aj

uj≥0,整數(shù)f0(s0)=0用動(dòng)態(tài)規(guī)劃求解分為n個(gè)階段例3、二維“背包”問(wèn)題旅行者的負(fù)重能力為a(kg),背包容積為b(m3),且各種物品的單重為a1,a2,…,an,體積為b1,b2,…,bn,價(jià)值c1,c2,…,cn,問(wèn)各種物品各裝多少件，才能使裝入的價(jià)值最大？其數(shù)學(xué)模型為：，整數(shù)分為n個(gè)階段（xk,yk)—第k個(gè)階段開(kāi)始留給前k種物品的重量和體積uk—裝入第k種物品的件數(shù)xk-1=xk–akuk,yk-1=yk–bkukfk(xk,yk)為背包中允許物品總重量不超過(guò)xk,且體積不超過(guò)yk，裝入前k種物品的最大價(jià)值(j=1,2,…,n)fk(xk,yk)=max{ckuk+fk-1(xk-akuk,yk-bkuk)}uk≤min(xk/ak,yk/bk)uk≥0,整數(shù)f0(x0,y0)=0用動(dòng)態(tài)規(guī)劃求解例4、一維資源分配問(wèn)題設(shè)有某種原料，總數(shù)量為a，用于生產(chǎn)n種產(chǎn)品，若分配數(shù)量xi用于生產(chǎn)第i種產(chǎn)品，其收益為gi(xi)。問(wèn)應(yīng)如何分配，才能使生產(chǎn)n種產(chǎn)品的總收入最大？sk—用于生產(chǎn)第k種產(chǎn)品到第n種產(chǎn)品的原料數(shù)量uk—分配給第k種產(chǎn)品的原料數(shù)量狀態(tài)轉(zhuǎn)移方程sk+1=sk-ukfk(sk)—以數(shù)量sk的原料分配給第k種產(chǎn)品至第n種產(chǎn)品的最大收入fk(sk)=max{gk(uk)+fk+1(sk-uk)}k=n,n-1,…,1fn(sn)=gn(sn)0≤uk≤sk當(dāng)gi(x)為線性函數(shù)或凸函數(shù)時(shí)，則不難求出fk(sk)的表達(dá)式，而當(dāng)gi(x)不具有此性質(zhì)時(shí)，則可用離散化方法去求解，方法是把[0,a]進(jìn)行分割,sk=0,Δ,2Δ,…,mΔ=a，然后計(jì)算出在這些點(diǎn)上的fk(sk)值.fn(sn)=gn(sn)fk(sk)=max[gk(pΔ)+fk+1(sk-pΔ)]k=n-1,…,1p=1,2,…q其中sk=qΔ首先求出fn(pΔ),p=1,2,…,m,然后求出fn-1(sn-1),…,f1(s1)在這些點(diǎn)上的值，最后再往回倒退求出最優(yōu)決策。例5、二維分配問(wèn)題設(shè)有兩種原料，數(shù)量各為a和b，需分配用于n種生產(chǎn)。如果第一種資源以xi數(shù)量單位，第二種資源以數(shù)量yi單位用于生產(chǎn)第i種產(chǎn)品，其收入為gi(xi,yi)，問(wèn)應(yīng)如何分配這兩種原料于n種產(chǎn)品的生產(chǎn)，使總收入最大？xk—分配給第k種產(chǎn)品的第一種原料數(shù)量yk—分配給第k種產(chǎn)品的第二種原料數(shù)量fk(x,y)—以第一種原料x(chóng)單位,第二種原料y單位,分配用于前k種產(chǎn)品所能得到的最大收入.fk(x,y)=max{gk(xk,yk)+fk-1(x-xk,y-yk)}k=1,…,n0≤xk≤x0≤yk≤yf1(x,y)=max{g1(x1,y1}其中，0≤x1≤x,0≤y1≤y在實(shí)際問(wèn)題中，由于g(x,y)的復(fù)雜性，常采用下面的方法求它的近似解(1)格子點(diǎn)法用離散化的方法，將定義區(qū)域矩形0≤x≤a,0≤y≤b分為m1和m2等分，則總共有(m1+1)*(m2+1)個(gè)格點(diǎn)，對(duì)每個(gè)k值，計(jì)算fk(x,y)，計(jì)算量較大?！按指褡狱c(diǎn)法”：先用少數(shù)的格子點(diǎn)進(jìn)行粗糙計(jì)算,在求出相應(yīng)的最優(yōu)解后，再在最優(yōu)解的附近小范圍內(nèi)進(jìn)一步細(xì)分，并求在細(xì)分格子點(diǎn)上的最優(yōu)解，如此繼續(xù)下去直到滿足要求為止，這種方法也可能出現(xiàn)“最優(yōu)解漏網(wǎng)”的情況，因此，應(yīng)用此法要結(jié)合對(duì)指標(biāo)函數(shù)的特性進(jìn)行分析。

(2)拉格朗日乘數(shù)法

這是一種降維方法。引入拉格朗日乘數(shù)λ，將二維問(wèn)題化為Max{g1(x1,y1)+g2(x2,y2)+…+gn(xn,yn)-λ(y1+…+yn)}令hi(xi)=hi(xi,λ)=max[g(xi,yi)-λyi]yi≥0于是問(wèn)題變?yōu)闈M足條件其中,λ為一固定的參數(shù).x1+x2+…+xn=axi≥0,yi≥0,i=1,2…,nmax[h1(x1)+h2(x2)+…+hn(xn)]x1+x2+…+xn=axi≥0(3)逐次逼近法這是另一種降維方法。令x(0)={x1(0),x2(0),…,xn(0)}為滿足Σxi(0)=a的一個(gè)可行解，固定x在x(0),先對(duì)y求解，則二維問(wèn)題變?yōu)橐痪S問(wèn)題max[g1(x1(0),y1)+g2(x2(0),y2)+…+gn(xn(0),yn)]y1+y2+…+yn=a,yi≥0設(shè)其解為y(0)={y1(0),y2(0),…,yn(0)},然后再固定y為y(0)對(duì)x求解maxΣgi(xi,yi(0))Σxi=axi≥0得其解為x(1)={x1(1),x2(1),…,xn(1)}，再固定x為x(1),對(duì)y求解，這樣依此得到一系列解{x(k)}，{y(k)}，故函數(shù)值列{Σgi(xi(k),yi(k))}單調(diào)上升,但不一定收斂到最優(yōu)解。因此一般應(yīng)選取幾個(gè)初始點(diǎn)x(0)開(kāi)始，然后從得到的幾個(gè)局部最優(yōu)解中選出一個(gè)最好的。Σgi(xi(0),yi)≤Σgi(xi(0),yi(0))≤Σgi(xi(1),yi(0))因?yàn)槔?、生產(chǎn)庫(kù)存問(wèn)題現(xiàn)有一個(gè)生產(chǎn)部門，生產(chǎn)計(jì)劃周期分為n個(gè)階段，即k=1~n,已知最初庫(kù)存量為s1，階段產(chǎn)品需求量為dk，生產(chǎn)的固定成本為K，單位產(chǎn)品的消耗費(fèi)用為c，單位產(chǎn)品的階段庫(kù)存費(fèi)用為h，倉(cāng)庫(kù)容量為M，階段生產(chǎn)能力為bk，問(wèn)應(yīng)如何安排各階段產(chǎn)量，使計(jì)劃期內(nèi)的費(fèi)用總和最小。sk——階段k的初始庫(kù)存量sn+1=00≤sk≤min{M,dk+dk+1+…+dn}k=1,2…,nuk——階段k的生產(chǎn)量dk–sk≤uk≤min{bk,dk+dk+1`+…+dn–sk}sk+1=sk+uk-dk階段k的費(fèi)用分為生產(chǎn)費(fèi)用與庫(kù)存費(fèi)用之和，階段k的生產(chǎn)費(fèi)用為Kδ(uk)+cukδ(uk)=0uk=01uk≠0庫(kù)存費(fèi)用按階段k初期的庫(kù)存量計(jì)算hsk。因而，階段k的總費(fèi)用為rk(sk,uk)=kδ(uk)+cuk+hskfk(sk)—階段k的初始庫(kù)存為sk時(shí),從階段k至階段n的最小費(fèi)用fk(sk)=min{rk(sk,uk)+fk+1(sk+1)}fn+1(sn+1)=0例7、復(fù)合系統(tǒng)工作可靠性問(wèn)題若某機(jī)器的工作系統(tǒng)有N個(gè)部件串聯(lián)組成，只要一個(gè)部件失靈，則整個(gè)系統(tǒng)就不能正常工作。為了提高系統(tǒng)的可靠性，可在每一個(gè)部件上裝有主要元件的備用件，并設(shè)計(jì)成并聯(lián)系統(tǒng)。顯然，備用元件越多，整個(gè)系統(tǒng)正常工作的可能性越大，但系統(tǒng)的成本，重量，體積均相應(yīng)增大，工作精度也降低，在考慮上述限制條件下，應(yīng)如何選用各部件的備用元件數(shù)，使整個(gè)系統(tǒng)的工作可靠性最大？設(shè)部件i(i=1,2,…,N)上裝有zi個(gè)備用元件時(shí)，它正常工作的概率為Pi(zi)，因此，整個(gè)系統(tǒng)正常工作的概率為

P=pi(zi)設(shè)裝一個(gè)部件i備用元件費(fèi)用為ci，重量為wi，要求總費(fèi)用不超過(guò)c，總重量不超過(guò)w，則這個(gè)問(wèn)題的數(shù)學(xué)模型為i=1nxk——由第k個(gè)部件到第n個(gè)部件所容許使用的總費(fèi)用

yk——由第k個(gè)部件到第n個(gè)部件所容許使用的總重量

uk——部件上裝的備用元件數(shù)zk(uk=zk)

狀態(tài)轉(zhuǎn)移方程:

xk+1=xk-uk·ck,yk+1=yk-uk·wk(1≤k≤n)

fk(xk,yk)——從xk和yk起發(fā),部件k到部件n的系統(tǒng)的最大可靠性

fk(xk,yk)=max{pk(uk)·fk+1(xk-ckuk,yk-wkuk)}

fn+1(xn+1,yn+1)=10≤uk≤min{[xk/ck],[yk/wk]}，且為整數(shù)。例8、排序問(wèn)題

設(shè)有n個(gè)工件，要在A,B機(jī)床上加工,每個(gè)工件必須經(jīng)過(guò)先A后B的兩道加工工序,以ai,bi分別表示工件i(1≤i≤n)在A,B上的加工時(shí)間,問(wèn)應(yīng)如何在兩機(jī)床上安排各工件加工的順序,使所用的加工總時(shí)間最少？可以證明：加工工件在兩臺(tái)機(jī)床上加工的順序不同，這樣的排序不是最優(yōu)的排序方案。當(dāng)加工順序取定后，工件在A上沒(méi)有等待時(shí)間，而在B上常常等待，因此，尋求最優(yōu)的加工順序，就是要尋求一個(gè)順序，使得工件在B上等待的時(shí)間最短。以機(jī)床A上更換工件的時(shí)刻作為時(shí)段X—在機(jī)床A上等待加工的按取定順序排列的工件集合

t—機(jī)床A上加工完X以外的工件后機(jī)床B上完成這些任務(wù)還需要的時(shí)間狀態(tài)變量：(X,t)一旦取定(X,t)，階段數(shù)就確定了f(X,t)—從(X,t)出發(fā)，對(duì)未加工完的工件采用最優(yōu)順序后，加工完X中工件所用的時(shí)間f(X,t,i)—從(X,t)出發(fā)，在A上加工工件i，對(duì)未加工的工件采用最優(yōu)順序,加工完X中所有工件所需的時(shí)間。f(X,t,i,j)—從(X,t)出發(fā)，在A上依次相繼加工i,j后，對(duì)未加工工件采用最優(yōu)順序后，加工完X中所有工件所需的時(shí)間。因而f(X,t,i)=記Ζi(t)=max(t-ai,0)+bi——從A上加工完i到B上加工完i所需的時(shí)間，則ai+f(X/i,t-ai+bi)當(dāng)t≥ai時(shí)ai+f(X/i,bi)當(dāng)t≤ai時(shí)f(X,t,i)=ai+f[X/i,Ζi(t)]由定義，可得f(X,t,i,j)=ai+aj+f[X/{i,j},Ζij(t)]Ζij(t)=max(Ζi(t)-aj,0)+bj在A上加工完X以外的工件的時(shí)間t≥ait-ai+bibi