第十一章对策论(管理运筹学,李军)

第一节：引论第二节：矩阵对策第三节：矩阵对策的求解第十一章对策论2023/1/15第一节：引论1.内涵：对策论亦称博弈论（GameTheory），具有竞争或对抗性质的行为称为对策行为。2.引例3.对策行为的基本要素4.对策行为的基本假设5.对策行为的分类2023/1/151.引例：齐王赛马齐王：上、中、下田忌：上、中、下

2023/1/151.引例：齐王赛马齐王：上、中、下田忌：上、中、下2023/1/152.对策行为的基本要素1.局中人（Player）：在一个对策行为中，有权决定自己行动方案的参加者称为局中人。2.策略（Strategy）：一局对策中，可供局中人选择的完整的行动方案称为策略。3.赢得函数（Score）：一局对策中，局中人使用每一策略都会有所得失，这种得失是全体局中人所采取的一组策略的函数，称为赢得函数。4.局势：一局对策中，各局中人选定的策略所形成的策略组称为一个局势。2023/1/153.对策行为的基本假设对策行为总是假定每一个局中人都是“理智的”决策者，不存在利用其他局中人的决策失误来扩大自身利益的可能性或相反。2023/1/154.对策行为的分类对策动态对策静态对策结盟对策不结盟对策联合对策合作对策无限对策有限对策二人多人零和非零和零和非零和同有限对策2023/1/15第二节：矩阵对策1.矩阵对策的数学模型2.矩阵对策解的问题3.矩阵对策的混合策略4.矩阵对策的基本定理5.矩阵对策解的性质2023/1/151.矩阵对策的数学模型（1）矩阵对策的内涵：二人有限零和对策，即对策双方的利益是激烈对抗的。（2）矩阵对策的数学模型：甲：有m个策略，表示为S1=（1,2,3,……,m)

乙：有n个策略，表示为S2=（1,2,3,……,n)

当甲选定策略i

、乙选定策略j

时，就形成了一个局势（i

,j

）。可见这样的局势总共有mn个，对任意局势（i

,j

）甲的赢得值为aij，即甲的赢得矩阵为Am×n={aij}。因为对策是零和的，所以乙的赢得矩阵为-Am×n。

2023/1/151.矩阵对策的数学模型

建立二人零和对策的模型就是要根据对实际问题的叙述，确定甲、乙两个局中人的策略集合以及相应的赢得矩阵。不难看出在“齐王赛马”的例子中，齐王的赢得矩阵为：A=31111-11333-111-13111-11131111-1131111-113

2023/1/151.矩阵对策的示例1乙甲石头剪子布石头01-1剪子-101布10例1：甲的赢得矩阵

2023/1/151.矩阵对策的示例2例2：从一张红牌和一张黑牌中随机抽取一张，在对乙保密的情况下拿给甲看。若甲看到的是红牌，他可以选择掷硬币或让乙猜；若甲选择掷硬币，出现正面甲赢p元，出现反面甲输q元；若让乙猜，当乙猜中是红牌时甲输r元，否则甲赢s元。若甲看到的是黑牌，他只能让乙猜，当乙猜中是黑牌时甲输u元，否则甲赢t元。试确定甲、乙各自的策略并建立赢得矩阵。正面1/2抽到红牌1/2抽到黑牌1/2掷硬币让乙猜让乙猜猜红反面1/2p-q-r猜红猜黑猜黑st-u

2023/1/151.矩阵对策的示例2正面1/2抽到红牌1/2抽到黑牌1/2掷硬币让乙猜让乙猜猜红反面1/2p-q-r猜红猜黑猜黑st-u若甲决定掷硬币这个策略，则乙的猜红或猜黑已无意义；若抽到黑牌，甲的掷硬币已无意义，只与乙的猜红或猜黑有关。所以，对于局势“掷硬币，猜红”甲的期望赢得为：1/2（1/2p-1/2q）+1/2t=1/4（p-q+2t）

2023/1/151.矩阵对策的示例2正面1/2抽到红牌1/2抽到黑牌1/2掷硬币让乙猜让乙猜猜红反面1/2p-q-r猜红猜黑猜黑st-u乙甲猜红猜黑掷硬币1/4（p-q+2t）1/4（p-q-2u）让乙猜1/2（-r+t）1/2（s-u）2023/1/152.矩阵对策解的问题设矩阵对策G={S1，S2，A}，其中：

S1

={1，2，3，4}，S2

={1，2，3}，A=-42-6-643538-1-10-10-306-3MinMax3局中人甲应选择2，此时不管局中人乙采取什么策略，甲的赢得均不小于3。

2023/1/152.矩阵对策解的问题设矩阵对策G={S1，S2，A}，其中：

S1

={1，2，3，4}，S2

={1，2，

3}A=-42-6-643538-1-10-10-306-3MinMax3局中人甲应选择2，乙应采取2策略；结果甲赢得3，乙付出3。Max836Min3

2023/1/152.矩阵对策解的问题定义1：设矩阵对策G={S1，S2，A}，其中：

S1

={1，2，…，m}，S2

={1，2，…，

n}

A={aij}mn

；若Maxminaij

=Minmaxaij

=ai*j*则称ai*j*为对策G的值，局势（i*

，j*

）为G的解，i*和j*分别称为局中人的最优策略。ijij

2023/1/152.矩阵对策解的问题由于ai*j*既是其所在行的最小值，又是其所在列的最大值，于是有：aij*ai*j*

ai*j定理1：设矩阵对策G={S1，S2，A}在策略意义下有解的充分必要条件是存在着局势（i*

，j*

）使得对于一切i与j都有aij*ai*j*

ai*j成立。

2023/1/152.矩阵对策解的问题

例：设矩阵对策G={S1，S2，A}，赢得矩阵为：

A=756552-39-4-46575501-12-1MinMax=5Max7595Min=5i

=1,3，j=2,4，ai*j*

=5，四个局势均为矩阵对策的解。2023/1/153.矩阵对策的混合策略对矩阵对策G={S1，S2，A}来说，局中人甲有把握的最小赢得是：v1=maxminaij局中人乙有把握的最大损失是：v2=min

maxaij当v1=v2时，对矩阵对策有策略意义下的解；然而并非总是如此，经常是v1<v2（总有v1v2

），此时没有策略意义下的解。ijij

2023/1/153.矩阵对策的混合策略A=-44-6-643538-1-10-10-306-3MinMax3Max845Min4v1=3<v2=4

2023/1/153.矩阵对策的混合策略

v1=3<v2=4对于两个局中人来说，不存在一个双方均可接受的平衡局势。设矩阵对策G={S1，S2，A}，其中：

S1

={1，，m}，S2

={1，，n}

A={aij}mn；则S1*

={xi

0，i=1,2,,m;x1+x2++xm

=1}S2*

={yj

0，j=1,2,,n;y1+y2++yn

=1}称为局中人的混合策略。

2023/1/153.矩阵对策的混合策略

对

x

S1*,y

S2*

称(x,y)为一个混合局势，局中人的赢得函数记成：E

(x,y)=xT

Ay这样便得到一个新的对策G*={S1*,S2*,E}G*称为G的混合扩充。

2023/1/153.矩阵对策的混合策略

G*={S1*,S2*,E}是G={S1，S2，A}的混合扩充，如果maxminE(x,y)=minmaxE(x,y)记其值为VG，则VG为对策G*的值，使上式成立的混合局势（x

*，y

*）为G在混合策略意义下的解，x

*，y

*分别称为局中人甲和乙的最优混合策略。注：策略意义下的解不存在时，自动转向混合策略意义下的解。x

S1*y

S2*x

S1*y

S2*

2023/1/153.矩阵对策的混合策略

对策矩阵G={S1，S2，A}在混合策略意义下有解的充分必要条件是存在着x

*

S1*

，y

*

S2*使（x

*，y

*）

为E(x,y)的一个鞍点，即对于一切x

S1*

，y

S2*

有E(x,y*)E(x*,y*)E(x*,y)

2023/1/153.矩阵对策的混合策略

例：对策矩阵G={S1，S2，A}，其中：

A=

显然G在策略意义下的解不存在，于是设x=(x1,x2)为局中人甲的混合策略，y=(y1,y2)为局中人乙的混合策略，则S1*

={xi0，i=1,2;x1+x2=1}S2*

={yj

0，j=1,2;y1+y2=1}局中人甲的赢得期望值是：E(x,y)=xT

Ay3654

2023/1/153.矩阵对策的混合策略

例：E(x,y)=xT

Ay=3x1y1+6x1y2+5x2y1+4x2y2=-4(x1-1/4)(y1-1/2)+9/2取x

*=（1/4，3/4），y

*=（1/2，1/2），则E(x,y*)=E(x*,y*)=E(x*,y)=9/2即有E(x,y*)E(x*,y*)E(x*,y)故x

*和y

*分别为局中人甲和乙的最优（混合）策略。

2023/1/154.矩阵对策的基本定理定理1：设矩阵对策G={S1，S2，A}在策略意义下有解的充分必要条件是存在着局势（i*

，j*

）使得对于一切i与j都有aij*ai*j*

ai*j成立。定理2：对策矩阵G={S1，S2，A}在混合策略意义下有解的充分必要条件是存在着x

*

S1*

，y

*

S2*使（x

*，y

*）

为E(x,y)的一个鞍点，即对于一切x

S1*

，y

S2*

有E(x,y*)E(x*,y*)E(x*,y)

2023/1/154.矩阵对策的基本定理定理3：设x

*

S1*

，y

*

S2*则（x

*，y

*）

是矩阵对策G的解的充分必要条件是对任意的i(1,2,…,m)和j(1,2,…,n)有E(x,y*)E(x*,y*)E(x*,y)

2023/1/154.矩阵对策的基本定理定理4：设

x

*

S1*

，y

*

S2*则（x

*，y

*）

是矩阵对策G的解的充分必要条件是存在数v使得x

*

和y

*

分别是不等式组aijxivaijyj

vxi=1yj=1

xi0yj

0的解，且v=VG。ij(j=1,2,…,n)(i=1,2,…,m)(i=1,2,…,m)(j=1,2,…,n)

2023/1/154.矩阵对策的基本定理定理5：对任一矩阵对策G={S1，S2，A}，一定存在混合策略意义下的解。2023/1/155.矩阵对策解的性质性质1：设（x

*，y

*）

是矩阵对策G={S1，S2，A}的解，v=VG

，则（1）若xi*>0，则aijyj*

=v，（2）若aijyj*

<v

，则xi*=0；（3）若yj*>0，则aijxi*

=v，（4）若aijxi*

>v

，则yj*=0。

2023/1/155.矩阵对策解的性质性质2：矩阵对策G1={S1，S2，A1}、G2={S1，S2，A2}，解集分别为T（G1）和T（G2），若其中有A1=（aij）、A2=（aij+L），L为任一常数，则：（1）VG2=G1+L；

（2）T（G2）=T（G1）。

2023/1/155.矩阵对策解的性质性质3：矩阵对策G1={S1，S2，A}、G2={S1，S2，A}，其中为大于0的任一常数，则：（1）VG2=VG1；

（2）T（G2）=T（G1）。

2023/1/155.矩阵对策解的性质性质4：设一矩阵对策G={S1，S2，A}存在A

=-AT

（称为对称对策）则：（1）VG=0；

（2）T1（G）=T2（G），分别为局中人甲、乙的最优策略集。

2023/1/155.矩阵对策解的性质性质5：设一矩阵对策G={S1，S2，A}，若在S1（或、和S2）中出现被优超的策略，那么去掉被优超的策略所形成的新的矩阵对策与原矩阵对策同解。

A=4023-2-214-43738454656652743例11-6：

2023/1/15第216页例11-6由于第4行优超于第1行，第3行优超于第2行，故可去掉第1行和第2行，得到新的赢得矩阵：

A1=738454656652743

2023/1/15第216页例11-6对于A1由于第1列优超于第3列，第2列优超于第4列，1/3（第1列）+2/3(第2列)优超于第5列，故可去掉第3、4、5列，得到新的赢得矩阵：

A2=734652

2023/1/15第216页例11-6对于A2由于第1行优超于第3行，故可去掉第3行，得到新的赢得矩阵：

A3=7346

2023/1/15第216页例11-6对于A3易之于无鞍点存在，应用定理4求解不等式组：7x3+4x4

v3x3+6x4

vx3+x4

=1x3,x407y1+3y2

v4y1+6y2

vy1+y2

=1y1,y20

2023/1/15第216页例11-6求得解为：x3*

=1/3，x4*

=2/3y1*

=1/2，y2*

=1/2于是原矩阵对策的一个解是：x*

=（0，0，1/3，2/3，0）Ty*

=（1/2，1/2，0，0，0）TVG=52023/1/15第三节矩阵对策的求解1.22对策的公式法2.2n或m2对策的图解法3.线性方程组求解法4.线性规划求解法2023/1/151.22对策的公式法所谓22对策是指局中人的赢得矩阵为22阶矩阵，即：

A=a11a12a21a22如果A有鞍点，则很快就可求出各局中人的最优策略；如果A没有鞍点，则可证明各局中人的最优混合策略中的xi*

,yj*均大于零。于是由定理6可知，为求混合策略可求解下列方程组：a11x1+a21x2

=va11y1+a12y2

=va12x1+a22x2

=va21y1+a22y2

=vx1+x2

=1y1+y2

=12023/1/152.2n或m2对策的图解法例：设一矩阵对策G={S1，S2，A}，其中S1

={1，2}，S2

={1，2，

3}

2311752A=设局中人甲的混合策略为(x,1-x)T，x[0,1]。过数轴上坐标为0和1的两点分别做两条垂线和，垂线上点的纵坐标值分别表示局中人甲采取纯策略1，2时，局中人乙采取各策略时的赢得值。如下图所示，当局中人甲选择每一混合策略(x,1-x)T时，他可能的最少赢得为局中人乙选择1，2，

3时所确定的3条直线在x处的纵坐标值的最小值。

2023/1/152.2n或m2对策的图解法A=2311752

V=2x+7(1-x)V=3x+5(1-x)V=11x+2(1-x)设局中人甲的混合策略为(x,1-x)T，x[0,1]。过数轴上坐标为0和1的两个点分别做两条垂线和，垂线上的点的纵坐标值分别表示局中人甲采取纯策略1，2时，局中人乙采取各策略时的赢得值。如下图所示：

2023/1/15甲采取混合策略最少的赢得：B1BB2B3甲确定x使赢得最大，即最小最大原则012571132xAB1B2BB3123

2023/1/15x=OA,AB即为对策值VG求解x及VG，解方程组：VG=3x+5(1-x)VG=11x+2(1-x)求得x=3/11,VG=49/11；所以甲的最优策略为x*=（3/11，8/11）E(x*,1)=23/11+78/11=62/11>49/11E(x*,2)=33/11+58/11=49/11E(x*,3)=113/11+28/11=49/11所以局中人乙的最优混合策略y*=（0,y2,y3）

2023/1/153y2+11y3=VG=49/115y2+2y3=VG=49/11y2+y3=1求解得y*=（0,9/11,2/11）.

2023/1/15例：设一矩阵对策G={S1，S2，A}，其中S1

={1，2，3}，S2

={1，2

}

27A=66

112设乙的混合策略为(y,1-y)，同理有：

2023/1/15012671162yA1B1B2B3乙采取混合策略最大的支付：7B1B211乙确定y使支付最小，即最大最小原则321A2

2023/1/15OA1yOA2VG=62y+7(1-y)=66y+6(1-y)=66y+6(1-y)=611y+2(1-y)=6求得OA1=1/5,OA2=4/9。故局中人乙的最优混合策略为y*=（y,1-y），其中y

[1/5，4/9]；而故局中人甲的最优策略显然只能是x*=（0,1,0），即策略2。2023/1/153.线性方程组求解法根据定理4求解矩阵对策解（x

*，y

*）的问题等价于求解：aijxivaijyjvxi=1yj=1xi0yj0又根据定理5和定理6，如果x

*，y

*中各分量均不为零，即可将不等式组转换为方程组：

2023/1/153.线性方程组求解法不等式组转换为方程组：aijxi=vaijyj=vxi=1yj=1xi0yj0如果这两个方程组存在非负解x

*和y

*，则已经求得了矩阵对策的解（x

*，y

*）。

2023/1/153.线性方程组求解法例：“齐王赛马”齐王的赢得矩阵为31111-11311-11A=1-13111

-11131111-1131111-113

2023/1/153.线性方程组求解法设：X

*=（x1，x2，x3，x4，x5，x6）TY

*=（y1，y2，y3，y4，y5，y6）T

从矩阵A的元素来看局中人采取任何一个策略的可能性都是存在的，故可事先假设X

*，Y

*中各分量均不为零；于是有：

ATX=vAY=v

xi=1yj=1求得解为：X

*=（1/6，1/6，1/6，1/6，1/6，1/6）TY

*=（1/6，1/6，1/6，1/6，1/6，1/6）T对策的值（齐王的期望赢得）为1。2023/1/154.线性规划求解法根据定理5有矩阵对策的解（x

*，y

*）等价于下述不等式组的解：aijxi

vaijyjvxi=1yj=1xi0yj0其中v=max[minE(x,y)]=min[maxE(x,y)]就是对策的值VG。做变量变换xi=xi/v,yj

=yj/v于是有：

2023/1/154.线性规划求解法aijxi

1aijyj1xi=1/vyj=1/vxi0yj