副本-高級運籌學(xué)考試提綱

矩陣對策老師復(fù)習(xí)例題1：確定p、q范圍使得矩陣在(

,)存在鞍點(即純策略解)?α2β2β1β2β3α1α2α3知識點1：鞍點從例中可以看出，矩陣A中的平衡局勢(α2,β2)對應(yīng)的元素a22即是所在行的最小元素，又是所在列的最大元素，即有ai2≤a22≤a2ji=1,2,3,4j=1,2,3將這一事實推廣到一般矩陣對策，可得定理1：矩陣對策G={S1,S2；A}在純策略下有解的充要條件是：存在純局勢(αi*,βj*

)，使得對任意i和j，有矩陣A的鞍點（對策的鞍點）（saddlepoint,orequilibriumpoint）知識點2：劃線法:按行最小列最大劃線例：設(shè)有一矩陣對策G={S1，S2；A}，其中解釋說明：1、先按局中人I選，看列選最大值并劃下劃線，局中人II出β1，則這一列最大值為9，同理，出β2，選2，出β1，選6。

2、再按局中人II選，看行選最小值并劃下劃線，局中人I出α1，則這一行最小值為-8，同理，出α2，選2，出α1，選-10，出α4，選-3。3、可以從上表看出2的位置被下劃線劃了2次，即2為純策略下均衡解的值，最優(yōu)策略的純局勢為（α2，β2）。β1β2β3α1α2α3α4矩陣對策老師復(fù)習(xí)例題2:已知,其最優(yōu)解求解、、知識點3：矩陣對策定理記T(G)為矩陣對策G的解集定理7：設(shè)有兩個矩陣對策G1={S1,S2;A1}，G2={S1,S2;A2}，其中A1=(aij)，A2=(aij+L)，L為任意常數(shù)，則（1）（2）定理8：設(shè)有兩個矩陣對策G1={S1,S2;A}，G2={S1,S2;αA}，其中α>0,為任意常數(shù)，則（1）（2）矩陣對策老師復(fù)習(xí)例題3：甲、乙兩個游戲者在互不知道的情況下，同時伸出1,2或3個指頭。用k表示兩人伸出的指頭總和。當(dāng)k為偶數(shù)，甲付給乙k元，若k為奇數(shù)，乙付給甲k元。列出甲的贏得矩陣。解釋說明：對角線以及（3,1）、（1,3）上k為偶數(shù)，甲付給乙k元，即甲贏得-k元。其余元素k為奇數(shù)，乙付給甲k元，即甲贏得k元。知識點4：贏得矩陣矩陣對策老師復(fù)習(xí)例題4：利用圖解法求解下列矩陣對策，其中矩陣A分別為解:(1)、利用劃線法易知無純策略解，第一行優(yōu)超于第二行，則劃去第二行，且，則原矩陣變?yōu)閥1-y矩陣對策畫圖：以y為橫軸。紅邊以上所圍區(qū)域的最低點即為局中人II的最小損失。

注：圖上小圓圈僅為標(biāo)記，未必需要畫出！y1-y矩陣對策解:(2)、利用劃線法易知無純策略解，

畫圖：以x為橫軸。紅邊以下所圍區(qū)域的最高點即為局中人I的最大贏得。注：圖上小圓圈僅為標(biāo)記，未必需要畫出！知識點5：優(yōu)超定理：劃去元素較小的行，劃去元素較大的列(用于化簡矩陣)定義5設(shè)矩陣對策G={S1,S2;A},其中S1={α1,…,αm},S2={β1,…,βn},A=(aij)m×n，如果對一切j=1,2,…,n都有即矩陣A的第i0行元素均不小于第k0行對應(yīng)的元素，則稱局中人I的純策略優(yōu)超于；元素較大的行優(yōu)超于元素較小的行，劃去元素較小的行同樣，若對一切i=1,2,…,m,都有即矩陣A的第l0列元素均不小于第j0列元素，則稱局中人II的純策略優(yōu)超于。元素較小的列優(yōu)超于元素較大的列，劃去元素較大的列。注：某兩行或兩列的凸線性組合如；>=某行或<=某列時也可以用優(yōu)超定理。注意必須是凸線性組合，否則可能出錯。優(yōu)超例子運用優(yōu)超定理化簡矩陣對策A：其第4行的所有元素都>=第1行，第3行的所有元素都>=第2行，則第4行優(yōu)超于第1行，第3行優(yōu)超于第2行，因此劃去第1行和第2行，得到。的第1列所有元素都<=第3列，第2列所有元素都<=第4列，則第1列優(yōu)超于第3列，第2列優(yōu)超于第4列，1/3*（第1列）+2/3*第2列優(yōu)超于第5列，因此劃去第3、4、5列，得到。中第1行所有元素>=第3行，則第1行優(yōu)超于第3行，因此劃去第3行，得到。

即為最簡形式。知識點6：圖解法圖解法用于求解矩陣為2×n或m×2階的對策問題例：用圖解法求解矩陣對策G={S1,S2;A}，其中解：設(shè)局中人I的混合策略為(x,1-x)T,x∈[0,1].過數(shù)軸上坐標(biāo)為0和1的兩點分別坐兩條垂線I-I和II-II。垂線上的縱坐標(biāo)分別表示局中人I采取純策略α1和α2時，局中人II采取各策略時的贏得值。當(dāng)局中人I選擇每一策略(x,1-x)T后，他的最少可能收入為由β1β2β3所確定的3條直線在x處的縱坐標(biāo)中之最小者決定。所以對局中人I來說，他的最優(yōu)選擇是確定x，使3個縱坐標(biāo)中的最小者盡可能的大。從圖上來看，就是使得x=OA，這時B點的縱坐標(biāo)即為對策的值。2×n的對策中以局中人I的策略X作為橫坐標(biāo)（因為他只有2個策略）范圍為[0,1]。所有曲線下邊界所圍范圍為局中人II的最小損失即局中人I的最小贏得值。局中人I的贏得要最多，則取所有曲線下邊界的最高點。572311令x=1時，2,3,11放在垂直于橫坐標(biāo)（1,0）處的縱軸上。則1-x=0,把7,5,2放在垂直于原點的縱軸上。為求x和對策值VG，可聯(lián)立過B點的兩條由β2β3確定的直線方程：解得x=3/11，VG=49/11。所以局中人I最優(yōu)策略為x*=(3/11,8/11).記y*=(y1*,y2*,y3*)T，則E(x*,1)=2×3/11+7×8/11=62/11>49/11=VGE(x*,2)=3×3/11+5×8/11=49/11=VGE(x*,3)=11×3/11+2×8/11=49/11=VG根據(jù)定理，必有y1*=0,y2*>0,y3*>0根據(jù)定理，有求得，y2*=9/11，y3*=2/11，所以局中人II的混合策略為y*=(0,9/11,2/11)例：用圖解法求解矩陣對策G={S1,S2;A},其中S1={α1,α2}；S2={β1,β2,β3}解：設(shè)局中人II的混合策略(y,1-y)T,y∈[0,1].據(jù)圖可以看出，直線α1α2α3的縱坐標(biāo)是局中人II采取混合策略(y,1-y)T時的支付根據(jù)最不利當(dāng)中選最有利原則，局中人II的最優(yōu)選擇就是如何確定y，以使三個縱坐標(biāo)中的最大值盡可能的小?？梢姡瑧?yīng)選擇OA1≤y≤OA2,這時對策值為6n×2的對策中以局中人II的策略y作為橫坐標(biāo)（因為他只有2個策略）范圍為[0,1]。所有曲線上邊界所圍范圍為局中人II的最大損失即局中人I的最大贏得值。局中人II要損失最小，則取所有曲線上邊界的最低點。7-5y2+9yA1A2y1-y令y=1時，2,6,11放在垂直于橫坐標(biāo)（1,0）處的縱軸上。則1-y=0,把7,6,2放在垂直于原點的縱軸上。6211由方程組解得,A1=1/5,A2=4/9,故局中人II的最優(yōu)混合策略是y*=(y,1-y)T,其中1/5≤y≤4/9局中人I的最優(yōu)策略顯然只能是(0,1,0)T,即采取純策略α2知識點7：小于VG使得某個元素為0

（用于化簡計算）即圖解法中所求交點不是所有直線的交點時，未過該交點直線對應(yīng)的元素值為0定理6：設(shè)(x*,y*)是矩陣對策G的解，v=VG，則(1)若xi*>0,則(2)若yj*>0,則(3)若,則xi*=0(4)若，則yi*=0例1：確定p、q范圍使得矩陣在(

,)存在鞍點(即純策略解)?α2β2β1β2β3α1α2α3矩陣對策鞍點補充習(xí)題例2：確定a、b、c范圍使得矩陣在對角線上三個元素分別存在鞍點(即純策略解)?β1β2β3α1α2α3矩陣對策鞍點補充習(xí)題例2、求解下列矩陣對策，其中贏得矩陣A分別為：最優(yōu)策略（α1

，β2），VG=1最優(yōu)策略（α2

，β2），VG=0矩陣對策劃線法補充習(xí)題最優(yōu)策略（α2

，β3），VG=4最優(yōu)策略（α1

，β1），VG=1最優(yōu)策略（α2

，β2），VG=0最優(yōu)策略（α1

，β1），VG=0最優(yōu)策略（α2

，β1），VG=1最優(yōu)策略（α3

，β1），VG=3最優(yōu)策略（α3

，β3），VG=4最優(yōu)策略（α2

，β1），VG=3矩陣對策定理補充習(xí)題例1：已知,其最優(yōu)解求解例1、甲乙兩名兒童玩剪刀、石頭、布游戲，雙方可以分別出拳頭（代表石頭），手掌（代表布），兩個手指（代表剪刀）。游戲規(guī)則是：剪刀贏布，布贏石頭，石頭贏剪刀，贏者得1分。若雙方所出相同，為和局，雙方都不得分。試列出兒童甲的贏得矩陣。例2、“二指莫拉問題”。甲、乙二人游戲，每人出一個或兩個手指，同時又把猜測雙方所出的指數(shù)叫出來。如果只有一個人猜測正確，則他所贏得的數(shù)目為二人所出指數(shù)之和，否則重新開始，寫出該對策中各局中人的策略集合及甲的贏得矩陣，并回答局中人是否存在某種出法比其他出法更為有利（即是否存在鞍點？）。根據(jù)劃線法可知不存在某種出法比其他出法更為有利，即不存在鞍點。

乙石頭布剪刀甲

石頭0-11布10-1剪刀-110矩陣對策贏得矩陣補充習(xí)題例3、AB兩人各有1角、5分和1分的硬幣各一枚。在雙方互不知道的情況下各處一枚硬幣，并規(guī)定當(dāng)和為奇數(shù)時，A贏得B所出硬幣；當(dāng)和為偶數(shù)時，B贏得A所出硬幣。試據(jù)此列出二人零和對策的模型，并說明該項游戲?qū)﹄p方是否公平合理？根據(jù)劃線法可知無純策略解因為第1行優(yōu)超于第2行，所以劃去第2行，得到A1,因為第1列優(yōu)超于第2列，所以劃去第2列，得到A2。

y1y3則因為策略集對等，對策值為0，所以該項游戲公平。

放入矩陣對策贏得矩陣補充習(xí)題矩陣對策圖解法補充習(xí)題解:(1)、利用劃線法易知無純策略解。因為第2行優(yōu)超于第1行與第4行所以劃去第1、4行，得到A1。A1中的第1列優(yōu)超于第2列與第4列，所以劃去第2、4列得到A2。

矩陣對策圖解法補充習(xí)題

畫圖：以x為橫軸。紅邊以下所圍區(qū)域的最高點即為局中人I的最大贏得。注：圖上小圓圈僅為標(biāo)記，未必需要畫出！矩陣對策圖解法補充習(xí)題解:(1)、利用劃線法易知無純策略解畫圖：以y為橫軸。紅邊以上所圍區(qū)域的最低點即為局中人II的最小損失。注：圖上小圓圈僅為標(biāo)記，未必需要畫出！

博弈論老師復(fù)習(xí)例題1：考慮如下的雙寡頭市場戰(zhàn)略投資模型：企業(yè)1和企業(yè)2目前情況下單位生產(chǎn)成本都是c=2。企業(yè)1可以引入一項新技術(shù)使單位成本降低到c=1,該項技術(shù)需要投資f。在企業(yè)1作出是否投資的決策（企業(yè)2可以觀察到）后，兩個企業(yè)同時選擇產(chǎn)量。假設(shè)市場需求函數(shù)為p(q)=14-q,其中p是市場價格，q是兩個企業(yè)的總產(chǎn)量。問上述投資額f處于什么水平時，企業(yè)1會引進(jìn)新技術(shù)？知識點1：完全且完美信息動態(tài)博弈

子博弈完美納什均衡

基本方法：逆推歸納法動態(tài)博弈具有非對稱性，有先行優(yōu)勢定義1：從動態(tài)博弈的最后一個階段博弈方的行為開始分析，逐步倒推回前一個階段相應(yīng)博弈方的行為選擇，一直到第一個階段的分析方法，稱為“逆推歸納法”。定義2：如果一個完美信息的動態(tài)博弈中，各博弈方的策略構(gòu)成的一個策略組合滿足，在整個動態(tài)博弈及它的所有子博弈中都構(gòu)成納什均衡，那么這個策略組合稱為該動態(tài)博弈的一個“子博弈完美納什均衡”。逆推歸納法是求完美信息動態(tài)博弈子博弈完美納什均衡的基本方法。32寡頭產(chǎn)量競爭——以兩廠商產(chǎn)量競爭為例雙方同時決定各自產(chǎn)量，即均不知對方的產(chǎn)量222126qqqq--=知識點2：古諾模型及其變種：

古諾的寡頭模型知識點2：古諾模型及其變種：寡占的斯坦博格模型先后選擇產(chǎn)量的產(chǎn)量競爭博弈把古諾模型改為廠商1先選擇，廠商2后選擇，而非同時選擇即可。222126qqqq--=產(chǎn)量得益廠商13單位4.5廠商21.5單位2.25先行優(yōu)勢博弈論補充習(xí)題例1：三寡頭市場的需求函數(shù)P=100-Q，其中Q是三個廠商的產(chǎn)量之和，并且已知三個廠商都有常數(shù)邊際成本2而無固定成本。如果廠商1和廠商2先同時決定產(chǎn)量，廠商3根據(jù)廠商1和廠商2的產(chǎn)量決策，問它們的各自產(chǎn)量和利潤是多少？博弈論補充習(xí)題例3：兩寡頭企業(yè)進(jìn)行價格競爭博弈，企業(yè)1的利潤函數(shù)是，企業(yè)2的利潤函數(shù)是，其中p是企業(yè)1的價格，q是企業(yè)2的價格。求：(1)、兩個企業(yè)同時決策的純策略納什均衡;(2)、企業(yè)1先決策的子博弈完美納什均衡;(3)、企業(yè)2先決策的純策略納什均衡;(4)、是否存在參數(shù)a、b、c的特定值或范圍使得兩個企業(yè)都希望自己先決策？馬爾可夫分析——吸收馬氏鏈老師復(fù)習(xí)例題1：一賭徒有$2,每次下注$1,贏的概率為0.6，若他資金漲到$4就收手，或他資金降為0，也收手。求(1)、這個賭徒有$4的概率(即求b22);(2)、這個賭徒被迫出局有$0的概率(即求b21);