对策论-运筹学

-1-习题解答1.已知矩阵博弈局中人I的赢得矩阵如下，求最优纯策略及博弈值。（1）8354667565443494（2）21221405126331222210解:(1)869535438354667565443494所以),(13,V=5(2)2-32-222562)2(1)2(214051263312)2(2)2(10所以),(31,),(51,),(33,),(53,V=-22．甲乙两国进行乒乓球团体赛，每国由三个人组成一个队参加比赛。甲国的人员根据不同的组合可组成4个队，乙国的人员可组成3个队，根据以往的比赛记录，已知各种组成队法相遇后甲国的得分如下表所示甲乙1队2队3队1队-51-72队3243队8-1-84队-2-16问双方应各派哪个队上场是最优决策?解:62828276128184)2(3715所以),(22,V=2答:双方应均派第2队出场3.对任意一个m行n列的实数矩阵A=（aij）,试证有下式成立-2-ijminjijnjmiaa1111maxminminmax证:ijminjijnjmiijmiijnjmiijijnjaaaajaanjmiji11111111maxminminmaxmaxminmax,min:1,1,,有有4.某城区有A、B、C三个居民小区，分别居住着40％，30%，30%的居民，有两个公司甲和乙都计划在区内建造超市，公司甲计划建两个，公司乙计划建一个，每个公司都知道，如果在某个小区内设有两个超市，那么这两个超市将平分该区的消费，如果在某个小区只有一个超市，则该超市将独揽这个小区的消费。如果在一个小区没有超市，则该小区的消费将平分给三个超市。每个公司都想使自己的营业额尽可能地多．试把这个问题表示成一个矩阵博弈，写出公司甲的赢得矩阵，井求两个公司的最优策略以及各占有多大的市场份额。解:甲公司的策略集为{(A,B),(A,C),(B,C)}乙公司的策略集为{A,B,C}甲的赢得矩阵为:75.075.07.06.07.07.0717.0717.06.075.07.0)7.0(7.075.0)7.0(),(),(),(CBCABACBA所以甲选(A,B)或(A,C),占70%份额。乙选A,占30%份额.5．一个病人的症状说明他可能患a，b，c三种病中的一种，有两种药C，D可用，这两种药对这三种病的治愈率为病药abcC0.50.40.6D0.70.10.8问医生应开哪一种药才能最稳妥?解:8.04.07.01.04.08.01.07.06.0)4.0(5.0最优策略为),(21答:应开C药较为稳妥.6．设矩阵博弈局中人I的赢得为A=203233-3-(1)当局中人I采用策略x=(0.2，0.5，0.3)时，Ⅱ应采用什么策略?(2)当局中人Ⅱ采用策略y=(5/7，2/7)时，I应采用什么策略?(2)x和y是否是最优策略?为什么?若是，试给出另一个局中人的最优策略和博弈值。解:(1)设II的策略为Y=(y1,y2),则3.023.0)3(5.033.04.003.025.0)3(2.01yys.t.0.3y-0.4ymin2121得:y1=0,y2=1,V1=-0.3,所以最优解为(0,1),V=-0.3(2)设II的策略为X=(x1,x2,x3),则74275074)3(7227579372)3(751xs.t.x74x74x79-max321321xx所以13211],1,0[,0xxxx,即I的最优策略为7/4],1,0[),1,,0(V(3)对于(x1,x2,x3)=(0.2,0.5,0.3),因为31231133),1,0(*,0ijjijjiyayaYx但所以(0.2,0.5,0.3)不是最优解.对于(y1,y2)=(5/7,2/7),因为)1,,0(*,0Xyi满足:72,52252)1(2)3()3(02)1(02)3(0得令所以(5/7,2/7)是II的最优解,对应I的最优策略为(0,2/7,5/7),V=4/77.给定矩阵博弈局中人I的赢得为A=113331135-4-试验证x*=(1/2，1/2，0)和y*=(1/4，0，3/4)分别是局中人I和Ⅱ的最优混合策略，井求博弈值。解:可验证满足:(1)若;,01**Vyaxnjjiji则(2)若Vxaymiiijj1**,0则(3)若;0,*1*injjijxVya则(4)若0,*1*jmiiijyVxa则且V=28.已知矩阵博弈的赢得矩阵如下，试用线性方程组法求最优混合策略及博弈值。（1）2282102622（2）021102210解:(1)将矩阵中各元素减2得:A-2=0060804001486321123xxxvxvxvx1684321123yyyvyvyvy解得:X*=(6/13,3/13,4/13),Y*=(4/13,3/13,6/13),V=50/13(2)1222321213132xxxvxxvxxvxx1222321213132yyyvyyvyyvyy解得:X*=(1/3,1/3,1/3),Y*=(1/3,1/3,1/3),V=19．用简便方法（降阶或化零元）求给定矩阵博弈的解与值，赢得矩阵如下-5-（1）0311221020430231（2）0683874768375990559243300解:(1)用优超法简化矩阵得:032042431234224xxvxvx1234343yyvyvy解方程组得:X*=(0,3/5,0,2/5),Y*=(0,0,2/5,3/5),V=6/5(2)用优超法则简化矩阵得:74374354各元素减7得:03404354则1434334xxvxvx1435454yyvyvy解方程组得:7/3,7/4,7/12,7/3,7/45434yyvxx所以得X*=(0,0,3/7,4/7,0),Y*=(0,0,0,4/7,3/7),V=37/710．用线性规划求下述矩阵博弈的混合策略解及博弈值，已知其赢得矩阵为（1）112103220（2）622241423解:(1)线性规划:0x,x,x1xxxvxx2xvx2xv2x3xs.t.maxv32132132131320y,y,y1yyyvyy2yvy3yv2y2ys.t.minv3213213213132解得:X*=(1/3,0,2/3),Y*=(1/3,1/3,1/3),V=4/3(2)矩阵各元素加2得:A+2=844461605线性规划为:-6-0x,x,x1xxxvx8x46xvx46xv4xx5xs.t.maxv321321321323210y,y,y1yyyvy8y44yvy46yv6y5ys.t.minv32132132132131y解得:X*=(0,0,1),Y*=(2/5,3/5,0),V=4-2=211.甲、乙两方交战。乙方用三个师守城，有两条公路通入该城，甲方用两个师攻城，可能两个师各走一条公路，也可能从一条公路进攻。乙方可用三个师防守某一条公路，也可用两个师防守一条公路，用第三个师防守另一条公路．哪方军队在一条公路上数量多，哪方军队就控制住这条公路．如果双方在同一条公路上的数量相同，则乙方控制住公路和甲方攻入城的机会各半，试把这个问题构成一个博弈模型。并求甲、乙双方的最优策略以及甲方攻入城的可能性。解:设两条路为A,B甲方攻城的策略集为:{2A,AB,2B}乙方宁城的策略集为:{3A,2AB,A2B,3B},甲方赢得矩阵为:00.51110.50.51110.50A线性方程组为:15.05.05.05.03212132132132xxxvxxvxxxvxxxvxx15.05.05.05.043213214321432yyyyvyyyvyyyyvyyy解得:x*=(1/3,1/3,1/3),v=2/3,y*=(1/6,1/3,1/3,1/6)即甲均以1/3的概率取两个师同走第一条路、各走一条路及同走第二条路。攻入城的机会为2/3。乙分别以1/6,1/3,1/3,1/6的概率取三个师同守第一条路、两师守第一条路和另一师守第二条路、一师守第一条路和两师守第二条路、以及三个师同守第二条路。12．设矩阵博弈Gl=(S1,S2,Ａ)和G2=(S1,S2,B)，其中A=(aij)m╳n,B=(bij)m╳n。如果bij=kaiji＝1,2,…,mj＝1,2,…,n其中k0，试证明Gl和G2具有相同的最优策略且它们的博弈值V1和V2之间有关系：V2=kV1证:设G*1=(X,Y,E1),G*2=(X,Y,E2)为G1,G2的混合扩充,则对X和Y中任意的x,y,有:-7-y)(x,Eminmaxy)(x,Eminmaxy)(x,Ey)(x,E1yXx2yXx11111112YYminjminjjiijjiijminjjiijkkyxakyxkayxb因此(x*,y*)是G1的最优策略当且仅当(x*,y*)是G2的最优策略,且V2=kV113．甲、乙二人游戏，每人出一个或两个手指，同时又把猜测对方所出的指数叫出来．如果只有一个人猜测正确，则他所赢得的数目为二人所出指数之和，如果两个人都猜对或都猜错，则算平局，都不得分。写出该博弈中各局中人的策略集合及甲的赢得矩阵。解:若令(i,j)中i为出的指数,j为叫的数目,则甲乙的策略集均为:{(1,1),(1,2),(2,1),(2,2)}甲的赢得矩阵为:0430400330020320)2,2()1,2()2,1()1,1()2,2()1,2()2,1()1,1(A14．甲、乙两个企业生产同一种产品，两个企业都想通过改革管理获取更多的市场销售份额．甲企业的策略措施有：①降低产品价格；②提高产品质量，延长保修年限：③推出新产品．乙企业考虑的措施有：①增加广告费用；②增设维修网点，扩大维修服务；③改进产品性能。假定市场份额一定，由于各自采取的策略措施不同，通过预测，今后两个企业的市场占有份额变动情况如下表所示(正值为甲企业增加的市场占有份额，负值为减少的市场占有份额)．试通过博弈分析，确定两个企业各自的最优策略。乙企业策略甲企业策略123110-1121210-53685解:求矩阵的鞍点(3,3),即甲乙均采用策略315.某企业有甲、乙两个公司，每年的税额分别是400万元和1200万元。对于每个公司，企业可以如实申报税款，或者篡改帐目，称税额为零。而国家税务局由于人力所限，对该企业每年只能检查一个公司的帐目。如果税务局发现有偷税现象，则该公司不但要如数缴纳税款，而且将被处以相当于一半税