吉林大學(xué)本科運(yùn)籌學(xué)(參考版)
2025-05-14 15:13本頁面
【正文】 再按計(jì)算的順序反推算可求得最優(yōu)解為 最大值為 。而 故 的最大值點(diǎn)在 處，所以得 及相應(yīng)的最優(yōu)解 第 4節(jié) 動(dòng)態(tài)規(guī)劃和靜態(tài)規(guī)劃的關(guān)系 3323 3 30 9 0 9m a x ( ) m a x 2 1 2ssf s s? ? ? ? ??????3 9s ? 33()fs21 ( 9 ) 2 9 1 2 1 7 4f ? ? ? ?**1 2 30 , 0 , 9x x x? ? ?1m a x ( 9) 174Ff??由于 s3不知道，故須再對(duì) s3求一次極值，即 顯然，當(dāng) 時(shí) 才能達(dá)到最大值。因而 的最大值必在兩個(gè)端點(diǎn)上選取。令最優(yōu)值函數(shù) 表示第 k階段的結(jié)束狀態(tài)為 sk，從 1階段至 k階段的最大值。 設(shè) 則有 第 4節(jié) 動(dòng)態(tài)規(guī)劃和靜態(tài)規(guī)劃的關(guān)系 121 2 1 2( ) m a x ( )xsf s x s??? *12xs?2 3 2 32 2 32 3 2 1 2 2 3 2 3004( ) m a x ( ) m a x ( ) 27x s x sf s x f s x s x x? ? ? ?? ? ? ?? ? ? ?? ? ? ?*2323xs?? ?3 4 3 4343 4 3 2 3 3 4 3 40041( ) m a x ( ) m a x ( )2 7 6 4x s x sf s x f s x s x S? ? ? ???? ? ? ?????*3314xs?4sc?* * *1 2 31 1 1,4 2 4x c x c x c? ? ?41m a x 64zc?用順推解法，從前向后依次有 及最優(yōu)解 及最優(yōu)解 及最優(yōu)解 由于已知 ，故易得到最優(yōu)解為 最大值為 及最優(yōu)解 第 4節(jié) 動(dòng)態(tài)規(guī)劃和靜態(tài)規(guī)劃的關(guān)系 2 2 21 2 31 2 3m a x 4 2 123 2 9 0 , 1 , 2 , 3iF x x xx x xxi? ? ? ?? ? ??? ???0 1 2 3s s s s、 、 、3 9s ? 1 2 3x x x、 、()kkfs例 5 用動(dòng)態(tài)規(guī)劃方法解下面問題 解： 按問題中變量的個(gè)數(shù)分為三個(gè)階段。 第 4節(jié) 動(dòng)態(tài)規(guī)劃和靜態(tài)規(guī)劃的關(guān)系 1()kkfs?2 1 2 2 3 3 3 4,s x s x s s x s c? ? ? ? ? ?1 2 2 3 3 4, 0 , 0x s x s x s? ? ? ? ?例 4 將例 3用順推解法解之。但應(yīng)注意，這里是在上述狀態(tài)變量和決策變量的記法不變的情況下考慮的。 已知終止?fàn)顟B(tài) sn+1用順推解法與已知初始狀態(tài)用逆推解法在本質(zhì)上沒有區(qū)別，它相當(dāng)于把實(shí)際的起點(diǎn)視為終點(diǎn)，實(shí)際的終點(diǎn)視為起點(diǎn)，而按逆推解法進(jìn)行的。 最優(yōu)解 由 所以 第 4節(jié) 動(dòng)態(tài)規(guī)劃和靜態(tài)規(guī)劃的關(guān)系 ? ?1 1 1 11131 1 1 2 2 1 1 1001 1 104( ) m a x ( ) m a x ( )27m a x ( , )x s x sxsf s x f s x s xh s x? ? ? ?????? ? ??????*1114xs?41 1 11() 64f s s?1sc?像前面一樣利用微分法易知 故 由于已知 而按計(jì)算的順序反推算，可得各階段的最優(yōu)決策和最優(yōu)值。 令最優(yōu)值函數(shù) fk(sk)表示為第 k階段的初始狀態(tài)為 sk，從 k階段到 3階段所得到的最大值。 第 4節(jié) 動(dòng)態(tài)規(guī)劃和靜態(tài)規(guī)劃的關(guān)系 ????????????,1i,0x0)(ccxxxxxxzm a xi3213221例 3 用逆推解法求解下面問題 解 : 按問題的變量個(gè)數(shù)劃分階段，把它看作為一個(gè)三階段決策問題 。在第 k階段，決策 xk使?fàn)顟B(tài) sk(輸入）轉(zhuǎn)移 為 sk+1 (輸出 )，設(shè)狀態(tài)轉(zhuǎn)移函數(shù)為 假定過程的總效益 (指標(biāo)函數(shù) )與各階段效益 (階段指標(biāo)函數(shù) )的關(guān)系為 其中記號(hào) ?*都表示為 +,或都表示為 。 第 4節(jié) 動(dòng)態(tài)規(guī)劃和靜態(tài)規(guī)劃的關(guān)系 ?動(dòng)態(tài)規(guī)劃方法 ?逆序解法 ?順序解法 ?關(guān)鍵：正確寫出動(dòng)態(tài)規(guī)劃的遞推關(guān)系式 ?逆 推形式 ， 當(dāng)初始狀態(tài)給定時(shí) ， 用逆推比較方便 ?順推形式 ， 當(dāng)終止?fàn)顟B(tài)給定時(shí) ， 用順推比較方便 第 4節(jié) 動(dòng)態(tài)規(guī)劃和靜態(tài)規(guī)劃的關(guān)系 1 2 1, , , ns s s ?12, , , nx x x1 ( , ) , 1 , 2 , ,k k k ks T s x k n? ??1 , 1 1 1 2 2 2( , ) ( , ) ( , )n n n nV v s x v s x v s x? ? ? ?1,nV1,opt nV 1,max nV考查如圖所示的 n階段決策過程。 ?動(dòng)態(tài)規(guī)劃研究的問題與時(shí)間有關(guān) ，研究具有多階段決策過程的一類問題，將問題的整體按時(shí)間或空間的特征分成若干個(gè)前后銜接的時(shí)空階段，把多階段決策問題表示為前后有關(guān)聯(lián)的一系列單階段決策問題，然后逐個(gè)加以解決，從而求出整個(gè)問題的最優(yōu)決策序列。 ?不同點(diǎn) ?線性規(guī)劃和非線性規(guī)劃研究的問題通常與時(shí)間無關(guān)，故又稱為靜態(tài)規(guī)劃?！? 簡(jiǎn)言之， 一個(gè)最優(yōu)策略的子策略總是最優(yōu)的 。 動(dòng)態(tài)規(guī)劃的基本思想和基本方程 ? ?11 1 1()( ) o p t ( , ) ( ) 1 , 2 , ,rk k kk k k k k k ku D sf s v s u f s k n?? ? ??? ? ?01( ) 0fs?1( , )rk k k ks T s u??1()nnfs?動(dòng)態(tài)規(guī)劃順序解法的基本方程 邊界條件 為 式中 求解過程：根據(jù)邊界條件， 從 k=1開始，由前向后順推 ，逐步求得各段的最優(yōu)決策和相應(yīng)的最優(yōu)值，最后求出 ， 就得到整個(gè)問題的最優(yōu)解。 動(dòng)態(tài)規(guī)劃的基本思想和基本方程 建立動(dòng)態(tài)規(guī)劃模型的五個(gè)要點(diǎn)： (1) 將問題的過程劃分成恰當(dāng)?shù)碾A段； (2) 正確選擇狀態(tài)變量 sk，使它既能描述過程的演變，又要滿足無后效性； (3) 確定決策變量 uk及每階段的允許決策集合 Dk(sk)； (4) 正確寫出狀態(tài)轉(zhuǎn)移方程； (5) 正確寫出指標(biāo)函數(shù)的關(guān)系，它應(yīng)滿足下面性質(zhì)： ① 是定義在全過程和所有后部子過程上的數(shù)量函數(shù)； ②
高考資料相關(guān)推薦
鄂ICP備17016276號(hào)-1