第五章-動態(tài)規(guī)劃(編輯修改稿)
2024-09-01 19:14 本頁面
【文章內(nèi)容簡介】 多階段決策問題 有一個系統(tǒng) ， 可以分成若干個階段 ， 任意一個階段 k， 系統(tǒng)的狀態(tài)可以用 xk表示 （ 可以是數(shù)量 、 向量 、 集合等 ） 。 在每一階段 k的每一狀態(tài)都有一個決策集合 Qk(xk)， 在 Qk(xk)中選定一個決策 qkQk(xk)， 狀態(tài) xk就轉(zhuǎn)移到新的狀態(tài)xk+1=Tk(xk,qk)， 并且得到效益 Rk(xk,qk)。 我們的目的就是在每一個階段都在它的決策集合中選擇一個決策 ， 使所有階段的總效益達到最大 。 這樣的多階段問題稱為 動態(tài)規(guī)劃 。 最優(yōu)化原理 動態(tài)規(guī)劃最優(yōu)化原理 ：一個過程的最優(yōu)策 略具有這樣的性質(zhì)，即無論其初始狀態(tài)及 其初始決策如何，其以后諸決策對以第一 個決策所形成的狀態(tài)作為初始狀態(tài)而言， 必須構(gòu)成最優(yōu)策略。 最優(yōu)化原理的性質(zhì) 對于多階段決策問題的最優(yōu)策略 ， 如果用它的前步策略產(chǎn)生的情況 （ 加上原有的約束條件 ） 來形成一個前步問題 ， 那么所給最優(yōu)策略的前階段的策略構(gòu)成這前步問題的一個最優(yōu)策略 。 用最優(yōu)化原理求解例 2 如果一開始的存儲量 u0已經(jīng)給定 ， 要求最后一個周期結(jié)束時有存儲量 un， 那么最優(yōu)生產(chǎn)和存儲費用就完全由 u0， un決定 。 對某一個周期 k， 如果這個周期開始時有庫存量 uk1， 要求結(jié)束時有庫存量 uk， 那么它的生產(chǎn)數(shù)量xk=sk+ukuk1， sk是這個周期的商品需求量 ， 所以它的生產(chǎn)和存儲費為 f(xk)+16 uk1， 其中 ?????????3015,300120150,100)(xxxxxf續(xù) (1) 用 Fk(u0,uk)表示開始的存儲量為 u0， 第 k個周期結(jié)束時存儲量為 uk的滿足前 k個周期需要的前 k個周期的最優(yōu)生產(chǎn)和存儲費用 ， 由最優(yōu)化原理 xk=sk+ukuk1, k=2,3,… ,6 x1=s1+u1u0, 讓 k=2,3,… ,6， 求出 F6(u0,u6)， 就得到問題的解 }16)(),({m i n),( 1101001 ???????? kkkkukkuxfuuFuuFk01101 16)(),( uxfuuF ??確定性的定期多階段決策問題 ?旅行售貨員問題 ?多階段資源分配問題 ?用最優(yōu)化原理解某些非線性規(guī)劃問題 ?排序 ?最優(yōu)排序法 旅行售貨員問題 旅行售貨員問題是圖論中一個著名問題 ， 就是在網(wǎng)絡(luò) N上找一條從 v0點出發(fā) ， 經(jīng)過 v1,v2,… ,vn各一次最后返回 v0的最短路線和最短路程 。 現(xiàn)把它看成一個多階段決策問題 。 從 v0出發(fā) ， 經(jīng)過 n個階段 ， 每個階段的決策是選擇下一個點 。 如果用所在的位置來表示狀態(tài) ， 那么狀態(tài)與階段數(shù)就不能完全決定決策集合了 ， 因為走過
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1