运筹学课件第六章对策论基础

1、 概论基本概念与名词对策分类 矩阵对策的基本理论矩阵对策的数学模型最优纯策略混合策略与混合扩充 基本概念与名词 对策分类博弈现象下棋与打牌体育比赛战争市场进入谈判生产管理决策竞拍 博弈论是研究博弈现象的规律的数学理论和方法 博弈现象的要素局中人（参与人） 二人或多人行动与策略有限或无限信息完全或不完全支付函数可正可负 局中人 策略与策略集 局势 赢得函数 零和对策 矩阵对策：二人有限零和对策一）按对策双方是否存在有约束力的协议来分：合作对策非合作对策二）按局中人数分类：二人对策多人对策三）按策略数分类：有限策略对策无限策略对策 二人非合作对策是我们讨论的重点。 非合作博弈的进一步分类非合作博弈

2、零和博弈 纯策略博弈 混合策略博弈 非零和博弈 完全信息博弈 w 静态博弈 w 动态博弈 不完全信息博弈 w 静态博弈 w 动态博弈 非零和的四种博弈也可以有纯策略和混合策略博弈之分。 动态时行动和策略不同，要素有五个；而静态时行动与策略不加区别，要素有三个。 矩阵对策的数学模型矩阵对策的数学模型 最优纯策略最优纯策略 混合策略与混合扩充混合策略与混合扩充一、矩阵对策的数学模型一、矩阵对策的数学模型 以齐王赛马为例说明齐王赛马二人非合作零和对策 局中人齐王和田忌 策略 上 中下三种等级的马的组合 ，比三次，有六组策略：( 上，中，下) 、 ( 中，上，下) 、 ( 上，下，中) 、 ( 中，下

3、，上) 、 ( 下，上，中) 、 ( 下，中，上) . 对齐王，这六组策略用 表示， 对田忌，则用 表示。 支付函数赢了得一千金，输了付一千金。6 , 5 , 4 , 3 , 2 , 1, ii6 , 5 , 4 , 3 , 2 , 1, ii齐王赛马赢得函数31111-11311-111-13111-11131111-1131111-113 (上中下) (上下中)齐 (中上下)王 (中下上) (下中上) (下上中)田 忌654321654321 二人矩阵对策用下列式子表示 其中I、II表示两个局中人，S1、S2分别表示局中人I、II的策略集，A则表示赢得矩阵：ASSGASSIIIG,2121

4、或)(ijaA 现有一矩阵对策 其中ASSG,216104801213936,4321321321243211ASS 若满足 则上述条件规定的局势 叫做最优纯局势，也是矩阵对策的最优解，是局中人I、II的最优纯策略。 定理：矩阵对策G=S1,S2,A有纯策略解的充要条件是存在一个纯局势 使得maxminminmaxijijijjiaa),(*ji),(*jinjmiaaajijiij, 2 , 1;, 2 , 1,* 在上述定理中 因此符合条件 的即为最优纯策略。 上述例子的最优纯策略为：最优局势 且G=2为局中人I的赢得值。)(max),(min*ijijiijjijaaaa)(min)(m

5、ax*jijijiaa),(22 基本概念：当 时不存在最优纯策略，此时需要应用混合策略的方法确定参加对策的纯策略。 例如maxminminmaxijijijjiaaASSG,212431,2121212211ASS 因为 所以 此时假设局中人I以概率x选取策略1，以概率(1-x)选取策略2；局中人II以概率y选取策略1，以概率(1-y)选取策略2。则对于局中人I来说，赢得的期望值为E(x,y)，它等于3maxmin, 2minmaxijijijjiaamaxminminmaxijijijjiaa 赢得期望值 在x=1/2，y=1/4时，赢得函数取得最优值5/2。这实际上是对策双方都满意的结果

6、。我们把纯策略对应的概率向量叫做混合策纯策略对应的概率向量叫做混合策略略，最优解则是最优混合策略。本例中，最优混合策略是(1/2,1/2)和(1/4,3/4)。2/5)4/1)(2/1(42/52/124)1)(1 (2)1 (4)1 (3),(yxyxxyyxyxyxxyyxE 令纯策略集对应的概率向量是 它们满足 混合策略的集合 将 叫做G的混合扩充。),(),(2121nmyyyYxxxX11, 2 , 1;, 2 , 1, 0,11njjmiijiyxnjmiyx,*2*1YSXS,*2*1*ESSG 若令 并有 则称(X*,Y*)为最优混合局势，或叫做G在混合策略下的解，V叫做对策G

7、的值。X*、Y*分别是局中人I、II的最优混合策略。),(min),(),(max),(*2*1*YXEYXEYXEYXESYSXVYXEYXESXSY),(max),(min*1*2 如果G的值是V，则局中人I和II的最优策略是下列两组不等式的解： 关于混合对策问题的解，我们有如下定理：0, 1, 2 , 1,11imiimiiijxxnjVxa0, 1, 2 , 1,11jnjjnjjijyymiVya 如果(X*,Y*)是对策G的最优混合局势，则对于某个i或j来说，有：0,)4(0,) 3(0)2(0) 1 (*1*1*1*1*jmiiijinjjijmiiijjnjjijiyVxaxV

8、yaVxayVyax则若则若，则若，则若 对于G=S1,S2,A38806678649593795205030435432154321A 划去普遍较小的行，例如第1、2行，得 划去普遍较大的列，例如第3、4、5三列，结果如上。46987580686493754354321A06364754321A 上述结果的第一行比第三行普遍更优，因此再划去第三行，得 若混合策略均不为零，由上述定理知混合对策问题数学模型的不等式应为等式。因此有64374321A 最优混合策略满足如下方程组 解得0,1634743434343xxxxVxxVxx0,1643721212121yyyyVyyVyy5, 2/1, 2/1; 3/2, 3/12143Vyyxx5)0 , 0 , 0 , 2/1 , 2/1 ()0 , 3/2 , 3/1 , 0 , 0(VYXTT记T(G)为矩阵对策G的解集定理1 设有两个矩阵对策 G1=S1,S2,A1， G2=S1,S2,A2， 其中A1=(aij)， A2=(aij+L)， L为一任意常数，则 (G)T(G)T )2( ) 1 (2112LVVGG 定理2 设有两个矩阵