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

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

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

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

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

5、）吸收態(tài)馬爾可夫鏈及應(yīng)用 基本概念： 設(shè)有一四個(gè)狀態(tài)馬爾可夫鏈，其轉(zhuǎn)移概率矩陣P為 根據(jù)轉(zhuǎn)移矩陣可以畫(huà)出狀態(tài)轉(zhuǎn)移圖，方框代表狀態(tài)，箭頭指向轉(zhuǎn)移方向， 箭頭上數(shù)字表示轉(zhuǎn)移概率，見(jià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,連通性：對(duì)于馬爾可夫鏈的狀態(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)都不可能到達(dá)狀態(tài)空間外的任何一狀態(tài)，稱為封閉類，例狀態(tài)1、2。 過(guò)渡類：若一個(gè)連通空間之內(nèi)

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

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

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

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