網絡優(yōu)化-第4章動態(tài)規(guī)劃(存儲版)
【正文】 sion Making），是將決策問題的 全過程 恰當地劃分為若干個相互聯(lián)系的子過程（每個子過程為一個 階段 ），以便按照一定的次序去求解 . 階段一般是根據時間和空間的自然特征來劃分，以便于問題的求解為目的 . 描述階段的變量稱為 階段變量 ，一般用 k表示 . 從第 k個階段開始點到全過程終點的過程稱為 后部子過程 ，或 k子過程 . 在多階段決策問題中 ， 狀態(tài) 表示每個階段開始時所處的自然狀況或客觀條件 . 描述過程狀態(tài)的變量稱為 狀態(tài)變量 ， 一般用 xk表示第 k個階段的狀態(tài)變量 . 當過程處于某個階段的某個狀態(tài)時 ， 從該狀態(tài)演變?yōu)橄乱粋€階段某狀態(tài)的選擇 ， 稱為 決策 （ 抉擇 ， Decision） . 描述決策的變量稱為決策變量 ， 一般用 uk表示第 k個階段的 決策變量 ， 而用Uk(xk)表示第 k個階段 xk狀態(tài)下的所有允許決策的集合 . 5 狀態(tài)轉移方程 ),(1 kkkk uxTx ??無后效性的多階段決策過程 動態(tài)規(guī)劃中，多階段決策問題具有 無后效性 （馬爾科夫性質），即當某階段的狀態(tài)一旦確定 ,則此后過程的演變不再受此前各狀態(tài)和決策的影響 , 或者說 “ 未來與過去無關 ” . 即由狀態(tài) xk出發(fā)的后部子過程可以看成一個以 xk為初始狀態(tài)的獨立過程 . 相應于后部子過程（ k子過程）的決策序列稱為 子策略 ，記為pk,n(xk) ，所有允許子策略的集合記為 Pk,n(xk). 由所有各階段的決策組成的決策序列稱為 全過程策略 ，或簡稱策略 ，記為 p1,n(x1). 可供選擇的所有全過程策略的集合構成 允許策略 集合，記為 P1,n(x1) .其中能使總體性能達到最優(yōu)的策略稱為 最優(yōu)策略 ，一般記為 ),( **2*1* ,1 nn uuup ??6 一般記為 nkkkknjjjjnk VuxvuxvV ,11, ),(),( ????? ?無后效性的多階段決策過程 準則函數及可分性 準則函數 /指標函數（ Criterion Function）是衡量策略好壞的尺度 (益損值 ). ? 定義在全過程上的準則函數相當于目標函數，一般記為 V1,n(x1。( ,1,1,1 nkkn ppp ?? ),( 111 ???? kkkk uxTx kx證明 : 必要性 . 設允許策略 是最優(yōu)策略，則 ),(**2*1* ,1 nn uuup ??)}。(,)(1,111,1)(,1,111,1)()(,1,111,1)(,11,1)(*,11,1,11,11,1,11,11,11,1,11,1,1nkknkxPpkkxPpnkknkkkxPpxPpnkknkkkxPpnnxPpnnpxVpxVpxVpxVpxVpxVpxVpxVknknkkkknknkkknnnn???????????????????????8 最優(yōu)性定理 充分性 . 設允許策略 滿足定理的條件（ ） , 為任一允許策略，則 ),( **2*1* ,1 nn uuup ??)。()。3)1()1( 33 ?? gf 。 用二進制變量 yt表示在時段 t工廠是否進行生產準備 . .,2,1,0,0,2,1,0,0,0,1,2,1,..)(m i n011TtIxITtxxyTtdIxItsIhxcyszttttttttttttttTtt???????????????????????19 可以只考慮 當 ct為常數 ， 目標函數變?yōu)? 單產品、無能力限制的批量問題 可以證明：一定存在滿足條件 的最優(yōu)解 . 假設費用均非負 ， 則在最優(yōu)解中 ， 即 用 ft表示當 t時段初始庫存為 0時 ， 從 t時段到 T 時段的子問題的最優(yōu)費用值 最優(yōu)值 （ 費用 ） 為 f1 . 計算復雜性
環(huán)評公示相關推薦
鄂ICP備17016276號-1