天津大学管理学院：《管理科学基础》课程PPT教学课件（运筹学）第十二章 二人有限非零和对策

第十二章二人有限非零和(双矩阵)对策 双矩阵对策及其特性 设二人有限非零和对策问题的局中人为和∏,策略 集分别为S1={a1,a2,…,Cn},S2={B,B2…,B A=la,]和B=[bLm分别为和∏的支付矩阵,其中 b分别为I和相应于c和B的赢得。双矩阵对策 记为G=(S1,S2,(A,B) I的混合策略集S={X=(x1 )|∑x=1,x≥0} ∏的混合策略集S2={=(y1…yn)∑y=1,y≥0}

一、双矩阵对策及其特性 1 1 2 2 1 2 1 2 { , }, { , } [ ] [ ] ( , ,( )) m n ij m n ij m n ij ij i j S S A a B b a b G S S A B                      设二人有限非零和对策问题的局中人为 和 ，策略 集分别为 ， ， ， ， ， ＝ 和 ＝ 分别为 和 的支付矩阵，其中 ， 分别为 和 相应于 和 的赢得。双矩阵对策 记为 ， 。 * 1 1 1 * 2 1 1 { ( ) | 1, 0} { ( ) | 1, 0} m m i i i n n i i i S X x x x x S Y y y y y                 混合策略集 混合策略集 的 的

在矩阵对策中,由于I的得就是∏的失,二人 处于完全竞争的非合作状态。而在双矩阵对策中, 由于I的得并不一定等于∏的失,二人可以同时得, 故二人之间可能合作,从而得到更多的利益 A+B=0时,双矩阵对策即化为矩阵对策

A B  0时，双矩阵对策即化为矩阵对策。     在矩阵对策中，由于 的得就是 的失，二人 处于完全竞争的非合作状态。而在双矩阵对策中， 由于 的得并不一定等于 的失，二人可以同时得， 故二人之间可能合作，从而得到更多的利益

、非合作双矩阵对策 解的概念与存在性定理 平衡局势: 设X∈S,Y∈S2,若对任何X∈S和任何Y∈S2 有XAy≤X"AY X BYX BY 则称(X,y)为双矩阵对策G的平衡局势 平衡局势(X,Y)对应的二局中人的期望收益 (X"AY,X"By)就是G的值,记为U’,V”)

1.解的概念与存在性定理 平衡局势： * * * * * * 1 2 1 2 * * * * * * * * , , ( , ) T T T T X S Y S X S Y S X AY X AY X BY X BY X Y G       设 若对任何 和任何 ， 有 则称 为双矩阵对策 的平衡局势。 * * * * * * * * , ( , ) ( , ) T T X Y X AY X BY G U V 平衡局势（ ）对应的二局中人的期望收益 就是 的值，记为

定理1:任何双矩阵对策至少存在一个平衡局势。 定理2:(X,Y)为双矩阵对策G的一个平衡局势的 充要条件是存在数p和q使[Xyp'q" 是下述问题的一个解: max (X AY+X BY-p-q AY≤pE XB≤aE EX=EY=1 XY≥0 其中E,E为分量为1的向量

* * * * * * * * , [ ] max . . 1 , 0 , 1 T T T n T m T T m n m n X Y G p q X Y p q X AY X BY p q AY pE X B qE s t E X E Y X Y E E              （ ）为双矩阵对策 的一个平衡局势的 充要条件是存在数 和 使 是下述问题的一个解： （ ） 其中 为分量为 的向量。 定理2：

2.2×2双矩阵对策的解法 当A和B均为2×2阶时,A41a12,B=b21b2 相应的双矩阵对策可表示为 y 1101 (0≤x1≤1,0≤y≤1 1-x(a21b1)(a2,b2 若(X,γ)是均衡局势,由平衡局势的定义,X和Y应 分别是XAy在S1上和X”BY在S2上的极大点

当A和B均为2×2阶时， 相应的双矩阵对策可表示为: 11 11 12 12 21 21 22 22 ( , ) ( , ) ( , ) ( , ) a b a b a b a b       1 y 1 1 y 1 1 x 1 x I II 1 1 (0  x 1,0  y 1) * * * * * * * * 1 2 ( , ) T T X Y X Y X AY S X BY S 若 是均衡局势，由平衡局势的定义， 和 应 分别是 在 上和 在 上的极大点。 11 12 11 12 21 22 21 22 , , a a b b A B a a b b              

而 XAr=[, 1-xl VI =[(a1-a2-a1+a2)-(a2-a2)x+a2+(a1-a2) a+a 则使XAY达到极大的x应满足 Ay1-A20

  * * 11 12 1 1 1 * 21 22 1 * * 11 12 21 22 1 22 12 1 22 21 22 1 1 1 ( ) ( ) ( ) T a a y X AY x x a a y a a a a y a a x a a a y                             而 1 11 12 21 22 2 22 12 A a a a a A a a       记 * * 1 * 1 1 2 * * 1 1 1 2 * 1 1 2 0, 0 [0,1] , 0 1, 0 T X AY x A y A x A y A A y A             则使 达到极大的 应满足 当 中任意值 当 当 （1）

y X"BY=「x;1-X」b21b2‖1-y =[(b1-b2-b1+b2)x-(b2-b2)]y1+b2+(h2-b2 记 B1=b1-b1,-b21+b 则使X”BY达到极大的y应满足 B,x1-B,0

* * * 11 12 1 1 1 21 22 1 * * 11 12 21 22 1 22 21 1 22 12 22 1 b 1 b 1 ( ) ( ) ( ) T b y X BY x x b y b b b b x b b y b b b x                              1 11 12 21 22 2 22 21 B b b b b B b b       记 * * 1 * 1 1 2 * * 1 1 1 2 * 1 1 2 0, 0 [0,1] , 0 1, 0 T X BY y B x B y B x B B x B             则使 达到极大的 应满足 当 中任意值 当 当 （2）

根据式(1)和式(2),可在以x和y为横、纵轴的坐标系中确 定出对局中人I来说可能成为平衡局势的点(不妨称为I的解) (x1y1)的轨迹和对于局中人I来说可能成为平衡局势的点(不妨 称为I的解)x1y1)的轨迹。二轨迹的公共点即(x2y1),由此便 可得到平衡局势。将这一分析的结果各分为9种情形(即A1和A B和B2取各种符号时的9种条件),如下表所示:

1 1 * 1 1 * * * 1 1 1 1 1 2 1 2 (1) (2) x y ( ) (x ,y ) ( )(x ,y ) (x ,y ) 9 ( A A B B 9 ) 根据式 和式 ，可在以 和 为横、纵轴的坐标系中确 定出对局中人I来说可能成为平衡局势的点 不妨称为I的解 的轨迹和对于局中人II来说可能成为平衡局势的点 不妨 称为II的解 的轨迹。二轨迹的公共点即 ，由此便 可得到平衡局势。将这一分析的结果各分为 种情形 即 和 、 和 取各种符号时的 种条件 ，如下表所示：

条件序 解 图示 J A1=0 0≤x,≤1 A2=0 JI 0 A1=0 0 A,>0 0≤y1≤1 0 XI yI 0 0 x1=1,0<y1 A2=0 0≤x1≤,y1=0

1 x 1 y 1 10 1 x 1 y 1 10 1 x 1 y 1 10 1 x 1 y 1 10 1 0  x 1 1 0  y 11 0  y 1 1 x  01 0  y 1 1 x 1 1 0  x 1, 1 y  0 1 0  y 1 1 x 1, 1423 12 00 AA 12 00 AA 12 00 AA  12 00 AA 

x1 1y 1 1 0 x1 1y 1 1 0 x1 1y 1 1 0 x1 1y 1 1 0 1 0x 1, 2 1 1 0 A y A   1 0y 1 1x 1, 1 0y 1 1x 0, 6 9 7 8 1 2 0 0 A A   1 2 0 0 A A   1 2 0 0 A A   1 2 0 0 A A   5 1 2 0 0 A A   1y 0 1 0y 1 1x 0, 1x 0, 2 1 1A y A  1x 1, 2 1 1 1 A y A   2 1 1 0 A y A   1x 0, 2 1 1A y A  1x 1, 2 1 1 1 A y A   1 0x 1, x1 1y 1 1 0 2 1A A 2 1A A 1 0x 1