運(yùn)籌學(xué)課件——第4講馬爾可夫決策(精)

1、引例：牛奶廠決策最佳經(jīng)營策略選擇： 北京地區(qū)鮮牛奶由三個(gè)廠家提供，該地區(qū)客戶總數(shù)為 100 萬戶，假定廠家每年從每個(gè)客戶那里平均獲利 50 元，客戶資源每月都在三個(gè)廠家之間相互流動(dòng)，廠家 2 考慮從以下兩套候選方案之中選擇一個(gè)實(shí)施： 方案一：吸引老客戶，須花費(fèi) 450 萬元； 方案二：吸引廠家 1 和廠家 3 的客戶，須花費(fèi) 400 萬元。您有什么好的建議來幫助廠家 2 決策？市場調(diào)查數(shù)據(jù) 今年一月份廠家 2 對(duì) 2000 名消費(fèi)者進(jìn)行了調(diào)查，購買廠家 1 ， 2 ， 3 產(chǎn)品的消費(fèi)者人數(shù)分別為 800 ， 600 和 600 ，得到市場占有率向量（概率向量）為（ 0.4 ， 0.3 ， 0.

2、3 ）； 同時(shí)通過詢問這 2000 名消費(fèi)者下月的購買傾向，得到如下轉(zhuǎn)移頻數(shù)矩陣： 123123狀態(tài)轉(zhuǎn)移概率矩陣 P從轉(zhuǎn)移頻數(shù)矩陣到狀態(tài)轉(zhuǎn)移概率矩陣 P ： 用各行總數(shù)分別去除轉(zhuǎn)移頻數(shù)矩陣 N 的每行各元素，得到狀態(tài)轉(zhuǎn)移概率矩陣 P 如下：/800/600/600均衡狀態(tài)的市場占有率在目前狀態(tài)轉(zhuǎn)移概率矩陣 P 下，達(dá)到均衡狀態(tài)時(shí)的市場占有率記為 u ；估計(jì)如果實(shí)施方案一或二以后狀態(tài)轉(zhuǎn)移概率矩陣分別為 P1 和 P2 ，他們各自對(duì)應(yīng)的均衡狀態(tài)時(shí)市場占有率分別為 u1 和 u2 ；具體數(shù)據(jù)如下： u= （ 0.5 ，0.25 ， 0.25 ） u 1= （ 0.39 ， 0.44 ，0.17 ）

3、u2= （ 0.44 ， 0.42 ，0.14 ）廠家 2 的方案選擇有了均衡狀態(tài)時(shí)的市場占有率 u ， u1 和 u2 ，廠家 2 就能夠方便地進(jìn)行分別方案選擇，根據(jù)前面的數(shù)據(jù)，我們知道： u=0.25 ， u1=0.44 ， u2=0.42 ， 因此，如果采用方案一可獲利： 100 (0.44- 0.25) 50 450=500 （萬元） 如果采用方案二可獲利： 100 (0.42- 0.25) 50 400=450 （萬元）結(jié)論：選擇方案一，即吸引老客戶的方案為佳。 例：人力資源預(yù)測某高校1990年為編制師資發(fā)展規(guī)劃，需要預(yù)測為了教師隊(duì)伍的結(jié)構(gòu)?，F(xiàn)在對(duì)教師狀況進(jìn)行如下四個(gè)分類：青年，中年

4、，老年和流退（流失或退休）。根據(jù)歷史資料以及調(diào)查分析，各類教師按照一年一期的狀態(tài)轉(zhuǎn)移概率矩陣如下，目前青年教師400人，中年教師360人，老年教師300人。試分析3年后教師的結(jié)構(gòu)以及為保持編制不變，3年內(nèi)應(yīng)當(dāng)多少碩士和博士畢業(yè)生充實(shí)教師隊(duì)伍？馬爾可夫（ Markov ）鏈隨機(jī)過程：不確定變化的隨機(jī)變量序列時(shí)間序列：X1 ， X2 ， Xt, ，指與時(shí)間相關(guān)的離散隨機(jī)變量序列狀態(tài)集合： S=S1 ， S2 ， Sn ，一般表示為 Xt= Si無后效性（馬爾可夫性）：時(shí)間序列在 t+1 時(shí)刻（將來）的狀態(tài)只與 t 時(shí)刻（現(xiàn)在）的狀態(tài)有關(guān)而與 t 時(shí)刻之前（過去）的狀態(tài)無關(guān)，即 P Xk+1= Si

5、k+1/ X1=Sik1 ， X2=Sik2 ， ,Xk=Sik =P Xk+1= Sik+1/Xk=Sik馬爾可夫（ Markov ）鏈：具備無后效性的時(shí)間序列。狀態(tài)轉(zhuǎn)移概率矩陣 P狀態(tài)轉(zhuǎn)移概率： pij 表示從狀態(tài) Si 轉(zhuǎn)移到狀態(tài) Sj 的概率，記： pij= P （ Sj/ Si ） =P （ Xk+1=Sj/Xk= Si ）, 簡稱為從狀態(tài) i 到狀態(tài) j 的轉(zhuǎn)移概率。狀態(tài)轉(zhuǎn)移概率矩陣：由狀態(tài)轉(zhuǎn)移概率 pij （ i ， j=1,2 ，,n ）構(gòu)成的 n 階方陣 P多步狀態(tài)轉(zhuǎn)移概率 pij一步狀態(tài)轉(zhuǎn)移概率：用 pij(1) 表示， pij(1) 即 pij ，表示從狀態(tài) Si 經(jīng)過一

6、個(gè)時(shí)刻轉(zhuǎn)移到狀態(tài) Sj 的概率，記為： pij=pij(1)=P （ Xt+1= Sj/Xt= Si ）,相應(yīng)的一步狀態(tài)轉(zhuǎn)移概率矩陣記為 P （ 1 ）= P 。k 步狀態(tài)轉(zhuǎn)移概率：用 pij(k) 表示，表示從狀態(tài) Si 經(jīng)過 k 個(gè)時(shí)刻轉(zhuǎn)移到狀態(tài) Sj 的概率，記為： pij(k)=P （ Xt+ k=Sj/Xt= Si ）,相應(yīng)的 k 步狀態(tài)轉(zhuǎn)移概率矩陣記為 P （ k ）。 P(k) 與 P （ 1 ）之間的關(guān)系如何?例：三品牌洗衣粉下月購買意愿調(diào)查求（ 1 ）一步狀態(tài)轉(zhuǎn)移概率矩陣 P （ 1 ）=? （ 2 ）購買 C 品牌的顧客在未來第 2 個(gè)月購買各品牌的概率? （ 3 ）二步狀

7、態(tài)轉(zhuǎn)移概率矩陣 P （ 2 ）=?您發(fā)現(xiàn)P（K）的一般規(guī)律了嗎？ A B C 調(diào)查總數(shù) A B C 40 30 30 60 30 60 60 30 30 100 150 120規(guī)律:P(K)=Pk定理: k 步狀態(tài)轉(zhuǎn)移概率矩陣 P （ k ）等于一步狀態(tài)轉(zhuǎn)移概率矩陣 P （ 1 ）= P 的k 次冪, 即P(k)=P P P= Pk例：通過 P （ 1 ）計(jì)算 P （ 3 ）已知一步狀態(tài)轉(zhuǎn)移概率矩陣 P （ 1 ）= P ，計(jì)算三步狀態(tài)轉(zhuǎn)移概率矩陣P （ 3 ）=?固定概率向量 u設(shè) P 為馬爾可夫（ Markov ）鏈的一步狀態(tài)轉(zhuǎn)移概率矩陣，如果存在概率向量 u=( u1 ， u2 ，, u

8、n) 滿足于 uP =u 則稱 u 為 P 的固定概率向量或者均衡點(diǎn)示例： u 為 P 的固定概率向量引例中均衡狀態(tài)時(shí)的市場占有率就是 P 的固定概率向量（均衡點(diǎn)） u 。均衡點(diǎn)是否一定存在，是否唯一？牛奶廠例：市場占有率變動(dòng)表及均衡狀態(tài)月份 k三個(gè)廠家的市場占有率u1u2u3012345670.40.520.4960.50080.499840.5000320.50.50.30.240.2520.24960.250080.2499840.250.250.30.240.2520.24960.250080.2499840.250.25正規(guī)概率矩陣設(shè) P 為馬爾可夫鏈的一步狀態(tài)轉(zhuǎn)移概率矩陣，如果存在

9、自然數(shù) k 使 Pk 的所有元素都是正數(shù)，則稱 P 為正規(guī)概率矩陣。正規(guī)概率矩陣的例子正規(guī)概率矩陣的判斷方法：看任意兩狀態(tài)之間是否可以相互連通（彼此到達(dá)），若是，則為正規(guī)概率矩陣，若否，則不是正規(guī)概率矩陣。馬爾可夫鏈基本定理定理：設(shè) P 為馬爾可夫鏈的一步狀態(tài)轉(zhuǎn)移概率矩陣，如果 P 為正規(guī)概率矩陣，則存在唯一的由正數(shù)組成的固定概率向量（均衡點(diǎn)） u ，并且對(duì)于任意的初始概率向量 u0 ，向量序列: u0 P ， u0 P2 ， u0 Pk 以 u 為極限, 即當(dāng) k 時(shí),有 lim u0 Pk =u均衡點(diǎn)舉例均衡點(diǎn) u 的求法設(shè)概率向量 u 為狀態(tài)轉(zhuǎn)移矩陣 P 的均衡點(diǎn)，有： uP =u 即 u （ P- I） =0 ，其中I為單位矩陣 等式兩邊取轉(zhuǎn)置，得到： （ PT - I） uT =0方法：聯(lián)立求解以下線性方程組 （ PT - I） uT =0 u1+u2+ + un =1例：項(xiàng)目選址問題某汽車維修公司有甲、乙、丙3個(gè)維修廠。由于公司注重對(duì)員工的技術(shù)培訓(xùn)，樹立顧客至上，信譽(yù)第一的理念，管理模