运筹学教学对策论.pptVIP

发 展 简 史 1912年E.Zermelo “关于集合论在象棋对策中的应用” 1921年E.Borel 引入最优策略 1928年J.V.Neumann证明了一些猜想 模 型 局中人 两个或两个以上---决策者 策略集合 策略----决策 局势----状态 支付函数 支付关于局势的函数----决策依据和标准 模型 分 类 局中人 两人对策、多人对策 策略 有限对策、无限对策；非合作对策、合作对策 支付 零和对策、非零和对策 时间 单阶段对策、多阶段对策 对策问题选择解的准则 均 衡 解 例 子 优 超（优势原则） 算 例 简 化 简 化 算 例 例：如下是二人零和对策的支付矩阵 2 3 a2 4 1 a1 b2 b1 分析发现： 此时若还使用纯策略，双方按照从最不利情形中选择 最有利情形的原则，应分别选择a2和b1,此时局中人I的 赢得是3，比至少赢得多了1，这是因为局中人II选择了 b1，才使得局中人I得到了不该得到的赢得，显然局中 人会考虑出b2,让局中人I的赢得变为2，而此时局中人I又 会选择a1，使得自己的赢得为4，… 如此下去就会出现不稳定状态。 解决此问题的想法很自然，既然局中人都没有最优策略 可出，可否给出一个选择不同策略的概率分布，以达到 一种平衡状态呢，这就是混合策略。 定义：混和策略 设有矩阵对策G={S1,S2;A},其中 记 则称 则称 为局中人A，B的混和策略集，称x,y为混 和策略，（x,y）为混和局势。局中人A的赢得函数为： 称 为对策G的混和扩充。 定义：混和策略意义下的解 设 如果 则称VG 为对策G的值，称使得上式成立的混和局势 是矩阵对策G={S1,S2;A}的混和扩充。 （x*,y*）为G在混和策略意义下的解（平衡局势），称x*,y*分别为局中人A和B的最优混和策略。 注：当局中人A选择混和策略x时，他的预期所得（按最小）是 因此局中人A应选取 使得 同理，B可保证损失的期望值 至多是 显然成立： 和纯策略类似，混合策略意义下同样有解存在的鞍点型充要条件： 定理1:矩阵对策在混和策略下有解的充要条件是：存在 使得对任意 有 例：考虑矩阵对策 解：易知G在纯策略意义下无解，所以，设 表示局中人I，II的混合策略，则 局中人I的赢得的期望是 取 则 所以 分别为局中人I，II的最优策略。 若记 则E(i,y)为局中人A取纯策略ai时的赢得值；E(x,j)为局中人B取纯策略bj时的赢得值,且有 则得到一个和定理1等价的定理2 混合策略意义下求解方法的相关理论 定理2: 则 为对策G的解的充要条件 为：对任意的i=1,2,…,m;j=1,2,…,n,有 证明：设 为对策G的解，则由定理1，成立 因为纯策略是混合策略的特例，所以，（*）成立。 反之，若（*）成立，则 定理2说明：要验证 为对策G的解时，只需要 对上式给出的有限个（m×n）不等式进行验证即可，大大简化了验证过程。 如此，便有了下面的等价定理－定理3 定理2得证。 定理3: 则 为：存在数v，使得 为对策G的解的充要条件 分别为不等式组(1),(2)的解, 且v=VG 定理4:任一矩阵对策G，一定存在混和策略意义下的解。 证明:由定理2知，只需证明存在 使得（*）式成立。所以，考虑如下规划问题 易知，规划问题（P）和（D）互为对偶问题，且 分别为（P）和（D）的一个可行解。由对偶定理知，他们都存在最优解，且最优目标值相等。即，存在 和 使得对任意的i=1,2,…,m;j=1,2,…,n有 或 又由 得 所以,(*)得证。 定理5:设 是矩阵对策G的解，v=VG，则 证明:由 有 又因为 所以，当 时，必有 当 时，必有 同理，可证（2），（4）。 第四节 混和策略的解法 方法1：图解法 上例中，设A以概率x和1-x使用策略a1和a2对付B使用纯策略b1时，A的收入为 对付B使用纯策略b2时，A的收入为 按照maxmin原则 混和策略意义下的maxmin值为va=5/2，此时x=1/4 为下图的B点 第*页 运 筹 帷 幄 之 中 决 胜 千 里 之 外 运 筹 学 课 件 对 策 论 Game Theory 第一节 对策论的基本概念和分类 博奕论( Game Theory)也就是运筹学中的对策论。 对策思想最早产生于我国古代。 早在两千多年前的春秋时期，孙武在《孙子兵法》中论述的军事思想和治国策略，就蕴育了丰富和深刻的对策论思想。孙武的后代孙膑，为