管理運籌學第13章對策論課件

第13章對策論2/6/20231課件教學目標與要求【教學目標】1.理解下列基本概念：矩陣對策，矩陣對策三要素，最優(yōu)純策略與最優(yōu)混合策略，鞍點和對策值2.算法要求：(1)會用“超優(yōu)原則”和“最大最小”原則求矩陣對策的最優(yōu)純策略(2)會用“線性規(guī)劃”方法求矩陣對策的最優(yōu)混合策略(3)了解純策略和混合策略的納什均衡求取?！局R結(jié)構(gòu)】2/6/20232課件2/6/20233課件本章主要內(nèi)容13.1對策論的基本概念13.1.1對策模型的基本要素13.1.2對策問題的分類13.2矩陣對策的純策略13.2.1優(yōu)超原則13.2.2最大最小原則13.3矩陣對策的混合策略13.3.1混合策略的概念13.3.2圖解法13.3.3線性規(guī)劃法13.4納什均衡13.4.1純策略納什均衡的劃線法13.4.2混合策略納什均衡的LP方法13.4應用舉例案例13-1市場競爭策略案例13-2對抗賽項目確定本章小結(jié)2/6/20235課件13.1.1對策模型的基本要素1．局中人局中人(players)是指參與競爭的各方，每方必須有獨立的決策能力和承擔風險的能力。(如:田忌、齊王）2．策略集在對策問題中，局中人為了應對其他局中人的行動而采取的方案和手段稱為該局中人的一個策略(strategy)。3．贏得及贏得函數(shù)局中人采用不同策略對策時，各方總是有得或有失，統(tǒng)稱贏得(payoff)或得益。(上中下)(上下中)(中上下)(中下上)(下上中)(下中上)(上中下)3，-31，-11，-11，-1-1，11，-1(上下中)1，-13，-31，-11，-11，-1-1，1(中上下)1，-1-1，13，-31，-11，-11，-1(中下上)-1，11，-11，-13，-31，-11，-1(下上中)1，-11，-11，-1-1，13，-31，-1(下中上)1，-11，-1-1，11，-11，-13，-32/6/20236課件13.1.2對策問題的分類局中人之間是否允許合作？策略選擇是否與時間有關(guān)？局中人多寡？贏得值代數(shù)和是否為0？2/6/20237課件13.2矩陣對策的純策略為求出對策模型的解，首先需要對雙方的對策條件作如下的假設(shè)。(1)對策雙方的行為是理智的，對策略的選擇不存在任何僥幸心理。(2)局中人選取策略的目標是收益最大或損失最小。(3)局中人同時選取各自的行動策略，且不知道對方選取哪一個策略。(4)對策中的有關(guān)規(guī)定和要求，局中人是知道的。2/6/20239課件13.2.1超優(yōu)原則1．對若恒有則稱超優(yōu)于2．對若恒有則稱超優(yōu)于【例13.2】第3行優(yōu)超于第2行，第1行優(yōu)超于第5行第1列優(yōu)超于第5列，第4列優(yōu)超于第2列

第1行優(yōu)于2、3行

最優(yōu)純策略（α1,β2）2/6/202310課件【例13.3】某地區(qū)有甲、乙兩家企業(yè)生產(chǎn)同種產(chǎn)品，采取相同的價格出售，為了提高市場份額，均采取做廣告的方式擴大自己的銷售量。甲和乙均有三種廣告策略。甲企業(yè)所占的市場份額增加的百分數(shù)如下面矩陣A所示。2/6/202311課件13.3.1混合策略的概念【例13.5】猜硬幣游戲：甲、乙兩個兒童玩猜硬幣游戲，甲手中拿著一枚硬幣，把硬幣蓋在桌子上，讓兒童乙猜是正面向上還是反面向上。如若猜對甲給乙1元錢，猜錯乙給甲1元錢。猜硬幣游戲?qū)儆诰仃噷Σ?，兒童甲的策略有出正面向?α1)和出反面向上(α2)，兒童乙的策略有猜正面向上(β1)和猜反面向上(β2)。2/6/202313課件13.3.1混合策略的概念設(shè)甲出正面(α1)的概率x,出反面(α2)的概率1-x;乙猜正面(β1)的概率y,猜反面(β2)的概率1-y。則乙兩個策略的期望值分別為:當x<0.5時，

，理性的兒童乙會選擇猜反面;

當x>0.5時，

，理性的兒童乙會選擇猜正面;(3)當x=0.5時，

，兒童乙不論采取何種策略，平均贏得都是零。乙的策略同理甲的策略最優(yōu)混合策略2/6/202314課件13.3.1混合策略的概念由于甲乙都是理智的，故混合擴充：設(shè)有矩陣對策混合擴充2/6/202315課件13.3.2圖解法圖解法求解矩陣對策，一般適用于贏得矩陣為或的對策問題，對于和都較大的對策問題就不適用了。下面通過例子來說明這種方法。解設(shè)甲的混合策略為x,(1-x),x∈[0,1],則乙分別使用β1,β2,β3時,甲贏得值:01xx*72β153β2211β3步驟:(1)繪制x數(shù)軸,標出x取值范圍[0,1](2)x取0和1,確定三條直線端點,繪制三條甲贏得值直線(3)由于乙是理智的,甲的贏得值只能是最小的(粗線所示)(4)甲只能在最小中取最大,對應的策略為

,最優(yōu)對策值為V*=49/11【例13.7】求解矩陣對策，其中2/6/202317課件13.3.2圖解法01xx*72β153β2211β3從圖還可以看出局中人乙的最優(yōu)混合策略為β2β3的組合.故β1的概率為0.設(shè)β2,β3的概率為y,(1-y).由效率矩陣:可知,當甲使用α1,α2,時,乙的損失值為:由于甲是理智的,故乙取最大損失(粗線)乙會在最大損失中找出最小,即乙最優(yōu)混合策略為:01yy*3α11152α2y分別取0和1,繪制圖形如下:2/6/202318課件13.3.3線性規(guī)劃法乙采取策略組合y1,…,yn時,是從利己主義出發(fā)的,會使自己的期望損失最小(也即甲的贏得最小)甲會使用某種策略組合x1,…,xm,使得在最小贏得的概率組合盡可能地大.因此有:2/6/202319課件綜上所述,二人零和對策可以表述成一對對偶規(guī)劃:【例13.7】解寫出一對對偶模型解得:求得最優(yōu)混合局勢:2/6/202321課件13.4納什均衡2/6/202322課件13.4納什均衡表示成贏得矩陣:如果某情況下無一參與者可以獨自行動而增加收益，則此策略組合被稱為納什均衡點?！凹{什均衡”，也叫非合作均衡，由諾貝爾經(jīng)濟學獎獲得者——美國普林斯頓大學約翰·納什提出?！凹{什均衡”描述的就是一種非合作博弈均衡，在現(xiàn)實中非合作的情況要比合作情況普遍。所以“納什均衡”是對馮·諾依曼和摩根斯坦的合作博弈理論的重大發(fā)展，甚至可以說是一場革命。納什均衡也分為純策略與混合策略.純策略可采取“劃線法”；混合策略可采取線性規(guī)劃方法。2/6/202323課件13.4.2混合策略納什均衡的LP方法由于納什均衡所解決的問題不是二人零和對策，故對策雙方的贏得矩陣不是同一個矩陣，其LP模型也不是一對對偶問題。設(shè)甲、乙的贏得矩陣分別為A和B，混合策略概率分別為：對于收益等贏得值，有收益最大化maxV(即min1/V)模型如下：對于成本等損失值，有損失最小化minV(即max1/V)模型如下：2/6/202325課件【例13.8】對下表（收益值）求取納什均衡。解甲的收益矩陣乙的收益矩陣A的3、4行收益值不大于第1行，刪除B的3、4列收益值不大于第1列，刪除收益矩陣簡化及使用概率如下：乙的收益矩陣各元素+4，對甲、乙建立LP模型并求解如下：，2/6/202326課件2/6/202329課件解決方案這是一個納什均衡問題。在甲的收益矩陣中，第2行的收益值均不小于第1、3行，故是一個純策略問題，即李參加仰泳比賽。由于甲是理智的，他會讓李參加仰泳比賽，而乙對付甲的最優(yōu)策略時，王參加3個項目比賽時的收益值分別為15、13、15?？梢娡鯀⒓友鲇竞屯苡境杀臼且粯拥模饕?.5的概率參加。決策建議甲隊李參加仰泳比賽；乙隊王參加參加仰泳或蛙泳比賽。甲隊得分12分，乙隊得分15分。2/6/202330課件本章小結(jié)對策論是研究具有競爭性質(zhì)的現(xiàn)象，并為參加者各方提供對策方法的數(shù)學理論。無論何種對策，構(gòu)成一個對策現(xiàn)象的共同特征是具有三個基本要素：局中人、策略集和損益值。本章重點研究的是矩陣對策，又稱為二人有限零和對策，是指兩個局中人、每一局中人策略數(shù)量都是有限的且在任何一對策略組合下兩個局中人的損益值之和始終為零的對策。通常矩陣對策表示為G={S1，S2，A}在求解矩陣對策時，我們可以采取以下步驟：首先用嚴格下策反復消去法對贏得矩陣進行簡化。判斷對策是否存