关闭

关闭

关闭

封号提示

内容

首页 第07章 对策论.pdf

第07章 对策论.pdf

第07章 对策论.pdf

上传者: Gingerjin 2012-07-26 评分 0 0 0 0 0 0 暂无简介 简介 举报

简介:本文档为《第07章 对策论pdf》,可适用于工程科技领域,主题内容包含第七章对策论引言社会及经济的发展带来了人与人之间或团体之间的竞争及矛盾应用科学的方法来解决这样的问题开始于世纪的科学家如CHuygens和WLeib符等。

第七章对策论引言社会及经济的发展带来了人与人之间或团体之间的竞争及矛盾应用科学的方法来解决这样的问题开始于世纪的科学家如CHuygens和WLeibnitz等。现代对策论起源于年JVonNeumann和OMorgenstern的著作《TheoryofGamesandEconomicBehavior》。对策论亦称竞赛论或博弈论。是研究具有斗争或竞争性质现象的数学理论和方法。一般认为它既是现代数学的一个新分支也是运筹学中的一个重要学科。对策论发展的历史并不长但由于它所研究的现象与人们的政治、经济、军事活动乃至一般的日常生活等有着密切的联系并且处理问题的方法又有明显特色。所以日益引起广泛的注意。在日常生活中经常看到一些具有相互之间斗争或竞争性质的行为。具有竞争或对抗性质的行为称为对策行为。在这类行为中。参加斗争或竞争的各方各自具有不同的目标和利益。为了达到各自的目标和利益各方必须考虑对手的各种可能的行动方案并力图选取对自己最为有利或最为合理的方案。对策论就是研究对策行为中斗争各方是否存在着最合理的行动方案以及如何找到这个合理的行动方案的数学理论和方法。对策问题对策问题的特征是参与者为利益相互冲突的各方其结局不取决于其中任意一方的努力而是各方所采取的策略的综合结果。先考察一个实际例子。例(囚徒的困境)警察同时逮捕了两人并分开关押逮捕的原因是他们持有大量伪币警方怀疑他们伪造钱币但没有找到充分证据希望他们能自己供认这两个人都知道:如果他们双方都不供认将被以持有大量伪币罪被各判刑个月如果双方都供认伪造了钱币将各被判刑年如果一方供认另一方不供认则供认方将被从宽处理而免刑但另一方面将被判刑年。将嫌疑犯A、B被判刑的几种可能情况列于表。表嫌疑犯B供认不供认嫌疑犯A供认不供认()()()()表中每对数字表示嫌疑犯BA、被判刑的年数。如果两名疑犯均担心对方供认并希望受到最轻的惩罚最保险的办法自然是承认制造了伪币。从这一简单实例中可以看出对策现象中包含有的几个基本要素。对策的基本要素(i)局中人在一个对策行为(或一局对策)中有权决定自己行动方案的对策参加者称为局中人。通常用I表示局中人的集合.如果有n个局中人则},,,{nIL=。一般要求一个对策中至少要有两个局中人。在例中局中人是BA、两名疑犯。(ii)策略集一局对策中可供局中人选择的一个实际可行的完整的行动方案称为一个策略。参加对策的每一局中人iIi都有自己的策略集iS。一般每一局中人的策略集中至少应包括两个策略。(iii)赢得函数(支付函数)在一局对策中各局中人所选定的策略形成的策略组称为一个局势即若is是第i个局中人的一个策略则n个局中人的策略组),,,(nssssL=就是一个局势。全体局势的集合S可用各局中人策略集的笛卡尔积表示即nSSSS=L当局势出现后对策的结果也就确定了。也就是说对任一局势Ss局中人i可以得到一个赢得)(sHi。显然)(sHi是局势s的函数称之为第i个局中人的赢得函数。这样就得到一个向量赢得函数))(,),(()(sHsHsHnL=。本节我们只讨论有两名局中人的对策问题其结果可以推广到一般的对策模型中去。零和对策(矩阵对策)零和对策是一类特殊的对策问题。在这类对策中只有两名局中人每个局中人都只有有限个策略可供选择。在任一纯局势下两个局中人的赢得之和总是等于零即双方的利益是激烈对抗的。设局中人Ⅰ、Ⅱ的策略集分别为},,{mSααL=},,{nSββL=当局中人Ⅰ选定策略iα和局中人Ⅱ选定策略jβ后就形成了一个局势),(jiβα可见这样的局势共有mn个。对任一局势),(jiβα记局中人Ⅰ的赢得值为ija并称=mnmmnnaaaaaaaaaALLLLLLL为局中人Ⅰ的赢得矩阵(或为局中人Ⅱ的支付矩阵)。由于假定对策为零和的故局中人Ⅱ的赢得矩阵就是A。当局中人Ⅰ、Ⅱ和策略集S、S及局中人Ⅰ的赢得矩阵A确定后一个零和对策就给定了零和对策又可称为矩阵对策并可简记成},{ASSG=。例设有一矩阵对策},{ASSG=其中},,{ααα=S},,,{ββββ=S=A从A中可以看出若局中人Ⅰ希望获得最大赢利需采取策略α但此时若局中人Ⅱ采取策略β局中人Ⅰ非但得不到反而会失去。为了稳妥双方都应考虑到对方有使自己损失最大的动机在最坏的可能中争取最好的结果局中人Ⅰ采取策略ααα、、时最坏的赢得结果分别为},,,min{=},,,min{=},,,min{=其中最好的可能为},,max{=。如果局中人Ⅰ采取策略α无论局中人Ⅱ采取什么策略局中人Ⅰ的赢得均不会少于。局中人Ⅱ采取各方案的最大损失为},,max{=},,max{=},,max{=和},,max{=。当局中人Ⅱ采取策略β时其损失不会超过。注意到在赢得矩阵中既是所在行中的最小元素又是所在列中的最大元素。此时只要对方不改变策略任一局中人都不可能通过变换策略来增大赢得或减少损失称这样的局势为对策的一个稳定点或稳定解。定义设),(yxf为一个定义在Ax及By上的实值函数如果存在Ax*By*使得对一切Ax和By有)*,(*)*,(*),(yxfyxfyxf则称*)*,(yx为函数f的一个鞍点。定义设},{ASSG=为矩阵对策其中},,,{mSαααL=},,,{nSβββL=nmijaA=)(。若等式**maxminminmaxjiijijijjiaaa==()成立记**jiGaV=则称GV为对策G的值称使()式成立的纯局势),(**jiβα为对策G的鞍点或稳定解赢得矩阵中与),(**jiβα相对应的元素**jia称为赢得矩阵的鞍点*iα与*jβ分别称为局中人Ⅰ与Ⅱ的最优纯策略。给定一个对策G如何判断它是否具有鞍点呢?为了回答这一问题先引入下面的极大极小原理。定理设},{ASSG=记ijjiaminmax=μijijamaxmin=ν则必有νμ。证明)(minmaxijija=ν易见μ为Ⅰ的最小赢得ν为Ⅱ的最小赢得由于G是零和对策故νμ必成立。定理零和对策G具有稳定解的充要条件为=νμ。证明:(充分性)由μ和ν的定义可知存在一行例如p行μ为p行中的最小元素且存在一列例如q列ν为q列中的最大元素。故有μpqa且νpqa又因=νμ所以νμ=从而得出μ=pqapqa为赢得矩阵的鞍点),(qpβα为G的稳定解。(必要性)若G具有稳定解),(qpβα则pqa为赢得矩阵的鞍点。故有pqpjjijjiaaa==minminmaxμpqiqiijijaaa==maxmaxminν从而可得νμ但根据定理νμ必成立故必有=νμ。上述定理给出了对策问题有稳定解(简称为解)的充要条件。当对策问题有解时其解可以不唯一当解不唯一时解之间的关系具有下面两条性质:性质无差别性。即若),(jiβα与),(jiβα是对策G的两个解则必有jijiaa=。性质可交换性。即若),(jiβα和),(jiβα是对策G的两个解则),(jiβα和),(jiβα也是解。零和对策的混合策略具有稳定解的零和问题是一类特别简单的对策问题它所对应的赢得矩阵存在鞍点任一局中人都不可能通过自己单方面的努力来改进结果。然而在实际遇到的零和对策中更典型的是νμ的情况。由于赢得矩阵中不存在鞍点此时在只使用纯策略的范围内对策问题无解。下面我们引进零和对策的混合策略。设局中人Ⅰ用概率ix选用策略iα局中人Ⅱ用概率jy选用策略jβ====minjjiyx记Tmxxx),,(L=Tnyyy),,(L=则局中人Ⅰ的期望赢得为AyxyxET=),(。记*S:策略mαα,,L*S:策略nββ,,L概率mxx,,L概率nyy,,L分别称*S与*S为局中人Ⅰ和Ⅱ的混合策略。下面简单地记},,,|),,{(*====miiiTmxmixxxSLL},,,|),,{(*====njjjTnynjyyySLL定义若存在m维概率向量x和n维概率向量y使得对一切m维概率向量x和n维概率向量y有AyxyAxyAxTyTxTminmax==则称),(yx为混合策略对策问题的鞍点。定理设*Sx*Sy则),(yx为},{ASSG=的解的充要条件是:====njyAxxamiyAxyaTimiijTnjjij,,,,,,,,LL定理任意混合策略对策问题必存在鞍点即必存在概率向量x和y使得:AyxAyxyAxTxyTyxTmaxminminmax==。使用纯策略的对策问题(具有稳定解的对策问题)可以看成使用混合策略的对策问题的特殊情况相当于以概率选取其中某一策略以概率选取其余策略。例BA、为作战双方A方拟派两架轰炸机Ⅰ和Ⅱ去轰炸B方的指挥部轰炸机Ⅰ在前面飞行Ⅱ随后。两架轰炸机中只有一架带有炸弹而另一架仅为护航。轰炸机飞至B方上空受到B方战斗机的阻击。若战斗机阻击后面的轰炸机Ⅱ它仅受Ⅱ的射击被击中的概率为(Ⅰ来不及返回攻击它)。若战斗机阻击Ⅰ它将同时受到两架轰炸机的射击被击中的概率为。一旦战斗机未被击中它将以的概率击毁其选中的轰炸机。请为BA、双方各选择一个最优策略即:对于A方应选择哪一架轰炸机装载炸弹?对于B方战斗机应阻击哪一架轰炸机?解双方可选择的策略集分别是},{αα=ASα:轰炸机Ⅰ装炸弹Ⅱ护航α:轰炸机Ⅱ装炸弹Ⅰ护航},{ββ=BSβ:阻击轰炸机Ⅰβ:阻击轰炸机Ⅱ赢得矩阵)(=ijaRija为A方采取策略iα而B方采取策略jβ时轰炸机轰炸B方指挥部的概率由题意可计算出:)(==a=a=a)(==a即赢得矩阵=R易求得minmax==ijjiaμmaxmin==ijijaν。由于νμ矩阵R不存在鞍点应当求最佳混合策略。现设A以概率x取策略α、以概率x取策略αB以概率y取策略β、以概率y取策略β。先从B方来考虑问题。B采用β时A方轰炸机攻击指挥部的概率期望值为)(xxE=β而B采用β时A方轰炸机攻击指挥部的概率的期望值为)(xxE=β。若)()(ββEE不妨设)()(ββEE<则B方必采用β以减少指挥部被轰炸的概率。故对A方选取的最佳概率x和x必满足:==xxxxxx即==xxxaxaxaxa由此解得=x=x。同样可从A方考虑问题得==yyyyyy即==yyyayayaya并解得=y=y。B方指挥部被轰炸的概率的期望值=GV。记零和对策G的解集为)(GT下面三个定理是关于对策解集性质的主要结果:定理设有两个零和对策},{ASSG=},{ASSG=其中}{ijaA=}{LaAij=L为任一常数。则(i)LVVGG=(ii))()(GTGT=定理设有两个零和对策},{ASSG=},{ASSGα=其中>α为任一常数。则(i)GGVVα=(ii))()(GTGT=定理设},{ASSG=为一零和对策且TAA=为反对称矩阵(亦称这种对策为对称对策)。则(i)=GV(ii))()(GTGT=其中)(GT和)(GT为局中人Ⅰ和Ⅱ的最优策略集。零和对策的线性规划解法当>m且>n时通常采用线性规划方法求解零和对策问题。局中人Ⅰ选择混合策略x的目的是使得jnjjyxnjjjTyxTyxTyEeyAxAyxyAx=====minmax)(minmaxminmax其中je为只有第j个分量为而其余分量均为零的单位向量jTjAexE=。记jjkEEumin=由于==njjy=njjjYyEmin在=ky)(kjyj=时达到最小值u故x应为线性规划问题umaxst=====mixxEEnjuxaimiimikjiij,,,,)(,,,,LL即()的解。同理y应为线性规划vminst=====njyymivyajnjjnjjij,,,,,,,,LL()的解。由线性规划知识()与()互为对偶线性规划它们具有相同的最优目标函数值。不妨设>u作变换uxxii='mi,,,L=则线性规划问题()化为:=miix'minst===mixnjxaimiiij,,,,',,,,'LL同理作变换vyyjj='nj,,,L=则线性规划问题()化为:=miiy'maxst===njymiyajnjjij,,,,',,,,'LL例在一场敌对的军事行动中甲方拥有三种进攻性武器,,AAA可分别用于摧毁乙方工事而乙方有三种防御性武器,,BBB来对付甲方。据平时演习得到的数据各种武器间对抗时相互取胜的可能如下:A对B:A对B:A对B:A对B:A对B:A对B:A对B:A对B:A对B:解先分别列出甲、乙双方的赢得的可能性矩阵将甲方矩阵减去乙方矩阵的对应元素得零和对策时甲方的赢得矩阵如下:=A编写程序如下:cleara=,,,,,,b=a=ab*ones()把赢得矩阵的每个元素变成大于的数x,u=linprog(ones(,),a',ones(,),,,zeros(,))x=xu,u=uby,v=linprog(ones(,),a,ones(,),,,zeros(,))y=y(v),v=(v)b解得T),,(=xT),,(=y=u故乙方有利。下面我们使用式()和()利用LINGO编程求例的解。LINGO程序如下:model:sets:player:xplayer:ygame(player,player):cendsetsdata:ctrl=!ctrl取求局中人的策略ctrl取求局中人的策略c=enddatamax=u*ctrlv*(ctrl)free(u)free(v)for(player(j):sum(player(i):c(i,j)*x(i))>u)for(player(i):sum(player(j):c(i,j)*y(j))<v)sum(player:x)=sum(player:y)=end由定理知混合对策问题的求解问题可以转化为求不等式约束的可行点而LINGO软件很容易做到这一点。我们编写如下Lingo程序求解上述问题。model:sets:player:xplayer:ygame(player,player):cendsetsdata:c=enddatafree(u)u=sum(game(i,j):c(i,j)*x(i)*y(j))for(player(i):sum(player(j):c(i,j)*y(j))<u)for(player(j):sum(player(i):c(i,j)*x(i))>u)sum(player:x)=sum(player:y)=end二人非常数和对策所谓常数和对策是指局中人I和局中人II所赢得的值之和为一常数。显然二人零和对策是二人常数和对策的特例即常数为零。对于二人常数和对策有纯策略对策和混合策略对策其求解方法与二人零和对策是相同的。二人非常数和对策也称为双矩阵对策。也有纯策略对策和混合策略对策两种策略。纯策略问题例给出了典型的二人非常数和对策每人的赢得矩阵是不相同的因此称为双矩阵对策。问题分析这是一个二人非常数和对策问题。从表面上看两犯罪嫌疑人拒不供认只能被判个月徒刑结果是最好的。但仔细分析却无法做到这一点。因为犯罪嫌疑人A如果采用不供认策略他可能被判刑的刑期为个月或年而犯罪嫌疑人B可能判的刑期为或个月。而A选择供认他被判的刑期为或年此时犯罪嫌疑人B可能判的刑期为年或年。因此犯罪嫌疑人A一定选择供认。基于同样的道理犯罪嫌疑人B也只能选择供认。选择供认是他们最好的选择各自被判年。按照上面的论述对于一般纯策略问题局中人I、II的赢得矩阵如表所示。其中局中人I有m个策略mαα,,L局中人II有n个策略nββ,,L分别记为},,{mSααL=},,{nSββL=nmijcC=)(为局中人I的赢得矩阵nmijcC=)(为局中人II的赢得矩阵。因此双矩阵对策记为},,,{CCSSG=表ββ…nβα),(cc),(cc…),(nnccα),(cc),(cc…),(nnccMMMMmα),(mmcc),(mmcc…),(mnmncc定义设},,,{CCSSG=是一双矩阵对策若等式maxmin**ijijjicc=maxmin**ijjijicc=()成立则记**jicv=并称v为局中人I的赢得值记**jicv=并称v为局中人II的赢得值称),(**jiβα为G在纯策略下的解(或Nash平衡点)称*iα和*jβ分别为局中人III的最优纯策略。实际上定义也同时给出了纯策略问题的求解方法。因此对于例)),(),,((是Nash平衡点这里),(表示以概率取第一个策略也就是说坦白是他们的最佳策略。混合对策问题如果不存在使式()成立的对策则需要求混合对策。类似于二人零和对策情况需要给出混合对策的最优解。()混合对策问题的基本概念定义在对策},,,{CCSSG=中若存在策略对**,SySx使得**,,SyyCxyCxSxyCxyCxTTTT则称),(yx为G的一个非合作平衡点。记yCxvT=yCxvT=则称,vv分别为局中人III的赢得值。对于混合对策问题有如下定理。定理每个双矩阵对策至少存在一个非合作平衡点。定理混合策略),(yx为对策},,,{CCSSG=的平衡点的充分必要条件是====njyCxxcmiyCxycTimiijTnjjij,,,,,,,,LL()()混合对策问题的求解方法由定义可知求解混合对策就是求非合作对策的平衡点进一步由定理得到求解非合作对策的平衡点就是求解满足不等式约束()的可行点。因此混合对策问题的求解问题就转化为求不等式约束()的可行点而LINGO软件可以很容易做到这一点。例有甲、乙两支游泳队举行包括三个项目的对抗赛。这两支游泳队各有一名健将级运动员(甲队为李乙队为王)在三个项目中成绩都很突出但规则准许他们每人只能参加两项比赛每队的其他两名运动员可参加全部三项比赛。已知各运动员平时成绩(秒)见表。表甲队乙队赵钱李王张孙米蝶泳米仰泳米蛙泳假定各运动员在比赛中都发挥正常水平又比赛第一名得分第二名得分第三名得分问教练员应决定让自己队健将参加哪两项比赛使本队得分最多?(各队参加比赛名单互相保密定下来后不准变动)解分别用α、α和α表示甲队中李姓健将不参加蝶泳、仰泳、蛙泳比赛的策略分别用β、β和β表示乙队中王姓健将不参加蝶泳、仰泳、蛙泳比赛的策略。当甲队采用策略α乙队采用策略β时在米蝶泳中甲队中赵获第一、钱获第三得分乙队中张获第二得分在米仰泳中甲队中李获第二得分乙队中王获第一、张获第三得分在米蛙泳中甲队中李获第一得分乙队中王获第二、张获第三得分。也就是说对应于策略),(βα甲、乙两队各自的得分为),(。表给出了在全部策略下各队的得分计算的Matlab程序如下:clc,cleara=m=n=kk=T=sc=::,zeros(,)名的得分sc=repmat(sc,kk,)fori=:mforj=:nb=ab(i,)=Tb(j,)=T不参加比赛时间成绩取为充分大b,ind=sort(b,)对b的每一行进行排序fork=:msc(k,ind(k,:))=sc计算得分endAsc(i,j)=sum(sum(sc(:,:m)))统计得分Bsc(i,j)=sum(sum(sc(:,m:end)))endendAsc,Bscfid=fopen('txttxt','w')fprintf(fid,'fn',Asc')fwrite(fid,'~','char')往纯文本文件中写LINGO数据的分割符fprintf(fid,'fn',Bsc')fclose(fid)表βββααα),(),(),(),(),(),(),(),(),(按照定理求最优混合策略就是求不等式约束()的可行解写出相应的LINGO程序如下:model:sets:pa:xpb:ylink(pa,pb):c,cendsetsdata:c=file(txttxt)c=file(txttxt)enddatav=sum(link(i,j):c(i,j)*x(i)*y(j))v=sum(link(i,j):c(i,j)*x(i)*y(j))for(pa(i):sum(pb(j):c(i,j)*y(j))<v)for(pb(j):sum(pa(i):c(i,j)*x(i))<v)sum(pa:x)=sum(pb:y)=free(v)free(v)end求得甲队采用的策略是α、α方案各占%乙队采用的策略是β、β方案各占%甲队的平均得分为分乙队的平均得分为分。习题七表是一双矩阵对策试求局中人BA,的最优策略。表局中人B局中人A(,)(,)(,)(,)(,)(,)有三张纸牌点数分别为显然按大小顺序为>>。先由A任抽一张看过后反放在桌上并任喊大(H)或小(L)。然后由B从剩下纸牌中任抽一张看过后B有两种选择:第一弃权付给A元第二翻A的牌当A喊H时得点数小的牌者付给对方元当A喊L时得点数大的牌者付给对方元。要求:(i)说明BA,各有多少个纯策略(ii)根据优超原则淘汰具有劣势的策略并列出A的赢得矩阵(iii)求解双方各自的最优策略和对策值。“二指莫拉问题”。甲、乙二人游戏每人出一个或两个手指同时又把猜测对方所出的指数叫出来。如果只有一个人猜测正确则他所赢得的数目为二人所出指数之和否则重新开始。写出该对策中各局中人的策略集合及甲的赢得矩阵并回答局中人是否存在某种出法比其他出法更为有利。甲、乙两队进行乒乓球团体赛每队由名球员组成。双方可排出种不同的阵容。甲队的种阵容记为CBA,,乙队的种阵容为ⅠⅡⅢ。根据以往的记录。两队以不同的阵容交手的结果如表所示。表甲队得分数乙队甲队ⅠⅡⅢA---B-C-表中的数字为双方各种阵容下甲队的得分数。这次团体赛双方各采取什么阵容比较稳妥?

用户评论(0)

0/200

精彩专题

上传我的资料

每篇奖励 +2积分

资料评价:

/13
0下载券 下载 加入VIP, 送下载券

意见
反馈

立即扫码关注

爱问共享资料微信公众号

返回
顶部