第十四章-对策论.ppt

第十四章对策论 对策论概论对策论 TheGameTheory 也称竞赛论或博弈论 是研究具有竞争 对抗 利益分配等方面的数量化方法 并提供寻求最优策略的途径 20世纪40年代形成并发展 1944年以来 对策论在投资分析 价格制定 费用分摊 财政转移支付 投标与拍卖 对抗与追踪 国际冲突 双边贸易谈判 劳资关系以及动物行为进化等领域得到广泛应用 14 1矩阵对策的基本概念案例 俾斯麦海的海空对抗1943年2月 第二次世界大战中的日本 在太平洋战区已经处于劣势 为扭转局势 日本统帅山本五十六大将统率下的一支舰队策划了一次军事行动 由集结地 南太平洋的新不列颠群岛的蜡包尔出发 穿过俾斯麦海 开往新几内亚的莱城 支援困守在那里的日军 当盟军获悉此情报后 盟军统帅麦克阿梭命令太平洋战区空军司令肯尼将军组织空中打击 日本统帅山本五十六大将心里很明白 在日本舰队穿过俾斯麦海的三天航行中 不可能躲开盟军的空中打击 他要策划的是尽可能减少损失 日美双方的指挥官及参谋人员都进行了冷静的思考与全面的谋划 自然条件对于双方都是已知的 基本情况如下 从蜡包尔出发开往莱城的海上航线有南北两条 通过时间均为3天 气象预报表明 未来3天中 北线阴雨 能见度差 而南线天气晴好 能见度好 肯尼将军的轰炸机布置在南线的机场 侦察机全天候进行侦察 但有一定的搜索半径 经测算 双方均可得到如下估计 局势1 盟军的侦察机重点搜索北线 日本舰队也恰好走北线 由于气候恶劣 能见度差 盟军只能实施两天的轰炸 局势2 盟军的侦察机重点搜索北线 日本舰队走南线 由于发现晚 尽管盟军的轰炸机群在南线 但有效轰炸也只有两天 局势3 盟军的侦察机重点搜索南线 而日本舰队走北线 由于发现晚 盟军的轰炸机群在南线 以及北线气候恶劣 故有效轰炸只有一天 局势4 盟军的侦察机重点搜索南线 日本舰队也恰好走南线 此时日本舰队迅速被发现 盟军的轰炸机群所需航程很短 加上天气晴好 有效轰炸时间三天 这场海空遭遇与对抗一定会发生 双方的统帅如何决策呢 历史的实际情况是 局势1成为现实 肯尼将军命令盟军的侦察机重点搜索北线 而山本五十六大将命令日本舰队取道北线航行 由于气候恶劣 能见度差 盟军飞机在一天后发现了日本舰队 基地在南线的盟军轰炸机群远程航行 实施了两天的有效轰炸 重创了日本舰队 但未能全歼 对策的三要素 局中人 有权决定自己行为方案的对局参加者称为局中人 案例中 美日双方的决策者为局中人 当对局中局中人只有两人时 称为二人对策 策略 对局中一个实际可行的方案称为一个策略 案例中 美日双方各有二个策略 赢得矩阵 支付 当每个局中人在确定了所采取的策略后 他们就会获得相应的收益或损失 此收益或损失的值称为赢得 支付 赢得与策略之间的对应关系称为赢得 支付 函数 案例中 肯尼将军与山本五十六大将的赢得 支付 函数都可以用矩阵A B表示 日军 北线南线 盟军 北线22 A南线13 盟军 北线南线 日军 北线 2 2 B南线 1 3 在本例中的每一个对局 双方的赢得的代数之和为零 这样的对策称为 有限零和二人对策 设两个局中人为I II 局中人I有m个策略 1 2 m 用S1表示这些策略的集合 S1 1 2 m 同样 局中人II有n个策略 1 2 n 用S2表示这些策略的集合 S2 1 2 n局中人I的赢得矩阵是 a11a12 a1na21a22 a2nA am1am2 amn 局中人II的赢得矩阵是 A把一个对策记为G G S1 S2 A北线 1南线 2 盟军 北线 122 A南线 213 在矩阵中 盟军的最大赢得是3 而要得到3 必须选择策略 2 而日军的目的是使盟军的赢得尽量的小 必须选择策略 1 使盟军的赢得只有1 在局中人I设法使自己的赢得尽可能大的同时 局中人II也设法使局中人I的赢得尽可能小 所以局中人I应首先考虑用 所能赢得的最小 然后在这些最小赢得中选择最大 局中人I可以保证赢得maxminaijij同样 局中人II可以保证局中人I的赢得不超过minmaxaijji 案例中局中人I 盟军 应当选择 北线 策略 1 这样能保证赢得2 局中人II 日军 应当选择 北线 策略 1使盟军赢得不超过2 实际上 在 1 1 局势下 有maxminaij minmaxaijijji上式蕴涵的思想是朴素自然的 可以概括为 从最坏处着想 去争取最好的结果 定义14 1 对给定的矩阵对策G S1 S2 A若等式maxminaij minmaxaijijji成立 则称这个公共值为对策G的值 记为VG 而达到的局势 i j 称为对策G在纯策略意义下的解 记为 I j 而 I 和 j 分别称为局中人I和局中人II的最优纯策略 定理14 1 矩阵对策G S1 S2 A在纯策略意义下有解的充分必要条件是 存在一个局势 i j 使得对一切i 1 2 m j 1 2 n均有aij ai j ai j 定理14 1表明矩阵对策G S1 S2 A有解的充分必要条件是在A中存在元素ai j 是其所在行中最小的同时又是其所在列中最大的 这时ai j 即是对策值 因此ai j 也称为 鞍点 而 i j 为对策的解 X Y 马鞍面z f x y 鞍点 Z Y Z 在X 0的平面上鞍点是z f 0 y 的极大值点 z f 0 y X Z 在Y 0的平面上鞍点是z f x 0 的极小值点 z f x 0 例14 3 对给定的矩阵对策G S1 S2 AS1 1 2 3 4S2 1 2 3 4min65655 maxA 142 1 185755 max02620max85 75 minmin显然ai2 a12 a1jai2 a32 a3j对i 1 2 3 4j 1 2 3 4都成立 a12 a32 5由定理5 1 对策值 5 对策的解 1 2 3 2 1 4 3 4 例14 4 某单位采购员在秋天时要决定冬天取暖用煤的采购量 已知在正常气温条件下需要用煤15吨 在较暖和较冷气温条件下需要用煤10吨和20吨 假定冬季的煤价随着天气寒冷的程度而变化 在较暖 正常 较冷气温条件下每吨煤价为100元 150元 200元 又秋季每吨煤价为100元 在没有关于当年冬季气温情况下 秋季应购多少吨煤 能使总支出最少 解 局中人I 采购员 有三个策略 策略 1 10吨 策略 2 15吨 策略 3 20吨 局中人II 环境 策略 1较暖 策略 2正常 策略 3较冷现把该单位冬天取暖用煤全部费用 秋季购煤费用与冬天不够时再补购煤费用 作为采购员的赢得矩阵 1较暖 2正常 3较冷 1 10 1000 1750 3000 2 15 1500 1500 2500 3 20 2000 2000 2000maxminaij minmaxaij a33 2000Ijji该最优策略为 3 3 即秋季购煤20吨 已知在正常气温条件下需要用煤15吨 在较暖和较冷气温条件下需要用煤10吨和20吨 在较暖 正常 较冷气温条件下每吨煤价为100元 150元 200元 又秋季每吨煤价为100元 练习 二指莫拉问题 甲乙两人游戏 每人出一个或两个手指头 同时又把猜测对方所出的手指数叫出来 若只有一个人猜测正确 则他所赢得数为二人所出手指之和 否则 重新开始 写出该对策各局中人的策略集合及甲的赢得矩阵 并回答局中人是否存在某种出法比其他出法更为有利 解 表示自己出个手指 猜测对方出个手指 练习 二指莫拉问题 甲乙两人游戏 每人出一个或两个手指头 同时又把猜测对方所出的手指数叫出来 若只有一个人猜测正确 则他所赢得数为二人所出手指之和 否则 重新开始 写出该对策各局中人的策略集合及甲的赢得矩阵 并回答局中人是否存在某种出法比其他出法更为有利 赢得矩阵为 14 2矩阵对策的混合策略定义 对给定的矩阵对策G S1 S2 A其中S1 1 2 mS2 1 2 nA 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 xiaijyj XAYT称为局中人I期望赢得 而局势 X Y 称为 混合局势 局中人I II的混合策略集合记为S1 S2 定义14 3 对给定的矩阵对策G S1 S2 A则对策G S1 S2 E称为对策G混合扩充 纯策略是混合策略的一个特例 例如 局中人 的纯策略等价于混合策略其中 定义14 4 设G S1 S2 E是对策G混合扩充 如果有maxminE X Y minmaxE 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在混合策略意义下有解的充分必要条件是 存在混合局势 X Y 使得对一切X S1 Y S2 均有E X Y E X Y E X Y 定理14 3 对给定的矩阵对策G S1 S2 A设X S1 Y S2 则混合局势 X Y 是G的解且V VG 的充分必要条件是 对一切i j均有E i Y V E X j 证明 必要性 因为纯策略是混合策略的特例 故成立充分性 当局中人取纯策略时 当局中人取纯策略时 则已知E i Y V E X j 所以故定理3把无限个不等式的证明转化为对有限个 mn 个不等式的证明问题 定理14 4 设 则为的解的充要条件 存在数使得分别是不等式组 和 的解 证明 由定理3 X Y 是G的解且V VG 的充分必要条件是 对一切i j均有E i Y V E X j 即 和 成立 定理14 5 任意一个给定的矩阵对策在混合策略意义下一定有解 矩阵对策的解可能不只一个 但对策值是唯一 证明 考虑两个线性规划问题 这是两个互为对偶的线性规划问题 P403 是问题 D 的可行解 故 P D 必有最优解 是问题 P 的可行解 设最优解分别为 且 即存在有即 E i Y V E X j 定理7 对两个矩阵对策 其中为常数 则有分别是局中人 的最优策略集 定理8 对两个矩阵对策 其中为常数 则有定理9 设为一矩阵对策 且则 分别是局中人 的最优策略集定义 设矩阵对策 其中 若 则 若 则 例 设赢得矩阵为A 求解这个矩阵对策 解 解方程组 求得 例 囚犯难题 设有两个嫌疑犯被警察拘留 警察分别对两人进行审讯 根据法律 如果两人都承认此案是他们干的 则每人各判刑7年 如果两人都不承认 则由于证据不足 两人各判刑1年 如果只有一人承认 则承认者以宽大处理 当场释放 而不承认者判刑9年 因此 对两个囚犯来说 面临着一个 承认 和 不承认 之间两个策略的选择的难题 14 2矩阵对策的解法一 2 2矩阵对策的公式解法对给定的矩阵对策G S1 S2 AA aij 2 2 如果A无鞍点 则局中人I的最优混合策略X x1 x2 局中人II的最优混合策略Y y1 y2 和对策值VG 由下列公式给出 x1 a22 a21 Dx2 a11 a12 Dy1 a22 a12 Dy2 a11 a21 DVG a11a22 a12a21 D 二 m 2或2 n矩阵对策的图解法例 矩阵对策G S1 S2 A 其中 解 设局中人1的混合策略为局中人1选择时 他的最少可能收入为局中人2选择时 所确定三条直线的纵坐标中最小者 按最小最大原则 V 7 5 2 1 x 1 3 2 11 A B 3 O 解方程组 例 求解赢得矩阵为的矩阵对策 解 局中人2的混合策略为 按最大最小原则 7 6 2 y 1 2 2 11 3 O 6 A1 B2 A2 B1 例 求解赢得矩阵为的矩阵对策 解 1 用优超原则 解 2 用图解法局中人2的混合策略为 7 5 1 y 1 2 2 13 14 3 O 4 3 4 4 由方程组确定 满足方程组的解有无穷多个 故局中人2有无穷多最优解 三 线性方程组方法见书上399页 四 m n矩阵对策的线性规划法求解矩阵对策可以等价地转化成求解互为对偶的线性规划问题对给定的赢得矩阵A aij mn转化成两个互为对偶的线性规划问题 矩阵对策的解法1 优超原则化简 若有鞍点 则为纯矩阵对策 2 若没有鞍点 赢得矩阵为2 2阵 用公式法3 赢得矩阵为2 n 或m 2阵 用图解法4 方程组法5 线性规划法3 2线性规划法 定理14 4 设 则为的解的充要条件 存在数使得分别是不等式组 和 的解 例 利用线性规划方法求解矩阵对策 同理 解 求解矩阵对策可化为两个互为对偶的线性规划问题 把 2 变为标准型 例14 9对给定的赢得矩阵A01 1231A 101A 1231 10312A aij 2 LP min p1 p2 p3 2p1 p2 3p3 13p1 2p2 p3 1p1 3p2 2p3 1pi 0 i 1 2 3 DLP max q1 q2 q3 2q1 3q2 q3 1q1 2q2 3q3 13q1 q2 2q3 1qj 0 j 1 2 3 且 pi qj 1 V 利用单纯形法可求出 P 1 6 1 6 1 6 Q 1 6 1 6 1 6 p1 p2 p3 1 6 1 6 1 6 1 2 1 VV 2原问题的解 X VP 1 3 1 3 1 3 Y VQ 1 3 1 3 1 3 对策值VG V 2 0 例14 10对给定的赢得矩阵A729A 2909011 LP min p1 p2 p3 7p1 2p2 9p3 12p1 9p2 19p1 11p3 1pi 0 i 1 2 3 DLP max q1 q2 q3 7q1 2q2 9q3 12q1 9q2 19q1 11q3 1qj 0 j 1 2 3 且 pi qj 1 V 利用单纯形