運籌學(xué)課件——第4講 馬爾可夫決策.ppt

引例 牛奶廠決策 最佳經(jīng)營策略選擇 北京地區(qū)鮮牛奶由三個廠家提供 該地區(qū)客戶總數(shù)為100萬戶 假定廠家每年從每個客戶那里平均獲利50元 客戶資源每月都在三個廠家之間相互流動 廠家2考慮從以下兩套候選方案之中選擇一個實施 方案一 吸引老客戶 須花費450萬元 方案二 吸引廠家1和廠家3的客戶 須花費400萬元 您有什么好的建議來幫助廠家2決策 市場調(diào)查數(shù)據(jù) 今年一月份廠家2對2000名消費者進行了調(diào)查 購買廠家1 2 3產(chǎn)品的消費者人數(shù)分別為800 600和600 得到市場占有率向量 概率向量 為 0 4 0 3 0 3 同時通過詢問這2000名消費者下月的購買傾向 得到如下轉(zhuǎn)移頻數(shù)矩陣 1 2 3 1 2 3 狀態(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下 達到均衡狀態(tài)時的市場占有率記為u 估計如果實施方案一或二以后狀態(tài)轉(zhuǎn)移概率矩陣分別為P1和P2 他們各自對應(yīng)的均衡狀態(tài)時市場占有率分別為u1和u2 具體數(shù)據(jù)如下 u 0 5 0 25 0 25 u1 0 39 0 44 0 17 u2 0 44 0 42 0 14 廠家2的方案選擇 有了均衡狀態(tài)時的市場占有率u u1和u2 廠家2就能夠方便地進行分別方案選擇 根據(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ù)測為了教師隊伍的結(jié)構(gòu) 現(xiàn)在對教師狀況進行如下四個分類 青年 中年 老年和流退 流失或退休 根據(jù)歷史資料以及調(diào)查分析 各類教師按照一年一期的狀態(tài)轉(zhuǎn)移概率矩陣如下 目前青年教師400人 中年教師360人 老年教師300人 試分析3年后教師的結(jié)構(gòu)以及為保持編制不變 3年內(nèi)應(yīng)當(dāng)多少碩士和博士畢業(yè)生充實教師隊伍 馬爾可夫 Markov 鏈 隨機過程 不確定變化的隨機變量序列時間序列 X1 X2 Xt 指與時間相關(guān)的離散隨機變量序列狀態(tài)集合 S S1 S2 Sn 一般表示為Xt Si無后效性 馬爾可夫性 時間序列在t 1時刻 將來 的狀態(tài)只與t時刻 現(xiàn)在 的狀態(tài)有關(guān)而與t時刻之前 過去 的狀態(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)移概率矩陣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)過一個時刻轉(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個時刻轉(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個月購買各品牌的概率 3 二步狀態(tài)轉(zhuǎn)移概率矩陣P 2 您發(fā)現(xiàn)P K 的一般規(guī)律了嗎 規(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 計算P 3 已知一步狀態(tài)轉(zhuǎn)移概率矩陣P 1 P 計算三步狀態(tài)轉(zhuǎn)移概率矩陣P 3 固定概率向量u 設(shè)P為馬爾可夫 Markov 鏈的一步狀態(tài)轉(zhuǎn)移概率矩陣 如果存在概率向量u u1 u2 un 滿足于uP u則稱u為P的固定概率向量或者均衡點示例 u為P的固定概率向量引例中均衡狀態(tài)時的市場占有率就是P的固定概率向量 均衡點 u 均衡點是否一定存在 是否唯一 牛奶廠例 市場占有率變動表及均衡狀態(tài) 正規(guī)概率矩陣 設(shè)P為馬爾可夫鏈的一步狀態(tài)轉(zhuǎn)移概率矩陣 如果存在自然數(shù)k使Pk的所有元素都是正數(shù) 則稱P為正規(guī)概率矩陣 正規(guī)概率矩陣的例子正規(guī)概率矩陣的判斷方法 看任意兩狀態(tài)之間是否可以相互連通 彼此到達 若是 則為正規(guī)概率矩陣 若否 則不是正規(guī)概率矩陣 馬爾可夫鏈基本定理 定理 設(shè)P為馬爾可夫鏈的一步狀態(tài)轉(zhuǎn)移概率矩陣 如果P為正規(guī)概率矩陣 則存在唯一的由正數(shù)組成的固定概率向量 均衡點 u 并且對于任意的初始概率向量u0 向量序列 u0P u0P2 u0Pk以u為極限 即當(dāng)k 時 有l(wèi)imu0Pk u均衡點舉例 均衡點u的求法 設(shè)概率向量u為狀態(tài)轉(zhuǎn)移矩陣P的均衡點 有 uP u即u P I 0 其中I為單位矩陣等式兩邊取轉(zhuǎn)置 得到 PT I uT 0方法 聯(lián)立求解以下線性方程組 PT I uT 0u1 u2 un 1 例 項目選址問題 某汽車維修公司有甲 乙 丙3個維修廠 由于公司注重對員工的技術(shù)培訓(xùn) 樹立顧客至上 信譽第一的理念 管理模式先進 所以公司在本行業(yè)具有良好的形象 形成