运筹说 第134期 | 矩阵对策的解法

上一期我们了解了矩阵对策的基本理论，包含矩阵对策的纯策略、矩阵对策的混合策略和矩阵对策的基本定理。

接下来小编将为大家介绍矩阵对策的解法，包括图解法、方程组法和线性规划法三种经典方法。

01 图解法

本节首先介绍矩阵对策的图解法，在学习矩阵对策的基本理论时，我们掌握了如何构造线性规划问题来解决矩阵对策的混合策略问题，相应地，可以将求解线性规划问题的图解法迁移到矩阵对策的求解之中。

图解法是通过图示局中人的期望收益，寻找期望收益的最小或最大，最后求出纳什均衡的方法，其思想是最大最小定理6的图形应用。这种方法不仅为赢得矩阵为2×n 或m×2阶的对策问题提供了一个简单直观的解法，而且通过这种方法可以使我们从几何上理解对策论的思想，总结如下：

图解法的适用范围为

（1）赢得矩阵为2×n 或m×2阶的对策问题

（2）混合策略（至少有一人策略只为2个策略）

图解法的决策原则为在最不利的情形下选择最有利的策略。

局中人1的最有利策略表示为：

局中人2的最有利策略表示为：

定理六

设(x*,y*)是矩阵对策G的解，v=VG则根据互补松弛性，有

（1）xi*＞0，则

（2）若yj*＞0，则

（3）若，则xi*=0

（4）若，则yj*=0

结合第132期学过的定理6，通过两个例题来详细说明如何使用图解法进行求解。

例题展示

例1：用图解法求解矩阵对策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点的纵坐标即为对策的值。为求x和对策的值VG，可联立过B点的两条由β2和β3确定的直线的方程：     

解得x=3/11,VG=49/11。所以，局中人I的最优策略为x*=(3/11,8/11)T。从图上还可看出，局中人II的最优混合策略只由β2和β3组成。

事实上，若设y*=（y1*,y2*,y3*）T为局中人II的最优混合策略，则由

（注：此处“1” 并不是一个数字，而是局中人 II 所有可选策略的集合的代表。 它的作用是确保局中人 II 在任何策略组合下，局中人 I 在最优策略下的收益都不会被破坏。 这符合极小极大原理，确保了均衡点的收益计算是对所有可能策略均成立的）

根据定理6，必有y1*=0。又因x1*=3/11>0，x2*=8/11>0，再根据定理6，可由

求得y2*=9/11，y3*=2/11。所以，局中人II的最优混合策略为y*=[0,9/11,2/11]T。

例题展示

例2：用图解法求解矩阵对策G={S1,S2;A}，其中

解：设局中人II的混合策略为(y,1-y)T，y∈[0,1]。由下图可知，对任一y∈[0,1]，直线α1,α2,α3的纵坐标是局中人II采取混合策略(y,1-y)T时的支付。

根据从最不利当中选择最有利的原则，局中人II的最优策略就是确定y，使得三个纵坐标中的最大者尽可能的小，从图上看，就是要选择y，使得A1≤y≤A2，这时，对策的值为6。由方程组

 解A1=1/5，A2=4/9，故局中人II的最优混合策略是y*=(y,1-y)T，其中1/5≤y≤4/9，局中人I的最优策略显然只能是(0,1,0)T，即取纯策略α2。

02 方程组法

方程组法主要是通过构造并化简求解的方法来解决矩阵对策问题，由定理4（见132期）可知，求矩阵对策解（x*，y*）的问题等价于求解如下两个不等式组1和不等式组2；

不等式组1：

 不等式组2：

又由定理5（见132期）和定理6可知，如果最优策略中的xi*和yj*均不为零，则可将上述两不等式组的求解问题转化为下面的两个方程组的求解问题。

方程组1：

方程组2：

（1）如果上述方程组1和方程组2存在非负解x*和y*，便求得了对策的一个解；

（2）如果这两个方程不存在非负解，可视具体情况，将上式中的某些等式改成不等式，继续尝试求解，直至求得对策的解。（注意，这种情况可用线性规划法进行求解）。

例题展示

例3：A、B玩游戏：有3张牌，分别为高、中、低，由A任抽一张，由B猜。

B只能猜高或低，若所抽牌恰好是高或低，B猜对，A输3元，否则B输2元。

若A所抽牌为中，则当B猜低时，B赢2元，猜高时，由A再从剩下的两张牌中任抽一张让B猜，若B猜对时，B赢1元，猜错时B输3元。

将此问题归结成对策问题，列出A的赢得矩阵，并求出各自的最优解和对策值。

解：A有4个策略：①抽高；②抽中，需再次抽牌时抽高；③抽中，需再次抽牌时抽低；④抽低。

B有3个策略：①猜高，需再次猜时猜高；②猜高，再次猜时猜低；③猜低。

列出对A的赢得矩阵如下表所示   

事先假定均不为零，列出方程

解得x*=(1/2,0,0,1/2)，y*=(1/4,1/4,1/2)，v=-1/2

方程组法由于事先假定xi*和yj*均不为零，故当最优策略的某些分量实际为零时，方程组1和方程组2可能无解，因此，这种方法在实际应用中有一定的局限性。但对于2×2的矩阵，当局中人I的赢得矩阵

不存在鞍点时，容易证明：各局中人的最优混合策略中的xi*和yj*均大于零。于是，由定理6，得到下述方程组

一定有严格的非负解（也就是两个局中人的最优策略）：

通过上述推理，我们可以得到求解矩阵对策的公式，针对一些2×2的矩阵对策问题可以直接套用公式进行快速求解。

面对矩阵对策题目，首先要判断是否有纯策略意义下的最优解，其次是要根据优超原则去化简。（优超原则是指在矩阵对策中，若某策略在所有情况下收益都不低于另一策略，即矩阵A中第i 行元素均不小于第j 行对应元素，则称局中人II的纯策略αi超优于αj，则可删除被优超的策略以简化分析。）

例题展示

例4：用图解法求解矩阵对策G={S1,S2;A}，其中

解：首先可利用矩阵对策的优超原则对矩阵A进行化简。为此，应用优超原则依次简化得到矩阵A1，A2和A3：     

易知A3没有鞍点，由定理6，可以求出两个方程组

非负解为：

于是，以矩阵A为赢得矩阵的对策的一个解就是

03 线性规划法

上面学习了两个特殊的求解方法，下面我们一起来学习一个具有一般性的求解矩阵对策的方法——线性规划法，用这种方法可以求解任一矩阵对策。

由定理5可知，求解矩阵对策可等价地转化为求解互为对偶的线性规划问题（P）和（D），（P）和（D）表示如下：

又由定理7可以假设，此处我们做归一化处理，将（P）和（D）进一步简化，将原问题中的策略变量xi 和yj 缩放到与对策值w和v无关的比例，使新变量 xi′ 和yj' 满足线性规划的标准形式，变为新的问题 (P′)和 (D′)。

根据上式，对原问题（P）和（D）约束两边同时除以w和v（w>0，v>0），则问题（P）和（D）等价于线性规划问题（P'）和（D'）：

（P'）和（D'）是互为对偶的线性规划，这样就可以利用单纯形法或对偶单纯形方法求解，由最优混合策略下w=v=VG的结论，得原对策问题的值为

对策的解为

求解步骤可总结如下：

（1）确定问题无鞍点，是混合策略；

（2）为了使，基于定理7构造，A+T→A'（≥0)；

（3）由A'构造（P'）和（D'）；

（4）求解（D'），得，由互补松弛定理求解（P'），得

（5）求原对策问题的解和值。

下面通过例5来进一步实践线性规划求解方法。

例题展示

例5：利用线性规划方法求解下述矩阵对策，其赢得矩阵为

如此，求解问题可化成两个互为对偶的线性规划问题：

将（D）转换为如下标准形式：

我们可以使用单纯性表法来求解这个线性规划问题，最终单纯形表如下表所示：

最后得到上述线性规划的解为

 则最优对策的值为

最优对策的解为

以上就是矩阵对策的解法的全部内容了，通过本期学习，大家是否学会了这三种矩阵对策的经典求解方法呢？下一期小编将带大家学习其他类型的对策，敬请关注！