第节矩阵对策的解法

1、第11 章 对策论基础 第3节 矩阵对策的解法2022-7-12定理定理4 设 x* S1* , y* S2* , 则( x* , y* ) 为 G 的解的充要条件是: 存在数 v, 使得 x* 和 y* 分别是不等式组 (1) 和 (2) 的解, 且 v = VG 。mixxnjvxaiiiiiij,.,2 , 1, 01,.,2 , 1,) 1 (njyymivyajjjjjij,.,2 , 1, 01,.,2 , 1,)2(2022-7-13定理定理6 设( x* , y* )是矩阵对策 G 的解, v = VG , 则(1) 若 xi* 0 , 则(2) 若 yj* 0 , 则(3)

2、若 则 xi* = 0(4) 若 则 yj* = 0.vyajjij*vxaiiij*vyajjij*vxaiiij*2022-7-143.1 公式法、图解法和方程组法1. 22 对策的公式法%22 对策是指局中人的赢得矩阵为22 阶的, 即%如果 A 有鞍点, 则很快可求出各局中人的最优纯策略; 如果 A 没有鞍点,则可证明各局中人最优混合策略中的 xi* , yj* 均大于零。于是, 由定理 6 可知, 为求最优混合策略可求下列等式组:22211211aaaaA1) 1 (21222112221111xxvxaxavxaxa1)2(21222121212111yyvyayavyaya202

3、2-7-15例12 %求解矩阵对策 G = S1 , S2 ; A , 其中2431A2022-7-162. 2 n 或m2 对策的图解法% 2 n 对策的解题步骤：（1）在直角坐标系中作直线 I：x = 0；II：x = 1；（2）在直线I处按矩阵第2行的值标纵坐标，在直线II处按矩阵第1行的值标纵坐标；其意义是指当局中人一采用其中一个纯策略时，局中人二各策略相对应的赢得值；（3）按列的方向将各对应纵坐标值连成直线；（4）令 0 x v, 所以又定理6的结果知 y1* = 0，从而由上述方程可解出 y2* = 9/11, y3* = 2/11.vxxvxx)1 (211)1 (531149,

4、113vx12571132*3*2*1*3*2*1*3*2*1yyyvyyyvyyy2022-7-1102. 2 n 或m2 对策的图解法% m2对策的解题步骤：（1）在直角坐标系(横坐标为 y)中作直线 I：y = 0；II：y = 1；（2）在直线I处按矩阵第2列的值标纵坐标，在直线II处按矩阵第1列的值标纵坐标；其意义是指当局中人二采用其中一个纯策略时，局中人一各策略相对应的赢得值；（3）按行的方向将各对应横坐标值连成直线；（4）令 0 y 1，即局中人二采用混合策略，按最大最小原则，在图中找出局中人二的最优策略；具体方法是：让 y 在(0, 1)内变动，找出经过点(y, 0)的垂线与上

5、述直线交点中纵坐标最大的点集(某些线段)，然后再从中找出纵坐标最小的点 P 所对应的横坐标即为所求；（5）确定经过点 P 的两相交直线，根据两相交直线列出对应方程组，求出 y*.（6）根据定理6的结论计算 x* 的值。2022-7-111例14 %用图解法求解矩阵对策 G = S1 , S2 ; A , 其中2116672A2022-7-1122022-7-113例 15 %求解赢得矩阵A 的矩阵对策755124384A2022-7-1142022-7-1153. 线性方程组方法%根据定理4 , 求解矩阵对策解( x*, y* ) 的问题等价于求解不等式组，又根据定理5 和定理6 , 如果假设

6、最优策略中的 xi* 和 yj* 均不为零, 即可将上述两个不等式组的求解问题转化成求解下面两个方程组的问题:1,.,2 , 1,) 1 (iiiiijxnjvxa1,.,2 , 1,)2(jjjjijymivya2022-7-1163. 线性方程组方法例16% 求解矩阵对策“齐王赛马”311111131111113111111311111131111113A2022-7-117例17 %某厂用三种不同的设备 1 、 2 、 3 加工三种不同的产品1 、 2 、 3 , 已知三种设备分别加工三种产品时, 单位时间内创造的价值由下表给出。使用设备被加工产品12313-242-1423226202

7、2-7-1183. 2 线性规划方法由定理5知, 任一矩阵对策 G = S1 , S2 ; A的求解均等价于一对互为对偶的线性规划问题, 而定理4 表明, 对策 G 的解 x* 和 y* 等价于下面两个不等式组的解。%其中%就是对策的值VG 。mixxnjvxaiiiiiij,.,2 , 1, 01,.,2 , 1,) 1 (njyymivyajjjjjij,.,2 , 1, 01,.,2 , 1,)2(),(maxmin),(minmax*1221yxEyxEvSxSySySx2022-7-119定理定理11 设矩阵对策G= S1 , S2 ; A的值为 VG , 则矩阵对策的线性规划方法%

8、作变换: xi = xi / v, i = 1 , , m,则不等式组(1)变为),(maxmin),(minmax1*1*21yiEjxEVmiSynjSxGmixvxnjxaiiiiiij,.,2 , 1, 0/1,.,2 , 1, 1) 1 (2022-7-120%根据定理11, 不等式组(1) 等价于以下线性规划问题:mixnjxaxzPiiiijii,.,2 , 1, 0,.,2 , 1, 1min)(2022-7-121%同理, 作变换 yj = yj / v, j = 1 , , n,则不等式组(2)变为% 与之等价的线性规划问题是:njyvymiyajjjjjij,.,2 , 1, 0/1,.,2 , 1, 1)2(njymiyayDjjjijjj,.,2 , 1, 0,.,2 , 1, 1max)(2022-7-122例18 %利用线性规划方法求解赢得矩阵为 A 的矩阵对策。解：所求问题化为以下两个互为对偶的线性规划问题:1109092927A0,11191921927. .min3213121321321xxxxxxxxxxtsxxx0,11191921927.