第6章-馬爾可夫決策和群決策

2023/12/26第六章馬爾可夫決策和群決策1目錄1馬爾可夫鏈的基本概念2馬爾可夫決策方法3群決策方法系統(tǒng)運行過程中的“無后效性”某些系統(tǒng)運行過程中存在或近似存在“無后效性”的特征系統(tǒng)在每一時刻的狀態(tài)僅僅取決于前一時刻的狀態(tài)，而與其過去的歷史狀態(tài)無關池塘荷葉與青蛙池塘里有三張荷葉1,2,3，一只青蛙在荷葉上隨機地跳來跳去，初始時刻t0，它位于荷葉2上，時刻t1，它可能仍在荷葉2上，也可能跳到1或3上，時刻t2，它位于哪張荷葉上與t0無關，只和t1有關可以近似認為無后效性的例子商店庫存市場占有率車間的設備狀態(tài)……馬爾可夫預測和決策法是應用隨機過程中的馬爾可夫鏈的理論和方法來研究分析有關系統(tǒng)狀態(tài)變化規(guī)律并籍此對未來進行預測和決策的一種方法——基于“無后效性”假設2123隨機過程隨機過程（StochasticProcess）隨機過程是含有一個時間參數的隨機變量族：{xt}，t∈T隨機變量的取值稱為狀態(tài)，可以連續(xù)或離散比如設備狀態(tài)、產品庫存、產品每日需求量等離散型隨機過程（DiscreteStochasticProcess）如若T

為離散集（設）同時的取值(狀態(tài))也是離散的，則稱為離散型隨機過程，用{1,2,3,…,k}表示狀態(tài)集3馬爾可夫鏈馬爾可夫鏈（MarkovChain）任何一個未來事件的條件概率只和現在狀態(tài)有關，而與過去的狀態(tài)無關——“馬爾可夫性”或“無后效性”離散型隨機過程：時間離散，狀態(tài)離散稱為狀態(tài)轉移概率(一步轉移概率)4有限狀態(tài)的馬爾可夫鏈齊次性特征：有限狀態(tài)的馬爾可夫鏈{xt}具有有限種(k種)狀態(tài)具有馬爾可夫性轉移概率滿足齊次性特征一步狀態(tài)轉移矩陣5例16陰天晴天下雨

晴天陰天下雨晴天0.500.250.25陰天0.3750.250.375下雨0.250.1250.625P=例2企業(yè)銷售狀況變化某產品銷售情況分為暢銷和滯銷兩種，1代表暢銷，2代表滯銷。以xt表示第t個季度的味精銷售狀態(tài)，則xt可取1或2的值。若未來的味精市場狀態(tài)只與現在的市場狀態(tài)有關，與以前的市場狀態(tài)無關，則市場狀態(tài){xt}構成一個馬爾可夫鏈。若：則狀態(tài)轉移矩陣：7例3考察一臺機床的運行狀態(tài)機床的運行存在正常和故障兩種狀態(tài)。S={1,2}。機床在運行中出現故障：1

2；處于故障中的機床經維修，恢復到正常狀態(tài)：2

1以一個月為單位，經觀察統(tǒng)計，知其從某個月份到下月份，機床出現故障的概率為0.3。在這一段時間內，故障機床經維修恢復到正常狀態(tài)的概率為0.98故障2正常10.30.90.70.1例4某企業(yè)為使技術人員具有多方面的經驗，實行技術人員在技術部門、生產部門和銷售部門的輪換工作制度。輪換采用隨機形式，每半年一次。初始狀態(tài)，技術人員在某部門工作的概率用

表示，Pij表示處在第i個部門的技術人員在半年后轉移到第j個部門的概率，已知一步狀態(tài)轉移矩陣如下，求n步后它在第i個部門工作的概率9對于二步轉移矩陣：，可證明：遞推：n步后技術人員在第i個部門工作的概率：比如1年后在某部門的工作概率10穩(wěn)態(tài)概率(1)由轉移概率和初始狀態(tài)的概率分布可以確定任意步上的轉移概率和絕對概率分布穩(wěn)態(tài)概率：穩(wěn)態(tài)概率的計算：對于例4：11穩(wěn)態(tài)概率(2)初始狀態(tài)對n步轉移后所處狀態(tài)的影響隨n的增大而減少——穩(wěn)態(tài)概率和初始狀態(tài)無關不是所有的馬爾可夫鏈都存在穩(wěn)態(tài)概率——具有遍歷性的馬爾可夫鏈才有穩(wěn)態(tài)概率1213目錄1馬爾可夫鏈的基本概念2馬爾可夫決策方法3群決策方法例1——市場競爭策略決策某生產商標為α的產品的廠商為了與另外兩個生產同類產品β和γ的廠家競爭，有三種可供選擇的措施：措施1為發(fā)放有獎債券，措施2為開展廣告宣傳，措施3為優(yōu)質售后服務三種方案實施后，經調查可知，該類產品的“用戶轉移矩陣”如下。已知三種商標的商品的月總銷量為1000萬件，每件可獲利1元，另外，三種措施的成本費分別為150萬元，40萬元和30萬元從長遠利益考慮，α生產廠商應該采取何種措施？14

15例2——最佳維修策略的選擇某化工企業(yè)對循環(huán)泵進行季度維修，每次檢查中，把泵按其外殼及葉輪的腐蝕程度定為五種狀態(tài)之一。分別為：狀態(tài)1：優(yōu)秀狀態(tài)，無任何故障或缺陷狀態(tài)2：良好狀態(tài)，稍有腐蝕狀態(tài)3：及格狀態(tài)，輕度腐蝕狀態(tài)4：可用狀態(tài)，大面積腐蝕狀態(tài)5：不可運行狀態(tài)，腐蝕嚴重16該公司可采用的維修策略有以下幾種：單狀態(tài)策略：泵處于狀態(tài)5時才進行修理，修理費用500元兩狀態(tài)策略：泵處于狀態(tài)4和5時進行修理，處于狀態(tài)4時的修理費用為250元，處于狀態(tài)5時的修理費用為500元三狀態(tài)策略：泵處于狀態(tài)3,4,5時進行修理，處于狀態(tài)3時的修理費用為200元，處于狀態(tài)4和5時的修理費用同前例2——最佳維修策略的選擇目前，該公司采用的維修策略為“單狀態(tài)”策略假定不管處于何種狀態(tài)，只要進行修理，泵都將恢復為狀態(tài)1。已知在不進行任何修理時狀態(tài)轉移概率如下表所示問題：確定哪個策略的費用最低17泵在周期n+1的狀態(tài)

泵在周期n的狀態(tài)

1

2

3

4

5

1

0.00

0.60

0.20

0.10

0.10

2

0.00

0.30

0.40

0.20

0.10

3

0.00

0.00

0.40

0.40

0.20

4

0.00

0.00

0.00

0.50

0.50

5

0.00

0.00

0.00

0.00

1.00

求解(1)單狀態(tài)維修策略下：18狀態(tài)轉移矩陣：穩(wěn)態(tài)概率：求解(2)兩狀態(tài)維修策略下：19狀態(tài)轉移矩陣：穩(wěn)態(tài)概率：求解(3)三狀態(tài)維修策略下：20狀態(tài)轉移矩陣：穩(wěn)態(tài)概率：結論單狀態(tài)維修策略下：兩狀態(tài)維修策略下：三狀態(tài)維修策略下：21因此，“兩狀態(tài)維修策略”是最佳決策非穩(wěn)定概率的例子(1)某高校教師狀態(tài)分為5類：助教、講師、副教授、教授、流失及退休。目前狀態(tài)：根據歷史資料：試分析三年后的教師結構以及三年內為保持編制不變應進多少研究生充實教師隊伍？22非穩(wěn)定概率的例子(2)一年后：要保持550人的總編制，流失76人，故第一年應進76位研究生二年后：補充74人三年后：補充72人在第三年底，人員結構：2324目錄1馬爾可夫鏈的基本概念2馬爾可夫決策方法3群決策方法群決策的概念現實生活中，決策往往是群體行為，是由多人參加進行的行動方案選擇活動——群決策(GroupDecisionMaking)在不同場合群有不同的名稱，例如，代表大會、委員會、集體、組織、團隊(Team)、議會、俱樂部、協(xié)會和小組等等群決策的基本目標是：將群中成員的不同偏好按某種規(guī)則集結（aggregation或稱并合，歸納，簡化）成為單一的群整體的偏好25群決策的三個前提①自主性。決策者有獨立選擇機會，其行動不受較高層權利的支配，但不排除群體成員間相互影響②共存性。決策成員都在已知的共同條件下進行選擇③共意性。群體做出的必然是所有參與者一致能夠接受的方案26群決策的復雜性群體決策研究比個人決策研究要復雜很多。這主要由幾個因素引起：①優(yōu)先度。集體中每個成員都有各自的目標和優(yōu)先觀念以及不同的效用函數②主觀概率判斷。群體中各成員由于信息的感受和處理方式不一樣，對未來狀態(tài)出現概率的估計也不同③溝通。集體決策可以在完全沒有溝通信息的情況下進行，而更多的決策是在有相互溝通信息的情況下進行27非排序式選舉方法—簡單多數投票法基本過程：群成員進行無記名投票按得票多少，即票數最多者獲勝，叫做簡單多數制或相對多數制得票超過半數才獲勝，叫過半數代表制或絕對多數制，可能需要反復投票表決或取舍表決存在不公平現象28投票人編號1234567891011偏好次序第一位aaabbbbcccd第二位cccaaaaaaaa第三位dddccccdddc第四位bbbddddbbbb排序式選舉(1)—康多西特原則在投票時，不僅要讓投票人表達他最希望看到多個候選人中哪一個被選上，還應該讓投票人說明他是以何種方式對這些候選人排序的，即在投票時表達他對各候選人的偏好次序，這就是排序式選舉，又稱偏好選舉，由Borda提出29康多西特原則Condorcet原則的例子30Condorcet投票悖論31排序式選舉(2)—波德原則集體中每一個成員將各種方案排序，如果有n個方案，則最優(yōu)方案打分為n-1，次優(yōu)方案打分n-2，依次類推，最劣方案打分為0統(tǒng)計每個方案的Borda數之和，最大者為最優(yōu)方案比如五個方案：A、B、C、D、E，甲認為A＞C＞D＞E＞B，乙認為B＞A＞C＞D＞E，由于A的Borda數大于B的Borda數，所以A是最優(yōu)的32波德原則的相悖現象A、B、C不分優(yōu)劣。加入方案D，保持原先對A、B、C的優(yōu)先判斷次序，結果C比A和B差33ABC甲012已120丙201波德數333ABCD甲0123已1302丙3012波德數4437幾種常見的策略性投票(1)謊報偏好而獲益34幾種常見的策略性投票(1)35謊報偏好而獲益幾種常見的策略性投票(2)選票交易36幾種常見的策略性投票(3)小集團操縱群37社會選擇函數群決策的關鍵問題：找出能正確反映群中成員意愿的公平合理的方法38群決策規(guī)則——社會選擇函數(SC