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

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

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

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

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

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

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

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