运筹学教程》胡云权第五版运筹学--6对策论--矩阵对策.pptx

第六章 对策论 基本概念 对策论又称博弈论，研究冲突对抗条件下最优决策问题 的理论。 策略形势：不完全竞争条件下的对抗行为，各方收益 由自身行为和其他方行为共同决定。 基本要素 局中人（I ）：有权决定自己行动方案的对策参加者，理性人 策略集（S ）：供局中人选择的实际可行完整行动方案的集合 ， 一局对策中，各局中人选定策略的集合，称局 势 赢得函数（ H(s) ）:对于任一局势，局中人的赢得值。支付函数 严格占优策略/严格劣势策略 上策均衡/纳什均衡 典型案例和重要结论 结论1：不要选择严格劣势策略。 结论2：个人理性选择导致非最优。 结论3：学会换位思考。 囚徒困境 智猪博弈 求解方法：删除严格劣势策略 矩阵对策的基本理论 局中人个数：二个，多个 策略集中的个数：有限，无限 支付/赢得代数和：零和，非零和 局中人是否合作：非合作，合作 局中人行动时间：静态，动态 局中人对他者信息了解程度：完全信息，非完全信息 对策次数：单次，重复 对策/博弈分类 课程目标 理解并掌握矩阵对策的纯策略 理解并掌握矩阵对策的混合策略 掌握矩阵对策的求解方法 矩阵对策的策略 纯策略：确定的选择某策略 混合策略：以某一概率分布选择各策略。 矩阵对策的纯策略 的赢得矩阵 或的支付矩阵 的赢得矩阵为-A 。 1、矩阵对策的一般表达 矩阵对策的纯策略 例：田忌赛马 局中人：田忌（I）、齐王（II） S1 =（上、中、下），（上、下、中），（中、上、下）， （中、下、上），（下、中、上），（下、上、中）= S2 1、矩阵对策的一般表达 矩阵对策的纯策略 -8 2 -10 -3 9 2 6 理智行为：从各自最不利情形中选择最有利 I：最大最小原则 II：最小最大原则 平衡局势：双方均可接受，且对双方都是最稳妥的结果。 （2 ，2），局中人I和II的最优纯策略。 2、矩阵对策解的引例 矩阵对策的纯策略 从上例看出，矩阵A中平衡局势（2 ，2）对应的元素 a22既是其所在行的最小元素，也是其所在列的最大元素， 即有 ai2a22 a2j i=1,2,3,4 j=1,2,3 3、矩阵对策的最优纯策略 矩阵对策的纯策略 1 2 3 1 3 7 4 6 3、矩阵对策的最优纯策略 矩阵对策的纯策略 对于一个对策G=S1, S2, A, 若 有 则称局势（i*, j*）为对策G的 鞍点，V = a i*j*为对策G的值。 注：在矩阵中，一个数在所在行中是最大值，在所 在列中是最小值，则被称为鞍点。 4、矩阵对策的鞍点与解 矩阵对策的纯策略 多鞍点与无鞍点对策 例: 设有一矩阵对策如下，求它的解。 局势（1, 2），（1, 4），（3, 2）（3, 4） 均构成鞍点，此对策有多个解。 4、矩阵对策的鞍点与解 矩阵对策的纯策略 性质1：无差别性 若（i 1 ，j1）和（i2，j2）是对策G的两个解， 则 ai 1j1 = ai2j2 性质2：可交换性 若（i 1 ，j1）和（i2，j2）是对策G的两个解，则（i1 ，j 2）和（i2，j1）也是对策G的两个解。 矩阵对策的值唯一。即当一个局中人选择了最 优纯策略后，他的赢得值不依赖于对方的纯策略。 5、矩阵对策纯策略的性质 作业 P385 习题 12.2 12.3 12.4 矩阵对策的混合策略 3 4 5 6 无鞍点 1、混合策略 矩阵对策的混合策略 1、混合策略 矩阵对策的混合策略 2、混合局势 3、赢得期望 4、混合策略对策模型 矩阵对策的混合策略 5、最优混合策略 设 ，是矩阵对策 的混合扩 充。 矩阵对策的混合策略 5、最优混合策略 矩阵对策的混合策略 定理2：矩阵对策G在混合策略意义下有解的充要条件是： 存在 ，使得对于任意 ，有 2、最优混合策略 矩阵对策的混合策略 3、最优混合策略解的引例 矩阵对策的解法 例：求解矩阵对策G= ,其中 解：（1）不存在鞍点，为混合策略求解问题。 （2）图解法求解 设局中人I的混合策略为（x, 1-x）T， 。 01 I I II II 数轴上坐标为0和1的两点 分别做两条垂线I-I和II-II。 画出局中人II的不同策略下 局中人I的赢得线段。 2 5 7 2 3 11 1=2x+7(1-x) 2=3x+5(1- x) 3=11x+2(1-x) 图解法 仅适用于赢得矩阵为2n或m2阶的矩阵对策问题。 1: v11 = 2x+7(1-x) 2 : v12 = 3x+5(1-x) 3 : v13 = 11x+2(1-x) 由于局中人II理性，局中人I 从最少可能收入中选择最大 的一个，为局中人I的最优对 策。B2 求解方程组可得最优混合策 略和矩阵对策的值。 图解法 01 I I II II 2 5 7 2 3 11 1=2x+7(1-x) 2=3x+5(1- x) 3=11x+2(1-x) B1 B2 B3 B4 联立过B2点两条直线的方程组 为 可解得 则，局中人I 的最优策略为 由图可见局中人II的混合策 略只有2和3组成。 设局中人II的最优混合策略 为 ，且 P365 例10 图解法 求局中人II的最优混合策 略。 同理，可得局中人II的赢得 ， 1: v21 = 3y2+11y3 2 : v22 = 5y2+2y3 画出赢得线段，见右图 0 1 y y* 3 1 11 5 2 2 局中人I理性，局中人II取 最大损失的最小值 联立方程组可得 解得 方程组法 定理：设 ，则 为G的解的充要条件是： 存在数v，使得x*,y*分别是下列不等式组的解，且v = VG。 若xi*,yj*均不为0，则上述不等式的求解即可转化为下列两个 方程组的求解问题。 注：若上述两个方程组存在非负解x*,y* ，即矩阵对策的解。若不存在 非负解，则将上述方程组中的某些等式转化为不等式，继续求解。 由于事先假设xi*,yj*均不为0，故，当最优策略的某些分量为0时， 方程组可能无解，因此该方法具有一定的局限性。 方程组法 例：求解矩阵对策G= ,其中A为 解：（1）删除劣势策略，得到 无鞍