当前位置：文档之家 › 矩阵对策的解法

矩阵对策的解法

  • 格式：ppt
  • 大小：285.50 KB
  • 文档页数：21

下载文档原格式

  / 21

合集下载

矩阵对策的最优纯策略

矩阵对策的最优纯策略

,m α，
,
,n β；则分别为
},m α和},n β。

当局中人Ⅰ选定纯策略i α和局中人Ⅱ选定纯策略后，就形成了一个纯局)j ，这样的纯局势共有m n ⨯个。

对任一纯局势赢得值为ij a ，称
12122
212n n m m mn a a a a a ⎤⎥⎥⎥⎥⎦
为局中人Ⅰ的赢得矩阵。

局中人Ⅱ的赢得矩阵就是当局中人Ⅰ，Ⅱ的策略集12,S S 及局中人Ⅰ的赢得矩阵对策也就给定了，记为{}12,,G S S A =。

在齐王赛马的例子中，齐王的赢得矩阵
},
,m α，
},n β，max ）
成立，记其值为）成立的纯局势()
,i j αβ**
在纯策略意义下的解（或鞍点）
},m α，},n S β，
1,2,
,,m x ∑1,2,
,,n y ∑分别称为局中人Ⅰ和Ⅱ的混合策略集分别称为局中人Ⅰ和Ⅱ的混合策略（或策略），对
),m x 可设想成当两个局中人多次重复进行对策
12,,
,m ααα的频率。

若只进行一次时对策，混合
对策可设想成局中人Ⅰ对各纯策略的偏爱程度。

求解混合策略的问题有图解法，迭代法、线性方程组法和线性规划法，在。

运筹与优化--对策论

运筹与优化--对策论

y∈S2*为局中人I和Ⅱ的混合策略,(x,y)为混合局势,
局中人I的赢得函数为 E(x,y)xTAy aix jiyj
称G* ={S1*,S2*,E}为对策G的混合扩充. i j
A
12
设 mm ax E i(x n ,y)mE i(x n *,y)
x S 1 * y S2 *
y S2 *
mm inE a(x,x y)mE a(x,x y*)
注意:G在纯策略下解存在时,定义4中的
VG ;Gai在j 混合策略意义下的解(x*,y*)
存在时,VG=E(x*,y*).
例4. 解矩阵对策 中
3 G6={S1 ,S2 ;A },其
A
5
4
A
14
局中人I取纯策略αi时,其赢得函数为 E(i,y)=∑aijyj ,
局中人Ⅱ取纯策略βj时,其赢得函数为 E(x,j)=∑aijxi .
人I以概率xi≥0取纯策略αi,局中人Ⅱ以概率yj≥0取
纯策略βj ,且
m
xi
1.记,
n
yj 1
i1
j1
m
S 1 {x(x1,x2, ,xm ) E mxi0 , xi1 }
i 1
n
S2 {y(y1,y2, ,yn) E nyj0, yj1 }
j 1
则S1* ,S2*分别称为局中人I和Ⅱ的混合策略集.称x∈S1*,
A
24
推论.如果纯策略α1被纯策略α2 , … αm的凸线 性组合所优超,则定理10的结论仍成立.
由上两式得
E(x,y)=∑E(i,y)xi
(5)
E(x,y)=∑E(x,j)yj . (6)
定理3.设x∈S1*,y∈S2*,则(x*,y*)是G的解的充要条 件是: 对任意i=1,2,…,m 和 j=1,2,…,n,有

第十三讲 对策矩阵解法

第十三讲 对策矩阵解法

4
矩阵对策解法
• 矩阵对策模型给定后，各局中人面临的问 题：如何选取对自己最为有利的纯对策略， 以谋取最大的赢得？
5
矩阵对策的纯策略
例1：设有一矩阵对策G={S1, S2; A}，其中
6 3 A 9 3 1 2 1 0 8 4 10 6
求最优纯策略？
取大则取2 max min aij= 2
i j
取小则取2 min max aij= 2
j
i
7
矩阵对策的纯策略
定义1 设G={S1, S2; A}为一矩阵对策，其中 S1={α1, …,αm}，S2={β1, …,βn}， A=(aij)m×n。若
max min aij min max aij
7 1 8 3 2 4 A 16 1 3 3 0 5
9
答案
1
2
3
min ai j
j
α1 α2 α3
max ai j
i
-7 3 16 -3 16
1 2 -1 0 2*
-8 4 -3 5 5
-8 2* -3 -3
7 1 8 3 2 4 A 16 1 3 3 0 5
16
矩阵对策实例
这一储量问题可以看成是一个对策问题，把采购员当作局中人Ⅰ，他 有三个策略：在秋天时买10吨、15吨与20吨，分别记为 1 , 2 ,3 把大自然看作局中人Ⅱ(可以当作理智的局中人来处理)，大自然(冬季 气温)有三种策略：出现较暖的、正常的与较冷的冬季，分别记为 1 , 2 ,3 把该单位冬季取暖用煤实际费用(即秋季购煤时的用费与冬季不够时 再补购的费用总和)作为局中人Ⅰ的赢得，得矩阵如下：

《运筹学》教材编写组《运筹学》笔记和课后习题(含考研真题)详解(对策论基础)

《运筹学》教材编写组《运筹学》笔记和课后习题(含考研真题)详解(对策论基础)

圣才电子书 十万种考研考证电子书、题库视频学习平台

（2）2× 或 ×2 对策的图解法
注意：该方法用在赢得矩阵为 2× 或 ×2 阶的对策上特别方便，也可用在 3× 或
×3 对策上。但对 和 均大于 3 的矩阵对策就丌适用了。
设缩减后的赢得矩阵为二阶无鞍点对策问题，局中人Ⅰ的混合策略为
的最优纯策略。 定理 1 矩阵对策 使得对一切
在纯策略意义下有解的充分必要条件是：存在纯局势
，均有
。
定义 2 设
为一个定义在
及
上的实值函数，如果存在
，使得对一切
和
，有
，则称
为
函数 的一个鞍点。 矩阵对策解的性质：
性质 1 无差别性。即若 性质 2 可交换性。即若
也是解。 定义 3 设有矩阵对策
记
是对策 G 的两个解，则
定理 11 设矩阵对策
的值为 ，则
6．矩阵对策的解法 （1）2×2 对策的公式法 所谓 2×2 对策是指局中人Ⅰ的赢得矩阵为 2×2 阶的，即
如果 A 有鞍点，则很快可求出各局中人的最优纯策略；如果 A 没有鞍点，为求最优混 合策略可求下列等式组：
上面等式组（Ⅰ）和（Ⅱ）一定有严格非负解
和
，其中
6 / 33
是对策 G 的两个解，则
和
，其中
，
，
则 和 分别称为局中人Ⅰ和Ⅱ的混的混合策略（或策略）；对
，称
为一个混合局势（或局
势），局中人Ⅰ的赢得函数记成
这样得到的一个新的对策记成
，称 为对策 G 的混合扩充。
定义 4 设
是矩阵对策
的混合扩充，如果
3 / 33
圣才电子书 十万种考研考证电子书、题库视频学习平台

矩阵对策问题及其解法

矩阵对策问题及其解法

矩阵对策问题及其解法背景对策论研究具有竞争性质的现象。

有权决定⾃⾝⾏为的对策参加者称为局中⼈，所有局中⼈构成集合I，在⼀局对策中可供剧中⼈选择的⼀个实际可⾏的完整的⾏动⽅案成为策略，对于任意剧中⼈i∈I，都有⾃⼰的策略集S i。

⼀局对策中由各剧中⼈选定的策略构成的策略组称为局势s=(s1,...,s n)，⽽全体局势集合S=S1×...×S n。

局势决定了对策的结果，对局势s∈S，局中⼈i可以得到收益H i(s)，也称为局中⼈i的赢得函数。

矩阵对策即⼆⼈有限零和对策，是⼀类较为简单的对策模型。

矩阵对策基础我们假设，局中⼈ I 有纯策略α1,...,αm，局中⼈ II 有纯策略β1,...,βn，⼆者各选择⼀个纯策略则构成m×n个纯局势 (αi,βj)，将 (αi,βj)下 I 的赢得值记为a i,j，设矩阵A=[a i,j]，称为 I 的赢得矩阵或 II 的⽀付矩阵。

局中⼈ II 的赢得矩阵就是 −A T。

最优纯策略若纯局势 (a i∗,b j∗) 满⾜max i minj a i,j=minjmaxi a i,j=a i∗,j∗则称为矩阵对策 {S1,S2;A} 的最优纯策略。

显然，最有纯策略在赢得矩阵中对应的元素⼀定满⾜，其是所在⾏的最⼩元素，也是所在列的最⼤元素，即矩阵的鞍点。

混合策略当纯策略不存在时，我们希望给出⼀个选取不同策略的概率分布。

我们记 I,II 的概率分布向量分别为x,y，所有概率分布向量构成的集合为S1,S2，则局中⼈ I 的赢得函数为E(x,y)=x T Ay。

纯策略是混合策略的特例。

若混合局势 (x∗,y∗) 满⾜max x miny E(x,y)=minymaxx E(x,y)=E(x∗,y∗)则称为矩阵对策 {S1,S2;A} 的最优混合策略。

同样，混合策略 (x∗,y∗) 是最有混合策略的充要条件也是 (x∗,y∗) 是函数E(x,y) 的鞍点。

对策论例题

对策论例题

策略 1 1 A 2 3 3 0 2
39; 3
把此对策问题表示成一个线性规划模型，并用单纯 形法求解此对策。 解 由 max min aij 0, min max aij 2, 知v>0 j j i i ' ' ' 先求B的最优策略，设B的策略为 ( y1 , y2 , y3 ), 对策值
* 1 * 2 * 3
例3 已知矩阵对策 , 局中人为A与B，A的赢的矩阵为
0 3 1 1 1 2 2 1 1 1 3 0
求对策的最优混合策略与对策的值。 解 由max min aij 2, min max aij 0, 知-2<V<0. 将上面的赢得矩阵中各元素都加上3， 得新的赢得
3 2 0 4
y y y 为v,并令 y1 , y2 , y3 , v v v
则B规划的线性规划模型为表5。1 初始表
max W y1 y2 y3,
3 y1 2 y2 s.t. 2 y y 1 2 y1 , y2 , 2 y3 4 y3 y3 0 1 1 1
的最优解为 2 或 4 ， 最优解 V

5.
注： 此例说明，对策的解可以不惟一，但值是唯一的.
2。无鞍点的混合策划问题 （1）线性规划法求解
例 2 某小城市有两家超级市场相互竞争，超级市场
A有三个广告策略，超级高级B也有三个广告策略， 已经算出当双方采取不同的广告策略时，A方所占市 场 份额增加的百分数如下：
0
0
1
0
-1/3
1/3
YB
b
y1
y2
y3
s1
s2
s3

双矩阵对策

双矩阵对策
则称( X *,Y * )为双矩阵对策G的平衡局势。
平衡局势（X *,Y *）对应的二局中人的期望收益 ( X *T AY *, X *T BY * )就是G的值，记为(U *,V *)。
定理1：任何双矩阵对策至少存在一个平衡局势。
定理2：（X *,Y *）为双矩阵对策G的一个平衡局势的
充要条件是存在数p*和q*使[ X * Y * p* q* ]T 是下述问题的一个解：
公理（5 线性变换不变性）：设P'是从P经线性变换 U ' aU b,V ' cV d (a, c 0)
(U0,V0 )称为安全点，表示收益的“下限”。
(2) Nash谈判集 满足U U0且V V0的Pareto点(U ,V )的全体。
VA
（U0 ,V0）
0
B
U
显然，最优点应从Nash谈判集中产生，称为Nash谈判解。
4.Nash谈判解的计算 ⑴Nash谈判公理
为了从Nash谈判集中寻找使双方可达成协议的解(U *,V *), 记所有可能成为(U *,V *)的可行解的集合为P(可即Nash谈判集) Nash给出了(U *,V *)的6个公理：
B1 0 B2 0
0yyyy01111yy110011,,,,11,0,BBB0B1212xx11xx11xy1B1BBB12BB12BB112112
y1
1
B2
B1
0
1
x1
y1
1
B2
B1
0
1
x1
y1
8
B1 0 B2 0
1
y1 1, 0 x1 1
0
1
x1
y1
9
B1 0 B2 0

对策论(Theory of Games)

对策论(Theory of Games)

定义
并不是所有的对策都存在鞍点，如 A为齐王的赢得矩阵 3 1 1 1 1 -1 1 3 1 1 -1 1 A= 1 -1 3 1 1 1 -1 1 1 3 1 1 1 1 -1 1 3 1 1 1 1 -1 1 3 max(min aij)= -1 min (max aij)=3 i j j i
例如：
• 给定矩阵对策
6 5 6 A 1 4 2 8 5 7
对策的最优值为5，对策的解有两个，分 别为局势 , 和 , 。
1 2 3 2
(三)矩阵对策的混合策略
1、矩阵对策的混合策略的定义
2、原则：坏中求好的原则。 3、解的存在：一定有解 4、混合策略求解：利用期望转化成 线性规划问题求解。
三、矩阵对策模型
（一）矩阵对策的概念 （二）矩阵对策的最优纯策略 （三）矩阵对策的混合策略 （四）矩阵对策的解法
（一）矩阵对策的概念 1、矩阵对策的定义 2、建立矩阵对策模型
1、矩阵对策的定义 局中人只有两个，对策中各方只能从有限 的策略集中确定性的选择一种，且对策双 方的支付之和为零的对策称为两人零和纯 策略对策。
表2
齐 王 上中 下 田忌 上中下 3 上下 中上 中 下 1 1 中下 上 -1 下中 上 1 下上 中 1
上下中 1 中上下 1
中下上 1 下中上 1
3 1
1 -1
-1 3
1 1
1 1
3 1
1 -1
1 3
1 1
-1 1
下上中 -1
1
1
1
1
3
引例3
有两个儿童A和B在一起玩“石头-剪子布”游戏。我们规定胜者得1分，负者得 -1分，平手时各得0分。双方选定的各种 出法及相应的结果可由下表列出。双方 应取何种策略？

矩阵对策

矩阵对策

2 3 1 1 2 3 3 1 2
第三部分
二人有限非零和对策
一、非零和对策的一般表达 1、局中人集合：i = 1, 2 ,…，n 2、每个局中人的策略集：Si (i = 1,…,n) 3、每个局中人的赢得函数：ui (s1, …, s i , … sn)
对策的一般表达：G={S1, … Sn ; u1, … un }
1
1 3 1
1
1 1 3
4、优超原理
定义： 若A中第i, k 行有aij akj , j 1 n 称 i 优超于 k 。 记 i k 若A中第j, l列有aij ail , i 1 m 称 j 优超于l 记 j l 。
例： A
1 0 2 2 3 1
称为i的劣策略(Dominated strategy)。
' i
'' i
例： B1 Ⅰ A1 A2 1， 0 0， 3
Ⅱ
B2 1， 2 0， 1 B3 0， 1 2， 0
劣策略
可按如下思路寻找均衡解： 首先找出某个局中人的劣策略（如果存在），剔除该劣 策略，得到新的博弈；再剔除该新博弈中的某个中人的 劣策略。重复进行，直至只剩下唯一的策略组合为止， 这个剩下的策略称为重复剔除的占优均衡（Iterated dominance equilibrium）。
对策值V=1
(2) 多鞍点与无鞍点对策
例 设有一矩阵对策如下，求它的解。
6 1 A 8 0 5 4 5 2 6 2 7 6 5 - 1 5 2
局势 ( s1 , d 2 ) ( s1 , d 4 ) ( s3 , d 2 ) ( s3 , d 4 ) 均构成鞍点， 此对策有多个解。

8.1对策问题的提出8.2对策论模型8.3矩阵对策的解法知识归纳习题

8.1对策问题的提出8.2对策论模型8.3矩阵对策的解法知识归纳习题

合作… 对策模型… 零和 二人 有限 非零和 完全信息 静态 多人…… 无限…… 非合作 不完全信息…… 完全信息 动态 不完全信息……
（2）策略 在一局对策中，可供局中人选择的一个实际可行的自始至终通盘筹划的完整行动 方案称为这个局中人的一个“策略”。参加对策的局中人i（i∈I）的所有可供选择的 策略的全体所构成的集合叫做局中人i的“策略集”，简记作Si。 （3）赢得函数 一局对策结束之后，对每个局中人来说，不外乎是胜利或失败，名次的前后， 以及其他物质的收入或支出等，这些可以统称为“得失”或“益损”。 在齐王与田 忌赛马的例子中，最后田忌赢得一千金，而齐王损失一千金，即为这局对策（结局时） 双方的“得失”。 实际上，每个局中人在一局对策结束时的得失，与局中人所选定的策略有关。 例如，上述赛马的例子中，当齐王出策略“上、中、下”，田忌出策略“下、上、中” 时，田忌得千金；而如果与田忌都出策略“上、中、下”时，田忌就得付出三千金了。 因此，在一局对策中，当局势给定以后，对策的结果也就确定了。 一局对策结束时，每个局中人的“得失”是全体局中人所决定的一组策略即 “局势”的函数，我们称之为“赢得函数”。 在最终局势ω下，局中人i∈I的赢得函数记作：H（i,ω）。 在一局对策中，如果在任一“局势”中，全体局中人的“得失”相加总和为零， 就称该对策为“零和对策”，否则，就称为“非零和对策”。上述齐王与田忌赛马的 例子中，不论比赛双方的策略如何，比赛的结果，一方的所得必为另一方的所失，因 此该对策就是一个零和对策。 一般来说，当上述三个基本要素确定以后，一个对策模型就确定了。
（3）发展阶段 20世纪60至80年代是博弈论体系的发展壮大时期。一方面，研究的领域从军事 战略战术问题推广应用到经济领域；另一方面，研究的内容也不断发展出新。合作博 弈理论继续得到充实和丰富，而非合作博弈理论更是发展迅速，成为博弈论研究和应 用的主流。 （4）成熟阶段 纪80年代至今是博弈论的完善和应用期。此间博弈论本身发展成为了一个 相对完善、内容丰富的理论体系，羽翼已丰的非合作博弈理论在理论研究和实践应用 中都占据了主导地位。更重要的是，博弈理论在各种经济学科中都得到了深入的应用， 在政治学、生物学、计算机科学、道德哲学、社会学等领域内也产生了重要影响。 1994年，纳什、泽尔腾、海萨尼三人因博弈论及其在经济应用方面的突出贡献而荣 获诺贝尔经济学奖，1996年诺贝尔经济学奖再度授予了在博弈论研究方面作出突出 贡献的维克里和莫里斯。由此，吸引了更多的学者投入到博弈论的研究当中，使得博 弈论成为世界范围内的研究热点，博弈论也逐步趋于完善和成熟。2001年，研究博 弈论的学者再一次获得诺贝尔经济学奖。美国教授乔治· 阿克尔洛夫、迈克尔· 斯彭斯 和约瑟夫· 斯蒂格利茨在20世纪70年代奠定了对充满不对称信息市场进行分析的理论 基础，正是由于他们在“对充满不对称信息市场进行分析”领域所做出的重要贡献， 而分享了2001年诺贝尔经济学奖。

矩阵对策纯策略意义下的解

矩阵对策纯策略意义下的解

此而来。通常把矩阵对策记为
G＝{Ⅰ,Ⅱ;S1,S2;A} 或
G＝{S1,S2;A}
例：G={S1,S2,A} S1={α1,α2,α3,α4} S2={β1,β2, β3}
-6 1 -8 A= 3 2 4
9 -1 -10 -3 0 6
对于G＝{S1,S2;A}， 若有等式
max min aij＝min max aij＝ai*j*
aij*≤ai*j*≤ai*j
例如
65 15 A= 8 5 02
65 2 -1 55 62
7.3 矩阵对策混合策略意义下的解
先看一个简单的例子: A= 3 6 54
一般地，设矩阵对策G＝{S1,S2;A}，其中 S1＝{α1,α2,…,αm}，S2＝{β1,β2,…,βn}， A＝（aij）m×n
为各局中人的最优混合策略。例
(2)线性规划法
当对策的值大于0时,可利用
线性规划法求解矩阵对策。构造
两个线性规划问题
min z＝∑xi i
∑i aijxi≥1 (j=1,2,…,n)
xi≥0
(i=1,2,…,m)
max w＝∑j yj
∑j aijyj≤1 (i=1,2,…,m)
பைடு நூலகம்
yj≥0
(j=1,2,…,n)
7.2 矩阵对策纯策略意义下的解
矩阵对策就是二人有限零和对策。设两个局中人为Ⅰ、
Ⅱ，它们各自的策略集为
S1＝{α1,α2,…,αm} S2＝{β1,β2,…,βn} 当局中人Ⅰ选定纯策略αi，局中人Ⅱ选定纯策略βj后，就 形成了一个纯局势(αi,βj)，这样的纯局势共有m·n个。
对任一纯局势(αi,βj)，记局中人Ⅰ的赢得值为aij，则得 矩阵 A=（aij），称为矩阵人Ⅰ的赢得矩阵。由于是零和对 策，则矩阵人Ⅱ的赢得矩阵为-A。矩阵对策的名称正是由

运筹学—对策论(四)

运筹学—对策论(四)
运筹学—对策论(四)
补充定理:
定理9 设(x*,y*)是矩阵对策G的解， υ =VG，则
=υ ⑴若xi*>0, 则 ∑ aijyj* j =υ ⑵若yj*>0, 则 ∑ aijxi* i ⑶若 ∑ aijyj* < υ 则xi*=0 j 则yj*=0 ⑷若 ∑ aijxi* >υ i
§3矩阵对策的解法
A
1 Ⅱ
Ⅰ
V=2x+7(1-x)
7 5 2
0
· β2 · β3 · B
1
β1
B
B2
Ⅰ
方程组：
折线B1 B B2 B3上的点的 · 11 纵坐标就是对应x的最 小赢得值。按最大最 小原则应选择x=OA， · 3 AB即为对策值。为求 B3 · 2 出x和对策值VG，可 1 Ⅱ 求 x=3/11, VG=49/11。所以
过数轴上O和1的两点作两条垂线Ⅰ–Ⅰ ,Ⅱ –Ⅱ,在垂线 上把局中人Ⅰ采取纯策略α1和α2时，局中人Ⅱ分别采取 纯策略β 1, β 2, β 3 时的赢得值标出。如图 Ⅰ Ⅱ 折线B1 B B2 B3上的点的 V=2x+7(1-x) · 11 纵坐标就是对应x的最 β1 小赢得值。按最大最 7 · β 小原则应选择x=OA， 5 ·2 β3 · 3 AB即为对策值。为求 B B2 2 · B1 B3 · 2 出x和对策值VG，可 0 Ⅰ
A
1 Ⅱ
Ⅰ
V=2y+7(1-y) B
B2 Ⅱ
B1 α 1
1 Ⅱ
折线B1 B B2 上的点的纵 · 11 坐标就是对应y的最大 损失值。按最小最大原 则应选择y=OA，AB即 · 3 为对策值。为求出y和 ·2 对策值VG，可求
方程组：

精心整理的运筹学重点10.对策论

精心整理的运筹学重点10.对策论

v1 = max min(3 − 2 x, 2 + 2 x) ， v1 = max min(3 − 2 x, 2 + 2 x) 就是折线 ＡＢＣ，它是局 0≤ x ≤1 0≤ x ≤1
中人 Ｉ 的最小赢得线，Ｂ 就是折线 ＡＢＣ 的最高点，所以 Ｂ 点所对应的值就是混合策略意 义下的最大最小值。
i j j i
３．无鞍点的两人有限零和对策求解 X = ( x1 , x2 ,..., xm )T 为局中人 Ｉ 的混合策略，
Y = ( y1 , y 2 ,..., yn )
T
∑ x = 1 为局中人 ＩＩ 的混合策略， ∑ y = 1 ， ( X , Y ) 称为混合局势。
i i
最优混合策略求解方法 y1 y2
第十章 对策论 １．对策论类型 １）根据局中人个数：二人对策、多人对策 ２）根据局中人间是否允许合作：合作对策、非合作对策 ３）根据局中人的策略集中的策略个数：有限对策、无限对策 ４）根据各局中人的赢得函数的代数和是否为零：零和对策、非零和对策 ５）根据策略的选择是否与时间推移有关：静态对策、动态对策 ６）根据对策中各局中人所拥有的有关决策信息：完全信息对策、不完全信息对策 ７）根据对策模型的数学特征：矩阵对策、连续对策、微分对策、随机对策 矩阵对策：又称为二人有限零和对策。 ２．有鞍点的两人有限零和对策求解 G = {S1, S2 , A} 求解： maxmin{aij } = V1,minmax{aij } = V2
x1 a11 x2 a21
矩阵对策求解方法
有
a12 a22
有无鞍点？
无 是
获得
２＊ｎ 或 ｍ＊２ 矩阵
否
图解

第 11.3 节 矩阵对策的解法

第 11.3 节 矩阵对策的解法

A
1
1
1
3
1
1
1 1 1 1 3 1
1 1 1 1 1 3
20211//1122//99
15
第十五页，共22页。
例17
某厂用三种不同的设备 1 、 2 、 3 加工三种不同的产品1 、
2 、 3 , 已知三种设备分别加工三种产品时, 单位时间内创造 的价值由下表给出。
被加工产品
使用设备
（4）令 0 < y < 1，即局中人二采用混合策略，按最大最小原则，在 图中找出局中人二的最优策略；具体方法是：让 y 在(0, 1)内变动， 找出经过点(y, 0)的垂线与上述直线交点中纵坐标最大的点集(某些线 段)，然后再从中找出纵坐标最小的点 P 所对应的横坐标即为所求；
（5）确定经过点 P 的两相交直线，根据两相交直线列出对应方程组， 求出 y*.
3.1 公式法、图解法和方程组法
1.赢得矩阵为2×2 阶的, 即
A
a11 a21
a12
a22
如果 A 有鞍点, 则很快可求出各局中人的最优纯策略; 如果 A
没有鞍点,则可证明各局中人最优混合策略中的 xi* , yj* 均大 于零。于是, 由定理 6 可知, 为求最优混合策略可求下列等式
矩阵对策的线性规划方法
作变换: xi = xi / v, i = 1 , ⋯ , m,则不等式组(1)变为
aij xi 1, j 1,2,..., n
i
(1) xi 1/ v i xi 0, i 1,2,..., m
20211//1122//99
18
第十八页，共22页。
根据定理11, 不等式组(1) 等价于以下线性规划问题:

(优选)矩阵对策的解法详解.

(优选)矩阵对策的解法详解.
矩阵对策的解法
3.1 公式法、图解法和方程组法
1. 2×2 对策的公式法
2×2 对策是指局中人Ⅰ的赢得矩阵为2×2 阶的, 即
A
a11 a21
a12
a22
如果 A 有鞍点, 则很快可求出各局中人的最优纯策略; 如果
A 没有鞍点,则可证明各局中人最优混合策略中的 xi* , yj* 均 大于零。于是, 由定理 6 可知, 为求最优混合策略可求下列
（5）确定经过点 P 的两相交直线，根据两相交直线列出对应方程 组，求出 y*.
（6）根据定理6的结论计算 x* 的值。
2020/7/19
10
例14
用图解法求解矩阵对策 G = { S1 , S2 ; A} , 其中
2 7
A
6
6
11 2
2020/7/19
11
2020/7/19
12
例 15
求解赢得矩阵A 的矩阵对策
A 4 1
8
3 5
4 5
2 7
2020/7/19
13
2020/7/19
14
3. 线性方程组方法
根据定理4 , 求解矩阵对策解( x*, y* ) 的问题等价于求解不 等式组，又根据定理5 和定理6 , 如果假设最优策略中的 xi* 和 yj* 均不为零, 即可将上述两个不等式组的求解问题转化 成求解下面两个方程组的问题:
(1) i
i
aij xi v, j 1,2,...,n
xi 1
(2)
j j
aij y j v,i 1,2,...,m yj 1
2020/7/19
15
3. 线性方程组方法
例16
求解矩阵对策——“齐王赛马”

运筹学--对策论

运筹学--对策论

max min E(X,Y)= min max E(X,Y)
X S1* Y S2*
Y S2* X S1*
则称这个公共值为对策G在混合意义 下的值，记为V*G，而达到V*G 的混 合局势（X*，Y*）称为对策G在混合 策略意义下的解，而X*和Y*分别称 为局中人I，II的最优混合策略。
定理14-2：矩阵对策 G = S1，S2；A
0 2 3 0
赢得矩阵为 A 2 0 3 0
0
3
0 4
0
3
4
0
14.2 矩阵对策的混合策略
定义:对给定的矩阵对策
G = Ⅰ，Ⅱ；S1,S2;A
其中 S1= 1, 2…m
S2= 1 , 2… n
A=(aij)mn
把纯策略集合对应的概率向量
X=(x1, x2 … xm) 其中 xi 0 xi=1 和 Y=(y1 , y2 … yn ) 其中 yj 0 yj=1
分别称为局中人I和局中人II的混合策略。
如果局中人I选取的策略为
X=(x1, x2 … xm) 局中人II选取的策略为
Y=(y1 , y2 … yn )，则期望值 E（X，Y）= xi aij yj=XAYT 称为局中人I期望赢得，而局势（X，Y） 称为“混合局势”，局中人I，II的混合 策略集合记为S1*， S2*。
S1= 1、 2…… m
同样，局中人II有n个策略：1、 2。。。 n ；用S2表示这些策略的集合： S2= 1、 2… n 局中人I的赢得矩阵是：
a11 a12 …… a1n a21 a22 …… a2n A= …… …… …… a m1 a m2 … a mn
局中人II的赢得矩阵是 -A 把一个对策记为G： G= S1，S2；A

《运筹学教程》胡云权 第五版 运筹学--6对策论--矩阵对策

《运筹学教程》胡云权 第五版 运筹学--6对策论--矩阵对策

13
矩阵对策的纯策略
4、矩阵对策的鞍点与解 多鞍点与无鞍点对策 例: 设有一矩阵对策如下，求它的解。
6 5 6 5
A 1 4 2 1 8 5 7 5
0 2 6
2
局势（α1, β2），（α1, β4），（α3, 均构成鞍点，此对策有多个解。
β2）（α3,
β4） 14
矩阵对策的纯策略
5、矩阵对策纯策略的性质
作业
P385 习题 • 12.2 • 12.3 • 12.4
16
矩阵对策的混合策略
1、混合策略
对于 G {S1, S2; A}
局中人Ⅰ有把握的赢得至少为 v1
max i
min j
aij
局中人Ⅱ有把握的支付至多为 v2
min max
j
i
aij
一般为 v1 v2 ，特别地当 v1 v2 时，则称对策 G 在
yS
* 2
xS1*
20
矩阵对策的混合策略
5、最优混合策略
定义 4：设 G* {S1*, S2*; E} 是矩阵对策 G {S1, S2; A}的混合扩充。
如果
maxmin E(x,
xS1* yS2*
y)
m in m ax E ( x,
yS2* xS1*
y)
，其值为 VG
，则称
VG 为
对策 G* 的值，相应的混合局势 (x*, y*) 称为在混合策略意义下的
44
22
23
对策的值（局中人
I
的赢得期望值）VG
9 2
。
矩阵对策的解法
24
图解法
仅适用于赢得矩阵为2×n或m×2阶的矩阵对策问题。

对策论第2,3节 矩阵对策的基本定理与解法

对策论第2,3节 矩阵对策的基本定理与解法

存在前提：
max min aij = min max aij= v
i
j
ji
ห้องสมุดไป่ตู้
又称（ 2 ，3 ）为对策G={s1,s2,A}的鞍点。值 V为G的值。
定义9-1：对给定的矩阵对策
G = S1，S2；A 若等式
max min aij= min max aij
i
j
j
i
成立，则称这个公共值为对策G的值，记 为VG，而达到的局势（ i， j ）称为对 策G在纯策略意义下的解，记为（ I*， j *）而I*和 j *分别称为局中人I和局中 人II的最优纯策略。
第2,3节 矩阵对策理论与求解方法
一、矩阵对策的最优纯策略
•在甲方赢得矩阵A=[aij]m*n中： aij代表甲方取策略i,乙方取策略j, 这一局势
下甲方的益损值，此时乙方的益损值为-aij（零 和性质）。 •在讨论各方采用的策略是必须注意一个前提就 是对方是理智的。这就是要从最有把握取得的 益损值情况考虑。
显然 ai2 a12 a1j ai2 a32 a3j 对 I=1,2,3 j=1,2,3 都成立： a12 = a32 =5 由定理5-1，对策值=5，对策的解：（ 1 , 2 ） 和（ 3 , 2 ）
例3：某单位采购员在秋天时要决定冬天取暖 用煤的采购量。已知在正常气温条件下需要用 煤15吨，在较暖和较冷气温条件下需要用煤10 吨和20吨。假定冬季的煤价随着天气寒冷的程 度而变化，在较暖、正常、较冷气温条件下每 吨煤价为100元、150元、200元。又秋季每 吨煤价为100元。在没有关于当年冬季气温情 况下，秋季应购多少吨煤，能使总支出最少？
E（X，Y）= xi aij yj=XAYT 称为局中人I期望赢得，而局势（X，Y）称为“混合 局势”，局中人I，II的混合策略集合记为S1*， S2*。

线性规划求解对策矩阵

线性规划求解对策矩阵

昆 明 理 工 大 学 理 学 院信息与计算科学专业 操作性实验报告年级： 09级 姓名： 陈龙飞 学号： 200911101111 指导教师： 范敏实验课程名称： 运筹学 开课实验室： 理216实验内容：1．实验/作业题目:用线性规划的方法求解矩阵对策3 3 2 98 2 4 32 6 6 56 4 4 22．实验/作业课时：2课时3．实验过程(包括实验环境、实验内容的描述、完成实验要求的知识或技能)：实验环境：多媒体计算机一台实验内容：（1）、对矩阵进行优超处理。

（2）、求解对策矩阵。

4．程序结构(程序中的函数调用关系图)优超算法：C++代码：#include <iostream>using namespace std;int main(){void youchao();//int youchao_a[4][4]={{3,3,2,9},{8,2,4,3},{2,6,6,5},{6,4,4,2}};int a[4][4]={{1,0,3,4},{-1,4,0,1},{2,2,2,3},{0,4,1,5}};cout<<"the array is:"<<endl;for (int i=0;i<4;i++){ for (int j=0;j<4;j++){cout<<a[i][j]<<" ";}if (j==4)cout<<'\n';}// int tt=1;for(int k=0;k<4;k++)/* for(int h=0;h<4;h++){if(a[k][h]<=a[k][h+tt])a[k][h]=NULL;}*/{if (a[0][k]<=a[1][k]&&a[0][k]<=a[2][k]&&a[0][k]<=a[3][k]){a[0][k]=NULL;}else if (a[1][k]<=a[0][k]&&a[1][k]<=a[2][k]&&a[1][k]<=a[3][k]) {a[1][k]=NULL;}else if (a[2][k]<=a[0][k]&&a[2][k]<=a[1][k]&&a[2][k]<=a[3][k]) {a[2][k]=NULL;}else if (a[3][k]<=a[0][k]&&a[3][k]<=a[1][k]&&a[3][k]<=a[2][k]) {a[3][k]=NULL;}}for (int e=0;e<4;e++){if (a[e][0]>=a[e][1]&&a[e][0]>=a[e][2]&&a[e][0]>=a[e][3]){a[e][0]=NULL;}else if (a[e][1]>=a[e][0]&&a[e][1]>=a[e][2]&&a[e][1]>=a[e][3]) {a[e][1]=NULL;}else if (a[e][2]>=a[e][0]&&a[e][2]>=a[e][1]&&a[e][2]>=a[e][3]) {a[e][2]=NULL;}else if(a[e][3]>=a[e][0]&&a[e][3]>=a[e][1]&&a[e][3]>=a[e][2]) {a[e][3]=NULL;}}cout<<endl<<endl<<"优超后的矩阵为"<<endl;for(int k2=0;k2<4;k2++){ for (int k1=0;k1<4;k1++){cout<<a[k2][k1]<<" ";}if(k1==4)cout<<endl;}return 0;}结果：当然c++里面的那个矩阵可以换成作业的里面这个，但是作业里面的那个不可以优超，所以效果不明显，我有重新找了一个矩阵，原来都是一样的Matlab代码：%请输入你要优超的矩阵L=[3 3 2 9;8 2 4 3;2 6 6 5;6 4 4 2];%调用main()函数mian(L)function E0=mian(a)global a;global Y;global k2;global T;global T1;global T2;Y=a;for k2 = 1:4% if(Y(1,k2)<=Y(2,k2)&Y(1,k2)<=Y(3,k2)&Y(1,k2)<=Y(4,k2))Yochao();%endendT=a;for k2 = 1:4if(T(2,k2)<=T(1,k2)&T(2,k2)<=T(3,k2)&T(2,k2)<=T(4,k2))Yochao1();endendT1=a;for k2 = 1:4if(T1(3,k2)<=T1(1,k2)&T1(3,k2)<=T1(2,k2)&T1(3,k2)<=T1(4,k2)) Yochao2();endendT2=a;for k2 = 1:4if(T2(4,k2)<=T2(1,k2)&Y(4,k2)<=T2(2,k2)&T2(4,k2)<=T2(3,k2)) Yochao3();endendfunction E=Yochao()global Y;global k2;if(Y(1,k2)<=Y(2,k2)&Y(1,k2)<=Y(3,k2)&Y(1,k2)<=Y(4,k2)) Y(1,:)=[];t=Y;if(t(1,k2)<t(2,k2)&t(1,k2)<t(3,k2))t(1,:)=[];else if(t(2,k2)<t(1,k2)&t(2,k2)<t(3,k2))t(2,:)=[];t1=t;if(t1(1,k2)<t1(2,k2))t1(1,:)=[];elset1(2,:)=[];endendendendt1function E=Yochao1()global k2;global T;T(2,:)=[];t=T;if(t(1,k2)<t(2,k2)&t(1,k2)<t(3,k2))t(1,:)=[];else if(t(2,k2)<t(1,k2)&t(2,k2)<t(3,k2))t(2,:)=[];t2=t;if(t2(1,k2)<t2(2,k2))t2(1,:)=[];elset2(2,:)=[];end。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

(1)i
i
aijxi v, j1,2,..n.,
xi 1
(2) j
j
aijyj v,i1,2,...m, yj 1
2020/7/26
15
3. 线性方程组方法
例16
求解矩阵对策——“齐王赛马”
3 1 1 1 1 1
1
3
1
1
1
1
1 1 3 1 1 1
A 1 1
1
3
1
1
1 1 1 1 3 1
2× n 对策的解题步骤：
（1）在直角坐标系中作直线 I：x = 0；II：x = 1；
（2）在直线I处按矩阵第2行的值标纵坐标，在直线II处按矩阵第1行 的值标纵坐标；其意义是指当局中人一采用其中一个纯策略时，局 中人二各策略相对应的赢得值；
（3）按列的方向将各对应纵坐标值连成直线；
（4）令 0 < x < 1，即局中人一采用混合策略，按最小最大原则，在 图中找出局中人一的最优策略；具体方法是：让 x 在(0, 1)内变动， 找出经过点(x, 0)的垂线与上述直线交点中纵坐标最小的点集(某些线 段)，然后再从中找出纵坐标最大的点 P 所对应的横坐标即为所求；
（5）确定经过点 P 的两相交直线，根据两相交直线列出对应方程 组，求出 x*.
（6）根据定理6的结论计算 y* 的值。
2020/7/26
6
例13
考虑矩阵对策 G = { S1 , S2 ; A}, 其中
2 3 11 A7 5 22020/7/267源自2020/7/268
如上图，由最小最大原则确定 B 点所对应的横坐标为所求， 故联立经过该点的两条直线方程：
23
j
aijyj 1,i 1,2,...,m
(2)yj 1/v
j
yj 0, j 1,2,...,n
与之等价的线性规划问题是:
max yj
j
(D) aijyj 1,i 1,2,...,m
j
yj 0, j 1,2,...,n
2020/7/26
21
例18
利用线性规划方法求解赢得矩阵为 A 的矩阵对策。
s.t.92
y1 y1
9y2 1 11 y3 1
y1, y2 , y3 0
2020/7/26
22
小结
在求解一个矩阵对策时, 应首先判断其是否具有鞍点, 当鞍 点不存在时, 利用优超原则和定理7、定理8 等提供的方法将 原对策的赢得矩阵尽量地化简, 然后再利用本节介绍的各种 方法去求解。
2020/7/26
（5）确定经过点 P 的两相交直线，根据两相交直线列出对应方程 组，求出 y*.
（6）根据定理6的结论计算 x* 的值。
2020/7/26
10
例14
用图解法求解矩阵对策 G = { S1 , S2 ; A} , 其中
2 7
A
6
6
11 2
2020/7/26
11
2020/7/26
12
例 15
等式组: a11x1 a21x2 v
(1)a12x1 a22x2 v x1 x2 1
a11y1 a12y2 v (2)a21y1 a22y2 v
y1 y2 1
2020/7/26
4
例12
求解矩阵对策 G = { S1 , S2 ; A} , 其中
1 3 A 4 2
2020/7/26
5
2. 2× n 或m×2 对策的图解法
（3）按行的方向将各对应横坐标值连成直线；
（4）令 0 < y < 1，即局中人二采用混合策略，按最大最小原则，在 图中找出局中人二的最优策略；具体方法是：让 y 在(0, 1)内变动， 找出经过点(y, 0)的垂线与上述直线交点中纵坐标最大的点集(某些线 段)，然后再从中找出纵坐标最小的点 P 所对应的横坐标即为所求；
2020/7/26
9
2. 2× n 或m×2 对策的图解法
m×2对策的解题步骤：
（1）在直角坐标系(横坐标为 y)中作直线 I：y = 0；II：y = 1；
（2）在直线I处按矩阵第2列的值标纵坐标，在直线II处按矩阵第1列 的值标纵坐标；其意义是指当局中人二采用其中一个纯策略时，局 中人一各策略相对应的赢得值；
(1)xi 1/v
i
xi 0,i 1,2,...,m
2020/7/26
19
根据定理11, 不等式组(1) 等价于以下线性规划问题:
minz xi
i
(P) aijxi 1, j 1,2,...,n
i
xi 0,i 1,2,...,m
2020/7/26
20
同理, 作变换 yj = yj / v, j = 1 , ⋯ , n,则不等式组(2)变为
第11 章 对策论基础
第3节 矩阵对策的解法
3.1 公式法、图解法和方程组法
1. 2×2 对策的公式法
2×2 对策是指局中人Ⅰ的赢得矩阵为2×2 阶的, 即
A
a11 a21
a12 a22
如果 A 有鞍点, 则很快可求出各局中人的最优纯策略; 如果
A 没有鞍点,则可证明各局中人最优混合策略中的 xi* , yj* 均 大于零。于是, 由定理 6 可知, 为求最优混合策略可求下列
3x5(1x)v 11x2(1x)v
x3,v49 11 11
即得 x1* = 3/11, x2* = 8/11，又因它们均大于零，故由定理6
又有：
72yy11**
3y2* 5y2*
11y3* v 2y3* v
y1* y2* y3* 1
又因为 2x1* + 7x2* = 62/11 > v, 所以又定理6的结果知 y1* = 0， 从而由上述方程可解出 y2* = 9/11, y3* = 2/11.
7 2 9
A 2
9
0
9 0 11
解：所求问题化为以下两个互为对偶的线性规划问题:
min x1 x2 x3
7 x1 2 x2 9 x3 1
s.t
.92
x1 x1
9 x2 11 x3
1 1
x1, x2 , x3 0
max Z y1 y2 y3
7 y1 2 y2 9 y3 1
i
j
xi 0,i 1,2,...,m
yj 0, j 1,2,...,n
其中
v m m a E ( x i , x y ) n m m iE ( n x a ,y )x
x S 1 * y S 2 *
y S 2 * x S 1 *
就是对策的值VG 。
2020/7/26
18
定理11 设矩阵对策G= { S1 , S2 ; A}的值为 VG , 则
V G m x S 1 * 1 m j n a E ( x i x ,j) n m y S 2 * m 1 i m iE ( n i, a y )x
矩阵对策的线性规划方法
作变换: xi = xi / v, i = 1 , ⋯ , m,则不等式组(1)变为
i
aijxi 1, j 1,2,...,n
由定理5知, 任一矩阵对策 G = { S1 , S2 ; A}的求解均 等价于一对互为对偶的线性规划问题, 而定理4 表明, 对策 G 的解 x* 和 y* 等价于下面两个不等式组的解。
i
aijxi v, j 1,2,...,n
aijyj v,i 1,2,...,m
j
(1)xi 1
(2)yj 1
1 1 1 1 1 3
2020/7/26
16
例17
某厂用三种不同的设备 1 、 2 、 3 加工三种不同的产品 1 、 2 、 3 , 已知三种设备分别加工三种产品时, 单位时间
内创造的价值由下表给出。
被加工产品
使用设备
1
2
3
1
3
-2
4
2
-1
4
2
3
2
2
6
2020/7/26
17
3. 2 线性规划方法
求解赢得矩阵A 的矩阵对策
A4 1
8
3 5
4 5
2 7
2020/7/26
13
2020/7/26
14
3. 线性方程组方法
根据定理4 , 求解矩阵对策解( x*, y* ) 的问题等价于求解不 等式组，又根据定理5 和定理6 , 如果假设最优策略中的 xi* 和 yj* 均不为零, 即可将上述两个不等式组的求解问题转化 成求解下面两个方程组的问题: