副本-高級(jí)運(yùn)籌學(xué)考試提綱

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

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

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

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

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

即為最簡(jiǎn)形式。知識(shí)點(diǎn)6：圖解法圖解法用于求解矩陣為2×n或m×2階的對(duì)策問(wèn)題例：用圖解法求解矩陣對(duì)策G={S1,S2;A}，其中解：設(shè)局中人I的混合策略為(x,1-x)T,x∈[0,1].過(guò)數(shù)軸上坐標(biāo)為0和1的兩點(diǎn)分別坐兩條垂線I-I和II-II。垂線上的縱坐標(biāo)分別表示局中人I采取純策略α1和α2時(shí)，局中人II采取各策略時(shí)的贏得值。當(dāng)局中人I選擇每一策略(x,1-x)T后，他的最少可能收入為由β1β2β3所確定的3條直線在x處的縱坐標(biāo)中之最小者決定。所以對(duì)局中人I來(lái)說(shuō)，他的最優(yōu)選擇是確定x，使3個(gè)縱坐標(biāo)中的最小者盡可能的大。從圖上來(lái)看，就是使得x=OA，這時(shí)B點(diǎn)的縱坐標(biāo)即為對(duì)策的值。2×n的對(duì)策中以局中人I的策略X作為橫坐標(biāo)（因?yàn)樗挥?個(gè)策略）范圍為[0,1]。所有曲線下邊界所圍范圍為局中人II的最小損失即局中人I的最小贏得值。局中人I的贏得要最多，則取所有曲線下邊界的最高點(diǎn)。572311令x=1時(shí)，2,3,11放在垂直于橫坐標(biāo)（1,0）處的縱軸上。則1-x=0,把7,5,2放在垂直于原點(diǎn)的縱軸上。為求x和對(duì)策值VG，可聯(lián)立過(guò)B點(diǎn)的兩條由β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)例：用圖解法求解矩陣對(duì)策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時(shí)的支付根據(jù)最不利當(dāng)中選最有利原則，局中人II的最優(yōu)選擇就是如何確定y，以使三個(gè)縱坐標(biāo)中的最大值盡可能的小。可見(jiàn)，應(yīng)選擇OA1≤y≤OA2,這時(shí)對(duì)策值為6n×2的對(duì)策中以局中人II的策略y作為橫坐標(biāo)（因?yàn)樗挥?個(gè)策略）范圍為[0,1]。所有曲線上邊界所圍范圍為局中人II的最大損失即局中人I的最大贏得值。局中人II要損失最小，則取所有曲線上邊界的最低點(diǎn)。7-5y2+9yA1A2y1-y令y=1時(shí)，2,6,11放在垂直于橫坐標(biāo)（1,0）處的縱軸上。則1-y=0,把7,6,2放在垂直于原點(diǎn)的縱軸上。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知識(shí)點(diǎn)7：小于VG使得某個(gè)元素為0

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

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

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

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

乙石頭布剪刀甲

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

y1y3則因?yàn)椴呗约瘜?duì)等，對(duì)策值為0，所以該項(xiàng)游戲公平。

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

矩陣對(duì)策圖解法補(bǔ)充習(xí)題

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

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

子博弈完美納什均衡

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

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