動態(tài)規(guī)劃與最優(yōu)控制模

#第四章最優(yōu)控制模型管理、決策方面應(yīng)用，因此可說管理決策模型)§1最優(yōu)控制的問題提法：§1.1最優(yōu)控制問題舉例、例，詳見最優(yōu)控制課聽課筆記第一節(jié)；§1.2最優(yōu)控制數(shù)學(xué)模型最優(yōu)控制模型問題的數(shù)學(xué)描述――最優(yōu)控制模型。尋找u*(t)eU(開，閉)[t,tIt可以固定或自由，使得:0ffJtu*(t)]=minJtu(t)]ueUs.t3=f(x(t),u(t),t)dts.tx(t)=x00x(t)=x(t)=x00x(t)=xeM='x(t)x(t)eR,ffffg1g2(x(t(x(tf),),tftf)=0其中：X(t)eRn，且x(t)eCl(—階連續(xù)可微)，U(t)eU<Rm,f[x(t),u,t]：向量值函數(shù)，且f(?)對x(t),u(t),t連續(xù)，對x(t),t連續(xù)可微。Jtu(t)1=?(x(t),t)+fL(x(t),u(t),t)dt,fft0沁(t」t」L[x(t),u(t),t1對x(t),t都可微。上述最優(yōu)控制的離散模型：求｛u*(i),x*(i)｝，使得目標泛函：J=±iL(x(i),u(i),i)達到最小。i=0而且滿足：x(k+x(k+1)=f(x(k),u(k),k)狀態(tài)方程：4x(0)=x0x(k)eMf最優(yōu)控制問題的求解方法：古典變分法：u開集；極大值原理：U閉集；現(xiàn)代變分法，把古典變分法看作特例動態(tài)規(guī)劃：便于數(shù)值計算，并有通用算法；發(fā)展了變分法，結(jié)果是充分條件。§2最優(yōu)控制模型的動態(tài)規(guī)劃解法§2.1動態(tài)規(guī)劃方法概述§2.2生產(chǎn)——庫存——銷售管理系統(tǒng)的動態(tài)規(guī)劃解法§2.1動態(tài)規(guī)劃方法概述某一類管理問題的數(shù)學(xué)模型(狀態(tài)方程)是一個差分方程x(k+1)=f(x(k),u(k),k)狀態(tài)方程：x(0)=x0x(k)eMf目標泛函：J=VL(x(i),u(i),i)達到最小。二0即：此為一個N階決策問題：動態(tài)規(guī)劃法是求這一決策問題的有效辦法，具有明顯優(yōu)點：將一個N階決策問題轉(zhuǎn)化為多次一步?jīng)Q策問題，即數(shù)學(xué)上的嵌入原理——將求一條極值曲線問題，嵌入到求一族極值曲線的更廣泛的類似問題中；大大簡化了計算量；具有局部優(yōu)，就是整體優(yōu)的最優(yōu)性原理：可廣泛應(yīng)用于運輸系統(tǒng)、生產(chǎn)庫存管理系統(tǒng)、生產(chǎn)計劃制定及最優(yōu)投資分配問題、最優(yōu)價格制定問題。下面以最短路問題舉例說明這種方法一、最短路問題(最小時間問題)1問題：若有一輛汽車以S城出發(fā)經(jīng)過若干城市到達F城，如圖：P,Q,i=1,2,3，ii是一些可以通過的城鎮(zhèn)。圖中兩點間的數(shù)字：可以表示兩城鎮(zhèn)之間的距離(單位10公里)，也可以表示行駛兩城鎮(zhèn)所用時間(應(yīng)綜合考慮：距離遠近，路面好壞，是否擁擠等情況)。

于是：汽車從S到F可經(jīng)多種途徑選擇到達F。問題是：從多種途徑選擇方案中，決定一種使S到F所走路線最短?；蛘呷魣D中數(shù)字表示時間，則決定一種路徑使從S到F所用時間最短。2．方法：I.決策樹法（窮舉法）：決策樹法是最容易想到的一種方法，但運算量很大——即把所有可能選擇的路途所用的時間都求出來，然后取最小值，即有最優(yōu)策略（最優(yōu)決策）。即：SPi*即：SPi*Q*F=mini{sPQFi=1,2,3}ii因此有：因此有：1514161514131817因此，最終得出：SQPPF=min{SPQF|i=1,2,3}123ii困難：這樣共有8條線路可選擇，每條線路要作3次運算。第1次：STP/QTP/QTQ；第2次：P/QTP/Q112222233第3次：P或QTF33因此，共需24次運算：8X3=24次，若階段更多，則計算量更大。II?“走一步瞧一步”（瞎子爬山？近視眼？）法：第一步：從S到P或Q:顯然SP=4<SQ=5，因此取決策SP；11111第二步：從P到P或Q:顯然PP=6=PQ，因此取PP,QQ均可，但從P到122121212122P或Q距離為1,而Q到PP距離為2,因此，第2步?jīng)Q策為P,因此取PP；33223212第三步：P到P或P到Q，均有PP=PQ=1，但Q到F的距離為3,因此第332323233步取路線PQ。23

因此使用這種方法得到的決策為：SPPQF=4+6+1+3=14123顯然不是“最優(yōu)決策”，同時還有：SQPPF=14123問題出現(xiàn)在“局部優(yōu)不能代替整體優(yōu)”的問題。III.動態(tài)規(guī)劃：即可把每一步?jīng)Q策都看成一個狀態(tài)的轉(zhuǎn)移，而每一種狀態(tài)的轉(zhuǎn)移又影響到下一階段的狀態(tài)，因此又是動態(tài)的，故稱為動態(tài)規(guī)劃法。將上述問題分為四個階段的多階決策問題，故可將問題分為四階段問題來考慮：第一階段問題：StP/Q11第二階段問題：第一階段問題：StP/Q111122tFtF解題方法從最后一個階段開始：1°分別計算P,Q至UF的最小代價，此處花費代價為時間，記為J，用J[p1J[Q]分別333表示P或Q到F的代價，則顯然有:33J*[P1=4J*[Q1=3332°由后往前，考慮倒數(shù)第二階段（即第三階段），再把第三階段和第四階段聯(lián)合作為一個子問題來考慮，若從P出發(fā)到F，則有兩種可能:2PPF23PQF23J=1+J*[P3]=1+4=5J=2+J*Iq]=1+3=43線路PQF最短，且J*[P]=4，故將線路PQF記成P2?Q32322323類似以Q出發(fā)到F，則有兩種可能:2Q2P3FJ=2+J[P3]=2+4=6、QQFJ=2+J[q]=2+3=5233線路QQF最短’貝Uj=J*[q]=5'故將線路QQF記成Q⑤Q2322323.3°再由2、3、4這三個階段構(gòu)成的子問題：若從P出發(fā)到F有兩種可能：1PPF12PQF12J=6+J*[P2]=6+4=610J=6+J*[Q]=6+5=112有線路ppF最短，且J*[P]=10，故將PPF記成：P⑩P1211212若從Q出發(fā)到F有兩種可能:1QPF12QQF12J=4+J*[P2]=4+4=8J=7+J*[Q]=7+5=12

2...有線路QPF最短，則J*[Q]=8，故將QPF記成：Q⑧P12112124°把由1、2、3、4階段作為子問題來考慮：從S出發(fā)到F有兩種可能:sPF1SQF1且J=4+J*4+10=14且J=5+J*[Q]=5+8=131故：SQ1315°因此有最優(yōu)策略：SQF1即：SQF=SQPQF，J*[S]=131123s@第1階段第2階段第3階段第4階段除“二決一”比較之外，且運算只用了10次，而窮舉法則算了24次，上次這種動態(tài)規(guī)劃的辦法：是將把一個四階段決策問題化為四個互相嵌入子問題，逐一進行簡化的計算方法，即數(shù)學(xué)上嵌入定理。IV.最優(yōu)性原理“最優(yōu)策略的一部分也是最優(yōu)策略”例如：上例中知：SQPQF是最優(yōu)決策，則QPQF也一定是從Q]出發(fā)到F的最優(yōu)1231231決策：證明[反證法]:設(shè)SQ]P2Q3F是最優(yōu)決策，則Q]P2Q3F不是最優(yōu)決策，則必存在另一個最優(yōu)決策，不妨設(shè)為Q1Q2Q3F為最優(yōu)決策。因而，SQ1Q2Q3F是整體最優(yōu)決策，因而與SQ]P2Q3F是最優(yōu)決策相矛盾，因而原結(jié)論正確。一般有最優(yōu)性原理；如果u*(0),u*(1),…,u*(N-1)是N階決策問題的最優(yōu)策略序列，那么：u*(l),…,u*(N-1)也是一個最優(yōu)策略序列，其初始狀態(tài)為：x(1)=f(x(0),u*(0))證明：同最短路.4．多階段決策問題的一般想法：設(shè)某系統(tǒng)的狀態(tài)方程為：fx(i+1)=f(x(i),u(i),i)x(0)=x設(shè)某系統(tǒng)的狀態(tài)方程為：0目標函數(shù)為：J=±-1L(x(i),u(i),i)，J表示控制N步時的目標函數(shù)值。NNi=0最優(yōu)控制問題，即：求最優(yōu)決策序列｛u*(i)｝=缶*(0),…,u(N-1)｝，使J取最小(大)N值。為簡化假定為定常狀態(tài)，即L不明顯還有時間變量ifx(i+1)=f(x(i),u(i))(1)因而有：＜1x(0)=x0(2)J=SL(x(i),u(i))Ni=0(3)對目標函數(shù)(3)逐次應(yīng)用(1)式有：JN=L(x(0),u(0))+L(x(1),u(1))+…+L(x(N—1),u(N—1)),=L(x(0),u(0))+L(f(x(0),u(0)),u(1)),+???+L(f(f(…(f(x(0),u(0)),u(1))???,u(N—2),u(N—1))))因此，可以由上式看出：J只依賴于：x(0),u(1),…,u(N-1)N因而可寫成：J=J(x(0),u(1),…,u(N—1))又若用某種方法求出了最優(yōu)決策：u*(0),…,u*(N-1)，貝l」J的最小值只依賴于初N始值x(0)，記為J*(x(0))，它可用下式來定義：NJ*(x(0))=minJ(x(0),u(l),…，u(N一1))Nu(0),u(1),…，u(N-1)N初始值是可變化的，因此：J*(x(0))表示初始狀態(tài)為x(0)時，控制N步的目標函數(shù)最小值。N5．動態(tài)規(guī)劃的基本方程：動態(tài)規(guī)劃的基本方程，給出N階決策問題的目標函數(shù)最優(yōu)值與它的子問題(N-1階決策問題)目標函數(shù)最優(yōu)值之間的遞推關(guān)系式，它是用動態(tài)規(guī)劃解一切多階決策問題的基礎(chǔ)。設(shè)u*(0)已求出，則求序列｛u*(1),u*(2),…,u*(N-1)｝的問題，構(gòu)成一個以x⑴二f(x(0),u(0))為初始條件的N-1階決策問題，若記這一子問題的目標函數(shù)最小值為：J*(x(1))；又若記J*(x(0))為N階決策問題最小值，則我們可以導(dǎo)出J*(x(0))N-1NN與J*(x(1))之間的關(guān)系：N-1由于J*(x(0))=minL(x(k),u(k))|NTOC\o"1-5"\h\zu(0),u(1),…,u(N-1)I0Jk—0=min<L(x(0),u(0))+Sl(x(k),u(k))]u(0)-u(N-1)〔k—1則第一項：minL(x(0),u(0))—minL(x(0),u(0))u(0),…,u(N-1)u(0)第二項：min<士L(x(k),u(k))>并不明顯依賴u(0)，u(0),u(1)…,u(N-1)〔k—1J但由狀態(tài)方程：x(1)—f(x(0),u(0))x(N-1)—f(x(N-2),u(N-2))可知：實際上第二項仍依賴于u(0),u(1),…,u(N-1)，因此，第二項可寫成：min￡L(x(k),u(k))u(0),…,u(N-1)、k=0丿=min<mm為L(x(k),u(0)u(k))>=minu(0)u(1)，…，u(N-1)N-1因此有：動態(tài)規(guī)劃基本方程:J*(x(0))=min(x(0),u(0))+J*(x(1))^NN-1…21u(0此給出了J*(x⑴)與J*(x(0))之間的遞推關(guān)系。它是動態(tài)規(guī)劃的基本方程。N-1N類似有動態(tài)規(guī)劃更一般的基本方程：J*(x(i))=min(x(i),u(i))+J*(x(i+1))^(**)N—iN-i-1I1因此依據(jù)基本遞推方程的遞推關(guān)系：可以把一個多階決策問題化為若干個子問題，而在決策的每一個階段中只須對一個變量進行最優(yōu)化決策即可。例如：J*(x(N-1))=min￡(x(N-1),u(N-1))}1u(N-1)是對一個單變量u(N-1)的優(yōu)化問題，當J*(x(N-1))求出后，由基本遞推方程(**)式可得:1J*(x(N-2))=min￡(x(N-2),u(N-2))+J*(x(N-1))}

2u(N-2)1這又是對u(N-2)的最優(yōu)化決策問題，因而把原來N階決策問題化成一系列對單變量的最優(yōu)化決策問題，從而使問題簡化?！?.2生產(chǎn)庫存——庫存管理決策問題的解設(shè)某工廠生產(chǎn)某種產(chǎn)品，四個季度定貨量為：一季一季二季四季600件700件500件1200件生產(chǎn)費用與產(chǎn)品平方成正比，即比例系數(shù)為0.005，C(x)=0.005u2(元)庫存費每件每季為：1.0元。第i季度庫存量為：x(i)件；第i季度生產(chǎn)量為：u(i)件；第i季度銷售量為：s(i)=定貨量一季一季二季四季600件700件500件1200件因此有：下季度庫存是：x(i+1)=本季度庫存量是x(i)+本季生產(chǎn)量u(i)—本季銷售量S(i)且要求年初、年終都沒有存貨即銷售已空。x(0)=x(5)=0最優(yōu)管理問題：求每季度的最優(yōu)生產(chǎn)量u(1),u(2),u(3),u(4)，使之能正好完成訂貨計劃且使生產(chǎn)費與庫存費總和最小。即：求｛u*(i)｝使Jlu*(i)Jlu*(i)]<J04i二11.005u2(i)+x(i)1)fx(i+1)=fx(i+1)=x(i)+u(i)-s(i)i=1,2,3,4s.t\x(0)=0|x(5)=0解：使用動態(tài)規(guī)劃的辦法：(2)(3)(4)先由最后一個季度考慮起：J=0.005u2(4)+x(4)1由(2)x(4+1)=x(4)+u(4)-s(4)及(4)x(5)=0得0=x(4)+u(4)—(4)—1200得u*(4)=1200-x(4)代入(1)J*[x(4)]=0.005(1200-x(4))2+x(4)=7200-11x(4)+0.005x2(4)4再考慮3－4兩個季度，由基本遞推方程知：其中即有J*(x(3))=min(3),u(3))其中即有J*(x(3))=min(3),u(3))+J*[x(4)卩21u(3)=min{.005u2(3)+x(3)+J*(x(4)Pu(3)1=min{.005u2(3)+x(3)+7200-11x(4)+0.005x2(4)^u(3)x(4)=x(3)+u(3)-s(3)=x(3)+u(3)-500代入上式J*(x(3))=2min0.005u2(3)+x(3)+7200u(3)-11(x(3)+u(3)-500)+0.005(x(3)+u(3)-500)2而u(3)應(yīng)使上式取最小值，因此有:Q{?}/du(3)=0即：即：即有凡}=0.02u(3)-16+0.01x(3)=0du(3)u*(3)=80-00.5x(3)為使u*(3)>0，必須有x(3)<1600，把u*(3)代入J*(x(3))2J*x(3))=0.005u*(3)+x(3)+7200-11(x(3)+u*(3)-500)+0.005(x(3)+u*(3)-500)22=7550-7x(3)+0.0025x2(3)

(2),u(2))+J*(x(3)/(2),u(2))+J*(x(3)/J*(x(2))=3minu(2)—7x(3)+0.0025x2(3)min0.005u2—7x(3)+0.0025x2(3)u(2)其中x(3)=其中x(3)=x(2)+u(2)-700代入上式J*(x(2))3J*(x(2))=3min{.005u2(2)+x(2)+7550-7(x(2)-u(2)-700)+0.0025(x(2)J*(x(2))=3u(2)aj*(x(2))/au(2)=0得ajaj*(x(2))a{?}——3—au(2)=0.015u(2)-7+0.005(x(2)-700)=0au(2)u*(2)=701-x(2)3再代J*(x(2))得30.005J*(x(2))=10,000-6x(2)+334.再考慮1—2—3—4季度，由遞推基本方程知：min((x(1),u(1