运筹学第15章对策论

运筹学第15章对策论2第十五章对策论由“齐王赛马”引入3§1

对策论的基本概念对策模型的三个基本要素：1.局中人：参与对抗的各方，可以是一个人，也可以是一个集团，可以是两方，也可以是多方；2.策略集：局中人选择对付其它局中人的行动方案称为策略；某局中人的所有可能策略全体称为策略集；3.一局势对策的益损值：局中人各自使用一个对策就形成了一个局势，一个局势决定了各局中人的对策结果（量化）称为该局势对策的益损值。4出赛的次序是一个策略

“齐王赛马”齐王在各局势中的益损值表（单位：千金）§1

对策论的基本概念5其中：齐王的策略集:S1={1,2,3,4,5,6}，田忌的策略集：S2={1,2,3,4,5,6}。下面矩阵称齐王的赢得矩阵：

3111-1113111-1A=1-13111-111311111-13111-1113§1

对策论的基本概念6二人有限零和对策（又称矩阵对策）：局中人为2；每个局中人的策略集的策略数目都是有限的；每一局势的对策均有确定的损益值，并且对同一局势的两个局中人的益损值之和为零。通常将矩阵对策记为:G={S1,S2,A}

S1：甲的策略集；S2：乙的策略集；A：甲的赢得矩阵。

“齐王赛马”是一个矩阵策略。§1

对策论的基本概念7在甲方的赢得矩阵中：A=[aij]m×ni

行代表甲方策略i=1,2,…,m；j列代表乙方策略j=1,2,…,n；aij代表甲方取策略

i，乙方取策略j，这一局势下甲方的益损值。此时乙方的益损值为-aij（零和性质）。在考虑各方采用的策略时，必须注意一个前提，就是双方都是理智的，即双方都是从各自可能出现的最不利的情形选择一种最为有利的情况作为决策的依据。§2矩阵对策的最优纯策略§2矩阵对策的最优纯策略8在矩阵博弈A中，aij表示局中人1的收益，因此，局中人1希望收益值aij越大越好；同时aij表示局中人2的支付或付出（局中人2的收益为-aij

），因此局中人2则希望付出的aij越小越好。因此，矩阵博弈完全是对抗的。一般地，如果局中人1采用他的第i个策略，则局中人2会选择策略使局中人1的收益最小，即这就是支付矩阵第i行元素中的最小元素。局中人1不存在侥幸心理，不冒险，而又追求收益越大越好，因此，他会从各行的最小元素中选择最大的，从而确定自己的策略。这就是说，局中人1可以选择i，使他得到的支付不少于（能够稳妥地保证得到该收益）9同样，如果局中人2采用他的第j个策略，由于局中人1希望自己的收益值（局中人2的支付）越大越好，即局中人1会选择策略使局中人2的支付最大，由于局中人2希望自己的支付越小越好，因此，他会从支付最大中选择最小。这就是说，局中人2可以选择j，保证他失去的不大于10在矩阵博弈中，纯策略纳什均衡点存在的充分必要条件为：11

例：甲乙乒乓球队进行团体对抗赛，每队由三名球员组成，双方都可排成三种不同的阵容，每一种阵容可以看作一种策略，双方各选一种策略参赛。比赛共赛三局，规定每局胜者得1分，输者得-1分，可知三赛三胜得3分，三赛二胜得1分，三赛一胜得-1分，三赛三负得-3分。甲队的策略集为S1={1，2，3}，乙队的策略集为S2={1，2，3}。根据以往比赛的资料，有甲队的赢得矩阵为A，如下所示，请问这次比赛各队采用哪种阵容上场最为稳妥?§2矩阵对策的最优纯策略12矩阵A中每行的最小元素分别为1，-3，-1。在这些最少赢得中最好的结果是1，故甲队会采取策略1，无论对手采取何策略，甲队至少得1分。对于乙队，{1，2，3}可能带来的最少赢得，即A中每列的最大元素，分别为3，1，3。乙队会采取2策略，确保甲队不会超过1分。1和2分别称为局中人甲队、乙队的最优策略。由于双方必然选择这一种策略，所以，这种策略又称为最优纯策略。这种最优纯策略只有当赢得矩阵A=（aij）中等式

成立时，双方才有最优纯策略，并把（1,2）称为对策G在纯策略下的解，又称（1,2）为对策G的鞍点。把其值V称之为对策G={S1，S2，A}的值。§2矩阵对策的最优纯策略13

例某单位采购员在秋天决定冬季取暖用煤的储量问题，已知在正常的冬季气温条件下要消耗15吨煤，在较暖和较冷的天气下要消耗10吨和20吨。假定冬天的煤价随天气寒冷程度而有所变化，在较暖和、正常、较冷的气候条件下每吨煤价分别为10元、15元、20元。又设冬季时煤炭价格为每吨10元。在没有关于当年冬季准确的气象预报的条件下，秋天储煤多少吨能使得单位的支出最少？解：局中人I为采购员，局中人II为大自然，采购员有三个策略，买10吨、15吨、20吨。分别记为1，2，3。大自然也有三个策略：暖、正常、冷，分别记为1，2，3。§2矩阵对策的最优纯策略14赢得矩阵如下：在此表上计算，有

得故（3，3）为对策G的解，VG=-200。1231(10吨）-100-175-3002(15吨）-150-150-2503(20吨）-200-200-200123min1(10吨）-100-175-300-3002(15吨）-150-150-250-2503(20吨）-200-200-200-200*max-100-150-200*§2矩阵对策的最优纯策略15【解】直接在赢得表上计算，有可知=5，i*=1,3，j*=2,4．故（α1，β2）（α1，β4）（α2，β2）（α2，β4）为对策的纳什均衡，VG=5．【例】设有矩阵对策G={S1，S2；A}，赢得矩阵为求纳什均衡16最优纯策略求解步骤：1、行中取小，小中取大得最大化最小收益值；2、列中取大，大中取小得最小化最大支付值；3、比较两值是否相等。若相等便存在最优纯策略。若不等，则不存在最优纯策略。17

设矩阵对策G={S1,S2,A}。当maxminaijminmaxaij

ijji时，不存在最优纯策略。例：设一个赢得矩阵如下:min595

A=max6策略2

866i

max89min8策略1

j§3矩阵对策的混合策略18

当甲取策略2，乙取策略1时，甲实际赢得8比预期的多2，乙当然不满意。考虑到甲可能取策略2这一点，乙采取策略2。若甲也分析到乙可能采取策略2这一点，取策略1，则赢得更多为9…

。此时，对两个局中人甲、乙来说，没有一个双方均可接受的平衡局势，其主要原因是甲和乙没有执行上述原则的共同基础，即maxminaijminmaxaij。

ijji

一个自然的想法：对甲（乙）给出一个选取不同策略的概率分布，以使甲（乙）在各种情况下的平均赢得（损失）最多（最少）-----即混合策略。§3矩阵对策的混合策略19如局中人1分别以概率x1和x2随机地采用策略α1和α2，局中人2也分别以概率y1和y2随机地采用策略β1和β2。两个局中人分别选取纯策略αi

和βj的事件是独立的，所以局势（αi，βj）出现的概率是xi和yj，这时局中人1的赢得是aij。于是局中人1赢得的期望值是20【例】设赢得矩阵A为:化简赢得矩阵．【解】第4行优于第1行，第3行优于第2行，故可划去第1行和第2行，得到新的赢得矩阵，x1=x2=0“严格下策反复消去法”(IteratedEliminationofStrictly

DominatedStrategies)优超原理——赢得矩阵的化简21对于A1第1列优于第3列，第2列优于第4列，(1/2)×（第1列）+(1/2)×（第2列）优超于第5列，因此去掉第3列，第4列和第5列，y3=y4=y5=0，得到A2：又由于第1行优超于第3行，所以从A2中划去第3行，x5=0，得到A3

，优超：行比较取大者留下，列比较取小者留下若α1不是为纯策略α2，…,αm中之一所优超，而是为α2，…,αm的某个凸线性组合所优超，仍然可以化简。22求解混合策略问题的方法：均衡法、极值法、线性规划法。1、极值法设局中人1选择策略1和策略2的概率分别为x1和x2，局中人2选择策略1和策略2的概率分别为y1和y2，概率均大于等于0。这样局中人1的赢得就成为一个随机变量，若设其期望值为v，则有：V=10x1y1-5x1y2-5x2y1+0x2y2=10x1y1-5x1y2-5x2y1x1+x2=1,y1+y2=123局中人1为了使此值达到最大，就调整x1和x2的值；而局中人2为了使此值达到最小，也要调整y1和y2的值。此时，上述问题变为条件极值问题，可用拉格朗日乘数法求解，令λ、μ为待定系数，将式W=10x1y1-5x1y2-5x2y1+λ(x1+x2-1)+μ(y1+y2-1)对x1、x2、y1、y2求偏导数，并让它们等于0。24对x1求偏导得，10y1-5y2+λ=0对x2求偏导得，-5y1+λ=0对y1求偏导得，10x1-5x2+μ=0对y2求偏导得，-5x1+μ=0再与x1+x2=1,y1+y2=1二式一起联立求解，得：x1=1/4,x2=3/4,y1=1/4,y2=3/4.λ=μ=5/4带入v中解得局中人1的预期赢得。例：设

解:如果A有鞍点，则易求出各局中人的最优纯策略；如果没有鞍点，则各局中人的最优混合策略中的xi*,yj*均大于零。于是可求下列方程组：2×2对策的公式法262、均衡法首先分析是否存在鞍点，另外是否可以用优超原理化简。纯策略可以看成是混合策略的特殊情况。即某一个策略的概率为1，其他策略的概率为0。优超原理化简，留下的策略概率取值大于0，删去的策略概率取值为0。27发现不存在鞍点，也无法化简。说明每个策略选取的概率均不为0。设局中人1的混合策略为(x1,x2,x3)，局中人2的混合策略为(y1,y2,y3)。这时的期望值为：V=E(x,y)=2x1y1+x1y2+2x2y2+3x2y3+x3y1+x3y2+2x3y3=(2y1+y2)x1+(2y2+3y3)x2+(y1+y2+2y3)x3=(2x1+x3)y1+(x1+2x2+x3)y2+(3x2+2x3)y328V=E(x,y)=2x1y1+x1y2+2x2y2+3x2y3+x3y1+x3y2+2x3y3=(2y1+y2)x1+(2y2+3y3)x2+(y1+y2+2y3)x3=(2x1+x3)y1+(x1+2x2+x3)y2+(3x2+2x3)y3试想，如果2y1+y2>2y2+3y3，对于局中人1来说，为了使v值变大，他应该增大x1，而让x2变为0。即取策略2的概率为0。而前面的分析显示，选择每个策略的概率均不为0。故2y1+y2=2y2+3y3。同理，2y1+y2=2y2+3y3=y1+y2+2y3=M(设一变量)。将M带入v中得，v=Mx1+Mx2+Mx3=M(x1+x2+x3)=M对于局中人2来说，为了使v值变小，也得出2x1+x3=x1+2x2+x3=3x2+2x3=v。29可得到线性方程组：2y1+y2=v2y2+3y3=vy1+y2+2y3=vy1+y2+y3=12x1+x3=vx1+2x2+x3=v3x2+2x3=vx1+x2+x3=1八个方程，七个未知数。消元法求解。x1=1/2,x2=1/4,x3=1/4,y1=1/2,y2=1/4,y3=1/4,v=5/430【解】建立方程组求解得：x=(0.525，0.275，0.2),y=(0.2，0.05，0.75);VG=－0.45博弈不存在鞍点和优超策略。31定理：在矩阵博弈G中，若S1={α1,α2,…αm}，S2={β1,β2,…βn}，局中人1的收益函数为A=(aij)m×n，则该定理使得其中一个集合Yn或Xm，从无限集到有限集，从而减少了求解难度。图解法32图解法3334【定理3】设（x*，y*）为矩阵对策G的一个纳什均衡，V=VG，则(1)若xi*＞0，则

(2)若yi*

＞0，则

(3)若，则

(4)若,则例3536373839线性规划法定理：在矩阵博弈G中，若S1={α1,α2,…αm}，S2={β1,β2,…βn}，局中人1的收益函数为A=(aij)m×n，则该定理使得其中一个集合Yn或Xm，从无限集到有限集，从而减少了求解难度。40根据定理，令V=maxu(x)若u(x)>0，令41令上述线性规划模型化为：对上述线性规划模型求得最优解和最优值。同理局中人2也可以列线性规划模型求得最优解和最优值。42【例】利用线性规划方法求解赢得矩阵为的矩阵对策的纳什均衡．【解】此问题可化为两个线性规划问题：最终结果v=1/z=1/wXi=xi/zYi=yi/w43最优解：X＝(0.1065，0.1448，0.0437),Y＝(0.1093，0.1038，0.0819)；w＝0.29508．利用变换得到x*=(0.36，0.49，0.15)，y*=(0.37，0.35，0.28)；v=3.3944作业利用优超原理化简该对策问题求解对策双方的混合策略及对策值45

求解混合策略的问题有图解法、迭代法、线性方程法和线性规划法等，我们这里只介绍线性规划法，其他方法略。例：设甲使用策略1的概率为X1′，使用策略2的概率为X2′，并设在最坏的情况下，甲赢得的平均值为V（未知）。

59A=STEP1861)X1′+X2′=1X1′,X2′0

§3矩阵对策的混合策略462)无论乙取何策略，甲的平均赢得应不少于V:对乙取1：5X1’+8X2’

V对乙取2：9X1’+6X2’

V注意V>0,因为A各元素为正。STEP2

作变换：X1=X1’/V;X2=X2’/V得到上述关系式变为：

X1+X2=1/V(V愈大愈好）待定

5X1+8X219X1+6X21X1,X20§3矩阵对策的混合策略47建立线性模型：

minX1+X2

s.t.5X1+8X21X1=1/21

9X1+6X21X2=2/21X1,X201/V=X1+X2=1/7

所以，V=7返回原问题：X1’=X1V=1/3

X2’=X2V=2/3于是甲的最优混合策略为：以1/3的概率选1，以2/3的概率选2，最优值V=7。§3矩阵对策的混合策略48

同样可求乙的最优混合策略：设乙使用策略1的概率为Y1′Y1′+Y2′=1设乙使用策略2的概率为Y2′Y1′,Y2′0

设在最坏的情况下，甲赢得的平均值为V。这也是乙损失的平均值，越小越好。作变换：Y1=Y1’/V，Y2=Y2’/V

建立线性模型：

maxY1+Y2

s.t.5Y1+9Y21Y1=1/14

8Y1+6Y21Y2=1/14Y1,Y201/V=Y1+Y2=1/7

所以，V=7§3矩阵对策的混合策略49返回原问题：Y1’=Y1V=1/2

Y2’=Y2V=1/2于是乙的最优混合策略为：以½

的概率选1；以½

的概率选2，最优值V=7。

当赢得矩阵中有非正元素时，V0

的条件不一定成立，可以作下列变换：选一正数k，令矩阵中每一元素加上

k得到新的正矩阵A’，其对应的矩阵对策G’={S1,S2,A’}与G={S1,S2,A}解相同，但VG=VG’–k。§3矩阵对策的混合策略50例：求解“齐王赛马”问题。已知齐王的赢得矩阵A求得故不存在纯策略问题下的解，可求其混合策略。A中有负元素，可以取k=2,在A的每个元素上加2得到A’如下：§3矩阵对策的混合策略51

建立对G′={S1，S2，A′}中求甲方最佳策略的线性规划如下：

Minx1+x2+x3+x4+x5+x6

约束条件：

5x1+3x2+3x3+x4+3x5+3x6≥13x1+5x2+x3+3x4+3x5+3x6≥13x1+3x2+5x3+3x4+3x5+x6≥13x1+3x2+3x3+5x4+x5+3x6≥1x1+3x2+3x3+3x4+5x5+3x6≥13x1+x2+3x3+3x4+3x5+5x6≥1xi≥0,i=1,2,…,6

可解得解为：x1=x4=x5=0,x2=x3=x6=0.111,v′=3,x1′=x4′=x5′=0，x2′=x3′=x6′=1/3,即X′*=(0,1/3,1/3,0,0,1/3)T，所以甲的最优策略为作出策略2、3、6的概率都为0.333,而作出1、4、5

的概率为0，此时V′G=V′=3。§3矩阵对策的混合策略52

同样可以建立对策G′={S1，S2，A′}中求乙方最佳策略的线性规划如下：

Miny1+y2+y3+y4+y5+y6

约束条件：

5y1+3y2+3y3+3y4+y5+3y6≤13y1+5y2+3y3+3y4+3y5+y6≤13y1+y2+5y3+3y4+3y5+3y6≤1y1+3y2+3y3+5y4+3y5+3y6≤13y1+3y2+3y3+y4+5y5+3y6≤13y1+3y2+y3+3y4+3y5+5y6≤1yi≥0,i=1,2,…,6

可解得解为：

y1=y4=y5=0.111,y2=y3=y6=0,v′=3,y1′=y4′=y5′=1/3，

y2′=y3′=y6′=0，即Y′*=(1/3,0,0,1/3,1/3,0)T。所以田忌的最优混合策略为作出策略1、4、5的概率都为1/3,而作出2，3，6的概率为0，此时VG=VG′-k=1。§3矩阵对策的混合策略53

齐王赛马问题的对策最优解可简记为X*=(0,1/3,1/3,0,0,1/3)T，Y*=(1/3,0,0,1/3,1/3,0)T，对策值VG=1。例两个局中人进行对策，规则是两人互相独立的各自从1、2、3这三个数字中任意选写一个数字。如果两人所写的数字之和为偶数，则局中人乙支付给局中人甲以数量为此和数的报酬；如果两人所写数字之和为奇数，则局中人甲付给局中人乙以数量为此和数的报酬。试求出其最优策略。解：首先计算局中人甲的赢得矩阵如下表：4-56-34-52-341（出1）2（出2）3（出3）3（出3）2（出2）1（出1）甲的赢得甲的策略§3矩阵对策的混合策略乙的策略54即甲的赢得矩阵为A：

可知无纯策略意义的解，下面求其在混合策略下的解。A的各元素都加上6，得到建立线性规划模型如下：

Minx1+x2+x3Maxy1+y2+y31+3x2+10x3≥18y1+3y2+10y3≤13x1+10x2+x3≥13y1+10y2+y3≤110x1+x2+12x3≥110y1+y2+12y3≤1x1,x2,x3≥0y1,y2,y3≥0

§3矩阵对策的混合策略55得到x1′=0.25,x2′=0.50,x3′=0.25；y1′=0.25,y2′=0.50,y3′=0.25。即此对策的解为X*=(0.25,0.50,0.25)T，Y*=(0.25,0.50,0.25)T。VG=VG′-k=0。§3矩阵对策的混合策略56例4

甲乙两个企业生产同一种电子产品，甲企业可以采取的策略措施有:(1)降低产品价格；(2)提高产品质量；(3)推出新产品。乙企业考虑采取的策略措施有(1)增加广告费用；(2)增设维修网点，加强售后服务；(3)改进产品性能。由于甲乙两个企业财力有限，都只能采取一个措施。假定这两个企业所占有的市场总份额一定，由于各自采取的措施不同，通过预测今后两个企业的市场占有份额变动情况如下表，试求出这两个企业各自的最优策略。3-58-6510108-121（措施1）2（措施2）3（措施3）3（措施3）2（措施2）1（措施1）§3矩阵对策的混合策略甲的赢得甲的策略乙的策略57解：易知此对策无纯策略意义下的解。把A的每一个元素加上12，得到A′建立线性规划模型如下：

Minx1+x2+x3Maxy1+y2+y31+20x2≥122y1+6y2+15y3≤16x1+17x2+22x3≥120y1+17y2+7y3≤115x1+7x2+20x3≥122y2+20y3≤1x1,x2,x3≥0y1,y2,y3≥0得到：x1=0.027,x2=0.020,x3=0.023；y1=0.0225,y2=0.0225,y3=0.025。V=14.29。x1′=0.3858,x2′=0.2858,x3′=0.3286；y1′=0.3215,y2′=0.3215,y3′=0.3572。即此对策的解为X*=(0.3858,0.2858,0.3286)T,Y*=(0.3215,0.3215,0.3572)T。VG=VG′-k=2.29。§3矩阵对策的混合策略58优超原则：假设矩阵对策G={S1,S2,A}

甲方赢得矩阵A=[aij]mn若存在两行（列），s行（列）的各元素均优于t行（列）的元素，即asjatjj=1,2…n(ais

aiti=1,2…m)称甲方策略s优超于t(s优超于t)。优超原则：当局中人甲方的策略t被其它策略所优超时，可在其赢得矩阵A中划去第t行（同理，当局中人乙方的策略t被其它策略所优超时，可在矩阵A中划去第t列）。如此得到阶数较小的赢得矩阵A’，其对应的矩阵对策G’={S1,S2,A’}与G={S1,S2,A}等价，即解相同。§3矩阵对策的混合策略59例.设甲方的益损值，赢得矩阵为

32030被第3、4行所优超

50259被第3行所优超A=7395946875.560883得到

73959被第1列所优超A1=46875.5被第2列所优超

60883§3矩阵对策的混合策略60得到

739A2=465.5603被第1行所优超得到

739被第1列所优超

A3=465.573最终得到

A4=46§3矩阵对策的混合策略61对A4计算，用线性规划方法得到：（注意：余下的策略为3，4，1，2）甲：X*=(0，0，1/15，2/15，0)TV=5X*’=(0，0，1/3，2/3，0)T

乙：Y*=(1/10，1/10，0，0，0)TV=5Y*’=(1/2，1/2，0，0，0)T

。

注：利用优超原则化简赢得矩阵时，有可能将原对策问题的解也划去一些（多解情况）；线性规划求解时有可能是多解问题。§3矩阵对策的混合策略62

§4其他类型的对