《運(yùn)籌學(xué)教程》第五版運(yùn)籌學(xué)6對策論矩陣對策課件

《《運(yùn)籌學(xué)教程》第五版運(yùn)籌學(xué)6對策論矩陣對策課件》由會(huì)員分享，可在線閱讀，更多相關(guān)《《運(yùn)籌學(xué)教程》第五版運(yùn)籌學(xué)6對策論矩陣對策課件（34頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、,單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,2015/3/30,#,單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,*,基本,概念,對策論又稱博弈論，,研究,沖突對抗條件下最優(yōu)決策問題的理論。,策略,形勢：,不完全競爭條件下的對抗行為,，各方收益由自身行為和其他方行為共同決定。,基本要素,局中人（,I,）,：有權(quán)決定自己行動(dòng)方案的對策參加者，理性人,策略,集（,S,）,：供局中人選擇的實(shí)際可行完整行動(dòng)方案的集合，,一局對策中，各局中人選定策略的集合，稱,局勢,贏得函數(shù)（,H(s),）,:,對于任一局勢，局中人的贏

2、得值。,支付函數(shù),嚴(yán)格占優(yōu)策略,/,嚴(yán)格劣勢,策略,上策均衡,/,納什,均衡,基本概念對策論又稱博弈論，研究沖突對抗條件下最優(yōu)決策問題的理,1,典型案例和重要結(jié)論,結(jié)論,1,：不要選擇嚴(yán)格劣勢策略,。,結(jié)論,2,：個(gè)人理性選擇導(dǎo)致非最優(yōu)。,結(jié)論,3,：學(xué)會(huì)換位思考,。,囚徒困境,智豬博弈,求解方法：刪除嚴(yán)格劣勢策略,典型案例和重要結(jié)論結(jié)論1：不要選擇嚴(yán)格劣勢策略。,2,矩陣對策的基本理論,矩陣對策的基本理論,3,局中人個(gè)數(shù)：二個(gè)，多個(gè),策略集中的個(gè)數(shù)：有限，無限,支付,/,贏得代數(shù)和：零和，非零和,局中人是否合作：非合作，合作,局中人行動(dòng)時(shí)間：靜態(tài)，動(dòng)態(tài),局中人對他者信息了解程度：完全信息，非

3、完全信息,對策次數(shù)：單次，重復(fù),對策,/,博弈分類,局中人個(gè)數(shù)：二個(gè)，多個(gè)對策/博弈分類,4,課程目標(biāo),理解并掌握矩陣對策的純策略,理解,并掌握,矩陣對策的混合策略,掌握矩陣對策的求解方法,課程目標(biāo) 理解并掌握矩陣對策的純策略,5,矩陣對策的策略,純策略：確定,的選擇某,策略,混合策略：以,某一概率分布選擇各策略。,矩陣對策的策略 純策略：確定的選擇某策略,6,矩陣對策的純策略,的贏得,矩陣,或,的,支付矩陣,的贏得矩陣為,-A,。,1,、矩陣對策的一般表達(dá),矩陣對策的純策略的贏得矩陣1、矩陣對策的一般表達(dá),7,矩陣對策的純策略,例：,田忌賽馬,局中人：田忌（,I,）、齊王（,II,）,S,1

4、,=,（上、中、下），（上、下、中），（中、上、下），,（中、下、上），（下、中、上），（下、上、中）,=,S,2,1,、矩陣對策的一般表達(dá),矩陣對策的純策略例：田忌賽馬1、矩陣對策的一般表達(dá),8,矩陣對策的純策略,-8,2,-10,-3,9,2,6,理智,行為：,從各自最不利情形中選擇最有利,I,：最大最小,原則,II,：最小最大原則,平衡局勢：,雙方均可接受，且對雙方都是最穩(wěn)妥的結(jié)果。,（,2,，,2,），,局中人,I,和,II,的最優(yōu)純策略。,2,、矩陣對策解的引例,矩陣對策的純策略-89 2 6理智行為：,9,矩陣對策的純策略,從上例看出，矩陣,A,中平衡局勢（,2,，,2,）對應(yīng)的元

5、素,a,22,既是其所在行的最小元素，也是其所在列的最大元素，即有,a,i2,a,22,a,2j,i=1,2,3,4 j=1,2,3,3,、矩陣對策的最優(yōu)純策略,矩陣對策的純策略 從上例看出，矩陣A中平衡局勢,10,矩陣對策的純策略,1,2,3,1,3,7 4 6,3,、矩陣對策的最優(yōu)純策略,矩陣對策的純策略13 7 4,11,矩陣對策的純策略,對于一個(gè)對策,G,=,S,1,S,2,A,若,有,則稱局勢（,i,*,j,*,）為對策,G,的,鞍點(diǎn),，,V=a,i*j*,為,對策,G,的值。,注：在,矩陣中，一個(gè)數(shù)在所在行中是最大值，在所在列中是最小值，則被稱為,鞍點(diǎn),。,4,、矩陣對策的鞍點(diǎn)與解

6、,矩陣對策的純策略對于一個(gè)對策G=S1,S2,A,若,12,矩陣對策的純策略,多鞍點(diǎn)與無鞍點(diǎn)對策,例,:,設(shè)有一矩陣對策如下，求它的解。,局勢,（,1,2,），（,1,4,），,（,3,2,）,（,3,4,）均構(gòu)成鞍點(diǎn)，此對策有多個(gè)解。,4,、矩陣對策的鞍點(diǎn)與解,矩陣對策的純策略多鞍點(diǎn)與無鞍點(diǎn)對策局勢（1,2），（,13,矩陣對策的純策略,性質(zhì),1,：無差別性,若,（,i,1,，,j,1,）,和,（,i,2,，,j,2,）,是對策,G,的兩個(gè)解，則,a,i,1,j,1,=a,i,2,j,2,性質(zhì),2,：可交換性,若（,i,1,，,j,1,）和（,i,2,，,j,2,）,是對策,G,的兩個(gè)解，,

7、則,（,i,1,，,j,2,）,和,（,i,2,，,j,1,）,也是,對策,G,的兩個(gè),解。,矩陣對策,的值唯一。,即當(dāng)一個(gè)局中人選擇了最優(yōu)純策略后，他的贏得值不依賴于對方的純策略,。,5,、矩陣對策純策略的性質(zhì),矩陣對策的純策略性質(zhì)1：無差別性5、矩陣對策純策略的性質(zhì),14,作業(yè),P385,習(xí)題,12.2,12.3,12.4,作業(yè)P385 習(xí)題,15,矩陣對策的混合策略,3,4,5,6,無鞍點(diǎn),1,、混合策略,35 6無鞍點(diǎn)1、混合策略,16,矩陣對策的混合策略,1,、混合策略,1、混合策略,17,矩陣對策的混合策略,2,、混合局勢,3,、贏得期望,4,、混合策略對策模型,2、混合局勢3、贏

8、得期望4、混合策略對策模型,18,矩陣對策的混合策略,5,、最優(yōu)混合策略,設(shè) ，是矩陣對策 的混合擴(kuò)充。,5、最優(yōu)混合策略設(shè),19,矩陣對策的混合策略,5,、最優(yōu)混合策略,5、最優(yōu)混合策略,20,矩陣對策的混合策略,定理,2,：,矩陣對策,G,在混合策略意義下有解的充要條件是：,存在 ，使得對于任意 ，有,2,、最優(yōu)混合策略,定理2：矩陣對策G在混合策略意義下有解的充要條件是：2、最優(yōu),21,矩陣對策的混合策略,3,、最優(yōu)混合策略解,的引例,3、最優(yōu)混合策略解的引例,22,矩陣對策的解法,矩陣對策的解法,23,例：求解矩陣對策,G=,其中,解：,（,1,）不存在鞍點(diǎn)，為混合策略求解問題。,（,

9、2,）圖解法求解,設(shè)局中人,I,的混合策略為（,x,1-x,）,T,，。,0,1,I,I,II,II,數(shù)軸上坐標(biāo)為,0,和,1,的兩點(diǎn)分別做兩條垂線,I-I,和,II-II,。,畫,出局中人,II,的不同策略下局中人,I,的贏得線段。,2,5,7,2,3,11,1,=2x+7(1-x),2,=3x+5(1-x),3,=11x+2(1-x),圖解法,僅適用于贏得矩陣為,2n,或,m2,階的矩陣對策問題。,1,:v,1,1,=2x+7(1-x),2,:,v,1,2,=3x+5(1-x,),3,:,v,1,3,=11x+2(1-x,),例：求解矩陣對策G=,其中,24,由于局中人,II,理性，局中人

10、,I,從最少可能收入中選擇最大的一個(gè)，為局中人,I,的最優(yōu)對策。,B,2,求解方程組可得最優(yōu)混合策略和矩陣對策的值。,圖解法,0,1,I,I,II,II,2,5,7,2,3,11,1,=2x+7(1-x),2,=3x+5(1-x),3,=11x+2(1-x),B,1,B,2,B,3,B,4,聯(lián)立過,B,2,點(diǎn)兩,條直線的方程組為,可解得,則，局中人,I,的最優(yōu)策略為,由圖可見局中人,II,的混合策略只有,2,和,3,組成。,由于局中人II理性，局中人I從最少可能收入中選擇最大的一個(gè),25,設(shè)局中人,II,的最優(yōu)混合策略為 ，且,P365,例,10,圖解法,求局中人,II,的最優(yōu)混合策略。,同理

11、，可得局中人,II,的贏得，,1,:v,2,1,=3y,2,+11y,3,2,:,v,2,2,=5y,2,+2y,3,畫出贏得線段，見右圖,0,1,y,y,*,3,1,11,5,2,2,局中人,I,理性，局中人,II,取最大損失的最小值,聯(lián)立方程組可得,解得,設(shè)局中人II的最優(yōu)混合策略為,26,方程組法,定理：,設(shè) ，則 為,G,的解的充要條件是：,存在數(shù),v,，使得,x,*,y,*,分別,是下列不等式組的解，且,v=V,G,。,若,x,i,*,y,j,*,均不為,0,，則上述不等式的求解即可轉(zhuǎn)化為下列兩個(gè)方程組的求解問題。,注：,若上述,兩個(gè)方程組存在非負(fù)解,x,*,y,*,，即矩陣對策的解

12、。若不存在非負(fù)解，則將上述方程組中的某些等式轉(zhuǎn)化為不等式，繼續(xù)求解。,由于事先假設(shè),x,i,*,y,j,*,均不為,0,，故，當(dāng)最優(yōu)策略的某些分量為,0,時(shí)，方程組可能無解，因此該方法具有一定的局限性。,定理：設(shè) ，則,27,方程組法,例：求解矩陣對策,G=,其中,A,為,解：（,1,）刪除劣勢策略，得到,無鞍點(diǎn),和,（,2,）構(gòu)造方程組,例：求解矩陣對策G=,其中,28,線性規(guī)劃法,注：,適用于所有,a,ij,0,若存在,a,ij,0,，可取一充分大的,M,0,，使得,M,+,a,ij,0,注：適用于所有aij0,29,線性規(guī)劃法,例：兩人“石頭、剪刀、布”矩陣對策求解,解：,(,X,*,，,Y,*,),為,矩陣對策的解,例：兩人“石頭、剪刀、布”矩陣對策求解(X*，Y*)為矩陣對,30,作業(yè),P386,習(xí)題,12.5,12.6,12.7,作業(yè)P386 習(xí)題,31,Q&A,Q&A,32,33,謝謝！,33謝謝！,34,34,