運(yùn)籌學(xué)4.5-動(dòng)態(tài)規(guī)劃應(yīng)用舉例

§4.5

動(dòng)態(tài)規(guī)劃應(yīng)用舉例1ppt課件多階段有限資源分配問題—資源連續(xù)分配問題設(shè)有數(shù)量為x的某種資源,將它投入兩種生產(chǎn)方式A和B中,以數(shù)量y投入生產(chǎn)方式A,剩下的量投入生產(chǎn)方式B,則可得到收入,其中和是已知函數(shù),并且=0.再設(shè)以y與x-y分別投入兩種生產(chǎn)方式A、B后可以回收再生產(chǎn),回收率分別為

與,因此在第一階段生產(chǎn)后回收的總資源為,再將投入生產(chǎn)方式A與B,和第一階段一樣,若以與分別投入生產(chǎn)方式A和B,則又可得到收入,回收資源.因此,兩個(gè)階段的總收入為若上面的過程進(jìn)行n個(gè)階段,希望選擇,使n個(gè)階段的總收入最大,則問題變成求,使?fàn)顟B(tài):擁有資源的數(shù)量對(duì)上述n個(gè)階段的決策問題,選在第k個(gè)階段狀態(tài)轉(zhuǎn)移方程:～下一階段的資源量基本方程的導(dǎo)出:k階段的效益:策略:目標(biāo):選取,使每一階段的效益合起來達(dá)到最大令表示開始有資源x,再進(jìn)行k個(gè)階段生產(chǎn)并采用最優(yōu)分配策略后得到的最大總收入.決策::對(duì)每個(gè)狀態(tài),都有一允許決策集合,當(dāng)k=2時(shí),由于前一階段分別以y,x-y投A、B,生產(chǎn)后回收得作為下一個(gè)階段開始時(shí)可以投入生產(chǎn)的資源量,若采用最優(yōu)方式投入生產(chǎn),由最優(yōu)性原理,后一個(gè)階段總收入是,所以:對(duì),同樣的分析得當(dāng)k=1時(shí),由此得逆推關(guān)系:g、h一般非線性函數(shù)、復(fù)雜、無法用解析法求解求數(shù)值解,離散化!對(duì)上述的資源分配問題,當(dāng),很復(fù)雜時(shí),基本方程的解就不容易找到.但當(dāng),均為凸函數(shù),且時(shí),則可以證明在每個(gè)階段上y的最優(yōu)決策總是取其端點(diǎn)的值.因?yàn)?(對(duì)于固定的x)a)由,凸b),Th.

:

設(shè),為凸函數(shù),且,則n階段資源分配問題的最優(yōu)策略y在每個(gè)階段總?cè)〉亩它c(diǎn)的值,并且:為y的凸函數(shù),其最大值一定在y=0或y=x處達(dá)到由歸納法即可得證Proof:

為x的凸函數(shù).也是y的凸函數(shù).a)b)y的凸函數(shù)

﹟Exp.:在有限資源分配問題中,故上述Th知:歸納法把區(qū)間[0,x]進(jìn)行分割,令

精度要求計(jì)算機(jī)容量對(duì),依次計(jì)算出確定出最優(yōu)決策所求的最大總收入離散取值,變化,逐步,逐個(gè)計(jì)算函數(shù)值或用表格法求出數(shù)值解計(jì)算機(jī)實(shí)現(xiàn)用DP求解某些NLP:按問題變量的個(gè)數(shù)劃分階段乘積可分可加可分前提:可直接用微分法(求穩(wěn)定點(diǎn))可得到解析解!二維資源分配問題:設(shè)有兩種原料,數(shù)量各為a和b單位,需要分配用于產(chǎn)生n種產(chǎn)品,如果第一種原料以數(shù)量為單位,第二種原料以數(shù)量為單位,用于生產(chǎn)第i種產(chǎn)品,其收入為.問應(yīng)如何分配這兩種原料于n種產(chǎn)品的生產(chǎn),使總收入最大?靜態(tài)規(guī)劃問題:用動(dòng)態(tài)規(guī)劃狀態(tài)變量、決策變量均為二維的狀態(tài)變量:x表示分配用于生產(chǎn)第k種產(chǎn)品至第n種產(chǎn)品的第一種原料的數(shù)量y表示分配用于生產(chǎn)第k種產(chǎn)品至第n種產(chǎn)品的第二種原料的數(shù)量決策變量:表示分配給第k種產(chǎn)品用的第一種原料的單位數(shù)量表示分配給第k種產(chǎn)品用的第二種原料的單位數(shù)量允許決策集合:狀態(tài)轉(zhuǎn)移方程效益函數(shù)::用來生產(chǎn)第k+1種產(chǎn)品至第n種產(chǎn)品的第一(二)種原料的數(shù)量:表示以第一種原料數(shù)量為x,第一種原料數(shù)量為y,分配用于生產(chǎn)第k種產(chǎn)品至第n種產(chǎn)品時(shí)所得的最大收入第k階段的則～問題的最大收入g(x,y)的復(fù)雜性,難于直接計(jì)算求解數(shù)值計(jì)算降維,簡(jiǎn)化處理1>逐次逼近法:先保持一個(gè)變量不變,對(duì)另一個(gè)變量求最優(yōu)(一維問題),然后交替地固定,以迭代的形式反復(fù)進(jìn)行,直到獲得滿足某種要求的解為止.設(shè)固定為用一維方法求解,得固定為2>粗格子點(diǎn)法(疏密法):一般只收斂到局部最優(yōu)解.為找到全局最優(yōu)解,可同時(shí)選各個(gè),…采用離散化方法計(jì)算.將矩形定義域劃分成網(wǎng)格,然后在格點(diǎn)上計(jì)算等分個(gè)格點(diǎn)對(duì)每個(gè)k值,需計(jì)算的個(gè)值.計(jì)算量很大,且隨著的增加迅速膨脹.分點(diǎn)維數(shù)維數(shù)災(zāi)難!粗格子點(diǎn)法:1)先用少數(shù)的格子點(diǎn)進(jìn)行粗糙的計(jì)算,求出對(duì)應(yīng)的最優(yōu)解.2)在“最大”解附近的小范圍內(nèi)進(jìn)一步細(xì)分,并求在細(xì)分格子點(diǎn)上的最優(yōu)解.轉(zhuǎn)1).可能導(dǎo)致漏掉全局最優(yōu)解!應(yīng)結(jié)合對(duì)指標(biāo)函數(shù)的特性進(jìn)行分析!3>Lagrange乘數(shù)法:引入Lagrange乘子,將二維問題轉(zhuǎn)化為因?yàn)楣潭ǖ膮?shù),問題關(guān)于可分.為有意義→supposethat:(△)一維問題一維方程求解為最優(yōu)解用插值法、優(yōu)化中乘子法調(diào)整的取值Otherwise(△)的解可能不唯一.不妨設(shè)有m個(gè)最優(yōu)解:可能出現(xiàn)下面幾種情況:令:1>存在某一個(gè)k,使為最優(yōu)解2>,則增大的值,重新求(△)3>,則減少的值,重新求(△)4>,且對(duì)所有的k,均有,則算法不適用!停止迭代.可考慮將Lagrange乘子法用于約束條件狀態(tài)轉(zhuǎn)移不能完全確定,它也許按某種已知的概率分布取值不確定性的多階段問題由于隨機(jī)因素稱為隨機(jī)性的決策過程采購(gòu)問題：某廠生產(chǎn)上需要在近五周內(nèi)必須采購(gòu)一批原料,而估計(jì)在未來五周內(nèi)價(jià)格會(huì)波動(dòng),其浮動(dòng)價(jià)格和概率已測(cè)得如下表所示:試求在哪一周內(nèi)以什么價(jià)格購(gòu)入,使其采購(gòu)價(jià)格的數(shù)學(xué)期望最小,并求出期望值.Scenario1

5000.3PriceProbScenario3

7000.4Scenario2

6000.3解:這里價(jià)格是一個(gè)隨機(jī)變量,是按已知的概率分布取值的.按采購(gòu)期限5周分為5個(gè)階段,將每周的價(jià)格看作該階段的狀態(tài).:狀態(tài)變量,表示第k周的實(shí)際價(jià)格.:決策變量=1表示第k周決定采購(gòu)0表示第k周決定等待:表示第k周決定等待,而在以后采取最優(yōu)決策時(shí)采購(gòu)價(jià)格的期望值.:表示第k周實(shí)際價(jià)格為時(shí),從第k周至第5周采取最優(yōu)決策所得的最小期望值.可寫出逆序遞推關(guān)系式為:其中由和的定義知:最優(yōu)決策為:從最后一周開始,逐步向前遞推計(jì)算,具體計(jì)算過程如下:即在第五周時(shí),若所需的原料尚未買入,則無論市場(chǎng)價(jià)格如何,都必須采購(gòu),不能再等.k=5時(shí),k=4時(shí),500600610500600700500574=500=600or700500551.8=500=600or700500536.26