资源描述：
《运筹学第八章对策论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第八章对策论对策论概述对策论(GameTheory)亦称博弈论，是研究具有竞争、对抗、利益分配等方面的数量化方法，并提供寻求最优策略的途径。对策论的理论形成于1944年，经过60多年的发展，现已成为运筹学的一大分支，在投资分析、价格制定、费用分摊、财政转移支付、投标与拍卖、对抗与追踪、国际冲突、双边贸易谈判、劳资关系以及动物行为进化等领域都有广泛应用。案例1：对一种产品，仅甲、乙两厂有能力生产。现在这两厂都想通过内部改革挖掘潜力，以获得更多的市场份额。已知两厂分别都有三个行动措施，据预测，当双方采取不同的
2、行动方案后，甲厂的市场占有份额变动情况见下表。问：甲、乙两厂各自最好的行动方案是什么？案例2：战国时，齐王和他的大将田忌赛马。双方约定，从各自的上、中、下三个等级的马中各选出一匹，比赛时，双方选出的每匹马都轮流参加，输者付给胜者一千金。现在齐王的同等马都比田忌的强，问：田忌有无取胜的可能？如果有，应采用的方案是什么？如果双方同等聪明，那么，为了达到最好的效果，双方应该怎么做？这两个问题都涉及到竞争性，因此都属于对策问题。局中人：有权决定自己行为方案的对策参加者称为局中人。案例1中，局中人是甲、乙两厂，案例
3、2中，局中人是田忌和齐王。有两个局中人的对策称为二人对策。策略：对策中一个实际可行的方案称为一个策略。案例1中，甲、乙两厂各有三个策略。局中人所有可行方案的集合称为策略集。赢得矩阵（支付）：当每个局中人在确定了所采取的策略后，他们就会获得相应的收益或损失，此收益或损失的值称为赢得（支付）。赢得与策略之间的对应关系称为赢得（支付）函数。对策的三要素矩阵对策的模型矩阵对策即二人有限零和对策。“二人”是指参加对策的局中人有两个；“有限”是指每个局中人的策略集均为有限集；“零和”是指在任一局势下，两个局中人的赢得
4、之和总等于零，即一个局中人的所得值恰好等于另一局中人的所失值，双方的利益是完全对抗的。上述两个案例均为矩阵对策。如案例2中，双方策略集同为{（上,中,下）,（上,下中）,（中,上,下）,（中,下,上）,（下,中,上）,（下,上,中）},为了区别，相应地记为和，则局中人，即齐王的赢得矩阵为一般地，用和分别表示两个局中人，并设局中人和的策略集分别为，局中人的收益矩阵为A,则矩阵对策的模型记为.纯策略矩阵对策定义1：设为矩阵对策，其中，若等式成立，称为的值，记作,称分别为相应局中人的最优(纯)策略；而称局势()
5、为的解。定理1矩阵对策在纯策略意义下有解的充要条件是。证：充分性:由可以得到。又因为和，于是有。容易证明，对于任意矩阵A，都有。综上得，即。必要性：设在达到最大，而在时达到最小，即，由于定义有，可得所以对于一切，有。定理得证。【例1】设有矩阵对策，其中局中人的收益矩阵为求解。解：由得又已知得。从而。所以局中人的最优策略为，局中人的最优策略为，而的解为或,的值。从上例可以看出，对策的解可能不唯一，但对策的值是唯一的。一般地，最优策略有以下性质（1）无差别性：若（2）可交换性：若混合策略矩阵对策定理1表明:矩
6、阵对策有解的充分必要条件是在A中存在元素是其所在行中最小的同时又是其所在列中最大的。这时即是对策值，因此也称为“鞍点”。但一般的来说，这样的可能不存在，请看下例。XY马鞍面z=f(x,y)鞍点Z在X=0的平面上鞍点是z=f(0,y)的极大值点YZz=f(0,y)XZ在Y=0的平面上鞍点是z=f(x,0)的极小值点z=f(x,0)【例2】在矩阵对策中，若,则显然二者不等，因此，在纯策略意义下，此对策无解。在这种情况下，一个比较自然的想法是：既然局中人没有最优策略可出，是否可以给出一个选择不同策略的概率分布，
7、并用期望值代替对策值？事实上，我们有下面矩阵对策的混合扩充。定义2：设有矩阵对策,其中,记则称,分别为局中人和的混合策略集，分别称为局中人和的混合策略。对于，称(x,y)为一个混合局势（或局势）。局中人的收益为如下形式的期望这样得到的新的对策模型记成称为矩阵对策的混合扩充。注：概率可解释为局中人在一局对策中，对各个纯策略的偏爱程度，或解释为在多局对策中,局中人采用纯策略的频率。的解释类似。定义3：设是矩阵对策的混合扩充，如果存在混合局势使得对于一切总有成立，则称分别为局中人和的最优混合策略。称为对策的值，
8、记为。称为对策的解。混合策略矩阵对策理论定理2设是矩阵对策的混合扩充，则为的解的充要条件是存在使得对于一切有定理2可解释为：如果局中人不采用策略而采用其他策略，那么他的收益就会减少；局中人不采用策略而采用其他策略，那么他的损失就会增大。定理3设是矩阵对策的混合扩充，则为的解的充要条件是对于一切都成立。定理4设是矩阵对策的混合扩充，则为的解的充要条件是存在数，使得分别是下列不等式组P,D的解，且。定理5任意矩阵对策在混合策略意义
