运筹学模型与软件求解.ppt

运筹学模型与软件求解 中国科学院研究生院 2.矩阵对策的最优纯策略 3.矩阵对策的混合策略 * * Models and Software Solutions of the Operations Research 第九章　 对策模型与试验 对策论的基本概念 混合对策 线性规划方法解（m*n）对策 概 论 名称 Game Theory 博奕论 发展历史 对策论模型 例 子 发 展 简 史 早期工作 1912年E.Zermelo ‘关于集合论在象棋对策中的应用’ 1921年E.Borel 引入最优策略 1928年J.V.Neumann证明了一些猜想 产生标志 1944年J.V.Neumann和O.Morgenstern”对策论与经济行为” 发展成熟 Nash均衡、经济博奕论、信息不对称对策和广义对策 由“齐王赛马”引入 三个基本要素 1.局中人：参与对抗的各方； 2.策略集：局中人选择对付其它局中人的行动方案称为策略。 某局中人的所有可能策略全体称为策略集； 3.局势对策的益损值：各局中人各自使用一个对策就形成一个局势，一个局势决定了个局众人 的对策结果（量化）称为该局势对策的益损值） “齐王赛马”齐王在各局势中的益损值表（单位：千金） 其中： 齐王的策略集: S1={?1,?2,?3,?4,?5,?6} 田忌的策略集：S2={?1,?2,?3,?4,?5,?6} 下列矩阵称齐王的赢得矩阵： 3 1 1 1 -1 1 1 3 1 1 1 -1 A= 1 -1 3 1 1 1 -1 1 1 3 1 1 1 1 1 -1 3 1 1 1 -1 1 1 3 二人有限零和对策：（又称矩阵策略） 局中人为2； 每局中人的策略集中策略个数有限； 每一局势的对策均有确定的损益值，并且对同一局势的两个局中人的益损值之和为零。 记矩阵对策为: G = {S1, S2, A} 甲的策略集 甲的赢得矩阵 乙的策略集 “齐王赛马”即是一个矩阵策略. 在甲方赢得矩阵中： A=[aij]m*n i行代表甲方策略 i=1,2…m J列代表乙方策略 j=1,2…n aij代表甲方取策略i,乙方取策略j,这一局势下甲方的益损值，此时乙方的益损值为-aij（零和性质）。 在讨论各方采用的策略是必须注意一个前提就是对方是理智的。这就是要从最有把握取得的益损值情况考虑。 例：有交易双方公司甲和乙，甲有三个策略?1，?2，?3；乙有四个策略?1，?2，?3，?4，根据获利情况建立甲方的益损值 赢得矩阵。 -3 0 -2 0 A= 2 3 0 1 -2 -4 -1 3 问：甲公司应采取什么策略比较适合？ 甲： 采取?1至少得益–3(损失 3） ?2 0 ?3 -4(损失 4） 乙： 采取?1甲最多得益2 （乙最少得益-2） ?2 3（乙得益-3） ?3 0（乙得益 0） ?4 3（乙得益-3） 取大则取?2 max min aij= 0 i j 取小则取?3 min max aij= 0 j i 甲采取策略?2 不管乙采取如何策略，都至少得益。 乙采取策略?3 不管甲采取如何策略， 都至少可以得益。（最多损失0） 分别称甲，乙公司的最优策略，由唯一性又称最优纯策略。 存在前提： max min aij = min max aij = v i j j i 又称（ ?2 ，?3 ）为对策G={s1,s2,A} 的鞍点。值V为G的值。 实际应用问题 设矩阵对策 G ={S1,S2,A} 当 max min aij ? min max aij i j j i 时，不存在最优纯策略