【正文】 1211ppppP設(shè) G＝ (g1， g2)，由 G＝ GP Markov Decision 設(shè) G＝ (g1， g2)，由 G＝ GP ??????????????????5352212122211211ppppP???????????53522121),(),( 2121 gggg1,5321,5221 21212211 ?????? gggggggg95,9421 ?? gg Markov Decision 收益預(yù)測模型 ),( nn if ? 設(shè)系統(tǒng)在第 n個(gè)時(shí)期處于狀態(tài) X(n)=i，轉(zhuǎn)移到過程終結(jié)時(shí)的總期望收益為 ?? ,2,1。,2,1)],([),(111 ???? ???? nmijfrPifnjnnijijnn ??rij 表示從狀態(tài) X(n)=i 轉(zhuǎn)移到下一個(gè)狀態(tài) X（ n+1） =j 相應(yīng)的收益，則有： πn表示從第 n個(gè)時(shí)期到過程終結(jié)的決策規(guī)則 δ的序列 },{1 ??nn ??),( 1?? nnn ???其中 δn為第 n個(gè)時(shí)期的決策規(guī)則， Markov Decision q(i)表示由狀態(tài) i 作一次轉(zhuǎn)移的期望報(bào)酬，即狀態(tài)的即時(shí)期望報(bào)酬．則 ),2,1()(1????mjijij mirPiq ?),()(),(111??????mjnnijnn jfPiqif ??令 或 )1()(1?????mjjijii nfPqnf Markov Decision 若記數(shù)從末端開始，上式的逆序?qū)懛椋? ?????????????)()()()(21nfnfnfnFm??????????????mqqqQ?21?????????????mmmmmmPPPPPPPPPP????212222111211則 ?,2,1)1()( ????? nnFPQnFQF ?)1(?? ,2,1。,2,1)1()(1????? ??nminfPqnfmjjijii Markov Decision Markov Decision 【 例 】 商品的轉(zhuǎn)移概率矩陣和利潤表如下 暢銷 滯銷 暢銷 滯銷 暢銷 滯銷 暢銷 50 10 滯銷 20 － 20 轉(zhuǎn)移概率表 利潤表 (萬元 ) q1= 50+ 10＝ 30， q2= 20+ (－ 20)＝－ 4 ),2,1()(1????mjijij mirPiq ??,2,1)1()( ????? nnFPQnF30 30 43( 2)4 4 30 43 54 .3( 3 )4 16 .56FF? ? ? ? ? ? ? ?? ? ?? ? ? ? ? ? ? ???? ? ? ? ? ? ? ?? ? ? ? ? ? ? ?? ? ?? ? ? ? ? ? ? ??? ? ? ? ? ? ? ?n 1 2 3 4 5 6 f1(n) 30 44 f2(n) － 4 6期利潤預(yù)測 最優(yōu)策略模型 Markov決策由五重組來描述： 1. 狀態(tài) i 2. 策略集 ，狀態(tài) i 的策略規(guī)則為 3. 轉(zhuǎn)移概率矩陣 P 4. 報(bào)酬，狀態(tài) i 的策略規(guī)則為 轉(zhuǎn)移到狀態(tài) j 的報(bào)酬為 期望即時(shí)報(bào)酬為 5. 目標(biāo)函數(shù) V(n) },{ 1 ??nn ?? )(i?)(i? )(iijr?)(iiq? Markov Decision Markov決策（ MD）描述 在某一時(shí)刻（階段）隨機(jī)變量 X處于狀態(tài) i ，決策者選擇某個(gè)策略使目標(biāo)最優(yōu)。 MD常用的目標(biāo)有 3種： ； 2. 折扣目標(biāo)； 有限階段目標(biāo)最大。通過 Z變換： mifnPqnfPqnfmjjijimjjijii,2,1])1[()1()(11????????? ???? Markov Decision ???Mjjiji qsv1( 1 ) ( 0)F T Q SF?? ()iif n nv f??記 ? ?11mi i jji jv n f p n vq f???? ? ? ?? ???1mi ij jijv f p fq?? ?? ?i=1,2, …, m () 解方程組求出變量 fi 與 v 采用迭代計(jì)算： （ 1）選擇一個(gè)初始策 ，每一個(gè)狀態(tài) i（ i=1， 2… ， m）選擇一個(gè)決策規(guī)則 使其決策 ，令 n=0； n?0)( ?nmf)()( iu nki ??n?(2) 對(duì)已知策略，令 ，求解方程組 ()，得相應(yīng)的策略獲利 v（ n） 和相對(duì)值 f（ n） ，（ i=1,2,…,m ； n=0,1,2… ）； Markov Decision （ 3）應(yīng)用上一策略已求得的 ，尋求一個(gè)新的策略規(guī)則 δn+1，對(duì)每一個(gè)狀態(tài) i，使 )(nmf11( ) ( ) ()1m a x nnmii ni i j j ijv q p f f?????? ? ? ??由此得新的策略 1?n?（ 4）若所得策略 與前次迭代所得策略 完全相等，則停止迭代，已得到了最優(yōu)策略；否則回到步驟 2，令 n=n+1． 1?n? n? Markov Decision 【 例 】 某水泥廠有一臺(tái)窯爐處于兩種運(yùn)行狀態(tài)，即運(yùn)轉(zhuǎn)和故障，窯爐工人每年定期檢查設(shè)備一次．若窯爐正常則選擇維護(hù)或不維護(hù)；若窯爐故障則選擇大修或常規(guī)維修，其轉(zhuǎn)移概率與相應(yīng)的報(bào)酬如下表，試求該廠應(yīng)采取的最佳策略使在無限期的未來每年所獲平均收入最大． 表 11 .12 轉(zhuǎn)移概率和報(bào)酬 )()( iv Ki ?? ??iip?1 ??iip2 ??2iir???1 iir?)(iiq?狀態(tài) I 決 策 轉(zhuǎn)移概率 報(bào) 酬 期望 即時(shí)報(bào)酬 1． 運(yùn)轉(zhuǎn) 1.(不維護(hù) ) 2.(維護(hù) ) 50 48 0 0 25 2． 故障 1.(大修 ) 2.(常修 ) － 5 － 3 0 0 － 4 － Markov Decision 【 解 】 此問題共有兩種狀態(tài)，每個(gè)狀態(tài)有兩種決策，因此共有四種可行決策。 1)1(u 2)1(u1)2(u 2)2(u111 ?????? ??mjijij rpq 21 ?q 412 ??q ??q為運(yùn)轉(zhuǎn)時(shí)不維護(hù)； 為運(yùn)轉(zhuǎn)時(shí)維護(hù)； 為故障時(shí)大修； 為故障時(shí)進(jìn)行常規(guī)維修． (1)選取初始策略 0? 1 )2(01 )1(0 )2(,)1( uu ?? ??令即當(dāng)運(yùn)轉(zhuǎn)時(shí)不維護(hù) ,而故障時(shí)大修，則有 ??????? ???????? 425Q Markov Decision Markov Decision (2) 開始定值運(yùn)算，并估計(jì)初始策略 ????????????212211fffvfffv令 f2=0，解上述方程組，得 v（ 0） =， )0(1 ?f0)0(2 ?f(3) 進(jìn)入策略改進(jìn)程序，求改進(jìn)策略． 對(duì)狀態(tài) 1，尋求策略 ,使 )(1ku)0(1)0(212)0(1111m a x ffPfpq kkk ??? a x ???????????????????選取決策 , ，當(dāng)窯爐運(yùn)轉(zhuǎn)，采取維護(hù)策略， 2)1(u????? ??mjinjiijii ffpqnn1)()()( 11m a x ??對(duì)狀態(tài) 2，尋求新策略 ,使 ku )2()0(2)0(2212)0(1212m a x ffPfpq kkk ??? a x ?????????????????????1 )2(u選取決策 ，當(dāng)窯爐故障時(shí)，采取大修策略． 求得改進(jìn)策略為： ,)1( 2 )1(1 u?? 1 )2(1 )2( u??策略 與 策略不同，所以還沒有得到最優(yōu)策略，須繼續(xù)迭代． 1? 0? Markov Decision (4) 再進(jìn)行定值運(yùn)算求 )1(2)1(1)1( , ffv????????????????)1(2)1(1)1(2)1()1(2)1(1)1(1)1(fffvfffv，令 0)1(2 ?f 解方程得： v（ 1） =， )1(1 ?f 0)1(2 ?f(5) 尋求改進(jìn)策略 ， 2?對(duì)狀態(tài) 1，有： a x ????????????????????仍取策略 )2(1u Markov Decision a x ?????????????????????對(duì)狀態(tài) 2，有： 仍取策略 )1(2u因此得到： )2(12 )1( u?? )1(22 )2( u??這與前一次迭代結(jié)果完全一樣，因而求得了最優(yōu)策略即為： 運(yùn)轉(zhuǎn)時(shí)的決策是進(jìn)行維護(hù)，故障時(shí)進(jìn)行大修， 工廠未來每年期望報(bào)酬為 ． Markov Decision Markov Decision 作業(yè)：教材 P269 T 10 The End of Chapter 11 2 3 1 現(xiàn)在擴(kuò)建 明年擴(kuò)建 () () 10 8 1 8 6 1 (1) () (0) () () () 習(xí)題 習(xí)題 1 2 3 摸球 不摸球 0 白： 紅： 4 5 藍(lán)： 綠： 10 11 50 0 12 13 50 0 藍(lán)： 綠： 6 8 7 9 第 2次摸球 第 2次摸球 不摸球 不摸球 － 10 － 10 － 10 0 0 25 － 5 25 0