运筹学教程对策论.ppt

交通运输与物流工程专业 运筹学教程同济大学 10 对策论 1 概述 1 对策模型 研究两个或两个以上的参加者在某种对抗性或竞争性的场合下各自作出决策 使自己的一方得到尽可能最有利的结果 带有竞争性质的现象 称为对策现象 日常生活中 在政治方面 正经济领域内 齐王赛马 10 对策论 1 概述 1 对策模型 2 对策现象的三个基本要素 局中人 决策者 利益得失者 不是公证人 马 谋士等 可以是团体 国家等 聪明的 有理智的 把那些利益完全一致的参加者们看作一个局中人 两人 多人 结盟 不结盟 10 对策论 1 概述 1 对策模型 2 对策现象的三个基本要素 局中人 策略 自始至终的行动方案 把局中人的策略全体 称做这个局中人的策略集合 例如 在齐王与田忌赛马的例子中 如果 开始就要把各人的三匹马排好次序 然后依次出赛 各局中人都有六个策略 1 上 中 下 2 上 下 中 3 中 上 下 4 中 下 上 5 下 中 上 6 下 上 中 这个策略全体就是局中人的策略集合 有限 无限 10 对策论 1 概述 1 对策模型 2 对策现象的三个基本要素 局中人 策略 得失 一局对策结束时 每个局中人的 得失 是全体局中人所取定的一组策略的函数 通常称为 支付函数 从每个局中人的策略集中各取 个策略 组成的策略组 称作 局势 得失 是 局势 的函数 如果全体局中人的 得失 相加总是等于零时 这个对策就称为零和对策 否则称为 非零和对策 10 对策论 1 概述 1 对策模型 2 对策现象的三个基本要素 3 对策模型的分类 10 对策论 2 矩阵对策 MatrixGames 1 定义 有限二人零和对策 即参加对策的局中人只有两个 而每个局中人都有有限个可供选择的策略 而且在任一局势中 两个局中人的得失之和总等于零 一个局中人的所得即为另一个局中人的所失 局中人的利益是冲突的 也称为对抗对策 2 矩阵对策 MatrixGames 例1 配钱币游戏 两个局中人1和2各出示一枚钱币 在不让对方看见的情况下 将钱币放在卓上 若两个钱币都呈正面或都呈反面 则局中人1得1分 局中人2得 1分 若两个钱币一正一反 则局中人2得1分 可用一个支付矩阵表示 2 矩阵对策 MatrixGames 例2 石头 剪刀 布 游戏 2 矩阵对策 MatrixGames 例3 局中人1从p 0 1 2 3四个数中选出一个数 局中人2在不知道局中人1出什么数的情况下从q 0 1 2三个数中选出一个数 局中人1得到的支付由下支付函数确定 P p q p q q p 或P q2 p2 2pq 2 矩阵对策 MatrixGames 2 数学模型 设局中人1有m个纯策略 1 2 m 记集合为S1 1 2 m 同样 局中人2有n个纯策略 集合为S2 1 2 n 支付矩阵 或赢得矩阵 局中人 赢得矩阵为 对策模型记为 S1 S2 A 2 矩阵对策 MatrixGames 2 数学模型 如齐王赛马 S1 上 中 下 上 下 中 中 上 下 中 下 上 下 中 上 下 上 中 S 上 中 下 上 下 中 中 上 下 中 下 上 下 中 上 下 上 中 田忌的支付 赢得 矩阵为 A 3 最优纯策略 例4对于一个矩阵对策 I S1 S2 A 其中S1 1 2 3 4 S2 1 2 3 求双方的最优策略 解由A可以看出 局中人I的最大赢得是16 就是说局中人I十分希望自己取得16 就会出 3加入博弈 然而 局中人 也在考虑 因为局中人I有出 3的心理状态 于是局中人 就想出 3进行博弈 这样不仅不能使I得到16 反而要输9 即赢得 9 同样 I也会这样想 有出 3的心理状态 于是I就会出 2 结果 不但得不到9 反而要输5 同样 如果I出 2 则 会出 2 使I的赢得达到最小2 而对于I来说 如果 出 2 I的最优策略仍然是 2 可获得最大赢得值2 2和 2分别是双方的最优策略 a22 2称为矩阵博弈G的值 它是第2行中最小值 也正好是第2列中的最大值 3 最优纯策略 对于给定的 S1 S2 A 局中人1希望支付值越大越好 局中人2希望支付值越小越好 局中人1可选择i 使他得到的支付不少于 局中人2可以选择j 保证他失去的支付不大于 容易证明 例1 配钱币游戏 1 1 3 最优纯策略 1 1 例2 石头 剪刀 布 游戏 3 最优纯策略 0 0 例3 3 最优纯策略 齐王赛马 1 3 3 最优纯策略 定义 一个矩阵对策 如果它的支付矩阵A的元素满足 则称这个值v为对策的值 如果纯局势 i j 使 则称 i j 为对策G的鞍点 Saddlepoint 也称它是对策G在纯策略中的解 i 与j 分别为局中人1和局中人2的最优解 3 最优纯策略 即矩阵对策有两个性质 一是鞍点的可交换性 二是各鞍点的值都相等 定理 为对策G的鞍点的充要条件是对于任意的i j 有 如 定理 若和都是矩阵对策A的鞍点 则和也都是它的鞍点 且在鞍点处的值都相等 即 即该列的最大元素及该行的最小元素 3 最优纯策略 例5 某单位在秋天要决定冬季取暖用煤贮量问题 在正常的冬季气温下要消耗15吨 但在较暖与较冷的冬季需要10吨和20吨 假定煤的价格随着冬季寒冷程度而有所变动 设在较暖的 正常的 较冷的冬季气温下分别为每吨100元 150元 200元 又设在秋季煤价是每吨100元 在没有关于当年冬季准确的气象预报条件下 秋季贮煤多少吨才较合理 解 把采购员当作局中人I 他有三个策略 在秋天时买10吨 15吨与20吨 分别记为a1 a2 a3 把大自然看作局中人 可以当作理智的局中人来处理 大自然 冬季气温 有三种策略 出现较暖的 正常的与较冷的冬季 分别记为b1 b2 b3 现在把该单位冬季取暖用煤实际费用 即秋季购煤时的用费 与冬季不够时再补购的费用总和 作为局中人I的赢得 得矩阵如下 3 最优纯策略 例5 某单位在秋天要决定冬季取暖用煤贮量问题 在正常的冬季气温下要消耗15吨 但在较暖与较冷的冬季需要10吨和20吨 假定煤的价格随着冬季寒冷程度而有所变动 设在较暖的 正常的 较冷的冬季气温下分别为每吨100元 150元 200元 又设在秋季煤价是每吨100元 在没有关于当年冬季准确的气象预报条件下 秋季贮煤多少吨才较合理 故对策的解为 3 3 即秋季贮煤20吨合理 决策论中的悲观准则 3 最优纯策略 例6 甲 乙双方谈判签订一项合同 甲方的 要价 是25万元 而乙方的 出价 是20万元 谈判陷于僵局 为打破僵局 双方约定 再各报一个价 以下述价格成交 谁让步多 取谁出的价 如果双方让步相同 则取双方报价的中间值 问甲 乙双方应如何报价 最后的成交价是多少 解显然 甲 乙双方的报价都在20万元到25万元之间 不妨取整数值 甲 乙各有6个策略 报价20 21 25 单位 万元 由约定知 甲的支付矩阵可用表所示 23 22 是鞍点 甲方的最优纯策略是要价23万元 乙方的最优纯策略是出价22万元 双方的让步相同 甲方降低2万元 乙方提高2万元 最后的成交价是22 5万元 2 矩阵对策 MatrixGames 4 混合策略 一般情况下 二人零和对策有 用多大概率选取各个纯策略 定义1 对于支付矩阵A aij mxn 局中人1的一个混合策略就是一组数xi 0 i 1 2 m 满足 局中人2的一个混合策略就是一组数yj 0 j 1 2 n 满足 设X x1 x2 xm 和Y y1 y2 yn 分别为局中人1和局中人2的混合策略 则局中人1选择策略i 局中人2选择策略j 并且支付为aij的概率为xiyj 局中人1的期望支付为 2 矩阵对策 MatrixGames 4 混合策略 定义2 称数学期望E X Y 为局中人1的赢得 E X Y 为局中人2的赢得 而 X Y 称为混合局势 定义3 设S1 是满足xi 0的一切X x1 x2 xm 的混合策略集 S2 是满足yi 0的一切Y y1 y2 yn 的混合策略集 即S1 X S2 Y 对于给定的一个对策G S1 S2 A 称G S1 S2 E 为G的混合扩充 2 矩阵对策 MatrixGames 4 混合策略 对于局中人2 若采取混合策略Y 则可能支出 因此他应选取Y 使支出最小 对于局中人1 若采取混合策略X 则只能希望赢得 因此他应选取X 使赢得最大 2 矩阵对策 MatrixGames 4 混合策略 定理1 对于给定的对策G 有 定理2 最小最大值定理 对策论基本定理 对于一切矩阵对策 都有 定义4 设G S1 S2 E 为对策G S1 S2 A 的混合扩充 如果有混合局势 X Y 使 则称V为对策G的值 而混合局势称为G在混合策略下的解 而X 与Y 分别称为局中人1和局中人2的最优解 2 矩阵对策 MatrixGames 4 混合策略 定理3 若矩阵对策G的值为V 则以下两组不等式的解就是局中人1和局中人2的最优策略 定理4 设混合局势 X Y 是矩阵对策G的最优解 记对策值V E X Y 则 1 若 2 若 3 若 4 若 3 矩阵对策的求解 1 特殊情况下的解 1 如果有鞍点 则鞍点就是最优解 2 如果没有鞍点 但事先知道均不为零 则可将两组不等式化成线性方程组来求解 例1 齐王赛马 没有鞍点 且各个策略出现的可能性均不为零 解 令 则有线性方程组 ATX V AY V 3 矩阵对策的求解 各方程相加 得 因为 所以v 1 代入方程得 3 矩阵对策的求解 例2 设 解 且无鞍点 混合策略的各分量不为零 求最优混合策略 3 矩阵对策的求解 3 可降低矩阵阶数求解 例3 给定一个矩阵对策G S1 S2 A 求对策G的值与解 其中 若所给矩阵中I行的各个元素比j行各元素小 则对局中人1来说策略i明显不如策略j 称纯策略j优超纯策略j 同理 若I列的元素比j列的对应元素大 则对局中人2来说策略j优超策略i 而明显不利策略出现的概率为零 3 矩阵对策的求解 4 化简矩阵 使矩阵的元素尽可能多地变成零 定理1 设两个矩阵对策 G1 S1 S2 A G2 S1 S2 B 其中A aij mxn B bij mxn 若bij aij d 其中d为一常数 则G1和G2有相同的混合策略 且V2 V1 d V1和V2分别为G1和G2的对策值 3 矩阵对策的求解 4 化简矩阵 使矩阵的元素尽可能多地变成零 例4 给定一个矩阵对策G S1 S2 A 求对策G的值与解 其中 解 1 直接解 3 矩阵对策的求解 解 2 阵中各元素加1 得 2 线性规划法求解 其中 令 对于扩充后的矩阵对策来说 求最优解就是解下列两个不等式组 2 线性规划法求解 即求线性规划 因 1 V 所以V 3 又因 得 解 例5 给定一个矩阵对策G S1 S2 A 求对策G的值与解 其中 4 合作对策 定义11 6 n人合作对策模型 设集合I 1 2 n 若对任意的 总存在V S 收益 实值 函数 满足 称 I v 为n人合作博弈 Cooperativen persongame v为博弈的的特征函数 n人合作博弈是指定义了特征函数的I中n个人的合作分配结果 用向量表示 4 合作对策 例 三人经商问题 A B C三人经商 若单干 每人获利1元 A和B合作可获利7元 A和C合作可获利5元 B和C合作可获利4元 三个合作可合可获10元 问三人合作时怎样合理分配10元的收入 方案 ABCABACBCABC效益 11175410 设x1 x2 x3为A B C各得的分配 应满足 x1 x2 x3 10 x1 x2 x3 1 x1 x2 7 x1 x3 5 x2 x3 4 满足上式的解有无穷多个 如 5 3 2 4 3 3 4 合作对策 设V S 为集合S中元素合作的收益 则 A V A B C V B C 10 4 6 V A B V B 6 V A C V C 4B V A B C V A C 5 V A B V A 6 V B C V C 3C V A B C V A B 3 V A C V A 4 V B C V B 3 方案 ABCABACBCABC效益 11175410 A B C的总贡献为 16 14 10 因此x1 x2 x3 16 14 10 且x1 x2 x3 10 得 x1 10 16 16 14 10 4 x2 10 14 40 3 5 x3 10 10 40 2 5 n人合作对策模型 Shaplay公理 设 I v 给定的一个n人合作博弈 则由v决定的一个分配应满足 1 合作获利对每个人的分配与赋予他的记号 i 无关 2 各人分配之和等于合作获利 3 如果 i 对于每一个他参加的合作都没有贡献 那么他不应从全体的合作获利中得到报酬 4 当n人同时进行两项合作时 每人获利可分两项合作计算 n人合作对策模型 Shaplay证明了满足上四假设的分配是有唯一解 其中 Si是I中包含 i 的所有子集 S 是S的人数 是加权因子可看作 i 对合作S的贡献 称为由V定义的合作的Shaplay值 其意义为 对于一个n人合作对策模型 其第i个人的收入应按照 i 对各种形式的合作的贡献的加权平均来确定 Shaplayn人合作对策模型 三人经商问题 对于第一个人 1 1 1 3 6 1 6 4 1 6 6 1 3 4同理 2 3 5 3 2 5 4 合作对策 设Q为污水量 T S L为管道长 km 已知 建处理厂的费用 CT 730Q0 712 铺管道费用 Cp 6 6Q0 51L 污水量 Q1 5 Q2 3 Q3 5 距离 L12 20 L23 38 问题 沿河有三镇1 2 3 污水需经处理后流入河中 若联合建厂 厂址应在下游 问如何联合及如何投资 污水处理问题 三镇联合建一个处理厂投资方案 1 平分 5560 3 1853 1600城2反对2 城3提出 建厂费按三城的污水量之比5 3 5分担 管道费由