第8章-馬爾可夫決策ppt課件

1、1,第8章 馬爾可夫決策 8.1馬爾可夫鏈的定義 定義8.1 設(shè) 是一個隨機序列，狀態(tài)空間E為有限集，對于任意的 正整數(shù)m，n若 ，有 則稱 為一個馬爾可夫鏈（簡稱馬氏鏈）。 定義8.2 設(shè) 是一個馬氏鏈，如果等式（13）的右邊的條件概率 與n無關(guān)，即 則稱 為齊次的馬氏鏈。稱 為系統(tǒng)由狀態(tài)i經(jīng)過m個時間間隔 （或步）轉(zhuǎn)移到狀態(tài)j的轉(zhuǎn)移概率。（14）式稱為齊次性。它的含義是：系統(tǒng)由 狀態(tài)i到狀態(tài)j的轉(zhuǎn)移概率只依賴于時間間隔的長短，與起始的時刻無關(guān)。以后無 特殊的說明，馬氏鏈都是齊次的。 8.2 轉(zhuǎn)移概率矩陣及柯爾莫哥洛夫定理,1,2,2,1）轉(zhuǎn)移概率矩陣 對于一個馬爾可夫鏈，稱 為由狀態(tài)i經(jīng)過

2、m步轉(zhuǎn)移到狀態(tài)j的概 率。其概率為： 式中 ； 例 已知一次轉(zhuǎn)移矩陣 試求二次轉(zhuǎn)移矩陣。 解 由公式（15）得,3,3,2）柯爾莫哥洛夫-開普曼方程 由遞推關(guān)系： 所以 8.3 應(yīng)用問題 （1）市場占有率的計算,5,4,4,例 假設(shè)市場上有A、B、C三種品牌的方便面，經(jīng)市場調(diào)查：上月購買A品牌的 顧客，有60%在本月仍購買A品牌，有20%轉(zhuǎn)移購買C 品牌，有20%轉(zhuǎn)移購買B品 牌；上月購買B品牌的顧客，有70%在本月仍購買B品牌，有20%轉(zhuǎn)移購買C 品牌， 有10%轉(zhuǎn)移購買A品牌；上月購買C品牌的顧客，有80%在本月仍購買C品牌，有10% 轉(zhuǎn)移購買B 品牌，有10%轉(zhuǎn)移購買A品牌。上月市場占有

3、率為：=（0.3，0.4，0.3）。 試求本月和下月三種方便面的市場占有率。 解： 由已知條件構(gòu)造轉(zhuǎn)移矩陣： 由公式（5），本月市場占有率,本 月 購 買,A B C,A B C,上月購買,5,同理，可算出下月的市場占有率： （2）占有率平衡態(tài)決策 當(dāng)處于平衡態(tài)時，上月各牌的市場占有率等于本月市場占有率。其平衡態(tài)模 型為： 左式= 令左式=右式，有,6,將轉(zhuǎn)移概率代入上式： 經(jīng)整理，得 去掉第三個多余方程，則,7,即得 （3）人力資源決策 例 某高校對教師進行分類，可分為5種狀態(tài)：助教、講師、副教授、教授、 流失(退休)。目前狀態(tài)向量：S0=（135，240，115，60，0）。根據(jù)歷史資料，

4、各 類職稱的轉(zhuǎn)移概率矩陣為： 試分析三年后的教師結(jié)構(gòu)及三年內(nèi)為保持編制不變應(yīng)進多少研究生充實教師隊伍。 解；一年后的人員分布為,8,由于要保持135+240+115+60+0=550人的總編制，流失走76人，因而第一年 需進76位研究生充實教師隊伍。此時人員分布為：S1=（81+76，198，123，72， 0）=（157，198，123，72，0） 第二年人員分布： 第二年流失74人，因而補充74位研究生。各類人員的結(jié)構(gòu)為S2=（168， 182，117，83，0） 第三年人員分布,9,第三年流失72人，因而補充72位研究生。各類人員的結(jié)構(gòu)為S3=（173， 176，110，91，0） （4

5、）吸收態(tài)馬爾可夫鏈及應(yīng)用 基本概念： 設(shè)有一四個狀態(tài)馬爾可夫鏈，其轉(zhuǎn)移概率矩陣P為 根據(jù)轉(zhuǎn)移矩陣可以畫出狀態(tài)轉(zhuǎn)移圖，方框代表狀態(tài)，箭頭指向轉(zhuǎn)移方向， 箭頭上數(shù)字表示轉(zhuǎn)移概率，見圖1。 圖1 狀態(tài)轉(zhuǎn)移圖,1,2,3,4,1/4,1/4,1/4,1/3,1/2,2/3,1,1/2,1/4,10,連通性：對于馬爾可夫鏈的狀態(tài)空間S=（S1，S2，Sn），若從Si 狀態(tài)可以轉(zhuǎn)移到S j狀態(tài)而且也可以從S j狀態(tài)轉(zhuǎn)移到Si狀態(tài)，則稱Si 狀態(tài)與S j狀態(tài)是連通的。例狀態(tài)1、2。 封閉類：若連通狀態(tài)空間內(nèi)的任何一狀態(tài)都不可能到達狀態(tài)空間外的任何一狀態(tài)，稱為封閉類，例狀態(tài)1、2。 過渡類：若一個連通空間之內(nèi)

6、的狀態(tài)可以到達連通空間之外的狀態(tài)，但外面的狀態(tài)不可轉(zhuǎn)入其內(nèi)，稱之為過渡類。例狀態(tài)3。 吸收態(tài)：若封閉類僅由一個狀態(tài)構(gòu)成且只有轉(zhuǎn)進沒有轉(zhuǎn)出稱為吸收態(tài)，例狀態(tài)4。含有吸收態(tài)的馬爾可夫鏈，稱為吸收態(tài)馬爾可夫鏈 馬爾可夫鏈的標(biāo)準(zhǔn)形： 或 其中，I為單位陣；0為零矩陣；R為過渡態(tài)到吸收態(tài)轉(zhuǎn)移概率矩陣，Q為過渡態(tài)之間的 轉(zhuǎn)移概率矩陣,11,例在轉(zhuǎn)移矩陣 ： 中 過渡態(tài)分析： 過渡態(tài)分析的目的：在到達吸收態(tài)前的過渡態(tài)中停留的平均時間；從某一 過渡態(tài)出發(fā)，在其被吸收前所經(jīng)歷的期望步數(shù)；轉(zhuǎn)移過程從某一過渡態(tài)出發(fā)，最 終為某特殊吸收態(tài)或為封閉類所吸收的概率。 基本矩陣： 。M的每一行和表示從某一狀態(tài)出發(fā)，最終轉(zhuǎn)至

7、吸收態(tài)之前的總期望轉(zhuǎn)移步數(shù)；M中的元素 表示過渡態(tài)Si 轉(zhuǎn)到過渡態(tài)S j平均次數(shù)。 吸收態(tài)轉(zhuǎn)移矩陣,12,式中，bij表示從過渡態(tài)Si出發(fā)，訪問過渡態(tài)S j后進入吸收態(tài)的概率。 例 已知 試對其進行過渡態(tài)分析。 解：將其標(biāo)準(zhǔn)化 則有,13,m 11 表示狀態(tài)3在吸收前平均有1個轉(zhuǎn)移期花費在第3狀態(tài)； m 12 表示狀態(tài)3在吸收前平均有0.8個轉(zhuǎn)移期花費在第4狀態(tài)； m 13 表示狀態(tài)3在吸收前平均有0.4個轉(zhuǎn)移期花費在第5狀態(tài)； m 21 表示狀態(tài)4在吸收前不會經(jīng)過第3狀態(tài)； m 22 表示狀態(tài)4在吸收前平均有1個轉(zhuǎn)移期花費在第4狀態(tài)； m 23 表示狀態(tài)4在吸收前平均有0.5個轉(zhuǎn)移期花費在第

8、5狀態(tài)； b 11 表明狀態(tài)3進入吸收態(tài)1的概率為0.88； b 12 表明狀態(tài)3進入吸收態(tài)2的概率為0.12； b 21 表明狀態(tài)4進入吸收態(tài)1的概率為0.85； b 22 表明狀態(tài)4進入吸收態(tài)2的概率為0.15； b 31 表明狀態(tài)5進入吸收態(tài)1的概率為0.7； b 32 表明狀態(tài)5進入吸收態(tài)2的概率為0.3,14,應(yīng)用： （1）銀行短期貸款回收 例 某銀行把它應(yīng)收的短期貸款期限定為1個季度，即轉(zhuǎn)移期為一季度，并規(guī)定超過3個季 度不能回收的短期貸款劃為呆帳，據(jù)以下資料，計算短期貸款回收率。貸款狀態(tài)劃分為：S= （結(jié)請，呆帳，欠1季，欠2季，欠3季）。假定未來應(yīng)分期收回貸款向量K=（4，2，

9、1），單 位：千萬元。據(jù)經(jīng)驗估計，轉(zhuǎn)移概率矩陣為 解：由已知 M1 表明處于欠一季度狀態(tài)的短期貸款經(jīng)2.2步便可望進入吸收態(tài)：結(jié)清或成呆帳； m 11 表明狀態(tài)3（欠一季度款）在吸收態(tài)前，平均有1個轉(zhuǎn)移期花費在欠一季狀態(tài)上； m 12 表明狀態(tài)3（欠一季度款）在吸收態(tài)前，平均有0.8個轉(zhuǎn)移期花費在欠二季狀態(tài)上； m 13 表明狀態(tài)3（欠一季度款）在吸收態(tài)前，平均有0.4個轉(zhuǎn)移期花費在欠三季狀態(tài)上,15,b 11 表明狀態(tài)3（欠一季度款）經(jīng)過逐次轉(zhuǎn)移有0.88可能性進入結(jié)清狀態(tài)； b 12 表明狀態(tài)3（欠一季度款）經(jīng)過逐次轉(zhuǎn)移有0.12可能性進入呆帳狀態(tài)； 設(shè)Y為銀行預(yù)期回收的貸款及呆帳向量，則 即預(yù)期可加收貸款5.92千萬元，呆帳1.08千萬元，即貸款回收率為：85% （2）保修費用估計 例 假定某耐用消費品投放市場,提供三年保修服務(wù)。保修期內(nèi)，修理一件