運籌學課件-第七章動態規劃(完整版)

　　

【正文】 }]()({m a x)( 2312032232xsfxpsfx sx??? ??為整數s3 0 1 2 3 4 x2 0 0 1 0 1 2 0 1 2 3 0 1 2 3 4 c2+f2 0 16 12 25 28 17 30 37 32 21 32 42 42 37 22 f2(s3) 0 16 28 37 42 42 x2* 0 0 1 1 1 2 K=2 銷售店 地區 0 1 2 3 4 1 0 16 25 30 32 2 0 12 17 21 22 3 0 10 14 16 17 )}4()({m a x)4( 3234,3,2,1,033xfxpf x ??? ?)}0(17),1(16),2(14),3(10),4({m a x 22222 fffff ?????}017,1616,2814,3710,42{m a x ?????47?K=3 全部策略為： x1*=2 x2*=1 x3*=1，最大價值為 47。 (4)狀態轉移方程： sk+1=sk+ukgk (5)最優指標函數： fk(sk)表示第 k月狀態為 sk時，采用最佳策略生產，從本月到計劃結束（第 4個月末）的生產與存貯最低費用。假設第 j+1個月的庫存量是第 j個月可銷售量與該月用戶需求量之差；而第 i個月的可銷售量是本月初庫存量與產量之和。試問在各個地區應如何設置銷售點，才能使每月獲得的總利潤最大 ?其值是多少？ 銷售店 地區 0 1 2 3 4 1 0 16 25 30 32 2 0 12 17 21 22 3 0 10 14 16 17 1階段 k： 將設點地區劃分為 3個階段，即 k＝ 1， 2， 3。 2狀態變量 sk+1：在第 k段開始時，背包中允許裝入前 k種物品的總重量。 基本方程為： ??? 33, )( 函數 指 標kiiik xgV????????? ????0)(1,2,3)}()({m a x)(44110sfksfxgsf kkkksxkk k狀態轉移方程： sk+1＝ skxk k＝ 3時 }2{m a x)(23033 33 xsf sx ???233*3 2 s，sx 取得極大值時當 ?2323033 2}2{m a x)( 33 sxsf sx ?? ??233*3 2 s，sx 取得極大值時當 ?????????? ????0)(1,2,3)}()({m a x)(44110sfksfxgsf kkkksxkk kk＝ 2時 })(29{m a x}29{m a x})(9{m a x)(222202320332022222222xsxsxsfxsfsxsxsx?????????????2222222 )(29),( xsxxsh ???令是極小值點9422 ?? sx22222229)(2)0(]0[ssfsf。 練 習 A－ B1－ C2－ D2－ E （三）基本方程分段求解時的幾種常用算法 1．離散變量的分段窮舉算法 動態規劃模型中的狀態變量與決策變量若被限定只能取離散值，則可采用分段窮舉法。 （二）逆序解法與順序解法 如果尋優的方向與多階段決策過程的實際行進方向相反，從最后一段開始計算逐段前推，求得全過程的最優策略，稱為逆序解法。 關鍵問題是如何正確選擇狀態變量，使各后部子過程之間具有遞進關系。在每一個子問題求解時，都要使用它前面已求出的子問題的最優結果，最后一個子問題的最優解，就是整個問題的最優解。 動態規劃方法－－－本方法是從過程的最后一段開始，用逆序遞推方法求解，逐步求出各段各點到終點的最短路線，最后求得起始點到終點的最短路線。 它分為階段指標函數和過程指標函數。 無后效性 。 動態規劃模型要用到的概念： (1)階段 。如果我們把每一種貨物看成是一個階段，這也是一個多階段的決策問題。 現在公司要確定時各廠投資多少才能使公司的總利潤達到最大？ 解： 在這個問題中，因為每個廠都有幾種投資方案，所以要對每個廠作出一項決策，總共要作出三個決策。 顯然，可以把每個月作為一個階段，全年分為 12個階段逐次決策。 ? 隨機型動態決策問題。即決策過程可劃分為明顯的階段。 動態決策問題分類： 按數據給出的形式分為： ? 離散型動態決策問題。 例 1 生產與存貯問題 某工廠每月需供應市場一定數量的產品，并將所余產品存入倉庫。 幾個例子 幾個例子 例 (基建投資問題 )一家公司有三個工廠，每個廠都需要進行擴建。 假定這艘貨船的總載重量是 10噸，現在要確定這四種貨物應各裝幾箱才能使裝載貨物的總價值達到最大。因此可以把整個路程分為 A， B(包括 B1， B2， B3)， C(包括 C1，C2， C3)和 D(包括 Dl， D2)四個階段。 狀態： 各階段開始時的客觀條件叫做狀態。 對每個實際問題，可供選擇的策略有一定范圍，稱為允許策略集合，記作 P1,n，使整個問題達到最優效果的策略就是最優策略。 最優指標函數記為 fk(sk)表示從第 k段狀態 sk采用最優策略到過程終止時的最佳效益值。 其次，動態規劃的計算結果不僅得到了從起始點到最終點的最短路線，而且得到了中間段任一點到最終點的最短路線 。資源分配問題是動態規劃的典型應用之一，資源可以是資金、原材料、設備、勞力等，資源分配就是將一定數量的一種或幾種資源恰當地分配給若干使用者，以獲取最大效益。即由第 k階段的狀態 sk出發的后部子過程，可以看作是一個以 sk為初始狀態的獨立過程。 fn(sn+1)是整體最優函數值。下面分別用逆序解法求解。 基本方程為： ????????? ???? ?0)(3,2,1)}()({m a x)(101011sfksfxgsf kkkksxkk kk動態規劃在經濟管理中應用 一、背包問題 背包問題的一般提法是：一位旅行者攜帶背包去登山、已知他所能承受的背包重量限度為 a千克，現有 n種物品可供他選擇裝入背包。 例 : 有一輛最大貨運量為 10噸的卡車，用以裝載 3種貨物．每種貨物的單位重量及相應單位價值如表所示。 動態規劃在經濟管理中應用 二、生產經營問題 —生產與存貯問題 在生產和經營管理中．經常遇到如何合理地安排生產計劃、采購計劃以及倉庫的存貨計劃和銷售計劃，使總效益最高的問題。 (6)基本方程： 解：建立動態規劃模型 K=4 u4=4s4 s4 0 1 2 3 f4(s4) 7 6 u4(s4) 4 3 2 1 })()({m in)( 4444 sEucsf ??K=3 s3={0,1,2,3} })()()({m i n)( 33343333 gusfsEucsf ?????且為整數)6,5,6m i n (}2,0m a x { 3333 ssus ?????i（月） 1 2 3 4 gi（需求） 2 3 2 4 s3 u3(s3) C+E+f4 f3(s3) u3 *(s3) 0)(1 , 2 , 3 , 4k })()()({m i n)(551??????? ?sfgusfsEucsf kkkkkkkks3 0 1 2 3 u3(s3) 2 3 4 5 1 2 3 4 0 1 2 3 0 1 2 C+E+f4 12 13 12 13 8 12 8 12 f3(s3) 12 8 8 u3 *(s3) 2 1 0 0 K=3 s3={0,1,2,3} })()()({m i n)( 33343333 gusfsEucsf ?????且為整數)6,5,6m i n (}2,0m a x { 3333 ssus ?????i（月） 1 2 3 4 gi（需求） 2 3 2 4 K=2 s2={0,1,2,3} })()()({m i n)( 22232222 gusfsEucsf ?????且為整數)9,6,6m i n (}3,0m a x { 2233 ssus ?????i（月） 1 2 3 4 gi（需求） 2 3 2 4 s2 u2(s2) C+E+f3 f2(s2) u2 *(s2) 0)(1 , 2 , 3 , 4k })()()({m i n)(551??????? ?sfgusfsEucsf kkkkkkkks2 0 1 2 3 u2(s2) 3 4 5 6 2 3 4 5 1 2 3 4 0 1 2 3 C+E+f3 18 16 17 18 17 15 16 17 f2(s2) 16 15 u2 *(s2) 5 4 3 0 K=2 s2={0,1,2,3} })()()({m i n)( 22232222 gusfsEucsf ?????且為整數)9,6,6m i n (}3,0m a x { 2233 ssus ?????i（月） 1 2 3 4 gi（需求） 2 3 2 4 s1 0 u1(s1) 2 3 4 5 C+f2 21 22