高级运筹学-第1章：对策论.ppt

1,第1章：对策论,1.1基本概念一、竞争现象各种比赛：体育、棋类等比赛。政治方面：外交谈判。经济方面：贸易谈判，争夺市场，各种经营竞争等。工业生产方面：多创价值。例1-1.齐王与田忌赛马：他们各有上等、中等、下等马各一匹，且同级马，齐王比田忌强些。双方约定：每局比赛三场，每负一场者应付1千金，且每匹马都应参加比赛。结果田忌以O：3输了后请教孙膑，则采用如下策略反败为胜，结果田忌二胜一负，实得1千金。,2,例1-2.两小孩玩石头、剪刀、布的游戏：甲、乙两小孩出的手势都有可能是石头、剪刀、布，若他们三次出的手势如下图，则乙小孩二胜一负。,二、竞争现象的特点双方均有理智：为击败对手，可随机应变改变策略(多为保密)。实力强者：稳扎稳打以优势取胜。实力弱者：避开对方优势锋芒，打击对方弱点取胜。在经济管理对策中：把非理智的客观世界设想为“理智人”，并与之斗争。三、对策论的概念研究竞争现象的一种定量分析理论。三、对策论的起源1我国古代围棋比赛和17世纪欧洲国际象棋比赛形成模拟模型。21912年，数学家翟墨罗发表论文“把集合论应用于象棋的博奕理论”，把对策从模拟模型抽象为数学模型。3第一次世界大战期间，产生了军事对策(战役、战略、军事装备等)。41944年，冯诺意曼与经济学家摩根斯特恩合写“对策论与经济行为”,把对策论应用于经济管理。5我国公元前六世纪(春秋)“孙子兵法”13篇。,3,四、对策参加竞争的各方为了取胜，而研究出一组对付对方的策略。五、对策的三要素1局中人：参加竞争，并有决策权的各方(二人或多人)。如：齐王和田忌。2策略：在一局竞争中，每一局中人均有供他选择的实际可行的完整行动方案。如例1-1，齐王有6个策略：(上中下)，(上下中),(中上下),(中下上),(下上中),(下中上)田忌有6个策略：(上中下)，(上下中),(中上下),(中下上),(下上中),(下中上)如例1-2，甲小孩有3个策略：石头，剪刀，布乙小孩有3个策略：石头，剪刀，布3一局对策的得失：局中人的得失。叫支付函数，对有限策略集，叫支付矩阵。如：齐王出策略(上中下)，田忌出策略(中上下)，则齐王二胜一负，赢得1千金；田忌损失1千金。六、局势每个局中人从各自的策略集合中选取一个策略参加对策，形成的一个处于竞争的策略组。如：齐王选策略(上中下)，田忌选策略(中上下)，构成一个局势(上中下)，(中上下)。局势的得失总和为0。七、对策的分类,4,对策,5,1.2支付矩阵有鞍点的二人有限零和对策一、特点1策略公开。2得失确定且总和为零：一方所得必为另一方所失，局中人利益冲突(对抗对策)。3单局竞争决定胜负。二、建模：建立支付函数，这里是支付矩阵(也叫矩阵对策问题)设局中人甲有m个纯策略S甲=1,2,m，局中人乙有n个纯策略S乙=1,2,n。纯局势(i,j)得失为aij：当aij0时，甲赢得aij，乙损失aij；当aij0时，甲损失-aij，乙赢得-aij。构成支付矩阵A：,对策可写成G=甲，乙，S甲，S乙，A。,6,如例1-1.齐王与田忌赛马：,则支付矩阵为：,7,如例1-2.两小孩玩游戏：,则支付矩阵为：,8,例1-3.某单位秋季要决定冬季取暖用煤的贮量。冬季用煤贮量在较暖、正常和较冷情况下分为10、15和20吨。设冬季煤价也随寒冷程度而变，在上述三种情况下分别为340、420和500元/吨，已知秋季煤价为340元/吨，冬季气象未能予知，问秋季合理贮煤量为多少？解：建模，设局中人甲为：贮煤量决策者；局中人乙为：未来冬季气候。费用总和=秋季贮煤量费用+冬季补购煤量费用,则支付矩阵为：,9,二、求解1稳妥性原则局中人在公开对策的前提下，都从最坏处着想，在最坏的环境中争取最好的结果。例1-4某企业决定由职工代表大会选举行政负责人，经提名产生候选人甲和乙。他们根据企业的发展战略和群众关心的事业各自提出了企业改革的方案。甲提出了四种：1,2,3,4；乙提出了三种：1,2,3。他们的参谋人员为使竞争对本方有利，予先作了个民意抽样测验。因各方提供的不同策略对选票吸引力不同。测验选票经比较后差额如下表(单位:十张)：,问：甲和乙在竞选中应采用何种策略？,解：对策时，双方均理智，且发挥主动性。最后，甲用2竞选，领先2O票优势；乙只能用2竞选，缩短票数差距。双方均认为只能如此，为双方妥协结果。,支付矩阵中：每行选最小值，这些最小值中选最大值V1；,每列选最大值，这些最大值中选最小值V2；,若V1=V2，则得最优解。,10,2稳妥性原则数学表达：对甲而言是最小最大原则：从支付矩阵每行元素中取最小数，再从这些最小数中取最大数，得,对乙而言是最大最小原则：从支付矩阵每列元素中取最大数，再从这些最大数中取最小数，得,若V1=V2=VG，则稳妥原则实现，VG为支付矩阵的稳定值即鞍点值，对应的纯策略i*,j*为甲、乙的最优纯策略，局势(i*,j*)为对策的最优解，即：,如例1-3.,甲用策略3，乙用策略3，即秋季购进煤2O吨，总费用最低为68OO元。,11,例1-5某厂工程师设计了三个矿石冶炼(或选矿)流程，考虑到它们的所用设备和工艺环节等因素，若付诸实施可会遇上生产正常和生产不正常两种情况,这两种情况的出现及其概率未能予知，但三个流程在这两种情况下的单位支付费用已算出，如下表，问：选用哪个流程较好?,解：有二个鞍点局势(1,2)和(3,2)甲用1，乙用2；甲用3，乙用2最小支付费用为：1.7(百元/吨)。所以应选“流程1”或“流程3”。,三、鞍点对策问题两个性质1解的稳定性对策的最终结局可在支付矩阵中得到双方均认可的妥协，双方均认识到在原有策略中存在最优策略。2对策的公开性双方均明确并可公开申明参加对策的最优策略，最优局势是双方妥协的结果，反映双方策略的实力。,12,1.3支付矩阵无鞍点的二人有限零和对策一、特点1策略保密性：图谋出奇制胜。2得失随机性：某局竞争的胜败难于予料，强者可败，弱者可胜。3多局竞争性：多局竞争后决定胜负。二、建模：建立得失期望值函数1混合策略设局中人甲有m个纯策略S甲=1,2,m，局中人乙有n个纯策略S乙=1,2,n。纯局势(i,j)得失为aij，构成的支付矩阵A无鞍点。G=甲，乙，S甲，S乙，A。设甲以x1,x2,xm的概率取纯策略1,2,m，则称概率向量X=(x1,x2,xm)为甲的一个混合策略，xi0，x1+x2+xm=1，甲的混合策略集记为S(m)；设乙以y1,y2,yn的概率取纯策略1,2,n，则称概率向量Y=(y1,y2,yn)为乙的一个混合策略，yi0，y1+y2+yn=1，乙的混合策略集记为T(n)。2混合局势(X,Y)称为混合局势。3得失期望值,13,如例1-2.两小孩共玩了10局游戏对策，最后总计谁胜谁负，设这10次游戏中：甲随机出了3次石头、3次剪刀、4次布，即甲采用混合策略X=(0.3,0.3,0.4)；乙随机出了0次石头、5次剪刀、5次布，即乙采用混合策略Y=(0,0.5,0.5)。,支付矩阵为(无鞍点)：,得失期望值为：,所以，甲平均要输0.05。,14,4最优混合策略定义:若X*S(m),Y*T(n)，使对所有XS(m),YT(n),都有E(X,Y*)E(X*,Y*)E(X*,Y),则X*、Y*分别称为甲、乙的最优混合策略，(X*,Y*)为对策的解，E(X*,Y*)为对策值V。例1-6给定一个矩阵对策G=甲,乙,S甲,S乙,A，S甲=1,2,S乙=1,2，,设甲以x,1-x的概率取纯策略1,2；乙以y,1-y的概率取纯策略1,2。得失期望值为：,求甲、乙的最优混合策略。,解：,G无鞍点，两局中人无纯策略稳定解，斗争转入策略保密，即求最优混合策略。,当甲以x=2/5=0.4的概率选1时，其赢利期望值E(X,Y)=4，是甲从稳妥原则出发能达到的最大期望赢利值,而x,1-x=0.4,0.6=X*是甲的最优混合策略，当x取一值时，y可取另外一值与其对抗，但当x=2/5时，y无论取何值都无法与其对抗；当乙以y=1/2=0.5的概率选1时，其损失期望值E(X,Y)=4，是乙从稳妥原则出发能达到的最小期望损失值,而y,1-y=0.5,0.5=Y*是乙的最优混合策略，当y取一值时，x可取另外一值与其对抗，但当y=1/2时，x无论取何值都无法与其对抗。故X*=0.4,0.6，Y*=0.5,0.5，E(X*，Y*)=4就是双方都感到只能如此的最好结果。,15,存在性定理：任意一个给定的矩阵对策一定有解，局中人双方总有一个最优混合策略，即：,则X*、Y*为甲、乙的最优混合策略，(X*,Y*)为对策的解，对策值V=V1=V2。,定理1：若矩阵对策值为V，则下面两组不等式的解是局中人甲、乙的最优混合策略：,定理2：若X*、Y*为甲、乙的最优混合策略，则对某一个i或j，有,16,5支付矩阵的缩减：若存在优势策略，则支付矩阵阶数可降低对局中人甲，他希望对策的局势值aij越大越好：若第i行所有元素第L行所有元素，即aijaLj，j=1,2,n，则甲理智，必采用i纯策略而舍去L纯策略，不影响最优混合策略和策略鞍点值。此时称i策略为对L策略的优势策略。对局中人乙，他希望对策的局势值aij越小越好：若第j列所有元素第K列所有元素，即aijaiK，i=1,2,m，则乙理智，必采用j纯策略而舍去K纯策略，不影响最优混合策略和策略鞍点值。此时称j策略为对K策略的优势策略。,例1-7设有矩阵对策,注：无鞍点对策时，要求决策的不是每次局中人应选那个纯策略，而是决定用多大的概率选择每一种纯策略，以期达到能平均反映各方纯策略实力的稳妥结果。,17,三、最优混合策略的求解方法1图解法：适用于缩减后的支付矩阵为2n或m2的无鞍点对策问题。,例1-8设有下列矩阵对策，求甲、乙的最优混合策略。,解：设甲的混合策略为(x,1-x)，乙的混合策略为(y,1-y)。得失期望值为：,甲的期望值方程为：V=x+6(1-x)=65xV=7x+2(1-x)=2+5x,乙的期望值方程为：V=y+7(1-y)=76yV=6y+2(1-y)=2+4y,甲的最优混合策略为(0.4,0.6,0),对策值为V=4;,乙的最优混合策略为(0.5,0.5,0),对策值为V=4;,18,2解析法：适用于缩减后的支付矩阵为nn方阵的无鞍点对策问题。,设甲的混合策略为(x1,x2,xn)，乙的混合策略为(y1,y2,yn)。得失期望值为：,甲的期望值方程为：,乙的期望值方程为：,解得甲的最优混合策略为X*=(x1*,xn*);,解得乙的最优混合策略为Y*=(y1*,yn*),对策值V=V*;,19,例1-9求两小孩玩游戏对策的最优混合策略。,甲小孩的期望值方程为：,乙小孩的期望值方程为：,解得甲的最优混合策略为X*=(1/3,1/3,1/3),V*=0,解得乙的最优混合策略为Y*=(1/3,1/3,1/3),V*=0;,无鞍点且不能缩减。,设甲的混合策略为(x1,x2,x3)，乙的混合策略为(y1,y2,y3)。得失期望值为：,甲、乙两小孩均以1/3的同等概率取石头、剪刀、布纯策略，在不考虑其它因素的前提下，多局竞争的结果是最终和局，谁也不占优势，反映双方纯策略实力相等。,20,例1-10求齐王与田忌赛马对策的最优混合策略。,齐王的期望值方程为：,田忌的期望值方程为：,解得齐王的最优混合策略为X*=(1/6,1/6,1/6,1/6,1/6,1/6),V*=1,无鞍点且不能缩减。,设齐王的混合策略为(x1,x2,x3,x4,x5,x6)，田忌的混合策略为(y1,y2,y3,y4,y5,y6)。,双方都示以莫测，但很理智，总结局齐王得1千金，表明齐王实力略胜一筹。,解得田忌的最优混合策略为Y*=(1/6,1/6,1/6,1/6,1/6,1/6),V*=1,21,3拉格朗日乘子法：适用于缩减后的支付矩阵为nn方阵的无鞍点对策问题。,设甲的混合策略为(x1,x2,xn)，乙的混合策略为(y1,y2,yn)。得失期望值为：,求出最优混合策略和对策值，并且有：,构造拉格朗日函数L为：,解下列方程组：,22,例1-11求下列对策的最优混合策略。,解下列方程组：,解下列方程组：,解得乙的最优混合策略为Y*=(14/45,11/45,20/45),V*=29/45,无鞍点且不能缩减。,设甲的混合策略为(x1,x2,x3)，乙的混合策略为(y1,y2,y3)。拉氏函数为：,解得甲的最优混合策略为X*=(20/45,11/45,14/45),V*=29/45,23,例1-12求下列对策的最优混合策略。,解下列方程组：,解得乙的最优混合策略为y1*=26/35,y2*=19/35,y3*=-2/70,违背概率定义1=V*=5/14,无鞍点且不能缩减。,设甲的混合策略为(x1,x2,x3)，乙的混合策略为(y1,y2,y3)。拉氏函数为：,解析法与拉氏法不是对所有的有解支付矩阵均能得到正确答案，没有顾及变量非负的要求。,24,4线性规划法：适用于缩减后的支付矩阵为mn矩阵的无鞍点对策问题。,设甲的混合策略为(x1,x2,xm),乙的混合策略为(y1,y2,yn)。得失期望值为：,这里不妨设V0，（否则可令aij=aij+K，使得V=V+K0）,25,由定理1的：,此时对甲，要求V取大，即Vmax，1/vmin，于是得下列LP数学模型：,由定理1的：,此时对乙，要求V取小，即VMin，1/vMax，于是得下列LP数学模型：,以上两