运筹学--对策论.ppt

第十四章对策论,对策论概论对策论（TheGameTheory)也称竞赛论或博弈论，是研究具有竞争、对抗、利益分配等方面的数量化方法，并提供寻求最优策略的途径。20世纪40年代形成并发展。1944年以来，对策论在投资分析、价格制定、费用分摊、财政转移支付、投标与拍卖、对抗与追踪、国际冲突、双边贸易谈判、劳资关系以及动物行为进化等领域得到广泛应用。,14-1矩阵对策的基本概念案例：俾斯麦海的海空对抗1943年2月，第二次世界大战中的日本，在太平洋战区已经处于劣势。为扭转局势，日本统帅山本五十六大将统率下的一支舰队策划了一次军事行动：由集结地南太平洋的新不列颠群岛的蜡包尔出发，穿过俾斯麦海，开往新几内亚的莱城，支援困守在那里的日军。,当盟军获悉此情报后，盟军统帅麦克阿梭命令太平洋战区空军司令肯尼将军组织空中打击。日本统帅山本五十六大将心里很明白：在日本舰队穿过俾斯麦海的三天航行中，不可能躲开盟军的空中打击，他要策划的是尽可能减少损失。日美双方的指挥官及参谋人员都进行了冷静的思考与全面的谋划。,自然条件对于双方都是已知的。基本情况如下：从蜡包尔出发开往莱城的海上航线有南北两条。通过时间均为3天。气象预报表明：未来3天中，北线阴雨，能见度差；而南线天气晴好，能见度好。肯尼将军的轰炸机布置在南线的机场，侦察机全天候进行侦察，但有一定的搜索半径。,经测算，双方均可得到如下估计：局势1：盟军的侦察机重点搜索北线，日本舰队也恰好走北线。由于气候恶劣，能见度差，盟军只能实施两天的轰炸。局势2：盟军的侦察机重点搜索北线，日本舰队走南线。由于发现晚，尽管盟军的轰炸机群在南线，但有效轰炸也只有两天。,局势3：盟军的侦察机重点搜索南线，而日本舰队走北线。由于发现晚、盟军的轰炸机群在南线，以及北线气候恶劣，故有效轰炸只有一天。局势4：盟军的侦察机重点搜索南线，日本舰队也恰好走南线。此时日本舰队迅速被发现，盟军的轰炸机群所需航程很短，加上天气晴好，有效轰炸时间三天。,这场海空遭遇与对抗一定会发生，双方的统帅如何决策呢？历史的实际情况是：局势1成为现实。肯尼将军命令盟军的侦察机重点搜索北线；而山本五十六大将命令日本舰队取道北线航行。由于气候恶劣，能见度差，盟军飞机在一天后发现了日本舰队，基地在南线的盟军轰炸机群远程航行，实施了两天的有效轰炸，重创了日本舰队，但未能全歼。,对策的三要素：局中人：有权决定自己行为方案的对局参加者称为局中人。案例中，美日双方的决策者为局中人。当对局中局中人只有两人时，称为二人对策。策略：对局中一个实际可行的方案称为一个策略。案例中，美日双方各有二个策略。,赢得矩阵（支付）：当每个局中人在确定了所采取的策略后，他们就会获得相应的收益或损失，此收益或损失的值称为赢得（支付）。赢得与策略之间的对应关系称为赢得（支付）函数。案例中，肯尼将军与山本五十六大将的赢得（支付）函数都可以用矩阵A、B表示。,（日军）北线南线（盟军）北线22=A南线13（盟军）北线南线（日军）北线-2-2=B南线-1-3,在本例中的每一个对局，双方的赢得的代数之和为零，这样的对策称为“有限零和二人对策”设两个局中人为I，II，局中人I有m个策略：1、2m；用S1表示这些策略的集合：S1=1、2m,同样，局中人II有n个策略：1、2。n；用S2表示这些策略的集合：S2=1、2n局中人I的赢得矩阵是：a11a12a1na21a22a2nA=am1am2amn,局中人II的赢得矩阵是-A把一个对策记为G：G=S1，S2；A北线1南线2（盟军）北线122=A南线213,在矩阵中，盟军的最大赢得是3，而要得到3，必须选择策略2，而日军的目的是使盟军的赢得尽量的小，必须选择策略1，使盟军的赢得只有1。在局中人I设法使自己的赢得尽可能大的同时，局中人II也设法使局中人I的赢得尽可能小。,所以局中人I应首先考虑用所能赢得的最小，然后在这些最小赢得中选择最大。局中人I可以保证赢得maxminaijij同样，局中人II可以保证局中人I的赢得不超过minmaxaijji,案例中局中人I（盟军）应当选择（北线）策略1，这样能保证赢得2。局中人II（日军）应当选择（北线）策略1使盟军赢得不超过2。实际上，在（1，1）局势下，有maxminaij=minmaxaijijji上式蕴涵的思想是朴素自然的，可以概括为：“从最坏处着想，去争取最好的结果”,定义14-1：对给定的矩阵对策G=S1，S2；A若等式maxminaij=minmaxaijijji成立，则称这个公共值为对策G的值，记为VG，而达到的局势（i，j）称为对策G在纯策略意义下的解，记为（I*，j*）而I*和j*分别称为局中人I和局中人II的最优纯策略。,定理14-1：矩阵对策G=S1，S2；A在纯策略意义下有解的充分必要条件是：存在一个局势（*i*，*j*），使得对一切i=1，2，m，j=1，2n均有aij*=ai*j*=ai*j,定理14-1表明矩阵对策G=S1，S2；A有解的充分必要条件是在A中存在元素ai*j*是其所在行中最小的同时又是其所在列中最大的。这时ai*j*即是对策值，因此ai*j*也称为“鞍点”，而（*i*，*j*），为对策的解。,X,Y,马鞍面z=f(x,y),鞍点,Z,Y,Z,在X=0的平面上鞍点是z=f(0,y)的极大值点,z=f(0,y),X,Z,在Y=0的平面上鞍点是z=f(x,0)的极小值点,z=f(x,0),例14-3：对给定的矩阵对策G=S1,S2;AS1=1,2,3,4S2=1,2,3,4min65655*maxA=142-1-185755*max02620max85*75*minmin显然ai2a12a1jai2a32a3j对i=1,2,3,4j=1,2,3,4都成立：a12=a32=5由定理5-1，对策值=5，对策的解(1,2）,（3,2）,（1,4）,（3,4）,例14-4：某单位采购员在秋天时要决定冬天取暖用煤的采购量。已知在正常气温条件下需要用煤15吨，在较暖和较冷气温条件下需要用煤10吨和20吨。假定冬季的煤价随着天气寒冷的程度而变化，在较暖、正常、较冷气温条件下每吨煤价为100元、150元、200元。又秋季每吨煤价为100元。在没有关于当年冬季气温情况下，秋季应购多少吨煤，能使总支出最少？,解：局中人I（采购员）有三个策略：策略1:10吨,策略2:15吨,策略3:20吨。局中人II（环境）：策略1较暖,策略2正常，策略3较冷现把该单位冬天取暖用煤全部费用（秋季购煤费用与冬天不够时再补购煤费用）作为采购员的赢得矩阵。,1较暖2正常3较冷1(10)-1000-1750-30002(15)-1500-1500-25003(20)-2000-2000-2000maxminaij=minmaxaij=a33=-2000Ijji该最优策略为（3，3），即秋季购煤20吨。,已知在正常气温条件下需要用煤15吨，在较暖和较冷气温条件下需要用煤10吨和20吨。在较暖、正常、较冷气温条件下每吨煤价为100元、150元、200元。又秋季每吨煤价为100元。,练习：“二指莫拉问题”，甲乙两人游戏，每人出一个或两个手指头，同时又把猜测对方所出的手指数叫出来，若只有一个人猜测正确，则他所赢得数为二人所出手指之和，否则，重新开始。写出该对策各局中人的策略集合及甲的赢得矩阵，并回答局中人是否存在某种出法比其他出法更为有利。,解：表示自己出个手指，猜测对方出个手指。,练习：“二指莫拉问题”，甲乙两人游戏，每人出一个或两个手指头，同时又把猜测对方所出的手指数叫出来，若只有一个人猜测正确，则他所赢得数为二人所出手指之和，否则，重新开始。写出该对策各局中人的策略集合及甲的赢得矩阵，并回答局中人是否存在某种出法比其他出法更为有利。,赢得矩阵为,14.2矩阵对策的混合策略定义:对给定的矩阵对策G=，；S1,S2;A其中S1=1,2mS2=1,2nA=(aij)mn把纯策略集合对应的概率向量X=(x1,x2xm)其中xi0xi=1和Y=(y1,y2yn)其中yj0yj=1分别称为局中人I和局中人II的混合策略。,如果局中人I选取的策略为X=(x1,x2xm)局中人II选取的策略为Y=(y1,y2yn)，则期望值E（X，Y）=xiaijyj=XAYT称为局中人I期望赢得，而局势（X，Y）称为“混合局势”，局中人I，II的混合策略集合记为S1*，S2*。,定义14-3:对给定的矩阵对策G=S1,S2;A则对策G*=S1*,S2*;E称为对策G混合扩充。纯策略是混合策略的一个特例。例如：局中人的纯策略等价于混合策略其中，,定义14-4:设G*=S1*,S2*;E是对策G混合扩充，如果有maxminE(X,Y)=minmaxE(X,Y)XS1*YS2*YS2*XS1*则称这个公共值为对策G在混合意义下的值，记为V*G，而达到V*G的混合局势（X*，Y*）称为对策G在混合策略意义下的解，而X*和Y*分别称为局中人I，II的最优混合策略。,定理14-2：矩阵对策G=S1，S2；A在混合策略意义下有解的充分必要条件是：存在混合局势（X*，Y*），使得对一切XS1*YS2*均有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*）VE（X*，j）证明：必要性：因为纯策略是混合策略的特例，故成立充分性：当局中人取纯策略时，当局中人取纯策略时，,则已知E（i，Y*）VE（X*，j）所以故定理3把无限个不等式的证明转化为对有限个（mn)个不等式的证明问题。,定理14-4：设，则为的解的充要条件：存在数使得分别是不等式组（）和（）的解。,证明：由定理3，（X*，Y*）是G的解且V=VG*的充分必要条件是：对一切i,j均有E（i，Y*）VE（X*，j）即（）和（）成立。,定理14-5：任意一个给定的矩阵对策在混合策略意义下一定有解。矩阵对策的解可能不只一个，但对策值是唯一。证明：考虑两个线性规划问题,这是两个互为对偶的线性规划问题（P403），,是问题（D）的可行解,故（P）,(D)必有最优解。,是问题（P）的可行解,设最优解分别为，且。即存在有即：E（i，Y*）V*E（X*，j）定理7：对两个矩阵对策，其中为常数，则有分别是局中人、的最优策略集,定理8：对两个矩阵对策，其中为常数，则有定理9：设为一矩阵对策，且则：分别是局中人、的最优策略集定义：设矩阵对策，其中，若，则；若，则。,例：设赢得矩阵为A,求解这个矩阵对策。解：,解方程组：求得：,例（囚犯难题）设有两个嫌疑犯被警察拘留，警察分别对两人进行审讯。根据法律，如果两人都承认此案是他们干的，则每人各判刑7年；如果两人都不承认，则由于证据不足，两人各判刑1年；如果只有一人承认，则承认者以宽大处理，当场释放，而不承认者判刑9年。因此，对两个囚犯来说，面临着一个“承认”和“不承认”之间两个策略的选择的难题。,14-2矩阵对策的解法一、2*2矩阵对策的公式解法对给定的矩阵对策G=S1，S2；AA=(aij)2*2。如果A无鞍点，则局中人I的最优混合策略X*=（x1*，x2*），局中人II的最优混合策略Y*=（y1*，y2*）和对策值VG*由下列公式给出：,x1*=（a22-a21）/Dx2*=（a11-a12）/Dy1*=（a22-a12）/Dy2*=（a11-a21）/DVG*=（a11a22-a12a21）/D,二、m*2或2*n矩阵对策的图解法例：矩阵对策G=S1，S2；A，其中,解：设局中人1的混合策略为局中人1选择时，他的最少可能收入为局中人2选择时，所确定三条直线的纵坐标中最小者，按最小最大原则，,V,7,5,2,1,x,(1),3,(2),11,A,B,(3),O,解方程组：,例：求解赢得矩阵为的矩阵对策。解：局中人2的混合策略为：，按最大最小原则,7,6,2,y,(1),2,(2),11,(3),O,6,A1,B2,A2,B1,例：求解赢得矩阵为的矩阵对策。解：(1)用优超原则,解：(2)用图解法局中人2的混合策略为：,7,5,1,y,(1),2,(2),13/14,(3),O,4,3/4,(4),由方程组确定：,满足方程组的解有无穷多个，故局中人2有无穷多最优解,三、线性方程组方法见书上399页,四、m*n矩阵对策的线性规划法求解矩阵对策可以等价地转化成求解互为对偶的线性规划问题对给定的赢得矩阵A=(aij)mn转化成两个互为对偶的线性规划问题,矩阵对策的解法1.优超原则化简,若有鞍点,则为纯矩阵对策.2.若没有鞍点,赢得矩阵为22阵.用公式法3.赢得矩阵为2n,或m2阵.用图解法4.方程组法5.线性规划法3.2线性规划法,定理14-4：设，则为的解的充要条件：存在数使得分别是不等式组（）和（）的解。,例：利用线性规划方法求解矩阵对策,同理,解：求解矩阵对策可化为两个互为对偶的线性规划问题,把（2）变为标准型：,例14-9对给定的赢得矩阵A01-1231A=-101A，=1231-10312A，=（aij+2）,（LP）min（p1+p2+p3）2p1+p2+3p313p1+2p2+p31p1+3p2+2p31pi0(i=1,2,3),(DLP)max（q1+q2+q3）2q1+3q2+q31q1+2q2+3q313q1+q2+2q31qj0(j=1,2,3)且pi=qj=1/V,利用单纯形法可求出：P*=（1/6，1/6，1/6）Q*=（1/6，1/6，1/6）p1+p2+p3=1/6+1/6+1/6=1/2=1/VV=2原问题的解：X*=VP*=（1/3，1/3，1/3）Y*=VQ*=（1/3，1/3，1/3）对策值VG*=V-2=0,例14-10对给定的赢得矩阵A729A=2909011,（LP）min（p1+p2+p3）7p1+2p2+9p312p1+9p219p1+11p31pi0(i=1,2,3),(DLP)max（q1+q2+q3）7q1+2q2+9q312q1+9q219q1+11q31qj0(j=1,2,3)且pi