《精编》对策论的基本概念

《《精编》对策论的基本概念》由会员分享，可在线阅读，更多相关《《精编》对策论的基本概念（39页珍藏版）》请在金锄头文库上搜索。

1、1 第十五章对策论 1对策论的基本概念 2矩阵对策的最优纯策略 3矩阵对策的混合策略 4其他类型的对策论简介 2 第十五章对策论由 齐王赛马 引入 3 1对策论的基本概念 对策模型的三个基本要素 1 局中人 参与对抗的各方 2 策略集 局中人选择对付其它局中人的行动方案称为策略 某局中人的所有可能策略全体称为策略集 3 一局势对策的益损值 局中人各自使用一个对策就形成了一个局势 一个局势决定了各局中人的对策结果 量化 称为该局势对策的益损值 4 齐王赛马 齐王在各局势中的益损值表 单位 千金 1对策论的基本概念 5 其中 齐王的策略集 S1 1 2 3 4 5 6 田忌的策略集 S2 1 2

2、3 4 5 6 下面矩阵称齐王的赢得矩阵 3111 1113111 1A 1 13111 111311111 13111 1113 1对策论的基本概念 6 二人有限零和对策 又称矩阵对策 局中人为2 每个局中人的策略集的策略数目都是有限的 每一局势的对策均有确定的损益值 并且对同一局势的两个局中人的益损值之和为零 通常将矩阵对策记为 G S1 S2 A S1 甲的策略集 S2 乙的策略集 A 甲的赢得矩阵 齐王赛马 是一个矩阵策略 1对策论的基本概念 7 在甲方的赢得矩阵中 A aij m ni行代表甲方策略i 1 2 m j行代表乙方策略j 1 2 n aij代表甲方取策略i 乙方取策略j

3、这一局势下甲方的益损值 此时乙方的益损值为 aij 零和性质 在考虑各方采用的策略时 必须注意一个前提 就是双方都是理智的 即双方都是从各自可能出现的最不利的情形选择一种最为有利的情况作为决策的依据 2矩阵对策的最优纯策略 2矩阵对策的最优纯策略 8 例 甲乙乒乓球队进行团体对抗赛 每队由三名球员组成 双方都可排成三种不同的阵容 每一种阵容可以看作一种策略 双方各选一种策略参赛 比赛共赛三局 规定每局胜者得1分 输者得 1分 可知三赛三胜得3分 三赛二胜得1分 三赛一胜得 1分 三赛三负得 3分 甲队的策略集为S1 1 2 3 乙队的策略集为S2 1 2 3 根据以往比赛的资料 有甲队的赢得矩

4、阵为A 如下所示 请问这次比赛各队采用哪种阵容上场最为稳妥 2矩阵对策的最优纯策略 9 矩阵A中每行的最小元素分别为1 3 1 在这些最少赢得中最好的结果是1 故甲队会采取策略 1 无论对手采取何策略 甲队至少得1分 对于乙队 1 2 3 可能带来的最少赢得 即A中每列的最大元素 分别为3 1 3 乙队会采取 2策略 确保甲队不会超过1分 1和 2分别称为局中人甲队 乙队的最优策略 由于双方必然选择这一种策略 所以 这种策略又称为最优纯策略 这种最优纯策略只有当赢得矩阵A aij 中等式成立时 双方才有最优纯策略 并把 1 2 称为对策G在纯策略下的解 又称 1 2 为对策G的鞍点 把其值V称

5、之为对策G S1 S2 A 的值 2矩阵对策的最优纯策略 10 例某单位采购员在秋天决定冬季取暖用煤的储量问题 已知在正常的冬季气温条件下要消耗15吨煤 在较暖和较冷的天气下要消耗10吨和20吨 假定冬天的煤价随天气寒冷程度而有所变化 在较暖和 正常 较冷的气候条件下每吨煤价分别为10元 15元 20元 又设冬季时煤炭价格为每吨10元 在没有关于当年冬季准确的气象预报的条件下 秋天储煤多少吨能使得单位的支出最少 解 局中人I为采购员 局中人II为大自然 采购员有三个策略 买10吨 15吨 20吨 分别记为 1 2 3 大自然也有三个策略 暖 正常 冷 分别记为 1 2 3 2矩阵对策的最优纯策

6、略 11 赢得矩阵如下 在此表上计算 有得故 3 3 为对策G的解 VG 200 2矩阵对策的最优纯策略 12 设矩阵对策G S1 S2 A 当maxminaij minmaxaijijji时 不存在最优纯策略 例 设一个赢得矩阵如下 min595A max6策略 2866imax89min8策略 1j 3矩阵对策的混合策略 13 当甲取策略 2 乙取策略 1时 甲实际赢得8比预期的多2 乙当然不满意 考虑到甲可能取策略 2这一点 乙采取策略 2 若甲也分析到乙可能采取策略 2这一点 取策略 1 则赢得更多为9 此时 对两个局中人甲 乙来说 没有一个双方均可接受的平衡局势 其主要原因是甲和乙没

7、有执行上述原则的共同基础 即maxminaij minmaxaij ijji一个自然的想法 对甲 乙 给出一个选取不同策略的概率分布 以使甲 乙 在各种情况下的平均赢得 损失 最多 最少 即混合策略 3矩阵对策的混合策略 14 求解混合策略的问题有图解法 迭代法 线性方程法和线性规划法等 我们这里只介绍线性规划法 其他方法略 例 设甲使用策略 1的概率为X1 使用策略 2的概率为X2 并设在最坏的情况下 甲赢得的平均值为V 未知 59A STEP1861 X1 X2 1X1 X2 0 3矩阵对策的混合策略 15 2 无论乙取何策略 甲的平均赢得应不少于V 对乙取 1 5X1 8X2 V对乙取

8、2 9X1 6X2 V注意V 0 因为A各元素为正 STEP2作变换 X1 X1 V X2 X2 V得到上述关系式变为 X1 X2 1 V V愈大愈好 待定5X1 8X2 19X1 6X2 1X1 X2 0 3矩阵对策的混合策略 16 建立线性模型 minX1 X2s t 5X1 8X2 1X1 1 219X1 6X2 1X2 2 21X1 X2 01 V X1 X2 1 7所以 V 7返回原问题 X1 X1V 1 3X2 X2V 2 3于是甲的最优混合策略为 以1 3的概率选 1 以2 3的概率选 2 最优值V 7 3矩阵对策的混合策略 17 同样可求乙的最优混合策略 设乙使用策略 1的概率

9、为Y1 Y1 Y2 1设乙使用策略 2的概率为Y2 Y1 Y2 0设在最坏的情况下 甲赢得的平均值为V 这也是乙损失的平均值 越小越好 作变换 Y1 Y1 V Y2 Y2 V建立线性模型 maxY1 Y2s t 5Y1 9Y2 1Y1 1 148Y1 6Y2 1Y2 1 14Y1 Y2 01 V Y1 Y2 1 7所以 V 7 3矩阵对策的混合策略 18 返回原问题 Y1 Y1V 1 2Y2 Y2V 1 2于是乙的最优混合策略为 以 的概率选 1 以 的概率选 2 最优值V 7 当赢得矩阵中有非正元素时 V 0的条件不一定成立 可以作下列变换 选一正数k 令矩阵中每一元素加上k得到新的正矩阵A

10、 其对应的矩阵对策G S1 S2 A 与G S1 S2 A 解相同 但VG VG k 3矩阵对策的混合策略 19 例 求解 齐王赛马 问题 已知齐王的赢得矩阵A求得故不存在纯策略问题下的解 可求其混合策略 A中有负元素 可以取k 2 在A的每个元素上加2得到A 如下 3矩阵对策的混合策略 20 建立对G S1 S2 A 中求甲方最佳策略的线性规划如下 Minx1 x2 x3 x4 x5 x6约束条件 5x1 3x2 3x3 x4 3x5 3x6 13x1 5x2 x3 3x4 3x5 3x6 13x1 3x2 5x3 3x4 3x5 x6 13x1 3x2 3x3 5x4 x5 3x6 1x1

11、 3x2 3x3 3x4 5x5 3x6 13x1 x2 3x3 3x4 3x5 5x6 1xi 0 i 1 2 6可解得解为 x1 x4 x5 0 x2 x3 x6 0 111 v 3 x1 x4 x5 0 x2 x3 x6 1 3 即X 0 1 3 1 3 0 0 1 3 T 所以甲的最优策略为作出策略 2 3 6的概率都为0 333 而作出 1 4 5的概率为0 此时V G V 3 3矩阵对策的混合策略 21 同样可以建立对策G S1 S2 A 中求乙方最佳策略的线性规划如下 Miny1 y2 y3 y4 y5 y6约束条件 5y1 3y2 3y3 3y4 y5 3y6 13y1 5y2

12、 3y3 3y4 3y5 y6 13y1 y2 5y3 3y4 3y5 3y6 1y1 3y2 3y3 5y4 3y5 3y6 13y1 3y2 3y3 y4 5y5 3y6 13y1 3y2 y3 3y4 3y5 5y6 1yi 0 i 1 2 6可解得解为 y1 y4 y5 0 111 y2 y3 y6 0 v 3 y1 y4 y5 1 3 y2 y3 y6 0 即Y 1 3 0 0 1 3 1 3 0 T 所以田忌的最优混合策略为作出策略 1 4 5的概率都为1 3 而作出 2 3 6的概率为0 此时VG VG k 1 3矩阵对策的混合策略 22 齐王赛马问题的对策最优解可简记为X 0

13、1 3 1 3 0 0 1 3 T Y 1 3 0 0 1 3 1 3 0 T 对策值VG 1 例两个局中人进行对策 规则是两人互相独立的各自从1 2 3这三个数字中任意选写一个数字 如果两人所写的数字之和为偶数 则局中人乙支付给局中人甲以数量为此和数的报酬 如果两人所写数字之和为奇数 则局中人甲付给局中人乙以数量为此和数的报酬 试求出其最优策略 解 首先计算局中人甲的赢得矩阵如下表 4 56 34 5 2 34 1 出1 2 出2 3 出3 3 出3 2 出2 1 出1 甲的赢得甲的策略 3矩阵对策的混合策略 乙的策略 23 即甲的赢得矩阵为A 可知无纯策略意义的解 下面求其在混合策略下的解

14、 A的各元素都加上6 得到建立线性规划模型如下 Minx1 x2 x3Maxy1 y2 y3S T 8x1 3x2 10 x3 18y1 3y2 10y3 13x1 10 x2 x3 13y1 10y2 y3 110 x1 x2 12x3 110y1 y2 12y3 1x1 x2 x3 0y1 y2 y3 0 3矩阵对策的混合策略 24 得到x1 0 25 x2 0 50 x3 0 25 y1 0 25 y2 0 50 y3 0 25 即此对策的解为X 0 25 0 50 0 25 T Y 0 25 0 50 0 25 T VG VG k 0 3矩阵对策的混合策略 25 例4甲乙两个企业生产同

15、一种电子产品 甲企业可以采取的策略措施有 1 降低产品价格 2 提高产品质量 3 推出新产品 乙企业考虑采取的策略措施有 1 增加广告费用 2 增设维修网点 加强售后服务 3 改进产品性能 由于甲乙两个企业财力有限 都只能采取一个措施 假定这两个企业所占有的市场总份额一定 由于各自采取的措施不同 通过预测今后两个企业的市场占有份额变动情况如下表 试求出这两个企业各自的最优策略 3 58 6510 108 12 1 措施1 2 措施2 3 措施3 3 措施3 2 措施2 1 措施1 3矩阵对策的混合策略 甲的赢得甲的策略 乙的策略 26 解 易知此对策无纯策略意义下的解 把A的每一个元素加上12

16、 得到A 建立线性规划模型如下 Minx1 x2 x3Maxy1 y2 y3S T 22x1 20 x2 122y1 6y2 15y3 16x1 17x2 22x3 120y1 17y2 7y3 115x1 7x2 20 x3 122y2 20y3 1x1 x2 x3 0y1 y2 y3 0得到 x1 0 027 x2 0 020 x3 0 023 y1 0 0225 y2 0 0225 y3 0 025 V 14 29 x1 0 3858 x2 0 2858 x3 0 3286 y1 0 3215 y2 0 3215 y3 0 3572 即此对策的解为X 0 3858 0 2858 0 3286 T Y 0 3215 0 3215 0 3572 T VG VG k 2 29 3矩阵对策的混合策略 27 优超原则 假设矩阵对策G S1 S2 A 甲方赢得矩阵A aij m n若存在两行 列 s行 列 的各元素均优于t行 列 的元素 即asj atjj 1 2 n ais aiti 1 2 m 称甲方策略 s优超于 t s优超于 t 优超原则 当局中人甲方的策略 t被其它策略所优超时 可