運籌學(xué)思想方法及應(yīng)用 ch8 馬爾可夫預(yù)測方法

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

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

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

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

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

（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我們稱為轉(zhuǎn)移概率.由于這種轉(zhuǎn)移概率不依賴于時間，因此具有穩(wěn)定性，我們用常數(shù)來表示.將各個狀態(tài)之間的轉(zhuǎn)移概率用一個矩陣表示出來，就得到一個馬爾科夫問題（有限狀態(tài)穩(wěn)定的馬爾可夫過程問題）的數(shù)學(xué)模型：2023/2/5118.1馬爾可夫過程定義及其性質(zhì)稱矩陣為一步概率轉(zhuǎn)移矩陣，簡稱轉(zhuǎn)移矩陣.由于轉(zhuǎn)移矩陣的每行都是獨立的分布，所有每行的元素滿足下列性質(zhì)：（8.2）

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

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

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

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

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

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

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

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

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

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

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

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

，則極限

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

，若對所有的

轉(zhuǎn)移概率

都存在極限

（不依賴于

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

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

（8.11）

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

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

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

上月

ABC

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

由.解得

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

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

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

2023/2/5418.3馬爾可夫預(yù)測的應(yīng)用

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

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

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

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

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

.由于設(shè)備B無故障的概率大于設(shè)備A無故障的概率,應(yīng)選購設(shè)備B.

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

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

新優(yōu)良=

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

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

2023/2/5498.4WinQSB軟件應(yīng)用

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

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