運籌學(xué)-第05章-動態(tài)規(guī)劃

運籌學(xué)

第五章動態(tài)規(guī)劃本章重點動態(tài)規(guī)劃的四大要素、一個方程動態(tài)規(guī)劃問題的建模與求解動態(tài)規(guī)劃概念(1)前面介紹的線性規(guī)劃研究的是一次性的決策線性規(guī)劃決策過程可以總結(jié)為在給定資源和環(huán)境的情況下，決定變量的取值，使某個目標達到最大或最小值這個決策過程可以表示如下圖決策x1x2uZ其中u表示決策變量x1

表示決策所依賴的資源和環(huán)境Z表示目標函數(shù)x2

表示決策后的資源和環(huán)境狀況動態(tài)規(guī)劃概念(2)例如，前面講過的生產(chǎn)計劃問題就是一次決策某工廠用三種原料生產(chǎn)三種產(chǎn)品，已知的條件如下表所示，試制訂總利潤最大的日生產(chǎn)計劃產(chǎn)品所需原料數(shù)量（公斤/件）產(chǎn)品Q1（件）產(chǎn)品Q2（件）產(chǎn)品Q3（件）原料可用量（公斤/日）原料P12301500原料P2024800原料P33252000產(chǎn)品的利潤（千元/件）354動態(tài)規(guī)劃概念(3)在這個模型中模型中的A、b和C就是x1模型中的X就是u模型中的f(X)=CX就是ZA、C和剩余的原料為x2設(shè)每天生產(chǎn)三種產(chǎn)品的件數(shù)分別為x1、x2、x3其線性規(guī)劃模型為決策x1x2uZ動態(tài)規(guī)劃概念(4)如果上例中的生產(chǎn)計劃不是只在一天里進行，而是連續(xù)一周，每天投入一定量的原料，剩余的原料后面可以繼續(xù)使用，每天只允許生產(chǎn)一種產(chǎn)品并獲得相應(yīng)的利潤。問怎樣決策才能使一周的總利潤最大？解決這樣的問題需要將決策過程分為多個階段，本問題需要分為如下的7個階段。周日x1x2u1r1周一x3u2r2周六x8u7r7x7…動態(tài)規(guī)劃概念(5)uk（k=1,2,3,4,5,6,7）表示第k天生產(chǎn)三種產(chǎn)品中的哪一種以及生產(chǎn)多少x1=技術(shù)環(huán)境A、市場環(huán)境C和原料bxk+1=技術(shù)環(huán)境A、市場環(huán)境C和原料b

+第k天剩余的原料（k=1,2,3,4,5,6,7）rk=第k天生產(chǎn)產(chǎn)品獲得的利潤總利潤=r1+r2+r3+r4+r5+r6+r7動態(tài)規(guī)劃就是解決這種多階段決策過程的方法多階段決策過程(1)其中包含n個決策子問題，每個子問題稱為一個階段，用變量k表示，稱為階段變量xk描述k階段初系統(tǒng)的狀況，稱為狀態(tài)變量每個階段有一個輸入狀態(tài)和一個輸出狀態(tài)一般把輸入狀態(tài)稱為該階段的階段狀態(tài)TnT1x1x2u1r1T2x3u2r2Tkxk+1ukrkxk…xn+1unrnxn…一般的多階段決策過程表示如下多階段決策過程(2)uk

代表k階段對第k子問題進行的決策，稱uk為k階段的決策變量，uk的一組確定的取值稱為一個決策rk

表示k階段從狀態(tài)xk出發(fā)做決策uk之后產(chǎn)生的后果，稱為k階段的階段效應(yīng)若在上述的多階段決策過程中，系統(tǒng)k階段以后的決策只與k階段系統(tǒng)的狀態(tài)xk

有關(guān)，而與系統(tǒng)以前的決策無關(guān)，則稱該多階段決策過程具有無后效性注：動態(tài)規(guī)劃的建模和求解都是針對具有無后效性的多階段決策過程多階段決策過程(3)在具有無后效性的多階段決策過程中，uk由xk

決定，rk

和xk+1

由xk

和uk決定，因此決策可以寫為uk(xk

)階段效應(yīng)可以寫為rk(xk

,uk)狀態(tài)xk+1=Tk(xk

,uk)稱為狀態(tài)轉(zhuǎn)移方程，其中Tk

是已知函數(shù)多階段決策過程中，從第k階段到最終階段的過程稱為k-后部子過程，簡稱k-子過程動態(tài)規(guī)劃模型動態(tài)規(guī)劃模型如下

表示求和或加權(quán)求和opt表示求最優(yōu)(最大值或最小值)Xk表示k階段狀態(tài)可能的取值范圍，稱為狀態(tài)可能集合Uk表示k階段決策可能的取值范圍，稱為決策允許集合動態(tài)規(guī)劃建模確定階段根據(jù)實際情況進行階段劃分明確狀態(tài)變量xk和狀態(tài)可能集合Xk確定決策變量uk(xk

)和決策允許集合Uk確定狀態(tài)轉(zhuǎn)移方程xk+1=Tk(xk

,uk)明確階段效應(yīng)rk(xk

,uk)和目標R示例(5.1-1)前面講過的生產(chǎn)計劃問題某工廠用三種原料生產(chǎn)三種產(chǎn)品，已知的條件如下表所示，如連續(xù)生產(chǎn)一周，每天投入一定量的原料，剩余的原料后面可以繼續(xù)使用，每天只允許生產(chǎn)一種產(chǎn)品并獲得相應(yīng)的利潤。試制訂總利潤最大的周生產(chǎn)計劃(只建模，不求解)產(chǎn)品所需原料數(shù)量（公斤/件）產(chǎn)品Q1（件）產(chǎn)品Q2（件）產(chǎn)品Q3（件）原料可用量（公斤/日）原料P12301500原料P2024800原料P33252000產(chǎn)品的利潤（千元/件）354示例(5.1-2)示例(5.1-3)動態(tài)規(guī)劃解的概念(1)最優(yōu)目標值在多階段決策過程中，從起始狀態(tài)x1開始，進行一系列的決策，使得目標R達到最優(yōu)，我們把這種目標的值稱為最優(yōu)目標值，記為R*最優(yōu)策略把使目標達到最優(yōu)的決策序列稱為最優(yōu)策略，記為{u1*,u2*,…,un*}最優(yōu)路線在采用最優(yōu)策略時，系統(tǒng)從x1開始所經(jīng)過的狀態(tài)序列稱為最優(yōu)路線，記為{x1*,x2*,…,xn+1*}動態(tài)規(guī)劃解的概念(2)求解動態(tài)規(guī)劃問題就是要找到最優(yōu)策略、最優(yōu)路線和最優(yōu)目標值動態(tài)規(guī)劃最優(yōu)性原理(1)一個多階段決策過程的最優(yōu)策略具有這樣的性質(zhì)無論其初始狀態(tài)及其初始決策如何，對于前面決策所形成的某一狀態(tài)而言，下余的決策序列必定構(gòu)成最優(yōu)策略最優(yōu)性原理的含義是最優(yōu)策略的任何一個k-后部子策略(uk*,uk+1*,…,un*)，是以xk*為初始狀態(tài)的k-后部子過程的最優(yōu)策略動態(tài)規(guī)劃最優(yōu)性原理(2)如上圖A到B之間的藍線是由狀態(tài)A到狀態(tài)B的最優(yōu)策略在線上任取一點M，M到B之間的藍線就是由狀態(tài)M到狀態(tài)B的最優(yōu)策略ABM貝爾曼函數(shù)(1)在k階段從初始狀態(tài)xk出發(fā)，執(zhí)行最優(yōu)決策序列，到達過程終點時，整個k-后部子過程中的目標函數(shù)取值，稱為條件最優(yōu)目標函數(shù)，也稱為貝爾曼函數(shù)，記為fk(xk

)，則為了將多階段決策過程的任一階段狀態(tài)xk

的最優(yōu)策略和最終的最優(yōu)策略相區(qū)別，稱前者為條件最優(yōu)策略不一定等于最優(yōu)路線中的k階段狀態(tài)系統(tǒng)從xk出發(fā)，在k-后部子過程中的最優(yōu)策略貝爾曼函數(shù)(2)構(gòu)成條件最優(yōu)策略的決策稱為條件最優(yōu)決策將k階段狀態(tài)xk的條件最優(yōu)決策表示為uk’(xk

)，簡記為uk’，相應(yīng)的條件最優(yōu)策略表示為{uk’,uk+1’,…,un’}執(zhí)行條件最優(yōu)策略時的階段狀態(tài)序列稱為條件最優(yōu)路線，表示為{xk,xk+1’,…,xn’,xn+1’}貝爾曼函數(shù)(3)動態(tài)規(guī)劃方法的原理就是建立起fk(xk

)與fk+1(xk+1)之間的遞推關(guān)系，然后逐步求出所有的fk(xk

)貝爾曼方程對于無后效性的多階段決策過程，根據(jù)最優(yōu)性原理和貝爾曼函數(shù)定義，可得動態(tài)規(guī)劃問題求解步驟(1)通過貝爾曼方程逆序求出條件最優(yōu)目標函數(shù)值集合和條件最優(yōu)決策集合k=n時，不存在n+1階段必須就階段n的所有可能狀態(tài)

計算和動態(tài)規(guī)劃問題求解步驟(2)k=n-1時，根據(jù)，就階段n-1的所有可能狀態(tài)

計算和余者類推，直到階段1動態(tài)規(guī)劃問題求解步驟(3)通過狀態(tài)轉(zhuǎn)移方程順序求出最優(yōu)決策序列和最優(yōu)路線階段1的狀態(tài)x1唯一確定時，x1*=x1，可得唯一確定的u1’(x1*

)和f1(x1*

)，則R*=f1(x1*

)，u1*(x1*

)=u1’(x1*

)當階段1的狀態(tài)x1不唯一時，由

求得，求出余者類推，直至階段n，求出、和動態(tài)規(guī)劃的四大要素、一個方程在動態(tài)規(guī)劃的建模和求解過程中，有五個方面起著極其重要的作用四大要素(模型里的)狀態(tài)變量及其可能集合決策變量及其可能集合狀態(tài)轉(zhuǎn)移方程xk+1=Tk(xk

,uk)階段效應(yīng)rk(xk

,uk)貝爾曼方程動態(tài)規(guī)劃應(yīng)用舉例(1)最短路線問題：從某地出發(fā)，途徑若干個中間點最后到達目的地，試求距離最短或費用最省的路線用動態(tài)規(guī)劃求解該問題分為三種情況考慮定步數(shù)問題不定步數(shù)問題(有限步=無循環(huán))不定步數(shù)問題(無限步=有循環(huán))示例(5.2-1)路線圖如下所示，箭頭表示通行方向，線上數(shù)字表示道路長度，試求s到t的最短路線sabcdeft9877456456754示例(5.2-2)該問題是一個定步數(shù)問題，分為3個階段階段1：決定由s到a、b還是c階段2：決定是到d、e或是f階段3：到t狀態(tài)變量xk設(shè)為k階段初始所在地x1∈{s}，x2∈{a,b,c}，x3∈{d,e,f}，x4∈{t}k階段決策uk是決定下一步走到哪里，有u1∈{a,b,c}u2(a)∈{d,f}，u2(b)∈{d,e}，u2(c)∈{d,e,f}u3∈{t}示例(5.2-3)狀態(tài)轉(zhuǎn)移方程xk+1=uk階段效應(yīng)rk(xk,uk

)

取為從xk

走到uk

的路線長度，如r1(s

,a)

=9貝爾曼函數(shù)fk(xk

)定義為從xk

走到

t的最短路線貝爾曼方程示例(5.2-4)通過貝爾曼方程逆序求出條件最優(yōu)目標函數(shù)值集合和條件最優(yōu)決策集合u3/x4x3t/tf3(

)u’3()defr3(x3,u3)+f4(x4)

f3()計算表+0+0+0ttt574574示例(5.2-5)u2/x3x2d/de/ef/ff2(

)u’2()abcr2(x2,u2)+f3(x3)

f2()計算表+5+5+5+7+7+4+474564568109fdd示例(5.2-6)u1/x2x1a/ab/bc/cf1(

)u’1()sr1(x1,u1)+f2(x2)

f1()計算表+8+10+998716c示例(5.2-7)通過狀態(tài)轉(zhuǎn)移方程順序求出最優(yōu)決策序列和最優(yōu)路線R*=f1(s

)=16，x1*=su1*(x1*

)=u1’(s

)=c，x2*=cu2*(x2*

)=u2’(c

)=d，x3*=du3*(x3*

)=u3’(d

)=t，x4*=t示例(5.2-8)sabcdeft9877456456754x1x2x3x4f4()u3,f3()u2,f2()u1,f1()End,0t,5t,7t,4f,8d,10d,9c,16示例(5.3-1)路線圖如下所示，箭頭表示通行方向，線上數(shù)字表示道路長度，試求s到t的最短路線sabcdt9865242443示例(5.3-2)該問題是一個無循環(huán)的不定步數(shù)問題，從s到t的路線最少可以經(jīng)過3步，最多可以經(jīng)過5步這樣的問題，可以劃分為5個(或3個)階段來處理，其中允許某個階段原地不動階段1：決定由s到a或是b階段2：決定是到a、c或是d階段3：決定是到c、d或是t階段4：決定是到d或是t階段5：到t示例(5.3-3)狀態(tài)變量xk設(shè)為k階段初始所在地x1∈{s}，x2∈{a,b}，x3∈{a,c,d}，x4∈{c,d,t}，x5∈{d,t}，x6∈{t}k階段決策uk是決定下一步走到哪里，有u1∈{a,b}u2(a)∈{c,d}，u2(b)∈{a,c,d}u3(a)∈{c,d}，u3(c)∈{d,t}，u3(d)∈{t}u4(c)∈{d,t}，u4(d)∈{t}，u4(t)∈{t}u5(d)∈{t}，u5(t)∈{t}u6∈{t}示例(5.3-4)狀態(tài)轉(zhuǎn)移方程xk+1=uk階段效應(yīng)rk(xk

,uk

)

取為從xk

走到uk

的路線長度，如r1(s

,a)

=9貝爾曼函數(shù)

fk(xk

)定義為從xk

走到

t的最短路線貝爾曼方程示例(5.3-5)通過貝爾曼方程逆序求出條件最優(yōu)目標函數(shù)值集合和條件最優(yōu)決策集合u5/x6x5t/tf5(

)u’5()dtr5(x5,u5)+f6(x6)

f5()計算表+0+0tt4040示例(5.3-6)u4/x5x4d/dt/tf4(

)u’4()cdtr4(x4,u4)+f5(x5)

f4()計算表+4+4+0+03040240td/tt+02示例(5.3-7)u3/x4x3c/cd/dt/tf3(

)u’3()acdr3(x3,u3)+f4(x4)

f3()計算表+2+2+4+4+4+0+06203504824cc/td/t示例(5.3-8)u2/x3x2a/ac/cd/df2(

)u’2()abr2(x2,u2)+f3(x3)

f2()計算表+8+8+2+4054284a/cc+2+464示例(5.3-9)u1/x2x1a/ab/bf1(

)u’1()sr1(x1,u1)+f2(x2)

f1()計算表+4+49812b示例(5.3-10)通過狀態(tài)轉(zhuǎn)移方程順序求出最優(yōu)決策序列和最優(yōu)路線R*=f1(s

)=12，x1*=su1*(x1*

)=u1’(s

)=b，x2*=bu2*(x2*

)=u2’(b

)=c，x3*=cu3*(x3*

)=u3’(c

)=c/t，x4*=c/tu4*(x4*

)=u4’(c/t

)=t，x5*=tu5*(x5*

)=u5’(t

)=t，x6*=t示例(5.3-11)sabcdt9865242443End,0t,4t,2c,8c,4b,12示例(5.4-1)路線圖如下所示，箭頭表示通行方向，線上數(shù)字表示道路長度，試求s到t的最短路線sabcdt5839149543示例(5.4-2)該問題是一個有循環(huán)的不定步數(shù)問題，循環(huán)一圈的路線長度為8若有一條從起點到終點經(jīng)過循環(huán)上頂點或邊但無循環(huán)的路線只要該循環(huán)的路線長度為非負值，只走該路線必定比走該路線且循環(huán)幾圈的路線總長度要小或等若該循環(huán)的路線長度為負值，只要走一圈循環(huán)其路線總長度就減少一些，這種情況下無最短路線不算循環(huán)，從s到t的路線最少可以經(jīng)過3步，最多可以經(jīng)過5步示例(5.4-3)這樣的問題，可以劃分為3個階段來處理，其中允許第2個階段走2或3條邊階段1：決定由s到a或是b階段2：決定由a或b經(jīng)過某條路線到c或d階段3：由c或d到t狀態(tài)變量xk設(shè)為k階段初始所在地x1∈{s}，x2∈{a,b}，x3∈{c,d}，x4∈{t}示例(5.4-4)k階段決策uk是決定下面要走的路線以及下一步走到哪里，有u1∈{a,b}u2(a)∈{c,d,cd,cbd}，u2(b)∈{d,ad,ac,acd}u3∈{t}示例(5.4-5)狀態(tài)轉(zhuǎn)移方程xk+1=k階段的目的地階段效應(yīng)rk(xk,uk

)

取為從uk

中所走路線的長度，如r2(b

,ac)

=7貝爾曼函數(shù)

fk(xk

)定義為從xk

走到

t的最短路線貝爾曼方程示例(5.4-6)通過貝爾曼方程逆序求出條件最優(yōu)目標函數(shù)值集合和條件最優(yōu)決策集合x4x3t/tf3(

)u’3()cdr3(x3,u3)+f4(x4)

f3()計算表+0+0tt9595示例(5.4-7)x3x2cdf2(

)u’2()abr2(x2,u2)+f3(x3)

f2()計算表+9+9+5+53674119cdd示例(5.4-8)x2x1abf1(

)u’1()sr1(x1,u1)+f2(x2)

f1()計算表+11+95816a示例(5.4-9)通過狀態(tài)轉(zhuǎn)移方程順序求出最優(yōu)決策序列和最優(yōu)路線R*=f1(s

)=16，x1*=su1*(x1*

)=u1’(s

)=a，x2*=au2*(x2*

)=u2’(a

)=cd，x3*=du3*(x3*

)=u3’(d

)=t，x4*=t示例(5.4-10)sabcdt5839149543End,0t,5d,8d,9cd,11a,16動態(tài)規(guī)劃應(yīng)用舉例(2)資源分配問題：設(shè)有某種資源，總量為M，可以投入n種生產(chǎn)活動。已知用于生產(chǎn)活動k的資源為uk

時的收益是gk(uk

)，問應(yīng)如何分配資源才能使n種生產(chǎn)活動的總收益最大？該問題用分為兩種情況uk

連續(xù)變化，gk(uk

)是線性函數(shù)時，該問題是線性規(guī)劃問題gk(uk

)不是線性函數(shù)時，該問題是非線性規(guī)劃問題，可以利用動態(tài)規(guī)劃方法求解示例(5.5-1)某公司擬將50萬元資金投放下屬的A、B、C三個部門，各部門在獲得資金后的收益如下表所示，試求總收益最大的投資分配方案投放資金(十萬元)012345收益(萬元)A01520252830B0010254570C01020304050示例(5.5-2)該問題可以作為