運籌學思想方法及應用 ch8 馬爾可夫預測方法

2023/2/51第八章馬爾可夫預測方法運籌學OperationalResearch2023/2/52馬爾可夫預測（MarkovForecast）也稱為馬爾可夫分析，作為一種企業(yè)管理的工具,已經(jīng)成功地應用到許多場合.它的優(yōu)點在于依靠現(xiàn)在資料推知未來,計算比較精確,適用于中、長期預測.因此，較多地應用于市場需求等諸多領域的預測.2023/2/538.1馬爾可夫過程定義及其性質8.2遍歷性定理與平衡態(tài)預測8.3馬爾可夫預測的應用8.4WinQSB軟件應用2023/2/548.1馬爾可夫過程定義及其性質2023/2/558.1馬爾可夫過程定義及其性質

1.馬爾可夫及其馬爾可夫過程馬爾可夫（A.Markov，1856—1922）俄國數(shù)學家.1878年大學畢業(yè)于彼得堡大學數(shù)學系，1884年獲物理數(shù)學博士學位，1886年成為教授，1896年當選為彼得堡院士.對概率論、數(shù)理統(tǒng)計、數(shù)論、函數(shù)逼近論、微分方程、數(shù)的幾何等都有建樹.他開創(chuàng)了一種無后效性隨機過程的研究，即在已知當前狀態(tài)的情況下，過程的未來狀態(tài)與其過去狀態(tài)無關，這就是現(xiàn)在大家熟悉的馬爾可夫過程.馬爾可夫的工作極大的豐富了概率論的內容，促使它成為自然科學和技術直接有關的最重要的數(shù)學領域之一.2023/2/568.1馬爾可夫過程定義及其性質我們先介紹幾個與馬爾科夫過程相關的概念.

隨機變量與隨機過程把隨機現(xiàn)象的每個結果對應一個數(shù)，這種對應關系稱為隨機變量.例如某一時間內公共汽車站等車乘客的人數(shù)，電話交換臺在一定時間內收到的呼叫次數(shù)等等，都是隨機變量的實例.

隨機過程隨機過程是一連串隨機事件動態(tài)關系的定量描述.

馬爾科夫過程與馬爾科夫鏈設x(t)是一隨機過程，當過程在時刻t0所處的狀態(tài)為已知時，時刻t（t>t0）所處的狀態(tài)與過程在時刻t0之前的狀態(tài)無關，這個特性成為無后效性.無后效的隨機過程稱為馬爾科夫過程(MarkovProcess).馬爾科夫過程中的時間和狀態(tài)既可以是連續(xù)的，又可以是離散的.我們稱時間離散、狀態(tài)離散的馬爾科夫過程為馬爾科夫鏈.2023/2/578.1馬爾可夫過程定義及其性質為了形象說明“狀態(tài)”和“狀態(tài)的轉移”的概念，假設在一個水池中有三片荷葉，一只青蛙在三片荷葉之間跳躍玩耍，見圖.觀察青蛙的活動會發(fā)現(xiàn)青蛙的動作是隨意的.為討論方便，我們給荷葉編號，我們關心的是在一定時間內，它從一片荷葉跳到其他兩片荷葉的轉移結構.當青蛙在第1片荷葉上時，它下一步動作跳躍到第2、3片荷葉上或原地不動，只與現(xiàn)在的位置1有關，而與它以前跳過的路徑無關.我們給出這只青蛙從各片荷葉上向另一片荷葉移動的轉移圖，見圖.2023/2/588.1馬爾可夫過程定義及其性質箭頭表示跳躍的方向，數(shù)字表示跳躍的概率，白環(huán)表示青蛙保持不動.此圖表明：在一定時間內，當青蛙開始時刻在第1片荷葉上時，它保持不動的概率為0.3，它跳躍到第2片荷葉上的概率為0.6，跳躍到第3片荷葉上的概率為0.1；當青蛙開始時刻在第2片荷葉上時，它保持不動的概率為0.4，它跳躍到第1片荷葉上的概率為0.2，跳躍到第3片荷葉上的概率為0.4；當青蛙開始時刻在第3片荷葉上時，它保持不動的概率為0.5，它跳躍到第1片荷葉上的概率為0.2，跳躍到第2片荷葉上的概率為0.3.2023/2/598.1馬爾可夫過程定義及其性質我們以x(t)表示青蛙跳躍t次后所處的位置,x(t)的取值叫做狀態(tài)，S={1,2,3}叫狀態(tài)空間.我們稱{x(t)}(t>0)為一個隨機過程.當從x(0)到x(t)已知時，青蛙在t+1時處在x(t+1)狀態(tài)上的概率僅與t時刻狀態(tài)有關，即滿足以下關系式

（8.1）

我們稱滿足（8.1）式的隨機過程{x(t)}(t>0)為馬爾可夫過程或馬爾可夫鏈，而把（8.1）式的隨機過程{x(t)}稱為馬爾可夫性，它反映了前一狀態(tài)x(t-1)

、現(xiàn)狀態(tài)x(t)和后一狀態(tài)x(t+1)之間的鏈接.因此，用馬爾可夫鏈描述隨機性狀態(tài)變量的變化時，只需求在某一點上兩個相鄰隨機變量的條件分布就可以了.2023/2/510我們稱為轉移概率.由于這種轉移概率不依賴于時間，因此具有穩(wěn)定性，我們用常數(shù)來表示.將各個狀態(tài)之間的轉移概率用一個矩陣表示出來，就得到一個馬爾科夫問題（有限狀態(tài)穩(wěn)定的馬爾可夫過程問題）的數(shù)學模型：2023/2/5118.1馬爾可夫過程定義及其性質稱矩陣為一步概率轉移矩陣，簡稱轉移矩陣.由于轉移矩陣的每行都是獨立的分布，所有每行的元素滿足下列性質：（8.2）

（8.3）2023/2/5128.1馬爾可夫過程定義及其性質

2.馬爾可夫鏈的基本方程

馬爾可夫性質的數(shù)學描述是：對任意的時間及任意的狀態(tài)i,j,i1，…，it,都有由圖8.2，青蛙跳躍的一步轉移矩陣為

2023/2/5138.1馬爾可夫過程定義及其性質其中為一步轉移概率.如果用矩陣表示步轉移概率組成的矩陣,（8.5）式的矩陣表達式為如果x(t)是齊次的（即對一切狀態(tài)i,j,條件概率（8.4）（8.5）（8.6）與m的取值無關）,則2023/2/514稱（8.5）或（8.6）式為柯爾莫哥洛夫—卡普曼方程,簡記為K-C方程.

特別地,8.1馬爾可夫過程定義及其性質（8.7）其中為系統(tǒng)經(jīng)過步轉移后處于狀態(tài)的概率.（8.8）

或者,同理有.設從（8.4）式,易見有2023/2/5158.1馬爾可夫過程定義及其性質記為系統(tǒng)的初始狀態(tài)向量,則（8.8）式的前一等式可表示為

由于,故有（8.9）由上述內容可以看到,應用馬爾可夫預測法的關鍵是要找出所考察系統(tǒng)的一步轉移矩陣及初始狀態(tài)向量..2023/2/516下面通過實例理解上述的預測模型.【例8.1】設任意相繼的兩天中，雨天轉晴天的概率為1/3，晴天轉雨天的概率為1/2，任一天晴或雨是互為逆事件.以0表示晴天狀態(tài)，以1表示雨天狀態(tài)，表示第8.1馬爾可夫過程定義及其性質

天狀態(tài)（0或1）.試寫出馬爾可夫鏈的一步轉移概率矩陣；又已知10月1日為晴天，問10月3日為晴天、10月5日為雨天的概率各等于多少？解由于任一天晴或雨是互為逆事件，而且雨天轉晴天的概率為1/3，晴天轉雨天的概率為1/2，故一步轉移概率矩陣分別為

2023/2/5178.1馬爾可夫過程定義及其性質由于故一步轉移概率矩陣為2023/2/5188.1馬爾可夫過程定義及其性質故10月1日為晴天，10月3日為晴天的概率為10月1日為晴天，10月5日為雨天的概率為2023/2/5198.1馬爾可夫過程定義及其性質【例8.2】已知,上月共銷售100萬包洗衣粉,其中、、三種牌號各為30萬包、40萬包、30萬包.又知本月與下月市場客量不變.試預測本月和下月三種牌號洗衣粉的市場占有率,并給出從本月起第六個月的市場占有率.

解將上月市場占有率寫成向量形式，也即初始狀態(tài)向量轉移矩陣為2023/2/5208.1馬爾可夫過程定義及其性質則本月市場占有率應為下月市場占有率應為2023/2/5218.1馬爾可夫過程定義及其性質由此可知：本月A、B、C三種牌號的洗衣粉預測銷售量依次為25萬,37萬,38萬包；下月則依次為22.5萬,34.7萬,42.8萬包.

從本月算起第六個月的市場占有率為2023/2/5228.1馬爾可夫過程定義及其性質可見A、B、C三種牌號洗衣粉的市場占有率,隨著月數(shù)的增長,,兩種牌號洗衣粉的市場占有率逐期下降,而牌號洗衣粉的市場占有率卻逐月上升.如果三個廠家都不采取競爭手段,如此發(fā)展下去,最終市場占有率將會是什么樣呢？利用馬爾可夫鏈的遍歷性定理可以回答這個問題.2023/2/5238.2遍歷性定理與平衡態(tài)預測2023/2/5248.2遍歷性定理與平衡態(tài)預測

遍歷性定理如果存在一個整數(shù)s,使對一切的狀態(tài)i或j均有pij(s)>0

，則極限

1.遍歷性與遍歷性定理設齊次馬爾可夫鏈的狀態(tài)空間為

，若對所有的

轉移概率

都存在極限

（不依賴于

），則稱該馬爾可夫鏈具有遍歷性.

對任意狀態(tài)或存在（注意：極限與起始狀態(tài)無關）,同時,這些極限是（8.10）2023/2/5258.2遍歷性定理與平衡態(tài)預測

（8.11）

及條件的唯一解（證明略）.方程組（8.10）式用矩陣表示,即2023/2/5268.2遍歷性定理與平衡態(tài)預測記（8.12）我們稱為轉移矩陣的固有概率向量,應滿足條件（8.11）2.平衡預測態(tài)遍歷性定理告訴我們,如無新的外界影響改變轉移概率,則系統(tǒng)早晚會進入平衡狀態(tài).這對管理決策十分有用.2023/2/5278.2遍歷性定理與平衡態(tài)預測.設【例8.3】

（例8.2續(xù)）求穩(wěn)定狀態(tài)時A、B、C三種洗衣粉的市場占有率,也就是求出最終市場占有率.解由遍歷性定理,我們只需求出方程組（8.12）滿足條件（8.11）的唯一解.這等價于求出轉移矩陣的滿足條件（8.11）的固有概率向量則由（8.12）式2023/2/5288.2遍歷性定理與平衡態(tài)預測即由解出2023/2/5298.2遍歷性定理與平衡態(tài)預測這表明A、B、C三種洗衣粉的最終市場占有率分別為20%,30%,50%.如果生產(chǎn)A牌洗衣粉的A廠對此嚴峻的市場局面,決定采取競爭手段.經(jīng)過分析認為,采取加強廣告宣傳的手段,可以改變轉移概率,使得買B和C牌的顧客有一部分轉而購買A牌.假設改變后的轉移概率為即得新的轉移矩陣2023/2/5308.2遍歷性定理與平衡態(tài)預測利用上述同樣方法,可求出最終市場占有率為A牌占33.3%,B牌占26.7%,C牌占40%.這正是A廠利用馬爾可夫預測進行決策的優(yōu)勢.2023/2/5318.2遍歷性定理與平衡態(tài)預測【例8.4】某市場銷售A、B、C三廠家生產(chǎn)的汽車備件,經(jīng)過市場調查分析得知：市場容量為10萬戶；轉移矩陣P為

問題：A廠通過加強廣告宣傳的手段,使最終市場占有率提高了13.3%,所帶來的經(jīng)濟效益是否大于廣告費用？因為只有此種手段帶來的經(jīng)濟效益大于廣告費用時,采用此種手段競爭才是可行的.這類問題又如何分析呢？請看下例.本月

上月

ABC

ABC2023/2/5328.2遍歷性定理與平衡態(tài)預測矩陣中第1行元素0.4，0.3，0.2分別表示：上月為A廠的客戶，本月仍為A廠的客戶占40%，本月轉為B廠的客戶占30%，本月轉為C廠的客戶占30%.第2，3行元素的意義類同.求：（1）在三廠家都不采取競爭措施時的最終市場占有率；（2）若B廠采取競爭措施,如提高產(chǎn)品質量、適當降低價格、加強廣告宣傳及售后服務等,以提高市場占有率.具體方案有方案一：采取上述措施,投資50萬元,使轉移矩陣為2023/2/5338.2遍歷性定理與平衡態(tài)預測可以使老用戶保留到50%,使廠從廠爭取用戶從60%下降為40%.方案二：投資60萬元,使轉移矩陣為2023/2/5348.2遍歷性定理與平衡態(tài)預測可以從C廠爭取20%客戶,從廠爭取10%客戶.若每個用戶使用B廠汽車備件能為B廠提供100元盈利,試問B廠應采用哪一個方案？解(1)記轉移矩陣P的固有概率向量為則由方程組解出2023/2/5358.2遍歷性定理與平衡態(tài)預測換言之,在三廠家都不采取競爭措施時,最終市場占有率為：A廠占50%,B廠占25%,C廠占25%.（2）B廠若采用方案一,此時轉矩陣為

由.解得

在此方案下,B廠可增加新用戶盈利（萬元）2023/2/5368.2遍歷性定理與平衡態(tài)預測（3）廠若采用方案二,此時轉移矩陣為,由解得.在此方案下,廠可增加新用戶(萬戶)增加盈利(萬元).(戶),顯然,從經(jīng)濟效益看,廠應采取第二個方案.2023/2/5378.2遍歷性定理與平衡態(tài)預測從以上例子可以看到,馬爾可夫分析不僅可以用于預測,也可以用于對策分析.如上例中企業(yè)為爭取顧客、提高市場占有率,可根據(jù)預測結果采取不同競爭方案（也稱策略）例如：第一種方案是設法保留住老顧客；第二種方案是盡量爭取其他新顧客；第三種方案是既設法保留住顧客,又盡量爭取新顧客.

第三種方案的效果比前兩種收效好,但所需費用也高.此外,當各方競爭力量旗鼓相當時,競爭結果,顧客往往沒有多大變動.所以,當市場占有率接近平衡狀態(tài)時,各種方案的效果都不會太好,只有等打破平衡時再做工作.2023/2/5388.2遍歷性定理與平衡態(tài)預測

由此可見,運用馬爾可夫分析,可以預測得兩項重要信息：其一,可以預測出事物各狀態(tài)經(jīng)過一段時間后,轉入其他狀態(tài)時所占的比例；其二,可根據(jù)某些轉移矩陣確定出在遠期（即平衡狀態(tài)時）各狀態(tài)所占的比例,即最終市場占有率.若能早期求得最終市場占有率,就可據(jù)此選擇經(jīng)營策略,制定分階段的最優(yōu)對策，避免“青蛙效應”。馬爾可夫預測法的工作流程如圖8.3所示：2023/2/539圖8.3馬爾可夫預測法的工作流程8.2遍歷性定理與平衡態(tài)預測2023/2/5408.3馬爾可夫預測的應用

2023/2/5418.3馬爾可夫預測的應用

1.設備狀態(tài)預測【例8.5】

設有A,B而一周后仍無故障的概率為0.7,即對設備A,若已知現(xiàn)在無故障（狀態(tài)1）,.兩種設備,其功能、價格、使用成本均相同.對設備B,相應的概率假設是因此,從無故障而一周后有故障（狀態(tài)2）的概率,對設備A而言,應為；對設備B而言,應為

2023/2/5428.3馬爾可夫預測的應用再假設我們的問題是：從長遠看,選擇哪一種設備更合適？

由遍歷性定理,可假設設備A和B的固有概率向量分別為及由于設備A與B的一周轉移概率分別是

2023/2/5438.3馬爾可夫預測的應用對設備A,由,解出.即當系統(tǒng)處于穩(wěn)定狀態(tài)時,設備A無故障的概率為,有故障的概率為.對設備B,由解出,即當系統(tǒng)處于穩(wěn)定狀態(tài)時,設備B無故障的概率為,有故障的概率為

.由于設備B無故障的概率大于設備A無故障的概率,應選購設備B.

2023/2/5448.3馬爾可夫預測的應用2.企業(yè)設備更新決策【例8.6】對某種設備每周檢查一次,并將它們的狀態(tài)分為新,優(yōu),良,壞,分別用狀態(tài)1,2,3,4表示.若發(fā)現(xiàn)已壞需要一周時間更新.經(jīng)統(tǒng)計,轉移矩陣為

新優(yōu)良壞新優(yōu)良壞= 2023/2/5458.3馬爾可夫預測的應用假設更新一臺設備需要25元；若發(fā)現(xiàn)已壞,生產(chǎn)損失為20元.試問,每周更新設備的費用和設備損壞造成的生產(chǎn)損失是多少？這個問題可用平衡分析解決.由遍歷性定理,只需求出矩陣的固有概率向量.由方程組解出(新,優(yōu),良,壞)=(0.19,0.30,0.32,0.19),于是對每臺設備而言,每周的更新費用和生產(chǎn)損失費分別為更新費=0.1925=4.75(元)，損失費=0.1920=3.80(元)，共計8.55元.2023/2/5468.3馬爾可夫預測的應用現(xiàn)在若采取另一種更新策略：一經(jīng)檢查發(fā)現(xiàn)設備處于“良”的狀態(tài),就馬上更新掉,以減少因設備損壞給生產(chǎn)造成的損失.此時,轉移矩陣為

新優(yōu)良=

新優(yōu)良由方程組解得(新,優(yōu),良)=(0.28,0.44,0.28).2023/2/5478.3馬爾可夫預測的應用此時,每周更新費增加到0.2825=7(元),但損失費減少到零,總費用小于原更新策略.若一個工廠有一千臺這種設備,采用新更新策略,每周可節(jié)約

1000(8.55-7)元=1550元.一年按50周計算,全年可節(jié)約501550元=77500元.這是一筆可觀的經(jīng)濟效益.2023/2/5488.4WinQSB軟件應用

2023/2/5498.4WinQSB軟件應用

馬爾可夫過程分析程序需要調用子程序MarkovProcess(MKP).

當給定一步轉移概率矩陣P、初始狀態(tài)概率向量