iT邦幫忙

第 11 屆 iThome 鐵人賽

DAY 26
0
AI & Data

連接數學與現實世界的橋樑 -- 數學建模系列 第 26

Day 26 : 隨機模型 -- 馬可夫鏈

  • 分享至 

  • xImage
  •  

當我們把不確定性納進模型時,所得到的模型可稱為隨機模型。接下來將介紹幾種經常使用的隨機模型,首先是馬可夫鏈

馬可夫鏈是一個離散時間的隨機模型,也可以看成是離散時間動力系統模型的延伸。

範例

五金店出售水族箱,每個周末商店老闆要盤點存貨,開出訂單。商店的策略是,如果當前所有的存貨都售出了,就在周末進三個新的水族箱,只要店內還有一個存貨,就不會再進新的。這個策略是基於商店平均每周僅出售一個水族箱的前提而訂定的。試問此策略是否能防止當商點缺貨時顧客需要水族箱而無貨銷售的損失。

  1. 提出問題
    假設前提為潛在購買者人數服從平均值為1的普瓦松分配。每周開始時,商店的存貨在1~3個水族箱之間,希望可以得知需求超過供給的機率。
    變量:
    https://chart.googleapis.com/chart?cht=tx&chl=S_n%20%3D%20https://chart.googleapis.com/chart?cht=tx&chl=n周開始水族箱的供給
    https://chart.googleapis.com/chart?cht=tx&chl=D_n%20%3D%20https://chart.googleapis.com/chart?cht=tx&chl=n周內水族箱的需求
    假設:
    如果https://chart.googleapis.com/chart?cht=tx&chl=D_%7Bn-1%7D%20%3C%20S_%7Bn-1%7D,則https://chart.googleapis.com/chart?cht=tx&chl=S_n%20%3D%20S_%7Bn-1%7D%20-%20D_%7Bn-1%7D
    如果https://chart.googleapis.com/chart?cht=tx&chl=D_%7Bn-1%7D%20%5Cge%20S_%7Bn-1%7D,則https://chart.googleapis.com/chart?cht=tx&chl=S_n%20%3D%203
    https://chart.googleapis.com/chart?cht=tx&chl=Pr%20%5Cleft%20%7B%20D_n%20%3D%20k%5Cright%20%7D%20%3D%20%5Cfrac%7Be%5E%7B-1%7D%7D%7Bk!%7D
    目標:
    計算https://chart.googleapis.com/chart?cht=tx&chl=Pr%20%5Cleft%20%7B%20D_n%20%3E%20S_n%20%5Cright%20%7D
  2. 選擇建模方法
    馬可夫鏈可以被描述為一個隨機跳躍的序列,在此列中,跳要續列為有限個離散的位置或狀態的集合,且隨機變量https://chart.googleapis.com/chart?cht=tx&chl=X_n%20%5Cin%20%5Cleft%20%7B1%2C2%2C3%2C%20%5Cdots%2C%20m%20%5Cright%20%7D
    https://chart.googleapis.com/chart?cht=tx&chl=p_%7Bij%7D%20%3D%20Pr%20%5Cleft%7B%20X_%7Bn%2B1%7D%20%3D%20j%20%7C%20X_n%20%3D%20i%20%5Cright%20%7D,即https://chart.googleapis.com/chart?cht=tx&chl=X_%7Bn%2B1%7D%20%3D%20j的機率僅根據https://chart.googleapis.com/chart?cht=tx&chl=X_n,則序列https://chart.googleapis.com/chart?cht=tx&chl=%5Cleft%20%7B%20X_n%20%5Cright%20%7D是馬可夫鏈。
  3. 推導模型的數學表達式
    令狀態轉移矩陣為https://chart.googleapis.com/chart?cht=tx&chl=P,狀態空間為https://chart.googleapis.com/chart?cht=tx&chl=X_n%20%5Cin%20%5Cleft%20%7B%201%2C%202%2C%203%20%5Cright%20%7D,初始狀態為https://chart.googleapis.com/chart?cht=tx&chl=X_0%20%3D%203。狀態轉移圖如下,
    https://ithelp.ithome.com.tw/upload/images/20190928/20119600BvVkZ6Lkht.jpg
    需求量分布為,
    https://chart.googleapis.com/chart?cht=tx&chl=Pr%20%5Cleft%7B%20D_n%20%3D%200%20%5Cright%7D%20%3D%200.368
    https://chart.googleapis.com/chart?cht=tx&chl=Pr%20%5Cleft%7B%20D_n%20%3D%201%20%5Cright%7D%20%3D%200.368
    https://chart.googleapis.com/chart?cht=tx&chl=Pr%20%5Cleft%7B%20D_n%20%3D%202%20%5Cright%7D%20%3D%200.184
    https://chart.googleapis.com/chart?cht=tx&chl=Pr%20%5Cleft%7B%20D_n%20%3D%203%20%5Cright%7D%20%3D%200.061
    https://chart.googleapis.com/chart?cht=tx&chl=Pr%20%5Cleft%7B%20D_n%20%3E%203%20%5Cright%7D%20%3D%200.019
    於是,若https://chart.googleapis.com/chart?cht=tx&chl=X_n%20%3D%203,則https://chart.googleapis.com/chart?cht=tx&chl=Pr%20%5Cleft%7B%20X_%7Bn%2B1%7D%20%3D%201%20%5Cright%7D%20%3D%20Pr%20%5Cleft%7B%20D_n%20%3D%202%20%5Cright%7D%20%3D%200.184
    https://chart.googleapis.com/chart?cht=tx&chl=Pr%20%5Cleft%7B%20X_%7Bn%2B1%7D%20%3D%202%20%5Cright%7D%20%3D%20Pr%20%5Cleft%7B%20D_n%20%3D%201%20%5Cright%7D%20%3D%200.368
    https://chart.googleapis.com/chart?cht=tx&chl=Pr%20%5Cleft%7B%20X_%7Bn%2B1%7D%20%3D%203%20%5Cright%7D%20%3D%201%20-%200.184%20-%200.368%20%3D%200.448
    其餘的狀態轉移機率可以由此類似的算出,故狀態轉移矩陣為
    https://ithelp.ithome.com.tw/upload/images/20190928/20119600vfaHGzUlJj.jpg
  4. 求解模型
    因為https://chart.googleapis.com/chart?cht=tx&chl=%7BX_n%7D是一個遍歷的馬可夫鏈,亦即在有限步長內從狀態i跳到狀態j。當馬可夫鏈是遍歷的,則一定會趨於穩定的狀態,即存在唯一的平穩態機率向量https://chart.googleapis.com/chart?cht=tx&chl=%5Cpi。透過https://chart.googleapis.com/chart?cht=tx&chl=%5Cpi%20%3D%20%5Cpi%20P,可以求解線性方程組來計算https://chart.googleapis.com/chart?cht=tx&chl=%5Cpi,因此有方程組
    https://chart.googleapis.com/chart?cht=tx&chl=%5Cpi_1%20%3D%200.368%20%5Cpi_1%20%2B%200.368%20%5Cpi_2%20%2B%200.184%20%5Cpi_3
    https://chart.googleapis.com/chart?cht=tx&chl=%5Cpi_2%20%3D%200.368%20%5Cpi_2%20%2B%200.368%20%5Cpi_3
    https://chart.googleapis.com/chart?cht=tx&chl=%5Cpi_3%20%3D%200.632%20%5Cpi_1%20%2B%200.264%20%5Cpi_2%20%2B%200.448%20%5Cpi_3
    限制條件為
    https://chart.googleapis.com/chart?cht=tx&chl=%5Cpi_1%20%2B%20%5Cpi_2%20%2B%20%5Cpi_3%20%3D%201
    解得https://chart.googleapis.com/chart?cht=tx&chl=%5CPi%20%3D%20(%5Cpi_1%20%2C%20%5Cpi_2%20%2C%20%5Cpi_3%20)%20%3D%20(0.285%2C%200.263%2C%200.452)
    https://chart.googleapis.com/chart?cht=tx&chl=n足夠大時,可近似得
    https://chart.googleapis.com/chart?cht=tx&chl=Pr%20%5Cleft%7B%20X_n%20%3D%201%20%5Cright%7D%20%3D%200.285
    https://chart.googleapis.com/chart?cht=tx&chl=Pr%20%5Cleft%7B%20X_n%20%3D%202%20%5Cright%7D%20%3D%200.263
    https://chart.googleapis.com/chart?cht=tx&chl=Pr%20%5Cleft%7B%20X_n%20%3D%203%20%5Cright%7D%20%3D%200.452
    最後將其與https://chart.googleapis.com/chart?cht=tx&chl=D_n整合一起,
    https://chart.googleapis.com/chart?cht=tx&chl=Pr%20%5Cleft%7B%20D_n%20%3E%20S_n%20%5Cright%7D%20%3D%20%5Csum_%7Bi%3D1%7D%5E3%20Pr%20%5Cleft%7B%20D_n%20%3E%20S_n%20%7C%20X_n%20%3D%20i%20%5Cright%7DPr%20%5Cleft%7B%20X_n%20%3D%20i%20%5Cright%7D
    https://chart.googleapis.com/chart?cht=tx&chl=%3D%20Pr%20%5Cleft%20%7BD_n%20%3E%201%20%7C%20X_n%20%3D%201%20%5Cright%20%7D%20Pr%20%5Cleft%20%7BX_n%20%3D%201%20%5Cright%20%7D%20%2B%20Pr%20%5Cleft%20%7BD_n%20%3E%202%20%7C%20X_n%20%3D%202%20%5Cright%20%7D%20Pr%20%5Cleft%20%7BX_n%20%3D%202%20%5Cright%20%7D%20%2B%20Pr%20%5Cleft%20%7BD_n%20%3E%203%20%7C%20X_n%20%3D%203%20%5Cright%20%7D%20Pr%20%5Cleft%20%7BX_n%20%3D%203%20%5Cright%20%7D
    https://chart.googleapis.com/chart?cht=tx&chl=%3D%20(0.184%20%2B%200.061%20%2B%200.019)%20*%200.285%20%2B%20(0.061%20%2B%200.019)%20*%200.263%20%2B%200.019%20*%200.452
    https://chart.googleapis.com/chart?cht=tx&chl=%3D%200.105
  5. 表達模型結果
    根據結果,當前的存貨策略會有約10%的時間無貨銷售的損失。

上一篇
Day 25 : 機率分配
下一篇
Day 27 : 隨機模型 -- 馬可夫過程
系列文
連接數學與現實世界的橋樑 -- 數學建模30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言