运筹学对策论(一)1对策论的基本概念 一 对策行为和对策论 1对策行为： 具有竞争或对抗性质的行为称为对策 行为。 对策行为的实例：下棋 打牌 体育比赛等。战争在战争活动中的双方，都力图选取对自 己最为有利的策略，千方百计去战胜对手。政治国际的谈判，各种政治力量之间的斗争 ，各国际集团之间的斗争等都具有斗争的性质。经济各国之间，各公司企业之间的各种经济 谈判，企业之间为争夺市场而进行的竞争。2对策论对策论是研究对策行为中斗争各方是否存在着最 合理的行动方案，以及如何找到这个合理的行动方案 的数学理论和方法。对策论也称为竞赛论或博奕论。经典的对策论研究的例子：“齐王賽马”战国时期，齐王有一天提出要与田忌进行賽马。 双方约定：从各自的上中下三个等级马中各选一匹参 赛，每匹均只能参赛一次，每次比赛双方各出一匹马 ，负者要付给胜者千金。已知：在同等级的马中，田 忌的马不如齐王的马，而如果田忌的马比齐王的马高 一等级，则田忌的马可取胜。 双方如何取胜？根据条件可看出，两人各采取什么的样出马顺序 对胜负是至关重要的。二 对策行为的三个基本要素1局中人在一个对策行为中，有权决定自己行动方案的 对策参加者，称为局中人。通常用I表示局中人的集 合。如果n个局中人，则I=1，2，n。说明：对策中关于局中人的概念是具有广义性的。 局中人除了可理解为个人外，还可以理解为一集体 ，如球队 交战国 企业等，以及研究自然界中某 个现象时，可把这个现象看成一个局中人。在对策中总是假定每一个局中人都是“理智的 ”决策者或竞争者。即对任一局中人来讲，不存在利 用其它局中人决策的失误来扩大自身利益的可能性 。2策略集策略策略集如：在“齐王赛马”中，如果用（上，中，下）表 示以上马 中马 下马依次参赛这样一个次序，这就 是一个完整的行动方案，即为一个策略。一局对策中，可供局中人选择的一个实际可行 的完整的行动方案，称为一个对策。设i为局中人，i的所有策略构成的集合Si称为i的 策略集。3赢得函数局势: 在一局对策中，各局中人所选定的策略形 成的策略组称为一个局势。即若设si是第i个局中人的 一个策略，则n个局中人的策略组s=s1， s2， sn 就是一个局势。全体局势的集合S可用各局中人策略集的笛卡尔 乘积表示，即S=S1 S2 Sn赢得函数：当局势出现后，对策的结果也就确定 了。也就是说，对任一局势sS，局中人i可以得到 一个赢得Hi(s)。显然， Hi(s)是局势s的函数，称之为第i局中人的 赢得函数。当局中人，策略，赢得函数三个因素确定后，一 个对策模型也就给定了。再如：2 =（上，下，中）， 1 =（上，中，下 ），则在局势s21下齐王的赢得值H1(s21)=1，田忌的赢 得值H2(s21)= 1。如此等等.如：在“齐王赛马”中，局中人集合I=1，2，齐 王和田忌的策略集可分别用S1=1， 2， 3 ， 4 ， 5 ， 6和S2=1 ， 2， 3 ， 4 ， 5 ， 6表示。 这样，齐王的一个策略i和田忌的一个策略 j就决定 了一个局势sij 。 如果1 =（上，中，下）， 1 =（上 ，中，下），则在局势s11下齐王的赢得值H1(s11)=3， 田忌的赢得值H2(s11)= 3。三 对策的分类对 策静 态 对 策动 态 对 策结 盟 对 策不 结 盟 对 策联合对策合作对策有 限无 限二人多人零和非零和零和非零和二人多人零和非零和零和非零和微分对策等重点 学习 的对 策。2矩阵对策的基本定理 一 矩阵对策的数学模型 1二人有限零和对策： 是指有两个参加对策的局中人 ，每个局中人都只有有限个策略可供选择，在任一局 势下，两个局中人的赢得之和总等于零。2矩阵对策：就是二人有限零和对策。 3矩阵对策模型设 分别表示两个局中人，且它们的纯策略 集分别为S1=1,2, ,m和S2= 1, 2, , n。记局 中人对任一纯局势（ i, j ）的赢得值为aij,并称a11 a12 a1n. . .am1 am2 amnA为局中人的赢得矩阵。局中人的赢得矩阵为 A。3矩阵对策模型设 分别表示两个局中人，且它们的纯策略 集分别为S1=1,2, ,m和S2= 1, 2, , n。记局 中人对任一局势（ i, j ）的赢得值为aij,并称a11 a12 a1n. . .am1 am2 amnA为局中人的赢得矩阵。由于假定对策为零和，所以局中人的赢得矩阵 为A。当局中人 和策略集S1 S2及局中人的赢 得矩阵A确定后，一个矩阵对策就确定了。通常，将矩阵对策记成G=，；S1 ， S2；A 或G=S1 ， S2；A 。4局中人如何选取对自己最有利的纯策略？ 局中人的“理智行为” ：双方都不想冒险，都不存在侥 幸心理，而是考虑到对方必然会设法使自己的所得最小 ，从各自可能出现的最不利的情形中选择一种最为有利 的情形作为决策的依据。 选择原则： 局中人按最大最小原则，局中人按最 小最大原则。即局中人从所有最小的赢得中选择最 大的赢得的策略，局中人从所有最大的损失中选择 最小的损失的策略。 例1 设有一矩阵G=S1 ， S2；A，其中S1=1,2, 2, 4和S2= 1, 2, 3 局中人的赢得矩阵为 6 1 83 2 4 9 2 10A= 3 0 6求出局中人 的最优策略 。例1 设有一矩阵G=S1 ， S2；A，其中S1=1,2, 2, 4和S2= 1, 2, 3 局中人的赢得矩阵为 6 1 83 2 4 9 2 10A= 3 0 6求出局中人 的最优策略 。 解：根据选择的原则，分析局中人的选择的策略局中人的策略 ：纯策略1,2, 2, 4可能带来的最小 赢得分别 8，2， 10， 3 所以，最小赢 得中最大的值为2。因此局中人的策略应为2 局中人的策略 ：纯策略 1, 2, 3可能带来的最大 损失分别9，2，6 。所以，最大损失中最小的值为2 。因此局中人的策略应为 2 。 总之，局中人 的最优察纯策略分别为2 ， 2。5矩阵对策的解定义1 设G=S1 ， S2；A为矩阵对策，其中 S1=1,2, ,m，S2= 1, 2, , n ， A=（aij）mn 若等式成立，记VG= ai*j* 。则称VG为对策G的值，称上 述等式成立的纯局势（ i* , j* ）为G在纯策略下的 解（或平衡局势）， i*与 j*分别称为局中人 的最优纯策略。根据定义1可知，例1中（ 2 , 2 ）是在纯策略 下的解。对策值VG=a22=2 ，i*=2，j*=2 。max min aij=min max aij =ai*j*ijji定理的直观解释：如果ai*j*既是矩阵A=(aij)mn中 第i*行的最小值，又是第j*列的最大值，则ai*j*是对策 的值，且( i* , j* )是在纯策略意义下的解。定理的对策意义：一个平衡局势( i* , j* )具有 这样的性质，当局中人 选择了纯策略 i* 后，局中 人为了其所失 最小，只能选择 j* ，否则就可能失 去更多；反之，当局中人 选择了纯策略 j* 后，局 中人为了得到 最大的赢得，只能选择 i* ，否则就 会赢得更少 。双方在局势( i* , j* )下达到一个平衡 状态。定理1 矩阵对策G=S1 ， S2；A在纯策略意义下有解 的充要条件是：存在纯局势（ i* , j* ）使得对一切 i=1,2, ,m, j=1,2, ,n, 均有aij* ai*j* ai*j 。定理1的一个等价命题：定义2 设f(x,y)为一个定义在xA ,yB上的实值 函数，如果存在x* A,y* B,使得对一切xA ,yB ， 有f(x,y*) f(x*,y*) f(x*,y) , 则称(x*,y*) 为函数 f(x,y)的一个鞍点。定理1的等价命题：矩阵对策G在纯策略意义下有 解，且VG=ai*j*的充要条件是： ai*j*是矩阵A的一个鞍 点(也称为对策的鞍点)。