動態(tài)規(guī)劃運籌學(xué)基礎(chǔ)及其應(yīng)用胡運權(quán)第五版1(完整版)
【正文】 fsxsxxxsfsxsxsxxsf???????????????????????得代入解得 注意 ：階段最優(yōu)總效果僅是當(dāng)前狀態(tài)的函數(shù)，與其后的決策無關(guān) 15 例 2 生產(chǎn) – 庫存管理問題 (連續(xù)變量 ) 第四步 ： (第一、二、三、四季度 ) 總效果 f1(s1,x1)= x12+s1+ f2*(s2) 將 s2= s1 + x1 – 600= x1 – 600 代入 f1(s1,x1) 得： 118 00)(),(,60008)(),()600)(()600(6100 ),(21111111111211121111????????????????sfxsfxxxxsfxxsxxsf得代入解得由此 回溯 ：得最優(yōu)生產(chǎn) –庫存方案 x1*=600， s2*=0； x2*=700， s3*=0； x3*=800， s4*=300； x4*=900。第五章 動態(tài)規(guī)劃 1 動態(tài)規(guī)劃 Dynamic programming ? 五十年代貝爾曼 (B. E. Bellman)為代表的研究成果 ? 屬于現(xiàn)代控制理論的一部分 ? 以長遠(yuǎn)利益為目標(biāo)的一系列決策 ? 最優(yōu)化原理，可歸結(jié)為一個遞推公式 動態(tài)規(guī)劃的最優(yōu)化原理及其算法 求解多階段決策過程的方法 例 最短路問題 HLOBIECA FJDGKNPM4352 3523447711 342 225 48 122 決策樹法 ACEHIIFJIFDGJJK可以枚舉出 20條路徑，其中最短的路徑長度為 16 3 例 最短路問題 ? 表現(xiàn)為明顯的階段性 ? 一條從 A 到 B 的最短路徑中的任何一段都是最短的 HLOBIECA FJDGKNPM4352 3523447711 342 225 48 121612140214571086711892 13456 階段 最優(yōu)性原理 “最優(yōu)策略的一部分也是最優(yōu)的” 每步的決策只與相鄰階段狀態(tài)有關(guān)，而與如何達(dá)到這一狀態(tài)無關(guān) ???????????DADCACAiSdSdSBiSmin則有徑的長度點的最短路點到表示由設(shè)?因此我們可以從 B向回搜索最短路 ?標(biāo)記法 ?如何找出最短路徑 4 動態(tài)規(guī)劃的基本概念及遞推公式 ? 狀態(tài) (每階段初始的出發(fā)點 ) – 最短路問題中，各個節(jié)點就是狀態(tài) – 生產(chǎn)庫存問題中，庫存量是狀態(tài) – 物資分配問題中，剩余的物資量是狀態(tài) ? 控制變量 (決策變量 ) – 最短路問題中，走哪條路 – 生產(chǎn)庫存問題中，各階段的產(chǎn)品生產(chǎn)量 – 物資分配問題中，分配給每個地區(qū)的物資量 ? 階段的 編號 與遞推的 方向 – 一般采用反向遞推，所以階段的編號也是逆向的 – 當(dāng)然也可以正向遞推 5 動態(tài)規(guī)劃的步驟 確定問題的階段和編號 確定狀態(tài)變量 – 用 Sk 表示第 k 階段的狀態(tài)變量及其值 確定決策變量 – 用 xk 表示第 k 階段的決策變量，并以 xk*表示該階段的最優(yōu)決策 狀態(tài)轉(zhuǎn)移方程 sk1= g(sk, xk) 反向編號 sk+1= g(sk, xk) 正向編號 直接效果 – 直接一步轉(zhuǎn)移的效果 dk(sk, xk) 總效果函數(shù) – 指某階段某狀態(tài)下到終端狀態(tài)的總效果，它是一個遞推公式 )),(),((),( 111? ???? kkkkkkkkkk xsfxsdhxsf6 動態(tài)規(guī)劃的步驟 – hk 是一般表達(dá)形式，求當(dāng)前階段當(dāng)前狀態(tài)下的階段最優(yōu)總效果 (1) 如最短路問題，是累加形式，此時有 ? ?)),((),(),(),(min),(11111??????????????kkkkkkkkkkkkkxkkkxxsgfxsdxsfxsdxsfk終端的邊際效果一般為 f0(s0, x0)=0 (2)如串聯(lián)系統(tǒng)可靠性問題，是連乘形式，此時有 ? ?)),((),(),(),(max),(11111??????????????kkkkkkkkkkkkkxkkkxxsgfxsdxsfxsdxsfk終端的邊際效果一般為 f0(s0,x0)=1 從第 1階段開始，利用邊際效果和邊界條件，可以遞推到最后階段 7 動態(tài)規(guī)劃模型舉例 產(chǎn)品生產(chǎn)計劃安排問題 例 1 某工廠生產(chǎn)某種產(chǎn)品的月生產(chǎn)能力為 10件，已知今后四個月的產(chǎn)品成本及銷售量如表所示。 解 ：四個季度為四個階段，采用階段編號與季度順序一致。下面利用決策樹來確定各階段的可能狀態(tài)。設(shè)分配次序為 x1, x2, x3，階段正向編號，但逆向遞推，由約束條件可得邊界條件 s1=27, s4=0?，F(xiàn)提出如下四種改進(jìn)方案： 方案 1: 不撥款，機器保持原狀； 方案 2: 加裝監(jiān)視設(shè)備，每部機器需款 1 萬元； 方案 3: 加裝設(shè)備，每部機器需款 2 萬元； 方案 4: 同時加裝監(jiān)視及控制設(shè)備，每部機器需款 3 萬元； 采用各方案后，各部機器的次品率如下表。 設(shè) sk 為第 k階段尚未分配的人員數(shù)，邊界條件為 s3=9 設(shè)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1