動(dòng)態(tài)優(yōu)化模型(完整版)PPT課件

動(dòng)態(tài)優(yōu)化模型（完整版）,連續(xù)動(dòng)態(tài)過(guò)程的優(yōu)化歸結(jié)為求泛函的極值.,求泛函極值的常用方法:變分法、最優(yōu)控制論.,離散動(dòng)態(tài)過(guò)程的優(yōu)化動(dòng)態(tài)規(guī)劃模型.,靜態(tài)優(yōu)化問(wèn)題,優(yōu)化目標(biāo)是數(shù)值,最優(yōu)策略是數(shù)值,函數(shù)對(duì)應(yīng)的數(shù)值稱(chēng)為泛函(函數(shù)的函數(shù)).,動(dòng)態(tài)優(yōu)化問(wèn)題,優(yōu)化目標(biāo)是數(shù)值,最優(yōu)策略是函數(shù),1速降線與短程線,通過(guò)兩個(gè)古典問(wèn)題介紹變分法的基本概念,給出主要結(jié)果.,速降線問(wèn)題,給定豎直平面內(nèi)不在一條垂直線上的兩個(gè)點(diǎn)A,B,求連接A,B的光滑曲線，使質(zhì)點(diǎn)在重力作用下沿該曲線以最短時(shí)間從A滑到B(摩擦力不計(jì)).,.A,.B,若沿陡峭曲線下滑,雖路徑加長(zhǎng)，但速度增長(zhǎng)很快.,速降線問(wèn)題,.A,.B,建立坐標(biāo)系xOy,曲線弧長(zhǎng),能量守恒,質(zhì)點(diǎn)在曲線y(x)上的速度ds/dt,質(zhì)點(diǎn)沿曲線y(x)從A到B的時(shí)間,求y(x)使J(y(x)達(dá)到最小.,m質(zhì)點(diǎn)質(zhì)量，g重力加速度,A(0,0),B(x1,y1),曲線ABy=y(x),滿(mǎn)足條件,短程線問(wèn)題,給定曲面上的兩個(gè)點(diǎn)A,B,求曲面上連接A,B的最短曲線.,建立坐標(biāo)系,A(x0,y0,z0),B(x1,y1,z1),曲線的弧長(zhǎng),曲線的長(zhǎng)度,求y=y(x),z=z(x)使J(y(x),z(x)達(dá)到最小.,滿(mǎn)足條件,泛函、泛函的變分和極值,自變量t，函數(shù)x(t),y(t),函數(shù)、函數(shù)的微分和極值,泛函、泛函的變分和極值,1.對(duì)于t在某域的任一個(gè)值,有y的一個(gè)值與之對(duì)應(yīng),稱(chēng)y是t的函數(shù)，記作y=f(t),1.對(duì)于某函數(shù)集合的每一個(gè)函數(shù)x(t),有J的一個(gè)值與之對(duì)應(yīng),稱(chēng)J是x(t)的泛函,記作J(x(t),2.t在t0的增量記作t=t-t0,微分dt=t,2.x(t)在x0(t)的增量記作x(t)=x(t)-x0(t)，x(t)稱(chēng)x(t)的變分,3.y在t0的增量記作f=f(t0+t)-f(t0)，f的線性主部是函數(shù)的微分,記作dy，dy=f(t0)dt,3.泛函J(x(t)在x0(t)的增量記作J=J(x0(t)+x(t)-J(x0(t),J的線性主部稱(chēng)泛函的變分,記作J(x0(t),泛函、泛函的變分和極值,函數(shù)、函數(shù)的微分和極值,泛函、泛函的變分和極值,4.若函數(shù)y在域內(nèi)t點(diǎn)達(dá)到極值，則在t點(diǎn)的微分dy(t)=0,4.若泛函J(x(t)在函數(shù)集合內(nèi)的x(t)達(dá)到極值,則在x(t)的變分J(x(t)=0,5.y在t的微分的另一表達(dá)式,5.泛函J(x(t)在x(t)的變分可以表為,泛函J(x(t)在x(t)達(dá)到極值的必要條件,歐拉方程(最簡(jiǎn)泛函極值的必要條件),最簡(jiǎn)泛函,F具有二階連續(xù)偏導(dǎo)數(shù)，x(t)為二階可微函數(shù),固定端點(diǎn)條件下的泛函,J(x(t)在x(t)達(dá)到極值的必要條件:,x(t)滿(mǎn)足二階微分方程,兩個(gè)任意常數(shù)由確定,歐拉方程,用歐拉方程解速降線問(wèn)題,求y(x)使達(dá)到最小,且,歐拉方程,圓滾線方程,c2=0,c1由y(x1)=y1確定.,橫截條件(變動(dòng)端點(diǎn)問(wèn)題),容許函數(shù)x(t)的一個(gè)端點(diǎn)固定:x(t1)=x1，另一個(gè)端點(diǎn)在給定曲線x=(t)上變動(dòng):x(t2)=(t2)(t2可變).,歐拉方程在變動(dòng)端點(diǎn)的定解條件,x=(t)垂直于橫軸(t2固定),x=(t)平行于橫軸,包含多個(gè)未知函數(shù)泛函的歐拉方程,歐拉方程,泛函的條件極值,最優(yōu)控制問(wèn)題:u(t)控制函數(shù),x(t)狀態(tài)函數(shù)(軌線).,泛函的條件極值,用拉格朗日乘子化為無(wú)條件極值,歐拉方程,由方程組和端點(diǎn)條件解出最優(yōu)控制u(t)和最優(yōu)軌線x(t).,Hamilton函數(shù),2生產(chǎn)計(jì)劃的制訂,問(wèn)題,生產(chǎn)任務(wù)是在一定時(shí)間內(nèi)提供一定數(shù)量的產(chǎn)品.,生產(chǎn)費(fèi)用隨著生產(chǎn)率(單位時(shí)間的產(chǎn)量)的增加而變大.,貯存費(fèi)用隨著已經(jīng)生產(chǎn)出來(lái)的產(chǎn)量的增加而變大.,生產(chǎn)計(jì)劃用每一時(shí)刻的累積產(chǎn)量表示.,建模目的,尋求最優(yōu)生產(chǎn)計(jì)劃,使完成生產(chǎn)任務(wù)所需的總費(fèi)用(生產(chǎn)費(fèi)用與貯存費(fèi)用之和)最小.,分析與假設(shè),生產(chǎn)任務(wù):t=0開(kāi)始生產(chǎn),t=T提供數(shù)量為Q的產(chǎn)品.,生產(chǎn)計(jì)劃(累積產(chǎn)量):x(t),生產(chǎn)率(單位時(shí)間產(chǎn)量):,生產(chǎn)費(fèi)用,貯存費(fèi)用,總費(fèi)用,生產(chǎn)率提高一個(gè)單位的生產(chǎn)費(fèi)用與生產(chǎn)率成正比,貯存費(fèi)用與貯存量成正比,模型與求解,求x(t)(0,0tT)使C(x(t)最小.,歐拉方程,考察x(t)0(0tT)的條件,只有當(dāng)生產(chǎn)任務(wù)Q足夠大時(shí)才需要從t=0開(kāi)始生產(chǎn).,若怎么辦?,模型解釋,最優(yōu)生產(chǎn)計(jì)劃,滿(mǎn)足方程,邊際成本,生產(chǎn)費(fèi)用,貯存費(fèi)用,邊際貯存,最優(yōu)生產(chǎn)計(jì)劃在邊際成本的變化率等于邊際貯存時(shí)達(dá)到.,生產(chǎn)計(jì)劃的制訂,最優(yōu)生產(chǎn)計(jì)劃的目標(biāo)函數(shù)只考慮生產(chǎn)費(fèi)用與貯存費(fèi)用,并對(duì)這兩種費(fèi)用作了最簡(jiǎn)單的假設(shè).,對(duì)于泛函極值問(wèn)題用古典變分法求解,得到最優(yōu)生產(chǎn)計(jì)劃x(t)(累積產(chǎn)量)為二次函數(shù).,實(shí)際條件x(t)0導(dǎo)致對(duì)已知參數(shù)的要求:,對(duì)函數(shù)施加的閉約束,如對(duì)生產(chǎn)率的限制可能導(dǎo)致古典變分法的失敗.,若參數(shù)不滿(mǎn)足該要求怎樣處理?,3國(guó)民收入的增長(zhǎng),背景和問(wèn)題,國(guó)民經(jīng)濟(jì)收入的來(lái)源:擴(kuò)大再生產(chǎn)的積累資金,滿(mǎn)足人民生活需要的消費(fèi)資金.,如何安排積累資金和消費(fèi)資金的比例，使國(guó)民經(jīng)濟(jì)收入得到最快的增長(zhǎng).,從最優(yōu)控制的角度討論十分簡(jiǎn)化的模型.,一般模型,國(guó)民經(jīng)濟(jì)收入x(t)，其中用于積累資金的部分y(t),求最優(yōu)積累率使國(guó)民收入x(t)在時(shí)間T內(nèi)增長(zhǎng)最快.,積累率u(t)=y(t)/x(t),國(guó)民收入增長(zhǎng)率,對(duì)偶等價(jià),泛函條件極值,哈密頓函數(shù),求解最優(yōu)控制函數(shù)u(t)和最優(yōu)狀態(tài)x(t).,簡(jiǎn)化模型,假設(shè),討論函數(shù)f的具體、簡(jiǎn)化形式,描述以上假設(shè)的最簡(jiǎn)模型,國(guó)民收入相對(duì)增長(zhǎng)率,積累率u較小時(shí)隨u的增加而增加積累資金擴(kuò)大再生產(chǎn)的促進(jìn)作用.,隨著u的變大的增加變慢.,u增加到一定程度后反而減小消費(fèi)資金太少對(duì)國(guó)民收入的制約作用.,模型求解,對(duì)于最簡(jiǎn)模型不必解泛函極值問(wèn)題,可以直接得到u=a/2b時(shí)最大.,使國(guó)民收入x(t)增長(zhǎng)最快的最優(yōu)積累率是常數(shù)u=a/2b,結(jié)果解釋,4漁船出海,背景和問(wèn)題,繼續(xù)討論開(kāi)發(fā)漁業(yè)資源的最大經(jīng)濟(jì)效益模型.,用出海漁船數(shù)量表示捕撈強(qiáng)度,作為控制函數(shù).,當(dāng)漁場(chǎng)魚(yú)量增長(zhǎng)到一定數(shù)量后才出海捕撈.,用特殊形式的控制函數(shù)將動(dòng)態(tài)優(yōu)化問(wèn)題化為普通的函數(shù)極值.,模型假設(shè),x(t)的自然增長(zhǎng)服從Logistic規(guī)律,單位時(shí)間捕撈量與u(t),x(t)成正比.,當(dāng)t時(shí)才派漁船出海,且u(t)=U(常數(shù)).,魚(yú)的出售單價(jià)為p,每只漁船單位時(shí)間費(fèi)用為c,折扣因子(通貨膨脹率)為.,漁場(chǎng)魚(yú)量x(t),漁船數(shù)量u(t),x(0)=N/K(K很大),t時(shí)x(t)保持穩(wěn)定.,建模與求解,泛函極值問(wèn)題,目標(biāo)函數(shù):捕魚(yú)業(yè)的長(zhǎng)期效益,函數(shù)極值問(wèn)題,建模與求解,目標(biāo)函數(shù):捕魚(yú)業(yè)的長(zhǎng)期效益,b(1)費(fèi)用-價(jià)格比的下界,模型解釋,最優(yōu)解應(yīng)在邊際收益等于邊際損失時(shí)達(dá)到,單位時(shí)間利潤(rùn),短期利潤(rùn)的增加:,長(zhǎng)期收益的減少:,漁船出海,以漁船數(shù)量u(t)為控制函數(shù)的最大效益模型泛函極值.,假定u(t)的特殊形式,化為函數(shù)極值.,u(t)假定的合理性:泛函極值問(wèn)題的解正是取這種形式.,最優(yōu)解在邊際收益等于邊際損失時(shí)達(dá)到,是短期利益與長(zhǎng)期利益取得折中的結(jié)果.,5賽跑的速度,背景和問(wèn)題,將賽程分成若干階段,根據(jù)賽跑運(yùn)動(dòng)員的生理?xiàng)l件對(duì)各階段的速度作最恰當(dāng)?shù)陌才?以期獲得最好的成績(jī).,Keller提出一個(gè)簡(jiǎn)單模型(1974),根據(jù)4個(gè)生理參數(shù)從最優(yōu)控制的角度確定各階段的速度函數(shù),并可以預(yù)測(cè)比賽成績(jī).,尋求速度安排的最佳策略是復(fù)雜的生理力學(xué)問(wèn)題.,問(wèn)題分析,運(yùn)動(dòng)員在賽跑中要克服體內(nèi)外的阻力以達(dá)到和保持一定速度,需要發(fā)揮向前的沖力.,這些能量怎樣分配到賽跑的各個(gè)階段,并在到達(dá)終點(diǎn)前將其全部用完.,為沖力作功提供能量的來(lái)源:賽跑前貯存在體內(nèi)的能量,賽跑中通過(guò)氧的代謝作用產(chǎn)生的能量.,模型要確定的3個(gè)關(guān)系:,沖力與速度,沖力作功與能量來(lái)源,速度與比賽成績(jī),將最佳成績(jī)歸結(jié)成以距離為目標(biāo),與速度、沖力、能量等函數(shù)有關(guān)的極值問(wèn)題.,模型假設(shè),賽跑中體內(nèi)外的阻力與速度成正比,比例系數(shù)-1,賽跑中在氧的代謝下單位時(shí)間產(chǎn)生的能量是常數(shù),賽跑前貯存在體內(nèi)供賽跑的能量是常數(shù)E0,運(yùn)動(dòng)員能發(fā)揮的最大沖力是F,運(yùn)動(dòng)員具有單位質(zhì)量，初速為零.,比賽成績(jī)：“一定距離下時(shí)間最短”等價(jià)為“一定時(shí)間內(nèi)距離最大”.,一般模型,以速度v(t)在時(shí)間T內(nèi)跑完賽程D,阻力與速度成正比,比例系數(shù)-1,單位質(zhì)量運(yùn)動(dòng)員，初速為零,運(yùn)動(dòng)員的最大沖力是F,單位時(shí)間產(chǎn)生的能量是,賽跑前貯存的能量是E0,運(yùn)動(dòng)員賽跑速度v(t),體內(nèi)能量E(t),D固定,求v(t)使T最小,以D(v(t)為目標(biāo)的泛函條件極值(,F,E0為已知參數(shù)),短跑模型,用最大沖力F跑全程,可取得最好成績(jī),最長(zhǎng)的短跑賽程以體內(nèi)能量E(t)不小于零為標(biāo)準(zhǔn),v小E增加,v大E減少,最遠(yuǎn)距離(最長(zhǎng)的短跑賽程)為,短跑模型,Keller根據(jù)當(dāng)時(shí)的世界記錄得到F,的估計(jì)值:,后來(lái)根據(jù)1987年約翰遜的百米成績(jī)(9.83s)修正參數(shù):,估計(jì)用最大沖力跑全程時(shí)最長(zhǎng)的短跑賽程,中長(zhǎng)跑模型,當(dāng)賽程超過(guò)Dc時(shí)不能用最大沖力跑全程,將賽程分為3個(gè)階段:,初始階段(0tt1)用最大沖力跑,在短時(shí)間獲得高速度.,中間階段(t1tt2)保持勻速.,最后階段(t2tT)把體內(nèi)能量用完,靠慣性沖刺.,問(wèn)題:確定t1,t2及3個(gè)階段的速度v1(t),v2(t),v3(t),中長(zhǎng)跑模型,初始階段用最大沖力跑,與短跑模型相同,t1待定,最后階段把體內(nèi)能量用完,E(t)=0,中間階段保持勻速,t2,v2待定,中長(zhǎng)跑模型,中間階段,在條件E(t2)=0下求v(t)使D(v(t)最大,t1,t2,v2待定,中長(zhǎng)跑模型,引入乘子化為無(wú)條件極值,泛函極值必要條件,確定t1,t2,v2,模型解釋,中長(zhǎng)跑模型3段速度示意圖,賽跑的最佳策略是最后把體內(nèi)能量全部用完,靠慣性沖刺,這必然導(dǎo)致速度的短暫下降,單從賽跑的時(shí)間看(不考慮比賽的策略),這樣做是最優(yōu)的.,Keller對(duì)一般模型提出分段解法,不能證明是最優(yōu)的,但它是合理的簡(jiǎn)化,在將動(dòng)力學(xué)與生理學(xué)相結(jié)合,用建模方法探討體育問(wèn)題上提供了范例.,最后一段(通常一兩秒鐘)速度有所下降,6多階段最優(yōu)生產(chǎn)計(jì)劃,離散動(dòng)態(tài)優(yōu)化問(wèn)題,動(dòng)態(tài)規(guī)劃模型是有效方法,問(wèn)題,考察T個(gè)時(shí)段某產(chǎn)品的生產(chǎn)計(jì)劃,生產(chǎn)準(zhǔn)備費(fèi)c0,單件生產(chǎn)成本k,單件每時(shí)段存貯費(fèi)h0,每時(shí)段最大生產(chǎn)能力Xm,每時(shí)段最大存貯量Im,第1時(shí)段初有庫(kù)存量i1,制訂產(chǎn)品生產(chǎn)計(jì)劃(每時(shí)段產(chǎn)量)使T個(gè)時(shí)段的總費(fèi)用最小,已知需求量dt(t=1,2,T),例T=3,d1=2,d2=1,d3=2,Xm=4,c0=3,k=2,h0=1,Im=3,i1=1,確定需求問(wèn)題,分析與求解,生產(chǎn)費(fèi)用,時(shí)段t初的存貯量it,時(shí)段t+1初的存貯量it+1=it+xt-dt,時(shí)段t的存貯費(fèi)h(it)=h0(it+xt-dt)=it+xt-dt,時(shí)段t的產(chǎn)量xt(t=1,2,3),xtXm=4，itIm=3,需求量dt,準(zhǔn)備費(fèi)c0=3,成本k=2,存貯費(fèi)h0=1,最大生產(chǎn)能力Xm=4,最大存貯量Im=3,將多時(shí)段生產(chǎn)計(jì)劃問(wèn)題簡(jiǎn)化為多個(gè)單時(shí)段問(wèn)題,由后向前分解,時(shí)段3初的存貯量i3,產(chǎn)量x3(i3),最小費(fèi)用f3(i3),1.最后時(shí)段(時(shí)段3),需求量d3=2,f3(0)=c(2)=3+22=7,為使3個(gè)時(shí)段的總費(fèi)用最小，時(shí)段3末的存貯量應(yīng)為0,i3=0,f3(1)=c(1)=3+21=5,f3(2)=c(0)=0,x3(0)=2,i3=1,x3(1)=1,i3=2,x3(2)=0,分析與求解,2.時(shí)段2,需求量d2=1,時(shí)段2初存貯量i2,產(chǎn)量x2(i2),時(shí)段2,3最小費(fèi)用之和,時(shí)段2的費(fèi)用:c(x2)+h(i2),i3=i2+x2-1,1i2+x23,3.時(shí)段1,時(shí)段1初存貯量i1=1,產(chǎn)量x1(i1),需求量d1=2,時(shí)段13最小費(fèi)用之和,時(shí)段1的費(fèi)用:c(x1)+h(i1),i2=i2+x2-2,2i2+x25,f1(1)=15,x1(1)=2,i2=i1+x1-2=1+2-2=1,i3=i2+x2-1=1+0-1=0,最優(yōu)生產(chǎn)計(jì)劃：3個(gè)時(shí)段的產(chǎn)量為x1=2，x2=0，x3=2,x2(i2)=x2(1)=0,x3(0)=2,最短路問(wèn)題,多階段生產(chǎn)計(jì)劃,尋找最短路,2,各路段站點(diǎn):i1=1,i2=0,1,2,3,i3=0,1,2,i4=0,兩站點(diǎn)距離:本時(shí)段生產(chǎn)費(fèi)與存貯費(fèi)之和,路段3各站點(diǎn)到終點(diǎn)的最短距離:f3(i3),路段2各站點(diǎn)到終點(diǎn)的最短距離:f2(i2),路段1站點(diǎn)1到終點(diǎn)的最短距離:f1(1),最短路:i1=1,x1(1)=2i2=1,x2(1)=0i3=0,x3(0)=2i4=0,它的子路徑如i2=1i3=0i4=0也是最短路,確定需求下多時(shí)段(T時(shí)段)生產(chǎn)計(jì)劃的一般模型,最大生產(chǎn)能力Xm,最大存貯量Im,第1時(shí)段初庫(kù)存量i1,需求量dt,產(chǎn)量xt,存貯量it,生產(chǎn)費(fèi)c(xt),存貯費(fèi)h(it),1.根據(jù)對(duì)時(shí)段T末存貯量的要求，確定fT+1(iT+1),2.時(shí)段從后向前地計(jì)算最小費(fèi)用，遞推公式：,f1(i1)為總費(fèi)用最小值,3.時(shí)段從前向后地確定最優(yōu)生產(chǎn)計(jì)劃:由i1,xt(it)及it+1=it+xt(it)-dt得到xt,動(dòng)態(tài)規(guī)劃模型,隨機(jī)需求下的多階段生產(chǎn)計(jì)劃,需求量隨機(jī),存貯量隨機(jī),存貯費(fèi)及總費(fèi)用隨機(jī),優(yōu)化目標(biāo)是總費(fèi)用的期望最小,隨機(jī)動(dòng)態(tài)規(guī)劃模型,隨機(jī)需求:P(dt=1)=1/3,P(dt=2)=2/3(t=1,2,3),存貯費(fèi)的期望值Eh(it)=h0E(it+xt-dt)=(it+xt-1)P(dt=1)+(it+xt-2)P(dt=2)=(it+xt-1)/3+2(it+xt-2)/3=it+xt-5/3,對(duì)于存貯量i3,計(jì)劃結(jié)束時(shí)出售剩余量得到的回報(bào)為s(i3),期望值Es(i3)=1.5(i3+x3-1)/3+2(i3+x3-2)/3=1.5(i3+x3)-2.5,計(jì)劃結(jié)束時(shí)存貯量隨機(jī),假定剩余存貯量以1.5的價(jià)格出售,隨機(jī)需求下的多階段生產(chǎn)計(jì)劃,1.最后時(shí)段(時(shí)段3),時(shí)段3初的存貯量i3,產(chǎn)量x3(i3),期望費(fèi)用最小值f3(i3),Es(i3)=1.5(i3+x3)-2.5,P(dt=1)=1/3,P(dt=2)=2/3,f3(0)=c(2)-Es(0)=7-1/2=13/2,x3(0)=2,f3(1)=c(1)-Es(1)=5-1/2=9/2,x3(1)=1,f3(2)=c(0)-Es(2)=0-1/2=-1/2,x3(2)=0,f3(3)=c(0)-Es(3)=0-2=-2,x3(3)=0,計(jì)算,2.時(shí)段2,時(shí)段2,3期望費(fèi)用最小值,2i2+x24,x2Xm,i2Im,3.時(shí)段1,時(shí)段1初存貯量i1=1,2i1+x14,時(shí)段13期望費(fèi)用最小值,x2(i2)=0,d1=1,i2=1+3-1=3,d1=2,i2=1+3-2=2,x2(i2)=0,x3(i3)=0,d2=1,i3=3+0-1=2,d2=2,i3=3+0-2=1,x3(i3)=1,x3(i3)=1,d2=1,i3=2+0-1=1,d2=2,i3=2+0-2=0,x3(i3)=2,隨機(jī)需求下多階段生產(chǎn)計(jì)劃,確定性需求下的最優(yōu)生產(chǎn)計(jì)劃在開(kāi)始時(shí)已完全確定:x