（精）矩阵对策论.ppt

定理14-2：矩阵对策 G = S1，S2；A 在混合策略意义下有解的充分必要条件是： 存在混合局势（ X*，Y*），使得对一切 X? S1* Y ? S2*均有 E（X，Y*） ? E（X*，Y*） ? E（X*，Y） 定理14-3：对给定的矩阵对策 G = S1，S2；A 设X*? S1* Y* ? S2*则混合局势（ X*，Y*）是G的解且V=VG*的充分必要条件是： 对一切 i,j均有 E（ ?i， Y*） ? V ? E（X*， ?j ） 定理14-4：任意一个给定的矩阵对策在混合策略意义下一定有解。 矩阵对策的解可能不只一个，但对策值是唯一。 例14-5（订货计划）某厂制造和销售一种新仪器，需要外购一种配件。现有三个厂生产这种配件，牌号为A，B，C。 A配件每只10元，但有次品，装配的仪器也是次品，每台损失100元；B配件每只55元，也有次品，但装配的仪器出售后可在保修期内稍加修理就能使用，修理费55元； C配件每只118元，没有次品；问该厂应如何购置各种配件，使总费用（包括损失费和修理费）最少？ 例14-6（费用分摊问题）假设沿某河流有相邻的三个城市：A，B，C。各城市都想建立自来水厂解决用水问题。各城市可单独建立自来水厂，也可以合作建一个大水厂，再用管道送到各城市。经估计，合作建一个大水厂比单独建三个自来水厂的总费用少。三个城市有意合作，但是否实施，看总费用的分摊是否合理。问题是如何合理分摊费用，使合作建立大水厂的方案得以实现。 例14-7（拍卖问题）拍卖形式是先由拍卖商对拍卖品描述一番，然后提出第一个报价。接下来由买者报价，每一次都比前次高，最后谁出的价格高拍卖品即归谁所有。假设报价为p1,p2… pn-1 , pn,设p1p2 … pn-1 pn.买主只要略高于 pn-1就能买到。问题是，各买主之间可能知道他人的估价，也可能不知道他人的估价，每人应如何报价对自己能以较低的价格得到拍卖品最为有利？ 例14-8（囚犯难题）设有两个嫌疑犯被警察拘留，警察分别对两人进行审讯。根据法律，如果两人都承认此案是他们干的，则每人各判刑7年；如果两人都不承认，则由于证据不足，两人各判刑1年； 如果只有一人承认，则承认者以宽大处理，当场释放，而不承认者判刑9年。因此，对两个囚犯来说，面临着一个“承认”和“不承认”之间两个策略的选择的难题。 14-2 矩阵对策的解法 一、 m*n 矩阵对策的线性规划法 求解矩阵对策可以等价地转化成求解互为对偶的线性规划问题 对给定的赢得矩阵 A=(aij)mn 转化成两个互为对偶的线性规划问题 ( LP) min ? pi ? pi aij ? 1 i pi ? 0(i=1,2,….. m) ( DLP) max ? qj ? qj aij ? 1 j qj ? 0(j=1,2,….. n) 且 ? pi = ? qj = 1/ V * 第十四章 对策论 对策论概论 对策论（The Game Theory)也称竞赛论或博弈论，是研究具有竞争、对抗、利益分配等方面的数量化方法，并提供寻求最优策略的途径。 1944年以来，对策论在投资分析、价格制定、费用分摊、财政转移支付、投标与拍卖、对抗与追踪、国际冲突、双边贸易谈判、劳资关系以及动物行为进化等领域得到广泛应用。 14-1矩阵对策的基本概念 案例：俾斯麦海的海空对抗 1943年2月，第二次世界大战中的日本，在太平洋战区已经处于劣势。为扭转局势，日本统帅山本五十六大将统率下的一支舰队策划了一次军事行动：由集结地——南太平洋的新不列颠群岛的蜡包尔出发，穿过俾斯麦海，开往新几内亚的莱城，支援困守在那里的日军。 当盟军获悉此情报后，盟军统帅麦克阿梭命令太平洋战区空军司令肯尼将军组织空中打击。 日本统帅山本五十六大将心里很明白： 在日本舰队穿过俾斯麦海的三天航行中，不可能躲开盟军的空中打击，他要策划的是尽可能减少损失。 日美双方的指挥官及参谋人员都进行了冷静的思考与全面的谋划。 自然条件对于双方 都是已知的。基本情况如下：从蜡包尔出发开往莱城的海