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

1、引例：牛奶廠決策引例：牛奶廠決策 最佳經(jīng)營策略選擇：最佳經(jīng)營策略選擇： 北京地區(qū)鮮牛奶由三個廠家提供，該地北京地區(qū)鮮牛奶由三個廠家提供，該地區(qū)客戶總數(shù)為區(qū)客戶總數(shù)為 100 萬戶，假定廠家每年從每個萬戶，假定廠家每年從每個客戶那里平均獲利客戶那里平均獲利 50 元，客戶資源每月都在三元，客戶資源每月都在三個廠家之間相互流動，廠家個廠家之間相互流動，廠家 2 考慮從以下兩套考慮從以下兩套候選方案之中選擇一個實施：候選方案之中選擇一個實施： 方案一：吸引老客戶，須花費(fèi)方案一：吸引老客戶，須花費(fèi) 450 萬元；萬元； 方案二：吸引廠家方案二：吸引廠家 1 和廠家和廠家 3 的客戶，須花的客戶，須花費(fèi)

2、費(fèi) 400 萬元。萬元。 您有什么好的建議來幫助廠家您有什么好的建議來幫助廠家 2 決策？決策？市場調(diào)查數(shù)據(jù)市場調(diào)查數(shù)據(jù) 今年一月份廠家今年一月份廠家 2 對對 2000 名消費(fèi)者進(jìn)行了調(diào)名消費(fèi)者進(jìn)行了調(diào)查，購買廠家查，購買廠家 1 ， 2 ， 3 產(chǎn)品的消費(fèi)者人數(shù)分別為產(chǎn)品的消費(fèi)者人數(shù)分別為 800 ， 600 和和 600 ，得到市場占有率向量（概率向，得到市場占有率向量（概率向量）為（量）為（ 0.4 ， 0.3 ， 0.3 ）；）； 同時通過詢問這同時通過詢問這 2000 名消費(fèi)者下月的購買名消費(fèi)者下月的購買傾向，得到如下轉(zhuǎn)移頻數(shù)矩陣：傾向，得到如下轉(zhuǎn)移頻數(shù)矩陣： 1806036060

3、180360240240320n1 12 23 31 12 23 3狀態(tài)轉(zhuǎn)移概率矩陣狀態(tài)轉(zhuǎn)移概率矩陣 p 從轉(zhuǎn)移頻數(shù)矩陣到從轉(zhuǎn)移頻數(shù)矩陣到狀態(tài)轉(zhuǎn)移概率矩陣狀態(tài)轉(zhuǎn)移概率矩陣 p ： 用各行總數(shù)分別去除轉(zhuǎn)移頻數(shù)矩陣用各行總數(shù)分別去除轉(zhuǎn)移頻數(shù)矩陣 n 的每行的每行各元素，得到狀態(tài)轉(zhuǎn)移概率矩陣各元素，得到狀態(tài)轉(zhuǎn)移概率矩陣 p 如下：如下：1806036060180360240240320n3 . 01 . 06 . 01 . 03 . 06 . 03 . 03 . 04 . 0p/800/600/600均衡狀態(tài)的市場占有率均衡狀態(tài)的市場占有率 在目前狀態(tài)轉(zhuǎn)移概率矩陣在目前狀態(tài)轉(zhuǎn)移概率矩陣 p 下，達(dá)到

4、均衡狀態(tài)時的市下，達(dá)到均衡狀態(tài)時的市場占有率記為場占有率記為 u ；估計如果實施方案一或二以后狀態(tài)；估計如果實施方案一或二以后狀態(tài)轉(zhuǎn)移概率矩陣分別為轉(zhuǎn)移概率矩陣分別為 p1 和和 p2 ，他們各自對應(yīng)的均衡，他們各自對應(yīng)的均衡狀態(tài)時市場占有率分別為狀態(tài)時市場占有率分別為 u1 和和 u2 ；具體數(shù)據(jù)如下：；具體數(shù)據(jù)如下：3 . 01 . 06 . 01 . 03 . 06 . 03 . 03 . 04 . 0p3 . 01 . 06 . 007 . 03 . 03 . 03 . 04 . 01p1 . 05 . 04 . 01 . 03 . 06 . 02 . 05 . 03 . 02p u=

5、 （ 0.5 ，0.25 ， 0.25 ） u 1= （ 0.39 ， 0.44 ，0.17 ） u2= （ 0.44 ， 0.42 ，0.14 ）廠家廠家 2 2 的方案選擇的方案選擇 有了均衡狀態(tài)時的市場占有率有了均衡狀態(tài)時的市場占有率 u ， u1 和和 u2 ，廠家，廠家 2 就能夠方便地進(jìn)行分別方案選擇，根據(jù)前面的數(shù)據(jù)，就能夠方便地進(jìn)行分別方案選擇，根據(jù)前面的數(shù)據(jù)，我們知道：我們知道： u=0.25 ， u1=0.44 ， u2=0.42 ， 因此，如果采用方案一可獲利：因此，如果采用方案一可獲利： 100 (0.44- 0.25) 50 450=500 （萬元）（萬元） 如果采用方

6、案二可獲利：如果采用方案二可獲利： 100 (0.42- 0.25) 50 400=450 （萬元）（萬元）結(jié)論：選擇方案一，即吸引老客戶的方案為佳。結(jié)論：選擇方案一，即吸引老客戶的方案為佳。 例：人力資源預(yù)測例：人力資源預(yù)測 某某高校高校1990年為編制師資發(fā)展規(guī)劃，需要預(yù)測年為編制師資發(fā)展規(guī)劃，需要預(yù)測為了教師隊伍的結(jié)構(gòu)?，F(xiàn)在對教師狀況進(jìn)行如為了教師隊伍的結(jié)構(gòu)?，F(xiàn)在對教師狀況進(jìn)行如下四個分類：青年，中年，老年和流退（流失下四個分類：青年，中年，老年和流退（流失或退休）。根據(jù)歷史資料以及調(diào)查分析，各類或退休）。根據(jù)歷史資料以及調(diào)查分析，各類教師按照一年一期的狀態(tài)轉(zhuǎn)移概率矩陣如下，教師按照一年

7、一期的狀態(tài)轉(zhuǎn)移概率矩陣如下，目前青年教師目前青年教師400人，中年教師人，中年教師360人，老年教人，老年教師師300人。試分析人。試分析3年后教師的結(jié)構(gòu)以及為保持年后教師的結(jié)構(gòu)以及為保持編制不變，編制不變，3年內(nèi)應(yīng)當(dāng)多少碩士和博士畢業(yè)生年內(nèi)應(yīng)當(dāng)多少碩士和博士畢業(yè)生充實教師隊伍？充實教師隊伍？馬爾可夫（馬爾可夫（ markov markov ）鏈）鏈 隨機(jī)過程：不確定變化的隨機(jī)變量序列隨機(jī)過程：不確定變化的隨機(jī)變量序列 時間序列：時間序列：x1 ， x2 ， xt, ，指與時間相關(guān)，指與時間相關(guān)的離散隨機(jī)變量序列的離散隨機(jī)變量序列 狀態(tài)集合：狀態(tài)集合： s=s1 ， s2 ， sn ，一般表示

8、為，一般表示為 xt= si 無后效性（馬爾可夫性）：時間序列在無后效性（馬爾可夫性）：時間序列在 t+1 時刻（將來）時刻（將來）的狀態(tài)只與的狀態(tài)只與 t 時刻（現(xiàn)在）的狀態(tài)有關(guān)而與時刻（現(xiàn)在）的狀態(tài)有關(guān)而與 t 時刻之前時刻之前（過去）的狀態(tài)無關(guān)，即（過去）的狀態(tài)無關(guān)，即 p xk+1= sik+1/ x1=sik1 ， x2=sik2 ， ,xk=sik =p xk+1= sik+1/xk=sik 馬爾可夫（馬爾可夫（ markov ）鏈：具備無后效性的時間序列。）鏈：具備無后效性的時間序列。狀態(tài)轉(zhuǎn)移概率矩陣狀態(tài)轉(zhuǎn)移概率矩陣 p 狀態(tài)轉(zhuǎn)移概率：狀態(tài)轉(zhuǎn)移概率： pij 表示從狀態(tài)表示從狀態(tài)

9、 si 轉(zhuǎn)移到狀態(tài)轉(zhuǎn)移到狀態(tài) sj 的概的概率，記：率，記： pij= p （ sj/ si ） =p （ xk+1=sj/xk= si ）, 簡稱為從狀態(tài)簡稱為從狀態(tài) i 到狀態(tài)到狀態(tài) j 的轉(zhuǎn)移概率。的轉(zhuǎn)移概率。 狀態(tài)轉(zhuǎn)移概率矩陣：由狀態(tài)轉(zhuǎn)移概率狀態(tài)轉(zhuǎn)移概率矩陣：由狀態(tài)轉(zhuǎn)移概率 pij （ i ， j=1,2 ，,n ）構(gòu)成的）構(gòu)成的 n 階方陣階方陣 pnnnnnnnxnpppppppppppij.)(212222111211多步狀態(tài)轉(zhuǎn)移概率多步狀態(tài)轉(zhuǎn)移概率 pij 一步狀態(tài)轉(zhuǎn)移概率：用一步狀態(tài)轉(zhuǎn)移概率：用 pij(1) 表示，表示， pij(1) 即即 pij ，表，表示從狀態(tài)示從狀態(tài)

10、 si 經(jīng)過一個時刻轉(zhuǎn)移到狀態(tài)經(jīng)過一個時刻轉(zhuǎn)移到狀態(tài) sj 的概率，記為：的概率，記為： pij=pij(1)=p （ xt+1= sj/xt= si ）,相應(yīng)的一步狀態(tài)轉(zhuǎn)移概率矩陣記為相應(yīng)的一步狀態(tài)轉(zhuǎn)移概率矩陣記為 p （ 1 ）= p 。 k 步狀態(tài)轉(zhuǎn)移概率：用步狀態(tài)轉(zhuǎn)移概率：用 pij(k) 表示，表示從狀態(tài)表示，表示從狀態(tài) si 經(jīng)經(jīng)過過 k 個時刻轉(zhuǎn)移到狀態(tài)個時刻轉(zhuǎn)移到狀態(tài) sj 的概率，記為：的概率，記為： pij(k)=p （ xt+ k=sj/xt= si ）,相應(yīng)的相應(yīng)的 k 步狀態(tài)轉(zhuǎn)移概率矩陣記為步狀態(tài)轉(zhuǎn)移概率矩陣記為 p （ k ）。）。 p(k) 與與 p （ 1 ）之

11、間的關(guān)系如何）之間的關(guān)系如何?例：三品牌洗衣粉下月例：三品牌洗衣粉下月購買意愿調(diào)查購買意愿調(diào)查求（求（ 1 ）一步狀態(tài)轉(zhuǎn)移概率矩陣）一步狀態(tài)轉(zhuǎn)移概率矩陣 p （ 1 ）=? （ 2 ）購買）購買 c 品牌的顧客在未來第品牌的顧客在未來第 2 個月購買個月購買各品牌的概率各品牌的概率? （ 3 ）二步狀態(tài)轉(zhuǎn)移概率矩陣）二步狀態(tài)轉(zhuǎn)移概率矩陣 p （ 2 ）=?您發(fā)現(xiàn)您發(fā)現(xiàn)p（k）的一般規(guī)律了嗎？）的一般規(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)移概率矩陣步狀態(tài)轉(zhuǎn)移概率矩陣

12、p （ k ）等于一步狀態(tài)轉(zhuǎn)移概率矩陣等于一步狀態(tài)轉(zhuǎn)移概率矩陣 p （ 1 ）= p 的的k 次冪次冪, 即即 p(k)=p p p= pk例：通過例：通過 p p （ 1 1 ）計算）計算 p p （ 3 3 ） 已知一步狀態(tài)轉(zhuǎn)移概率矩陣已知一步狀態(tài)轉(zhuǎn)移概率矩陣 p （ 1 ）= p ，計算三步狀態(tài)轉(zhuǎn)移概率矩陣計算三步狀態(tài)轉(zhuǎn)移概率矩陣p （ 3 ）=?固定概率向量固定概率向量 u u 設(shè)設(shè) p 為馬爾可夫（為馬爾可夫（ markov ）鏈的一步狀態(tài)轉(zhuǎn)移概率）鏈的一步狀態(tài)轉(zhuǎn)移概率矩陣，如果存在概率向量矩陣，如果存在概率向量 u=( u1 ， u2 ，, un) 滿足滿足于于 up =u 則稱則

13、稱 u 為為 p 的固定概率向量或者均衡點(diǎn)的固定概率向量或者均衡點(diǎn) 示例：示例： u 為為 p 的固定概率向量的固定概率向量 引例中均衡狀態(tài)時的市場占有率就是引例中均衡狀態(tài)時的市場占有率就是 p 的固定的固定概率向量（均衡點(diǎn)）概率向量（均衡點(diǎn)） u 。 均衡點(diǎn)是否一定存在，是否唯一？均衡點(diǎn)是否一定存在，是否唯一？牛奶廠例：市場占有率變動牛奶廠例：市場占有率變動表及均衡狀態(tài)表及均衡狀態(tài)月份月份 k三個三個廠家的市場占有率廠家的市場占有率u1u2u3012345670.40.520.4960.50080.499840.5000320.50.50.30.240.2520.24960.250080.2

14、499840.250.250.30.240.2520.24960.250080.2499840.250.253 . 01 . 06 . 01 . 03 . 06 . 03 . 03 . 04 . 0p正規(guī)概率矩陣正規(guī)概率矩陣 設(shè)設(shè) p 為馬爾可夫鏈的一步狀態(tài)轉(zhuǎn)移概率矩陣，如果為馬爾可夫鏈的一步狀態(tài)轉(zhuǎn)移概率矩陣，如果存在自然數(shù)存在自然數(shù) k 使使 pk 的所有元素都是正數(shù)，則稱的所有元素都是正數(shù)，則稱 p 為正規(guī)概率矩陣。為正規(guī)概率矩陣。 正規(guī)概率矩陣的例子正規(guī)概率矩陣的例子 正規(guī)概率矩陣的判斷方法：看任意兩狀態(tài)之間是否正規(guī)概率矩陣的判斷方法：看任意兩狀態(tài)之間是否可以相互連通（彼此到達(dá)），若是，

15、則為正規(guī)概率可以相互連通（彼此到達(dá)），若是，則為正規(guī)概率矩陣，若否，則不是正規(guī)概率矩陣。矩陣，若否，則不是正規(guī)概率矩陣。馬爾可夫鏈基本定理馬爾可夫鏈基本定理 定理：設(shè)定理：設(shè) p 為馬爾可夫鏈的一步狀態(tài)轉(zhuǎn)移概率矩為馬爾可夫鏈的一步狀態(tài)轉(zhuǎn)移概率矩陣，如果陣，如果 p 為正規(guī)概率矩陣，則存在唯一的由正為正規(guī)概率矩陣，則存在唯一的由正數(shù)組成的固定概率向量（均衡點(diǎn)）數(shù)組成的固定概率向量（均衡點(diǎn)） u ，并且對于，并且對于任意的初始概率向量任意的初始概率向量 u0 ，向量序列，向量序列: u0 p ， u0 p2 ， u0 pk 以以 u 為極限為極限, 即當(dāng)即當(dāng) k 時時,有有 lim u0 pk =

16、u 均衡點(diǎn)舉例均衡點(diǎn)舉例均衡點(diǎn) u 的求法 設(shè)概率向量設(shè)概率向量 u 為狀態(tài)轉(zhuǎn)移矩陣為狀態(tài)轉(zhuǎn)移矩陣 p 的均衡點(diǎn)，有：的均衡點(diǎn)，有： up =u 即即 u （ p- i） =0 ，其中，其中i為單位矩陣為單位矩陣 等式兩邊取轉(zhuǎn)置，得到：等式兩邊取轉(zhuǎn)置，得到： （ pt - i） ut =0 方法：聯(lián)立求解以下線性方程組方法：聯(lián)立求解以下線性方程組 （ pt - i） ut =0 u1+u2+ + un =1例：項目選址問題例：項目選址問題 某某汽車維修公司有甲、乙、丙汽車維修公司有甲、乙、丙3個維修廠。由于公個維修廠。由于公司注重對員工的技術(shù)培訓(xùn)，樹立顧客至上，信譽(yù)第司注重對員工的技術(shù)培訓(xùn)，樹立顧客至上，信譽(yù)第一的理念，管理模式先進(jìn)，所以公司在本行業(yè)具有一的理念，管理模式先進(jìn)，所以公司在本行業(yè)具有良好的形象，形成了一定規(guī)模的客戶群。對客戶的良好的形象，形成了一定規(guī)模的客戶群。對客戶的