《管理运筹学-对策论》东北大学-PPT课件.ppt

对策论 由 齐王赛马 引入 1 1 对策论的基本概念 三个基本要素 1 局中人 参与对抗的各方 2 策略集 局中人选择对付其它局中人的行动方案称为策略 某局中人的所有可能策略全体称为策略集 3 局势对策的益损值 各局中人各自使用一个对策就形成一个局势 一个局势决定了个局众人的对策结果 量化 称为该局势对策的益损值 2 齐王赛马 齐王在各局势中的益损值表 单位 千金 3 其中 齐王的策略集 S1 1 2 3 4 5 6 田忌的策略集 S1 1 2 3 4 5 6 下列矩阵称齐王的赢得矩阵 3111 1113111 1A 1 13111 111311111 13111 1113 4 1 基本概念 续 二人有限零和对策 又称矩阵策略 局中人为2 每局中人的策略集中策略权目有限 每一局势的对策均有确定的损益值 并且对同一局势的两个局中人的益损值之和为零 5 1 基本概念 续 记矩阵对策为 G S1 S2 A 甲的策略集甲的赢得矩阵乙的策略集 齐王赛马 即是一个矩阵策略 6 2 矩阵对策的最优纯策略 在甲方赢得矩阵中 A aij m ni行代表甲方策略i 1 2 mJ列代表乙方策略j 1 2 naij代表甲方取策略i 乙方取策略j 这一局势下甲方的益损值 此时乙方的益损值为 aij 零和性质 在讨论各方采用的策略是必须注意一个前提就是对方是理智的 这就是要从最有把握取得的益损值情况考虑 7 2 矩阵对策的最优纯策略 续 例 有交易双方公司甲和乙 甲有三个策略 1 2 3 乙有四个策略 1 2 3 4 根据获利情况建立甲方的益损值赢得矩阵 30 20A 2301 2 4 13问 甲公司应采取什么策略比较适合 8 甲 采取 1至少得益 3 损失3 20 3 4 损失4 乙 采取 1甲最多得益2 乙最少得益 2 23 乙得益 3 30 乙得益0 43 乙得益 3 取大则取 2maxminaij 0ij 取小则取 3minmaxaij 0ji 9 甲采取策略 2不管乙采取如何策略 都至少得益 乙采取策略 3不管甲采取如何策略 都至少可以得益 最多损失0 分别称甲 乙公司的最优策略 由唯一性又称最优纯策略 存在前提 maxminaij minmaxaij vijji又称 2 3 为对策G s1 s2 A 的鞍点 值V为G的值 10 3 矩阵对策的混合策略 设矩阵对策G S1 S2 A 当maxminaij minmaxaijijji时 不存在最优纯策略求解混合策略 11 3 矩阵对策的混合策略 例 设一个赢得矩阵如下 min595A max6策略 2866imax89min8策略 1j 12 2020 3 18 13 矛盾 甲取 2 乙取时 1 甲实际赢得8比预期多2 乙就少2 这对乙讲是不满意的 考虑这一点 乙采取策略 2 若甲分析到这一点 取策略 1 则赢得更多为9 此时 甲 乙方没有一个双方均可接受的平衡局势 一个思路 对甲 乙 给出一个选取不同策略的概率分布 以使甲 乙 在各种情况下的平均赢得 损失 最多 最少 即混合策略 14 求解方法 线性规划法 其他方法 图解法 迭代法 线性方程法等略 例 59设在最坏的情况下 A 甲赢得的平均值为V 86 未知 STEP11 设甲使用策略 1的概率为X1 X1 X2 1设甲使用策略 2的概率为X2 X1 X2 0 15 2 无论乙取何策略 甲的平均赢得应不少于V 对乙取 1 5X1 8X2 V对乙取 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 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 17 同样可求乙的最优混合策略 设乙使用策略 1的概率为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 18 返回原问题 Y1 Y1V 1 2Y2 Y2V 1 2于是乙的最优混合策略为 以1 2的概率选 1 以1 2的概率选 2最优值V 7 当赢得矩阵中有非正元素时 V 0的条件不一定成立 可以作下列变换 选一正数k 令矩阵中每一元素加上k得到新的正矩阵A 其对应的矩阵对策G S1 S2 A 与G S1 S2 A 解相同 但VG VG k 19 例 求解 齐王赛马 问题 见备课稿 优超原则 假设矩阵对策G S1 S2 A 甲方赢得矩阵A aij m n 若存在两行 列 s行 列 的各元素均优于t行 列 的元素 即asj atjj 1 2 n ais aiti 1 2 m 称甲方策略 s优超于 t s优超于 t 3 矩阵对策的混合策略 续 20 优超原则 当局中人甲方的策略 t被其它策略所优超时 可在其赢得矩阵A中划去第t行 同理 当局中人乙方的策略 t被其它策略所优超时 可在矩阵A中划去第t列 如此得到阶数较小的赢得矩阵A 其对应的矩阵对策G S1 S2 A 与G S1 S2 A 等价 即解相同 3 矩阵对策的混合策略 续 21 例设甲方的益损值赢得矩阵 32030被第3 4行所优超50259被第3行所优超A 7395946875 560883得到73959被第1列所优超A1 46875 5被第2列所优超60883 3 矩阵对策的混合策略 续 22 续例得到739A2 465 5603被第1行所优超得到739被第1列所优超A3 465 573最终得到A4 46 3 矩阵对策的混合策略 续 23 对A4计算 用线性规划方法得到 注意 余下的策略为 3 4 1 2 甲 X 0 0 1 15 2 15 0 TV 5X 0 0 1 3 2 3 0 T乙