《运筹学教程胡云权第五运筹学对策论矩阵对策.pptx》由会员分享，可在线阅读，更多相关《运筹学教程胡云权第五运筹学对策论矩阵对策.pptx（33页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、基本概念对策论又称博弈论，研究冲突对抗条件下最优决策问题的理论。策略形势：不完全竞争条件下的对抗行为，各方收益由自身行为和其他方行为共同决定。基本要素局中人（I）：有权决定自己行动方案的对策参加者，理性人策略集（S）：供局中人选择的实际可行完整行动方案的集合，一局对策中，各局中人选定策略的集合，称局势赢得函数（H(s)）:对于任一局势，局中人的赢得值。支付函数严格占优策略/严格劣势策略上策均衡/纳什均衡第1页/共33页典型案例和重要结论结论1：不要选择严格劣势策略。结论2：个人理性选择导致非最优。结论3：学会换位思考。囚徒困境 智猪博弈 求解方法：删除严格劣势策略第2页/共33页矩阵对策的基本
2、理论第3页/共33页局中人个数：二个，多个策略集中的个数：有限，无限支付/赢得代数和：零和，非零和局中人是否合作：非合作，合作局中人行动时间：静态，动态局中人对他者信息了解程度：完全信息，非完全信息对策次数：单次，重复对策/博弈分类第4页/共33页课程目标 理解并掌握矩阵对策的纯策略 理解并掌握矩阵对策的混合策略 掌握矩阵对策的求解方法第5页/共33页矩阵对策的策略 纯策略：确定的选择某策略 混合策略：以某一概率分布选择各策略。第6页/共33页矩阵对策的纯策略的赢得矩阵或的支付矩阵的赢得矩阵为-A。1、矩阵对策的一般表达第7页/共33页矩阵对策的纯策略例：田忌赛马局中人：田忌（I）、齐王（II
3、）S1=（上、中、下），（上、下、中），（中、上、下），（中、下、上），（下、中、上），（下、上、中）=S2 1、矩阵对策的一般表达第8页/共33页矩阵对策的纯策略-82-10-39 2 6理智理智行为：行为：从各自最不利情形中选择最有利从各自最不利情形中选择最有利 I：最大最小：最大最小原则原则 II：最小最大原则：最小最大原则平衡局势：平衡局势：双方均可接受，且对双方都是最稳妥的结果。双方均可接受，且对双方都是最稳妥的结果。（2，2），），局中人局中人I和和II的最优纯策略。的最优纯策略。2、矩阵对策解的引例第9页/共33页矩阵对策的纯策略 从上例看出，矩阵A中平衡局势（2，2）对应的元素
4、a22既是其所在行的最小元素，也是其所在列的最大元素，即有 ai2a22 a2j i=1,2,3,4 j=1,2,33、矩阵对策的最优纯策略第10页/共33页矩阵对策的纯策略12313 7 4 63、矩阵对策的最优纯策略第11页/共33页矩阵对策的纯策略对于一个对策G=S1,S2,A,若有则称局势（i*,j*）为对策G的鞍点，V=a i*j*为对策G的值。注：在矩阵中，一个数在所在行中是最大值，在所在列中是最小值，则被称为鞍点。4、矩阵对策的鞍点与解第12页/共33页矩阵对策的纯策略多鞍点与无鞍点对策例:设有一矩阵对策如下，求它的解。局势（1,2），（1,4），（3,2）（3,4）均构成鞍点，
5、此对策有多个解。4、矩阵对策的鞍点与解第13页/共33页矩阵对策的纯策略性质1：无差别性若（i1，j1）和（i2，j2）是对策G的两个解，则ai1j1=ai2j2性质性质2 2：可交换性：可交换性若（i1，j1）和（i2，j2）是对策G的两个解，则（i1，j2）和（i2，j1）也是对策G的两个解。矩阵对策矩阵对策的值唯一。的值唯一。即当一个局中人选择了最即当一个局中人选择了最优纯策略后，他的赢得值不依赖于对方的纯策略优纯策略后，他的赢得值不依赖于对方的纯策略。5、矩阵对策纯策略的性质第14页/共33页作业P385 习题12.212.312.4第15页/共33页矩阵对策的混合策略345 6无鞍点
6、1、混合策略第16页/共33页矩阵对策的混合策略1、混合策略第17页/共33页矩阵对策的混合策略2、混合局势3、赢得期望4、混合策略对策模型第18页/共33页矩阵对策的混合策略5、最优混合策略设 ，是矩阵对策 的混合扩充。第19页/共33页矩阵对策的混合策略5、最优混合策略第20页/共33页矩阵对策的混合策略定理2：矩阵对策G在混合策略意义下有解的充要条件是：存在 ，使得对于任意 ，有2、最优混合策略第21页/共33页矩阵对策的混合策略3、最优混合策略解的引例第22页/共33页矩阵对策的解法第23页/共33页例：求解矩阵对策G=,其中解：（1）不存在鞍点，为混合策略求解问题。（2）图解法求解设
7、局中人I的混合策略为（x,1-x）T，。01IIIIII 数轴上坐标为0和1的两点分别做两条垂线I-I和II-II。画出局中人II的不同策略下局中人I的赢得线段。25723111=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)第24页/共33页由于局中人II理性，局中人I从最少可能收入中选择最大的一个，为局中人I的最优对策。B2 求解方程组可得最优混合策略和矩阵对策的值。图解法01IIIIII25723111=2x+7(1-x)2=3
8、x+5(1-x)3=11x+2(1-x)B1B2B3B4联立过B2点两条直线的方程组为可解得则，局中人I 的最优策略为由图可见局中人II的混合策略只有2和3组成。第25页/共33页设局中人II的最优混合策略为 ，且P365 例10图解法 求局中人II的最优混合策略。同理，可得局中人II的赢得，1:v21=3y2+11y32:v22=5y2+2y3画出赢得线段，见右图0 1 y y*3 111 5 2 2局中人I理性，局中人II取最大损失的最小值联立方程组可得解得第26页/共33页方程组法定理：设 ，则 为G的解的充要条件是：存在数v，使得x*,y*分别是下列不等式组的解，且v=VG。若xi*,
9、yj*均不为0，则上述不等式的求解即可转化为下列两个方程组的求解问题。注：若上述两个方程组存在非负解x*,y*，即矩阵对策的解。若不存在非负解，则将上述方程组中的某些等式转化为不等式，继续求解。由于事先假设xi*,yj*均不为0，故，当最优策略的某些分量为0时，方程组可能无解，因此该方法具有一定的局限性。第27页/共33页方程组法例：求解矩阵对策G=,其中A为解：（1）删除劣势策略，得到无鞍点和（2）构造方程组第28页/共33页线性规划法注：适用于所有aij0 若存在aij0，可取一充分大的M0，使得M+aij0第29页/共33页线性规划法例：两人“石头、剪刀、布”矩阵对策求解解：(X*，Y*)为矩阵对策的解第30页/共33页作业P386 习题12.512.612.7第31页/共33页Q&A第32页/共33页感谢您的观看！第33页/共33页