副本-高级运筹学考试提纲

矩阵对策老师复习例题1：确定p、q范围使得矩阵在(

,)存在鞍点(即纯策略解)?α2β2β1β2β3α1α2α3知识点1：鞍点从例中可以看出，矩阵A中的平衡局势(α2,β2)对应的元素a22即是所在行的最小元素，又是所在列的最大元素，即有ai2≤a22≤a2ji=1,2,3,4j=1,2,3将这一事实推广到一般矩阵对策，可得定理1：矩阵对策G={S1,S2；A}在纯策略下有解的充要条件是：存在纯局势(αi*,βj*

)，使得对任意i和j，有矩阵A的鞍点（对策的鞍点）（saddlepoint,orequilibriumpoint）知识点2：划线法:按行最小列最大划线例：设有一矩阵对策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为纯策略下均衡解的值，最优策略的纯局势为（α2，β2）。β1β2β3α1α2α3α4矩阵对策老师复习例题2:已知,其最优解求解、、知识点3：矩阵对策定理记T(G)为矩阵对策G的解集定理7：设有两个矩阵对策G1={S1,S2;A1}，G2={S1,S2;A2}，其中A1=(aij)，A2=(aij+L)，L为任意常数，则（1）（2）定理8：设有两个矩阵对策G1={S1,S2;A}，G2={S1,S2;αA}，其中α>0,为任意常数，则（1）（2）矩阵对策老师复习例题3：甲、乙两个游戏者在互不知道的情况下，同时伸出1,2或3个指头。用k表示两人伸出的指头总和。当k为偶数，甲付给乙k元，若k为奇数，乙付给甲k元。列出甲的赢得矩阵。解释说明：对角线以及（3,1）、（1,3）上k为偶数，甲付给乙k元，即甲赢得-k元。其余元素k为奇数，乙付给甲k元，即甲赢得k元。知识点4：赢得矩阵矩阵对策老师复习例题4：利用图解法求解下列矩阵对策，其中矩阵A分别为解:(1)、利用划线法易知无纯策略解，第一行优超于第二行，则划去第二行，且，则原矩阵变为y1-y矩阵对策画图：以y为横轴。红边以上所围区域的最低点即为局中人II的最小损失。

注：图上小圆圈仅为标记，未必需要画出！y1-y矩阵对策解:(2)、利用划线法易知无纯策略解，

画图：以x为横轴。红边以下所围区域的最高点即为局中人I的最大赢得。注：图上小圆圈仅为标记，未必需要画出！知识点5：优超定理：划去元素较小的行，划去元素较大的列(用于化简矩阵)定义5设矩阵对策G={S1,S2;A},其中S1={α1,…,αm},S2={β1,…,βn},A=(aij)m×n，如果对一切j=1,2,…,n都有即矩阵A的第i0行元素均不小于第k0行对应的元素，则称局中人I的纯策略优超于；元素较大的行优超于元素较小的行，划去元素较小的行同样，若对一切i=1,2,…,m,都有即矩阵A的第l0列元素均不小于第j0列元素，则称局中人II的纯策略优超于。元素较小的列优超于元素较大的列，划去元素较大的列。注：某两行或两列的凸线性组合如；>=某行或<=某列时也可以用优超定理。注意必须是凸线性组合，否则可能出错。优超例子运用优超定理化简矩阵对策A：其第4行的所有元素都>=第1行，第3行的所有元素都>=第2行，则第4行优超于第1行，第3行优超于第2行，因此划去第1行和第2行，得到。的第1列所有元素都<=第3列，第2列所有元素都<=第4列，则第1列优超于第3列，第2列优超于第4列，1/3*（第1列）+2/3*第2列优超于第5列，因此划去第3、4、5列，得到。中第1行所有元素>=第3行，则第1行优超于第3行，因此划去第3行，得到。

即为最简形式。知识点6：图解法图解法用于求解矩阵为2×n或m×2阶的对策问题例：用图解法求解矩阵对策G={S1,S2;A}，其中解：设局中人I的混合策略为(x,1-x)T,x∈[0,1].过数轴上坐标为0和1的两点分别坐两条垂线I-I和II-II。垂线上的纵坐标分别表示局中人I采取纯策略α1和α2时，局中人II采取各策略时的赢得值。当局中人I选择每一策略(x,1-x)T后，他的最少可能收入为由β1β2β3所确定的3条直线在x处的纵坐标中之最小者决定。所以对局中人I来说，他的最优选择是确定x，使3个纵坐标中的最小者尽可能的大。从图上来看，就是使得x=OA，这时B点的纵坐标即为对策的值。2×n的对策中以局中人I的策略X作为横坐标（因为他只有2个策略）范围为[0,1]。所有曲线下边界所围范围为局中人II的最小损失即局中人I的最小赢得值。局中人I的赢得要最多，则取所有曲线下边界的最高点。572311令x=1时，2,3,11放在垂直于横坐标（1,0）处的纵轴上。则1-x=0,把7,5,2放在垂直于原点的纵轴上。为求x和对策值VG，可联立过B点的两条由β2β3确定的直线方程：解得x=3/11，VG=49/11。所以局中人I最优策略为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根据定理，必有y1*=0,y2*>0,y3*>0根据定理，有求得，y2*=9/11，y3*=2/11，所以局中人II的混合策略为y*=(0,9/11,2/11)例：用图解法求解矩阵对策G={S1,S2;A},其中S1={α1,α2}；S2={β1,β2,β3}解：设局中人II的混合策略(y,1-y)T,y∈[0,1].据图可以看出，直线α1α2α3的纵坐标是局中人II采取混合策略(y,1-y)T时的支付根据最不利当中选最有利原则，局中人II的最优选择就是如何确定y，以使三个纵坐标中的最大值尽可能的小。可见，应选择OA1≤y≤OA2,这时对策值为6n×2的对策中以局中人II的策略y作为横坐标（因为他只有2个策略）范围为[0,1]。所有曲线上边界所围范围为局中人II的最大损失即局中人I的最大赢得值。局中人II要损失最小，则取所有曲线上边界的最低点。7-5y2+9yA1A2y1-y令y=1时，2,6,11放在垂直于横坐标（1,0）处的纵轴上。则1-y=0,把7,6,2放在垂直于原点的纵轴上。6211由方程组解得,A1=1/5,A2=4/9,故局中人II的最优混合策略是y*=(y,1-y)T,其中1/5≤y≤4/9局中人I的最优策略显然只能是(0,1,0)T,即采取纯策略α2知识点7：小于VG使得某个元素为0

（用于化简计算）即图解法中所求交点不是所有直线的交点时，未过该交点直线对应的元素值为0定理6：设(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矩阵对策鞍点补充习题例2：确定a、b、c范围使得矩阵在对角线上三个元素分别存在鞍点(即纯策略解)?β1β2β3α1α2α3矩阵对策鞍点补充习题例2、求解下列矩阵对策，其中赢得矩阵A分别为：最优策略（α1

，β2），VG=1最优策略（α2

，β2），VG=0矩阵对策划线法补充习题最优策略（α2

，β3），VG=4最优策略（α1

，β1），VG=1最优策略（α2

，β2），VG=0最优策略（α1

，β1），VG=0最优策略（α2

，β1），VG=1最优策略（α3

，β1），VG=3最优策略（α3

，β3），VG=4最优策略（α2

，β1），VG=3矩阵对策定理补充习题例1：已知,其最优解求解例1、甲乙两名儿童玩剪刀、石头、布游戏，双方可以分别出拳头（代表石头），手掌（代表布），两个手指（代表剪刀）。游戏规则是：剪刀赢布，布赢石头，石头赢剪刀，赢者得1分。若双方所出相同，为和局，双方都不得分。试列出儿童甲的赢得矩阵。例2、“二指莫拉问题”。甲、乙二人游戏，每人出一个或两个手指，同时又把猜测双方所出的指数叫出来。如果只有一个人猜测正确，则他所赢得的数目为二人所出指数之和，否则重新开始，写出该对策中各局中人的策略集合及甲的赢得矩阵，并回答局中人是否存在某种出法比其他出法更为有利（即是否存在鞍点？）。根据划线法可知不存在某种出法比其他出法更为有利，即不存在鞍点。

乙石头布剪刀甲

石头0-11布10-1剪刀-110矩阵对策赢得矩阵补充习题例3、AB两人各有1角、5分和1分的硬币各一枚。在双方互不知道的情况下各处一枚硬币，并规定当和为奇数时，A赢得B所出硬币；当和为偶数时，B赢得A所出硬币。试据此列出二人零和对策的模型，并说明该项游戏对双方是否公平合理？根据划线法可知无纯策略解因为第1行优超于第2行，所以划去第2行，得到A1,因为第1列优超于第2列，所以划去第2列，得到A2。

y1y3则因为策略集对等，对策值为0，所以该项游戏公平。

放入矩阵对策赢得矩阵补充习题矩阵对策图解法补充习题解:(1)、利用划线法易知无纯策略解。因为第2行优超于第1行与第4行所以划去第1、4行，得到A1。A1中的第1列优超于第2列与第4列，所以划去第2、4列得到A2。

矩阵对策图解法补充习题

画图：以x为横轴。红边以下所围区域的最高点即为局中人I的最大赢得。注：图上小圆圈仅为标记，未必需要画出！矩阵对策图解法补充习题解:(1)、利用划线法易知无纯策略解画图：以y为横轴。红边以上所围区域的最低点即为局中人II的最小损失。注：图上小圆圈仅为标记，未必需要画出！

博弈论老师复习例题1：考虑如下的双寡头市场战略投资模型：企业1和企业2目前情况下单位生产成本都是c=2。企业1可以引入一项新技术使单位成本降低到c=1,该项技术需要投资f。在企业1作出是否投资的决策（企业2可以观察到）后，两个企业同时选择产量。假设市场需求函数为p(q)=14-q,其中p是市场价格，q是两个企业的总产量。问上述投资额f处于什么水平时，企业1会引进新技术？知识点1：完全且完美信息动态博弈

子博弈完美纳什均衡

基本方法：逆推归纳法动态博弈具有非对称性，有先行优势定义1：从动态博弈的最后一个阶段博弈方的行为开始分析，逐步倒推回前一个阶段相应博弈方的行为选择，一直到第一个阶段的分析方法，称为“逆推归纳法”。定义2：如果一个完美信息的动态博弈中，各博弈方的策略构成的一个策略组合满足，在整个动态博弈及它的所有子博弈中都构成纳什均衡，那么这个策略组合称为该动态博弈的一个“子博弈完美纳什均衡”。逆推归纳法是求完美信息动态博弈子博弈完美纳什均衡的基本方法。32寡头产量竞争——以两厂商产量竞争为例双方同时决定各自产量，即均不知对方的产量222126qqqq--=知识点2：古诺模型及其变种：

古诺的寡头模型知识点2：古诺模型及其变种：寡占的斯坦博格模型先后选择产量的产量竞争博弈把古诺模型改为厂商1先选择，厂商2后选择，而非同时选择即可。222126qqqq--=产量得益厂商13单位4.5厂商21.5单位2.25先行优势博弈论补充习题例1：三寡头市场的需求函数P=100-Q，其中Q是三个厂商的产量之和，并且已知三个厂商都有常数边际成本2而无固定成本。如果厂商1和厂商2先同时决定产量，厂商3根据厂商1和厂商2的产量决策，问它们的各自产量和利润是多少？博弈论补充习题例3：两寡头企业进行价格竞争博弈，企业1的利润函数是，企业2的利润函数是，其中p是企业1的价格，q是企业2的价格。求：(1)、两个企业同时决策的纯策略纳什均衡;(2)、企业1先决策的子博弈完美纳什均衡;(3)、企业2先决策的纯策略纳什均衡;(4)、是否存在参数a、b、c的特定值或范围使得两个企业都希望自己先决策？马尔可夫分析——吸收马氏链老师复习例题1：一赌徒有$2,每次下注$1,赢的概率为0.6，若他资金涨到$4就收手，或他资金降为0，也收手。求(1)、这个赌徒有$4的概率(即求b22);(2)、这个赌徒被迫出局有$0的概率(即求b21);