运筹学第八章对策论.ppt

第八章 对策论,对策论概述 对策论(Game Theory)亦称博弈论，是研究具有竞争、对抗、利益分配等方面的数量化方法，并提供寻求最优策略的途径。对策论的理论形成于1944年，经过60多年的发展，现已成为运筹学的一大分支，在投资分析、价格制定、费用分摊、财政转移支付、投标与拍卖、对抗与追踪、国际冲突、双边贸易谈判、劳资关系以及动物行为进化等领域都有广泛应用。,案例1：对一种产品，仅甲、乙两厂有能力生产。现在这两厂都想通过内部改革挖掘潜力，以获得更多的市场份额。已知两厂分别都有三个行动措施，据预测，当双方采取不同的行动方案后，甲厂的市场占有份额变动情况见下表。问：甲、乙两厂各自最好的行动方案是什么？,案例2：战国时，齐王和他的大将田忌赛马。双方约定，从各自的上、中、下三个等级的马中各选出一匹，比赛时，双方选出的每匹马都轮流参加，输者付给胜者一千金。现在齐王的同等马都比田忌的强，问：田忌有无取胜的可能？如果有，应采用的方案是什么？如果双方同等聪明，那么，为了达到最好的效果，双方应该怎么做？这两个问题都涉及到竞争性，因此都属于对策问题。,局中人：有权决定自己行为方案的对策参加者称为局中人。案例1中，局中人是甲、乙两厂，案例2中，局中人是田忌和齐王。有两个局中人的对策称为二人对策。策略：对策中一个实际可行的方案称为一个策略。案例1中，甲、乙两厂各有三个策略。局中人所有可行方案的集合称为策略集。赢得矩阵（支付）：当每个局中人在确定了所采取的策略后，他们就会获得相应的收益或损失，此收益或损失的值称为赢得（支付）。赢得与策略之间的对应关系称为赢得（支付）函数。,对策的三要素,矩阵对策的模型,矩阵对策即二人有限零和对策。“二人”是指参加对策的局中人有两个；“有限”是指每个局中人的策略集均为有限集；“零和”是指在任一局势下，两个局中人的赢得之和总等于零，即一个局中人的所得值恰好等于另一局中人的所失值，双方的利益是完全对抗的。上述两个案例均为矩阵对策。,如案例2中，双方策略集同为（上,中,下）,（上,下中）,（中,上,下）,（中,下,上）,（下,中,上）,（下,上,中）,为了区别，相应地记为 和，则局中人，即齐王的赢得矩阵为,一般地，用 和 分别表示两个局中人，并设局中人 和 的策略集分别为，局中人 的收益矩阵为A,则矩阵对策的模型记为.,纯策略矩阵对策,定义1：设 为矩阵对策，其中，若等式 成立，称,为 的值，记作,称 分别为相应局中人的最优(纯)策略；而称局势()为 的解。,定理 1 矩阵对策在纯策略意义下有解的充要条件是。证：充分性:由 可以得到。又因为 和，于是有。容易证明，对于任意矩阵A，都有。综上得，即。,必要性：设 在 达到最大，而 在 时达到最小，即，由于定义有，可得所以对于一切，有。定理得证。,【例1】设有矩阵对策，其中 局中人 的收益矩阵为 求解。解：由 得又已知得。从而。,所以局中人 的最优策略为，局中人 的最优策略为，而 的解为 或,的值。从上例可以看出，对策的解可能不唯一，但对策的值是唯一的。一般地，最优策略有以下性质（1）无差别性：若（2）可交换性：若,混合策略矩阵对策,定理1表明:矩阵对策 有解的充分必要条件是在A中存在元素 是其所在行中最小的同时又是其所在列中最大的。这时 即是对策值，因此 也称为“鞍点”。但一般的来说，这样的 可能不存在，请看下例。,X,Y,在X=0的平面上鞍点是z=f(0,y)的极大值点,【例2】在矩阵对策 中，若,则 显然二者不等，因此，在纯策略意义下，此对策无解。,在这种情况下，一个比较自然的想法是：既然局中人没有最优策略可出，是否可以给出一个选择不同策略的概率分布，并用期望值代替对策值？事实上，我们有下面矩阵对策的混合扩充。,定义2：设有矩阵对策,其中,记则称,分别为局中人 和 的混合策略集，分别称为局中人 和 的混合策略。,对于，称(x,y)为一个混合局势（或局势）。局中人 的收益为如下形式的期望这样得到的新的对策模型记成称 为矩阵对策的混合扩充。注：概率 可解释为局中人 在一局对策中，对各个纯策略的偏爱程度，或解释为在多局对策中,局中人 采用纯策略 的频率。的解释类似。,定义3：设 是矩阵对策的混合扩充，如果存在混合局势 使得对于一切 总有成立，则称 分别为局中人 和 的最优混合策略。称为对策 的值，记为。称 为对策 的解。,混合策略矩阵对策理论,定理 2 设 是矩阵对策的混合扩充，则 为 的解的充要条件是存在 使得对于一切 有 定理2 可解释为：如果局中人 不采用策略 而采用其他策略，那么他的收益就会减少；局中人 不采用策略 而采用其他策略，那么他的损失就会增大。,定理 3设 是矩阵对策的混合扩充，则 为 的解的充要条件是对于一切 都成立。定理 4设 是矩阵对策的混合扩充，则 为 的解的充要条件是存在数，使得 分别是下列不等式组P,D的解，且。,定理 5 任意矩阵对策 在混合策略意义下有解。注：定理4和5给出了矩阵对策的一般求解方法线性规划法。,求解矩阵对策常用的其他两个定理,定理 6 设有两个矩阵对策,其中为任一常数，则其中 分别表示 的解集。,定理 7设有两个矩阵对策,其中 为任一常数，则其中 分别表示 的解集。,矩阵对策的线性规划解法,设矩阵对策 在混合策略下的对值，构造下列两个互为对偶的线性规划问题：令 由定理4和5，问题LP和LD等价于,且。显然 和 仍然是互为对偶的，只需求出其中一个的解，利用对偶关系即可得到另一个的解。最后由，反代就可以得到对策问题的解和值。,当矩阵对策较大时，利用线性规划方法求解计算量就会很大，此时，如果对问题精度要求不是太高，那么，我们可以用下面的迭代法求对策问题的近似解。下面通过例子来介绍这种方法。迭代法的优点是便于用计算机求解，还可以用于多人对策问题的情形；缺点是收敛速度较慢。,矩阵对策的迭代法,1、2 2矩阵对策 所谓2 2矩阵对策是指局中人I的收益矩阵是2阶的，即。当纯策略下无解时，容易证明，各局中人的最优混合策略中的 均大于零。由线性规划解法可以求得对策值和唯一解：，其中。,特殊矩阵对策求解,2、优超降阶法 在求解大型矩阵对策问题时，通常会针对收敛矩阵的特点，采用某种特定的方法将其转化为较小型的问题。优超降阶法就是这样一种方法。定义：设有矩阵对策，其中如果对于一切 都有 则称局中人I的纯策略 优超于；类似地，如果对于一切都有，则称局中人II 的纯策略 优超于。显然，我们可以利用对策的矩阵相应之特点，降低其阶数，从而减少计算量。,其他两种特殊问题,1、设，其中 若符号相同,则 且,其中。,2、设，是 阶方阵，若则 且。,1、某单位采购员在秋天时要决定冬天取暖用煤的采购量。已知在正常气温条件下需要用煤15吨，在较暖和较冷气温条件下需要用煤10吨和20吨。假定冬季的煤价随着天气寒冷的程度而变化，在较暖、正常、较冷气温条件下每吨煤价为100元、150元、200元。又秋季每吨煤价为100元。在没有关于当年冬季气温情况下，秋季应购多少吨煤，能使总支出最少？,几个典型的矩阵对策问题,2、（订货计划）某厂制造和销售一种新仪器，需要外购一种配件。现有三个厂生产这种配件，牌号为A，B，C。A配件每只10元，但有次品，装配的仪器也是次品，每台损失100元；B配件每只55元，也有次品，但装配的仪器出售后可在保修期内稍加修理就能使用，修理费55元；C配件每只118元，没有次品；问该厂应如何购置各种配件，使总费用（包括损失费和修理费）最少？,3、（费用分摊问题）假设沿某河流有相邻的三个城市：A，B，C。各城市都想建立自来水厂解决用水问题。各城市可单独建立自来水厂，也可以合作建一个大水厂，再用管道送到各城市。经估计，合作建一个大水厂比单独建三个自来水厂的总费用少。三个城市有意合作，但是否实施，看总费用的分摊是否合理。问题是如何合理分摊费用，使合作建立大水厂的方案得以实现。,4、（拍卖问题）拍卖形式是先由拍卖商对拍卖品描述一番，然后提出第一个报价。接下来由买者报价，每一次都比前次高，最后谁出的价格高拍卖品即归谁所有。假设报价为p1,p2 pn-1,pn,设p1p2 pn-1 pn.买主只要略高于pn-1就能买到。问题是，各买主之间可能知道他人的估价，也可能不知道他人的估价，每人应如何报价对自己能以较低的价格得到拍卖品最为有利？,5、（囚犯难题）设有两个嫌疑犯被警察拘留，警察分别对两人进行审讯。根据法律，如果两人都承认此案是他们干的，则每人各判刑7年；如果两人都不承认，则由于证据不足，两人各判刑1年；如果只有一人承认，则承认者以宽大处理，当场释放，而不承认者判刑9年。因此，对两个囚犯来说，面临着一个“承认”和“不承认”之间两个策略的选择的难题。,