【正文】 8 2 89 2 6 .5( 6 ) ( 4 ) ( 1 )xs f c x h f xc h fc h fxc h fc h f??? ? ? ? ??? ???? ???? ???? ??? ? ? ?? ? ? ?? ? ? ?? ? ? ?? ? ? ?? ? ? ?????????信息系 羅捍東 40 22 2 2 2 2 1 2462 2 1*2 2 1 22 2 15 , ( 5 ) m i n [ ( ) ( 5 ) ( 8 ) ]( 4) ( 5 ) ( 4) 7 11m i n ( 5 ) ( 5 ) ( 3 ) m i n 8 , 69 8( 6) ( 5 ) ( 2)xs f c x h f xc h fc h f xc h f??? ? ? ? ??? ???? ??? ? ? ?? ? ? ? ? ? ? ?? ? ? ?? ? ? ????? ????22 2 2 2 2 1 2562 2 1 *22 2 16 , ( 6) m in [ ( ) ( 5 ) ( 9 ) ]( 5 ) ( 6) ( 4) 8 3 11m in m in 21 .5 , 6( 6) ( 6) ( 3 ) 9 3 9. 5xs f c x h f xc h fxc h f??? ? ? ? ??? ???? ??? ? ? ?? ? ? ?? ? ? ?????信息系 羅捍東 41 3） 當(dāng) k=3時 ， 由于 331 3 33 3 3 3 3 3 2 203 3 3 3 2 3 30 m in( , 6 )( ) m i n [ ( ) ( ) ( ) ]m i n [ ( ) ( ) ( 2 ) ]xx s df s c x h s f sc x h s f s x???? ? ?? ? ?? ? ? ? ?對 s3的可能取值在 0至 4 2 3m in[ , ] m in[ 4 , 6 6 2] 4d s M d? ? ? ? ? ?( s2最大可取到 6)的 值分別進行計算。 信息系 羅捍東 48 解： 設(shè) xi為第 i種物品的裝入件數(shù) ， 則問題的數(shù)學(xué)模型為： 有一個徒步旅行者帶一背包 ， 它可容納物品重量的限度為 a公斤 。 這 n種物品編號為 1， 2， … ， n。 問該旅行者應(yīng)如何選擇攜帶這些物品的件數(shù) ,使得總使用價值最大 ? 四、 背包問題 11m a x ( )0 1 , 2 , ,niiiniiiiz c xw x ax i n?????????????整 數(shù) ，信息系 羅捍東 49 將 n種物品劃分為 n個階段 ， 最優(yōu)值函數(shù) fk(sk)表示當(dāng)總重量不超過 sk公斤 ， 背包中只裝前 k種物品的最大使用價值 。 狀態(tài)變量 sk表示裝入第 1種物品至第 k種物品的總重量。 則狀態(tài)轉(zhuǎn)移方程為： sk1=skwkxk 則動態(tài)規(guī)劃的基本方程為： 信息系 羅捍東 50 1 2 31 2 31 2 3m a x 4 +5 63 4 5 10, , 0z x x xx x xx x x??? ? ????? 整 數(shù)例 4： 解 : 用動態(tài)規(guī)劃方法來解，問題變?yōu)榍? f3(10) 。而 323 2 3 25 1020 ( 1 0 )m a x [ 6 ( 1 0 5 ) ] m a x 6 ( 5 )1 2 ( 0 )xfx f x ff???????? ? ? ????? ???信息系 羅捍東 51 1 2 1 22 1 2 2 1 13 4 1 0 3 1 0 4( 1 0 ) m a x [ 4 + 5 ] m a x [ 5 ( ) ]x x x xf x x x f s?? ? ?? ? ?1 2 1 22 1 2 2 1 13 4 5 3 5 4( 5 ) m a x [ 4 + 5 ] m a x [ 5 ( ) ]x x x xf x x x f s?? ? ?? ? ?212 1 2 14 1010 ( 1 0 )m a x [ 5 ( 1 0 4 ) ] m a x 5 ( 6 )1 0 ( 2 )xfx f x ff???????? ? ? ????? ???212 1 24510 ( 5 )m a x [ 5 ( 5 4 ) ] m a x5 ( 1 )xfx f xf?????? ? ? ?????信息系 羅捍東 52 1 2 1 22 1 2 2 1 13 4 0 3 0 4( 0 ) m a x [ 4 + 5 ] m a x [ 5 ( ) ]x x x xf x x x f s?? ? ?? ? ?為此必須先算出 f1(10)， f1(6)， f1(5)， f1(2)， f1(1)，f1(0) 。 信息系 羅捍東 56 某人在退休時可拿到總數(shù)為 x0的養(yǎng)老金，他估計自己還可活 T年，如何利用這筆錢，使得他在 T年內(nèi)消費總效用最大？由于年齡大，不愿意冒險，他打算把錢存入銀行 (年利率為 r ) ，試建立該問題的數(shù)學(xué)模型。 設(shè)狀態(tài)變量 xt表示在第 t年擁有的資金數(shù) 。 則狀態(tài)轉(zhuǎn)移方程為： 1 1 0 1 2( ) , , , ,t t tx x r c t T? ? ? ? ?第 t階段的階段指標為： ( , ) ( )t t t tr x c U c?信息系 羅捍東 58 最優(yōu)值函數(shù) Vt(xt)表示 第 t年擁有的資金數(shù)為xt時按最優(yōu)方案消費所獲得的最大總效用。 信息系 羅捍東 60 最優(yōu)增長模型 (無限階段的動態(tài)規(guī)劃模型 ) 將上述模型進行推廣，若假設(shè) T趨向于 ∞，再假設(shè)資本生產(chǎn)函 數(shù)為 f(xt)，則可得無限階段的消費模型 (最優(yōu)增長模型 )如下： 由于這個無窮級數(shù)可能發(fā)散，數(shù)學(xué)上不易處理。 ? ?? ?01m axttctt t tUcx c f x????????????信息系 羅捍東 61 ? ?? ?01m axtttctt t tUcx c f x?????????????? 其中 β=1/(1+r)為貼現(xiàn)系數(shù)， x0為初始資本，是給定的。即 ? ?( ) m a xjjtt t jcjtV x U c???????? ?????信息系 羅捍東 63 由于現(xiàn)在沒有最后的結(jié)束階段，前面所介紹的逆序法不適用。對上面模型，利用動態(tài)規(guī)劃的遞推原理，可導(dǎo)出該問題的貝爾曼方程： ? ? ? ?11m a xjjttjcjtU c U c?????????? ? ? ??????? ?( ) m a xjjtt t jcjtV x U c???????? ?????信息系 羅捍東 64 ? ? ? ?11m a x m a xtjjttjccjtU c U c?????????? ? ? ??????? ?? ?11m a x ( )tt t tc U c V x? ??? ? ? 在有限階段的情形下，不同時間開始的子問題是不同的，而且到達規(guī)劃結(jié)束時所需要的時間也不同。這樣對于無限水平下的穩(wěn)定性問題，時期 t時的值函數(shù) Vt(xt)只是初始狀態(tài) xt的函數(shù)，與時期 t無關(guān)，因此 貝爾曼方程變?yōu)椋? 信息系 羅捍東 65 ? ?? ?? ?11( ) m a x ( )( 1 )1 , 2 ,tt t tct t tV x U c V xx c f x t? ??? ? ?? ? ? 這樣得到的策略函數(shù) xt+1=h(xt)也是時間不變的，這是一個非常 關(guān)鍵的簡化 ，因為這樣我們只需找到一個這樣的函數(shù)，而不是 Tt個 這樣的函數(shù)。而且可以證明值函數(shù) V(xt)是 嚴格遞增、嚴格凹的函數(shù)；策略函數(shù) h(xt)是嚴格遞增函數(shù)。一方面， t期的效用損失為 ；另一方面， t期增加單位投資導(dǎo)致下期增加消費量 ，相應(yīng)效用增加 由此可得歐拉方程： ? ?? ? ? ?? ? ? ?1 1 2 1t t t t tU f x x U f x x f x?? ? ? ?? ? ?? ? ? ? ? 利用消費變量將上式改寫為： ? ? ? ? ? ?11 3()t t tU c U c f x? ??? ? ?? ? ?? ?tUc?? ?1tfx?? ? ? ? ?11ttU c f x?????信息系 羅捍東 68 最優(yōu)路徑要求當(dāng)期的損失必須等于未來的收益 ,否則應(yīng)該重新設(shè)計可行的消費 /投資計劃能提高目標函數(shù)值。有三種求解方法： 1）值函數(shù)迭代法 2）猜測和驗證法 3）策略函數(shù)迭代法 01m ax lntttctt t tcx c A x???????????????信息系 羅捍東 69 ? ?? ? ? ?11111l n l n l n()t t tttx h x A xA A xVx???? ? ?? ? ? ?? ? ? ????????? ? ? ??????????? 上述問題策略函數(shù)和值函數(shù)的解分別為： 信息系 羅捍東 70 作業(yè)： P118 ,