《数模(对策与决策模型)PPT课件.ppt》由会员分享，可在线阅读，更多相关《数模(对策与决策模型)PPT课件.ppt（92页珍藏版）》请在金锄头文库上搜索。
1、数学模型电子教案 重庆邮电大学计算机科学与技术学院沈世云 1 第八章对策与决策模型 2 第八章对策与决策模型 对策与决策是人们生活和工作中经常会遇到的择优活动 人们在处理一个问题时 往往会面临几种情况 同时又存在几种可行方案可供选择 要求根据自己的行动目的选定一种方案 以期获得最佳的结果 有时 人们面临的问题具有竞争性质 如商业上的竞争 体育中的比赛和军事行动 政治派别的斗争等等 这时竞争双方或各方都要发挥自己的优势 使己方获得最好结果 因而双方或各方都要根据不同情况 不同对手做出自己的决择 此时的决策称为对策 在有些情况下 如果我们把可能出现的若干种情况也看作是竞争对手可采取的几种策略 那么
2、也可以把决策问题当作对策问题来求解 3 8 1对策问题 对策问题的特征是参与者为利益相互冲突的各方 其结局不取决于其中任意一方的努力而是各方所采取的策略的综合结果 先考察几个实际例子 例8 1 田忌赛马 田忌赛马是大多数人都熟知的故事 传说战国时期齐王欲与大将田忌赛马 双方约定每人挑选上 中 下三个等级的马各一匹进行比赛 每局赌金为一千金 齐王同等级的马均比田忌的马略胜一筹 似乎必胜无疑 田忌的朋友孙膑给他出了一个主意 让他用下等马比齐王的上等马 上等马对齐王的中等马 中等马对齐王的下等马 结果田忌二胜一败 反而赢了一千金 4 例8 2 石头 剪子 布 这是一个大多数人小时候都玩过的游戏 游戏
3、双方只能选石头 剪子 布中的一种 石头赢剪子 剪子赢布 而布又赢石头 赢者得一分 输者失一分 双方相同时不得分 见下表 表8 1 5 一 对策的基本要素 1 局中人 参加决策的各方被称为决策问题的局中人 一个决策总是可以包含两名局中人 如棋类比赛 人与大自然作斗争等 也可以包含多于两名局中人 如大多数商业中的竞争 政治派别间的斗争 局中人必须要拥用可供其选择并影响最终结局的策略 在例8 2中 局中人是田忌 齐王 从这些简单实例中可以看出对策现象中包含的几个基本要素 6 2 策略集合 局中人能采取的可行方案称为策略 每一局中人可采取的全部策略称为此局中人的策略集合 对策问题中 对应于每一局中人存
4、在着一个策略集合 而每一策略集合中至少要有两个策略 否则该局中人可从此对策问题中删去 因为对他来讲 不存在选择策略的余地 应当注意的是 所谓策略是指在整个竞争过程中对付他方的完整方法 并非指竞争过程中某步所采取的具体局部办法 例如下棋中的某步只能看和一个完整策略的组成部分 而不能看成一个完整的策略 当然 有时可将它看成一个多阶段对策中的子对策 策略集合可以是有限集也可以是无限集 策略集为有限集时称为有限对策 否则称为无限对策 记局中人i的策略集合为Si 当对策问题各方都从各自的策略集合中选定了一个策略后 各方采取的策略全体可用一矢量S表示 称之为一个纯局势 简称局势 7 例如 若一对策中包含A
5、 B两名局中人 其策略集合分别为SA 1 m SB 1 n 若A选择策略i而B选策略j 则 i j 就构成此对策的一个纯局势 显然 SA与SB一共可构成m n个纯局势 它们构成表8 3 对策问题的全体纯局势构成的集合S称为此对策问题的局势集合 8 3 赢得函数 或称支付函数 对策的结果用矢量表示 称之为赢得函数 赢得函数F为定义在局势集合S上的矢值函数 对于S中的每一纯局势S F S 指出了每一局中人在此对策结果下应赢得 或支付 的值 综上所述 一个对策模型由局中人 策略集合和赢得函数三部分组成 记局中人集合为I 1 k 对每一i I 有一策略集合Si 当I中每一局中人i选定策略后得一个局势s
6、 将s代入赢得函数F 即得一矢量F s F1 s Fk s 其中Fi s 为在局势s下局中人i的赢得 或支付 本节讨论只有两名局中人的对策问题 即两人对策 其结果可以推广到一般的对策模型中去 对于只有两名局中人的对策问题 其局势集合和赢得函数均可用表格表示 例如 表8 2就给出了例8 2的局势集合和赢得函数 9 二 零和对策 存在一类特殊的对策问题 在这类对策中 当纯局势确定后 A之所得恰为B之所失 或者A之所失恰为B之所得 即双方所得之和总为零 在零和对策中 因F1 s F2 s 只需指出其中一人的赢得值即可 故赢得函数可用赢得矩阵表示 例如若A有m种策略 B有n种策略 赢得矩阵 表示若A选
7、取策略i而B选取策略j 则A之所得为aij 当aij 0时为支付 10 在有些两人对策的赢得表中 A之所得并非明显为B之所失 但双方赢得数之和为一常数 例如在表8 4中 无论A B怎样选取策略 双方赢得总和均为10 此时 若将各人赢得数减去两人的平均赢得数 即可将赢得表化为零和赢得表 表8 4中的对策在转化为零和对策后 具有赢得矩阵 表8 4 11 给定一个两人对策只需给出局中人A B的策略集合SA SB及表示双方赢得值的赢得矩阵R 综上所述 当遇到零和对策或可转化为零和对策的问题时 R可用通常意义下的矩阵表示 否则R的元素为一两维矢量 故两人对策G又可称为矩阵对策并可简记成G SA SB R
8、 12 例8 3给定G SA SB R 其中SA 1 2 3 SB 1 2 3 4 从R中可以看出 若A希望获得最大赢利30 需采取策略1 但此时若B采取策略4 A非但得不到30 反而会失去22 为了稳妥 双方都应考虑到对方有使自己损失最大的动机 在最坏的可能中争取最好的结果 局中人A采取策略1 2 3时 最坏的赢得结果分别为 min 12 6 30 22 22 min 14 2 18 10 2 min 6 0 10 16 10 其中最好的可能为max 22 2 10 2 如果A采取策略2 无论B采取什么策略 A的赢得均不会少于2 13 B采取各方案的最大损失为max 12 14 6 14 m
9、ax 6 2 0 2 max 30 18 10 30和max 22 10 16 16 当B采取策略2时 其损失不会超过2 注意到在赢得矩阵中 2既是所在行中的最小元素又是所在列中的最大元素 此时 只要对方不改变策略 任一局中人都不可能通过变换策略来增大赢得或减小损失 称这样的局势为对策的一个稳定点或稳定解 注 也被称为鞍点 定义8 1对于两人对策G SA SB R 若有 则称G具有稳定解 并称VG为对策G的值 若纯局势 使得 则称 为对策G的鞍点或稳定解 赢得矩阵中与 相对应的元素称为赢得矩阵的鞍点 与分别称为局中人A与B的最优策略 对 8 1 式中的赢得矩阵 容易发现不存在具有上述性质的鞍点
10、 给定一个对策G 如何判断它是否具有鞍点呢 为了回答这一问题 先引入下面的极大极小原理 14 定理8 1设G SA SB R 记 则必有 0 证明 易见 为A的最小赢得 为B的最小赢得 由于G是零和对策 故 0必成立 定理8 2零和对策G具有稳定解的充要条件为 0 证明 充分性 由 和 的定义可知 存在一行 例如p行 为p行中的最小元素且存在一列 例如q列 为q列中的最大元素 故有apq 且apq 又因 0 所以 从而得出apq apq为赢得矩阵的鞍点 p q 为G的稳定解 15 必要性 若G具有稳定解 p q 则apq为赢得矩阵的鞍点 故有 从而可得 0 但根据定理8 1 0必成立 故必有
11、0 上述定理给出了对策问题有稳定解 简称为解 的充要条件 当对策问题有解时 其解可以不唯一 例如 若 则易见 2 2 2 4 4 2 4 4 均为此对策问题的解 一般又可以证明 16 定理8 3对策问题的解具有下列性质 1 无差别性 若 与 同为对策G的解 则必有 2 可交换性 若 j1 j2 均为对策G的解 则 j2 和 j1 也必为G的解 17 具有稳定解的零和对策问题是一类特别简单的对策问题 它所对应的赢得矩阵存在鞍点 任一局中人都不可能通过自己单方面的努力来改进结果 然而 在实际遇到的零和对策中更典型的是 0的情况 由于赢得矩阵中不存在鞍点 至少存在一名局中人 在他单方面改变策略的情况
12、下 有可能改善自己的收益 例如 考察 8 1 中的赢得矩阵R 若双方都采取保守的maxmin原则 将会出现纯局势 4 1 或 4 3 但如果局中人A适当改换策略 他可以增加收入 例如 如果B采用策略1 而A改换策略1 则A可收益3 但此时若B改换策略2 又会使A输掉4 此时 在只使用纯策略的范围内 对策问题无解 这类决策如果只进行一次 局中人除了碰运气以外别无办法 但如果这类决策要反复进行多次 则局中人固定采用一种策略显然是不明智的 因为一旦对手看出你会采用什么策略 他将会选用对自己最为有利的策略 这时 局中人均应根据某种概率来选用各种策略 即采用混合策略的办法 使自己的期望收益尽可能大 18
13、 设A方用概率xi选用策略i B方用概率yj选用策略j 且双方每次选用什么策略是随机的 不能让对方看出规律 记X x1 xm T Y y1 yn T 则A的期望赢得为 E X Y XTRY 其中 R为A方的赢得矩阵 记 分别称SA与SB为A方和B方的混合策略 对于需要使用混合策略的对策问题 也有具有稳定解的对策问题的类似结果 19 定义8 2若存在m维概率向量和n维概率向量 使得对一切m维概率向量X和n维概率向量y有则称 为混合策略对策问题的鞍点 定理8 4 VonNeumann 任意混合策略对策问题必存在鞍点 即必存在概率向量和 使得 证明从略 使用纯策略的对策问题 具有稳定解的对策问题 可
14、以看成使用混合策略的对策问题的特殊情况 相当于以概率1选取其中某一策略 以概率0选取其余策略 对于双方均只有两种策略的对策问题 即2 2对策 可按几何方法求解 20 例8 5A B为作战双方 A方拟派两架轰炸机I和II去轰炸B方的指挥部 轰炸机I在前面飞行 II随后 两架轰炸机中只有一架带有炸弹 而另一架仅为护航 轰炸机飞至B方上空 受到B方战斗机的阻击 若战斗机阻击后面的轰炸机II 它仅受II的射击 被击中的概率为0 3 I来不及返回击它 若战斗机阻击I 它将同时受到两架轰炸机的射击 被击中的概率为0 7 一旦战斗机未被击落 它将以0 6的概率击毁其选中的轰炸机 请为A B双方各选择一个最优
15、策略 即 对于A方应选择哪一架轰炸机装载炸弹 对于B方战斗机应阻击哪一架轰炸机 解 双方可选择的策略集分别为 SA 1 2 1 轰炸机I装炸弹 II护航2 轰炸机II装炸弹 I护航 SA 1 2 1 阻击轰炸机I2 阻击轰炸机II 21 赢得矩阵R aij 2 2 aij为A方采取策略i而B方采取策略j时 轰炸机轰炸B方指挥部的概率 由题意可计算出 a11 0 7 0 3 1 0 6 0 82 a12 1 a21 1 a22 0 3 0 7 1 0 6 0 58 即 易求得 由于 0 矩阵R不存在鞍点 应当求最佳混合策略 22 现设A以概率x1取策略1 概率x2取策略2 B以概率y1取策略1
16、概率y2取策略2 先从B方来考虑问题 B采用1时 A方轰炸机攻击指挥部的概率的期望值为E 1 0 82x1 x2 而B采用2时 A方轰炸机攻击指挥部的概率的期望值为E 2 x1 0 58x2 若E 1 E 2 不妨设E 1 E 2 则B方必采用1以减少指挥部被轰炸的概率 故对A方选取的最佳概率x1和x2 必满足 即 由此解得x1 0 7 x2 0 3 23 同样 可从A方考虑问题 得 即 并解得y1 0 7 y2 0 3 B方指挥部轰炸的概率的期望值VG 0 874 上述方法也可以用几何方式表达 在x轴上取长度为1的线段 左端点为x 0 右端点为x 1 过x 0和x 1各作x轴的垂线 称之为轴I和轴II 在轴I上取B1 B2 它们到x轴的距离分别的a11和a12 表示在A采取策略1即 x2 0 时A方在B方分别采取策略1和2下的赢得 如图8 1所示 24 借助几何方法也可以解m 2或2 n的使用混合策略的对策问题 但当m 2且n 2时 采用几何方法求解就变得相当麻烦 此时通常采用线性规划方法求解 现设A以概率x2采取策略2 若B采取策略2 则A的期望赢得为a11 1 x2 a21x2
