【正文】 1)1(u 2)1(u1)2(u 2)2(u111 ?????? ??mjijij rpq 21 ?q 412 ??q ??q為運轉(zhuǎn)時不維護(hù)； 為運轉(zhuǎn)時維護(hù)； 為故障時大修； 為故障時進(jìn)行常規(guī)維修． (1)選取初始策略 0? 1 )2(01 )1(0 )2(,)1( uu ?? ??令即當(dāng)運轉(zhuǎn)時不維護(hù) ,而故障時大修，則有 ??????? ???????? 425Q Markov Decision Markov Decision (2) 開始定值運算，并估計初始策略 ????????????212211fffvfffv令 f2=0，解上述方程組，得 v（ 0） =， )0(1 ?f0)0(2 ?f(3) 進(jìn)入策略改進(jìn)程序，求改進(jìn)策略． 對狀態(tài) 1，尋求策略 ,使 )(1ku)0(1)0(212)0(1111m a x ffPfpq kkk ??? a x ???????????????????選取決策 , ，當(dāng)窯爐運轉(zhuǎn)，采取維護(hù)策略， 2)1(u????? ??mjinjiijii ffpqnn1)()()( 11m a x ??對狀態(tài) 2，尋求新策略 ,使 ku )2()0(2)0(2212)0(1212m a x ffPfpq kkk ??? a x ?????????????????????1 )2(u選取決策 ，當(dāng)窯爐故障時，采取大修策略． 求得改進(jìn)策略為： ,)1( 2 )1(1 u?? 1 )2(1 )2( u??策略 與 策略不同，所以還沒有得到最優(yōu)策略，須繼續(xù)迭代． 1? 0? Markov Decision (4) 再進(jì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?對狀態(tài) 1，有： a x ????????????????????仍取策略 )2(1u Markov Decision a x ?????????????????????對狀態(tài) 2，有： 仍取策略 )1(2u因此得到： )2(12 )1( u?? )1(22 )2( u??這與前一次迭代結(jié)果完全一樣，因而求得了最優(yōu)策略即為： 運轉(zhuǎn)時的決策是進(jìn)行維護(hù)，故障時進(jìn)行大修， 工廠未來每年期望報酬為 ． 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 。 MD常用的目標(biāo)有 3種： ； 2. 折扣目標(biāo)； 有限階段目標(biāo)最大。,2,1)],([),(111 ???? ???? nmijfrPifnjnnijijnn ??rij 表示從狀態(tài) X(n)=i 轉(zhuǎn)移到下一個狀態(tài) X（ n+1） =j 相應(yīng)的收益，則有： πn表示從第 n個時期到過程終結(jié)的決策規(guī)則 δ的序列 },{1 ??nn ??),( 1?? nnn ???其中 δn為第 n個時期的決策規(guī)則， Markov Decision q(i)表示由狀態(tài) i 作一次轉(zhuǎn)移的期望報酬，即狀態(tài)的即時期望報酬．則 ),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。 【 解 】 P0＝ (， ， ) )5()0()5( PGG ?),(),()0()1(???????????? ＝PGG)3 3 4 0 ,3 3 2 6 ,(),()0()5(55???????????? ＝PGG Markov Decision 遍歷性：如果一個齊次的馬爾可夫鏈 {X(n), n=1,2,…} 的 n步轉(zhuǎn)移概率為 Pij(n)，對于一切狀態(tài) i,j，存在著不依賴于初始狀態(tài) i的常數(shù) Pj，使得 jijn pnp ??? )(l i m成立，則稱此馬爾可夫鏈具有遍歷性．也就是說，一個具有遍歷性的馬爾可夫鏈，當(dāng)轉(zhuǎn)移的次數(shù) n極大時，此系統(tǒng)轉(zhuǎn)移到狀態(tài) j的概率為一個常數(shù) Pj，而與初始狀態(tài)無關(guān)． nn P??lim求 【 引理 】 設(shè) m 階矩陣 P具有 m個線性無關(guān)的特征向量 B＝ (b1,b2, …, bm) 對應(yīng)的特征值為 λ1， λ2， … ， λm，則 B可逆且有 P＝ BΛB－ 1， Pn= BΛnB－ Λ＝ diag(λ1， λ2， … ， λm) Markov Decision 上例中，求 Pn及 nn P??lim求轉(zhuǎn)移概率矩陣 P的特征值及特征向量。 記 Pj(n)=P(Xn=j)為 Markov鏈 X時刻 n處于狀態(tài) j的概率， P為初始分布。假設(shè)在任一時刻，公司 1能留住它的 1/2的老顧客，其余的則對半購買另兩個公司的產(chǎn)品；公司 2的一半顧客能留下，其余轉(zhuǎn)向公司 1；公司 3有 3/4能留下，其余流向公司 2。各公司所占的市場比例是隨時間變化的。 轉(zhuǎn)移概率 記 Pij為從狀態(tài) X(n)=i轉(zhuǎn)移到下一個狀態(tài) X（ n+1） =j 的概率，一步轉(zhuǎn)移概率矩陣為 ?????????????mmmmmmPPPPPPPPPP????212222111211 Markov Decision 【 例 】 有 3家電器公司分別生產(chǎn)三種不同牌子的空調(diào)。例如，今天下雨這一狀態(tài)用“ 0”表示，不下雨用“ 1”表示，則狀態(tài)空間為 E＝ {0， 1}。 ? ?TttX ?)。 ? ?TttX ?)。(若對任意的 0t1t2…t ntn+1及 ti∈ T， X（ tn+1）關(guān)于 X（ t1） ,…, X（ tn）的條件概率恰好等于 X（ tn+1）關(guān)于 X（ tn）的條件概率，用數(shù)學(xué)符號表示為： },)()({}。 一般采用改進(jìn) V－ M(Von Neumann－ Menstern)方法，固定 P＝， x1， x2改變 x0三次，得出相應(yīng)的 y的值，確定三點，作出效用曲線． )()()( 021 xyxyxy ?? 效用理論 Utility Theory )()()( 021 xyxyxy ??【 例 】 x1=－ 100， x2=400,取 y(x1)=0, y(x2)=1 100 400 第一次提問： x0為何值時，上式成立？答：“ 0” y(0)= 0+ 1＝ 1 (0,) 第二次提問： x0為何值時，上式成立？答：“ 200” y(200)= y(0)+ 1 = + 1＝ 第三次提問： x0為何值時，上式成立？答：“ 100” y(100)= y(0)+ y(200) = + ＝ (200,) (100,) 100 200 300 0 效用理論 Utility Theory 不同決策者對待風(fēng)險態(tài)度不同，因而會得到不同形狀的效用曲線．一般可分為保守型 Ⅰ 、中間型 Ⅱ 、風(fēng)險型 Ⅲ ，如下圖． y 1 I II x (Xmax,1) (Xmin,0) Xmax Xmin 0 效用曲線類型 圖中 I為保守型，其特點為：當(dāng)收益值較小時，效用值增加較快；隨收益值增大時，效用值增加速度變慢，表明決策者不求大利，謹(jǐn)慎小心，保守． 圖中 II為中間型，其特點為：收益值和效用值成正比，表明決策者完全按機(jī)遇辦事，心平氣和． 圖中 III為風(fēng)險型，其特點為與 I保守型恰好相反，當(dāng)收益值較小時，效用值增加較慢；隨收益值增大時，效用值增加速度變快，表明決策者對增加收益反應(yīng)敏感，愿冒較大風(fēng)險，謀求大利，不怕冒險． III 效用理論 Utility Theory 常用的效用函數(shù)： 效用理論 Utility Theory 效用值的應(yīng)用 【 例 】 若某決策問題的決策樹如下圖所示，其決策者的效用期望值同時附在效益期望值后，請做出決策． E(2)= 300＋ (－ 200)=50 E(3)＝ 200＋ (－ 100)=50 根據(jù)最大效益期望值準(zhǔn)則，無法判斷優(yōu)劣． y2= 1＋ 0＝ ， y3= + = 解： (1）計算效益期望值分別為 效用理論 Utility Theory A2方案效用值＞ A1方案效用值，因此取 A2方案為決策方案． 繪制效用曲線圖見下圖，可知，該決策者偏向于保守型，不求大利，謹(jǐn)慎小心． 效用理論 Utility Theory 200 300 1 0 100 200 100 y x 馬爾可夫決策 Markov Decision Markov Decision 馬爾可夫鏈 用 X(t)表示隨機(jī)系統(tǒng)在時刻 t 的狀態(tài)，狀態(tài)序列 ? ?TttX ?)。 大多數(shù)選擇 A E(B1)E(A1)， E(B2)E(A2) 一般來說效用值在 [0,1]之