对策论_运筹学

《对策论_运筹学》由会员分享，可在线阅读，更多相关《对策论_运筹学（12页珍藏版）》请在装配图网上搜索。

1、习题解答1. 已知矩阵博弈局中人 I 的赢得矩阵如下，求最优纯策略及博弈值。494301222445621336（ 1）766（2）1504524538122124943344564解: (1)57665 所以 ( 3, 1) ,V=545383596801(2)2(2)2(2)21336621504512(2)1(2)222- 23- 2所以 (1,3), (1 ,5), (3 ,3), (3, 5 ) ,V=-22 甲乙两国进行乒乓球团体赛， 每国由三个人组成一个队参加比赛。 甲国的人员根据不同的组合可组成 4 个队，乙国的人员可组成 3 个队，根据以往的比赛记录，已知各种组成队法相遇后甲

2、国的得分如下表所示甲1 队2 队3 队乙1 队-51-72 队3243 队8-1-84 队-2-16问双方应各派哪个队上场是最优决策?解 :51773(2)428188所以 ( 2,2),V=22162826答: 双方应均派第 2 队出场3.对任意一个 m 行 n 列的实数矩阵 A= （aij ） ,试证有下式成立max min aij1 im 1jnmin max aij1 jn 1 im证 :i , j ,1im,1jn有 : min aij1jnaijj , 有max min aij1 im 1jnmax aij1 immax min aij1 im 1jnmin max aij1jn

3、1 im4. 某城区有 A 、B、C 三个居民小区，分别居住着 40，30%，30%的居民，有两个公司甲和乙都计划在区内建造超市，公司甲计划建两个，公司乙计划建一个，每个公司都知道，如果在某个小区内设有两个超市，那么这两个超市将平分该区的消费，如果在某个小区只有一个超市，则该超市将独揽这个小区的消费。如果在一个小区没有超市，则该小区的消费将平分给三个超市。每个公司都想使自己的营业额尽可能地多试把这个问题表示成一个矩阵博弈，写出公司甲的赢得矩阵，井求两个公司的最优策略以及各占有多大的市场份额。解 : 甲公司的策略集为 (A,B), (A,C), (B,C)乙公司的策略集为 A,B,CABC(A,

4、B)(0.7)0.750.70.7甲的赢得矩阵为 : ( A, C) (0.7)0.70.750.7(B,C)0.60.7170.7170.60.70.750.75所以甲选 (A,B) 或(A,C), 占 70%份额。乙选 A, 占 30%份额 .5 一个病人的症状说明他可能患a，b，c 三种病中的一种，有两种药C，D 可用，这两种药对这三种病的治愈率为病abc药C0.50.40.6D0.70.10.8问医生应开哪一种药才能最稳妥 ?0.5(0.4)0.60.4解: 0.70.10.80.1 最优策略为 (1, 2)0.70.40.8答 :应开 C 药较为稳妥 .6设矩阵博弈局中人I 的赢得为

5、33A=2302(1) 当局中人 I 采用策略 x=(0.2，0.5，0.3)时，应采用什么策略 ?(2) 当局中人采用策略 y=(5/7，2/7)时， I 应采用什么策略 ?(2) x 和 y 是否是最优策略 ?为什么 ?若是，试给出另一个局中人的最优策略和博弈值。解 : (1)设 II 的策略为 Y=(y 1,y2 ),则0.2( 3)0.520.300.40.330.5( 3)0.320.3min 0.4y1 - 0.3y2s.t. y1y 21得 :y 1=0,y 2=1,V1=-0.3, 所以最优解为 (0,1),V=-0.3(2) 设 II 的策略为 X=(x 1,x2,x3),则

6、5(3)239777522(3)4777540277max - 9 x14 x 24 x 3777s.t. x1x2x31所以 x10, x20,1, x31x1 ,即 I 的最优策略为 (0, ,1), 0,1, V4 / 733(3)对于 (x 1,x2,x3)=(0.2,0.5,0.3),因为 xi0,Y*(0,1), 但a1 j y j3a2 j y j3i 1i1所以 (0.2,0.5,0.3)不是最优解 .对于 (y1,y2)=(5/7,2/7),因为 yi0,X*(0, ,1)满足:0( 3)20(1)20(3)(3)2(1)2 5令 225 ,得27所以 (5/7,2/7)是

7、II 的最优解 ,对应 I 的最优策略为 (0,2/7,5/7),V=4/77.给定矩阵博弈局中人I 的赢得为531A=133311试验证 x*=(1/2 ，1/2，0)和 y*=(1/4 ，0，3/4)分别是局中人 I 和的最优混合策略，井求博弈值。解 :可验证满足 :若 xi*0,则naij y*jV ;(1)j1m(2)若 y*j0,则aij xi*Vi1(3)naij y*jV ,则xi*0;若j 1maij xi*V ,则 y*j0(4) 若i 1且 V=28. 已知矩阵博弈的赢得矩阵如下， 试用线性方程组法求最优混合策略及博弈值。226012（ 1）2102（2）201822120

8、解: (1)将矩阵中各元素减2 得:004A-2=0806006x3v4y3v8x2v8y2v4x1v6y1vx1x2x31y1y2y31解得 : X *=(6/13,3/13,4/13),Y* =(4/13,3/13,6/13),V=50/13(2)2x2x3vy22 y3vx12x3v2 y1y3v2x1x2vy12 y2vx1x2x31y1y2 y31解得 : X *=(1/3,1/3,1/3),Y* =(1/3,1/3,1/3),V=19用简便方法（降阶或化零元）求给定矩阵博弈的解与值，赢得矩阵如下13200033429550（ 1）3402（ ）9957301222867471130

9、83860解: (1)用优超法简化矩阵得 :343x4v3 y3v2022x2 v2 y4v解方程组得 :43 0x2x41y3 y41X*=(0,3/5,0,2/5),Y* =(0,0,2/5,3/5),V=6/5(2) 用优超法则简化矩阵得 :45453x4v3 y4v37 3各元素减 7 得:304则4x3v4 y5v44 743 0x3 x41y4 y51解方程组得 :x4 4 / 7, x33/ 7,v12/ 7, y44 / 7, y5 3 / 7所以得 X* =(0,0,3/7,4/7,0),Y* =(0,0,0,4/7,3/7),V=37/710用线性规划求下述矩阵博弈的混合策

10、略解及博弈值，已知其赢得矩阵为022324（ 1）301（2）142211226解 : (1) 线性规划 :max vmin vs.t. 3x22x 3vs.t. 2y 22y3v2x1x 3v3y1y 3v2x 1x 2x 3v2y1y2y3vx1x 2 x 31y1y 2y31x1, x 2 , x30y1 , y 2, y30解得 : X *=(1/3,0,2/3),Y* =(1/3,1/3,1/3),V=4/3(2) 矩阵各元素加 2 得:506A+2= 164线性规划为 :448max vmin vs.t. 5x1x 24x 3vs.t. 5y16y3v6x24x3vy16y24y3

11、v6x14x 28x 3v4y14y28y3vx1x 2 x 3 1y1y2 y3 1x1, x 2 , x 30y1 ,y 2 , y 30解得 : X *=(0,0,1),Y* =(2/5,3/5,0),V=4-2=211. 甲、乙两方交战。乙方用三个师守城，有两条公路通入该城，甲方用两个师攻城，可能两个师各走一条公路，也可能从一条公路进攻。乙方可用三个师防守某一条公路，也可用两个师防守一条公路，用第三个师防守另一条公路哪方军队在一条公路上数量多，哪方军队就控制住这条公路如果双方在同一条公路上的数量相同，则乙方控制住公路和甲方攻入城的机会各半，试把这个问题构成一个博弈模型。并求甲、乙双方的

12、最优策略以及甲方攻入城的可能性。解 : 设两条路为 A,B甲方攻城的策略集为 :2A,AB,2B乙方宁城的策略集为 :3A,2AB,A2B,3B,甲方赢得矩阵为 :00.511A10.50.51110.50线性方程组为 :x2x3v0.5y2y3y4v0.5x10.5x2x3v0.5 y3y4 vx1 0.5x20.5x3y1 0.5y2vy20.5 y3vx1x2vy1y1y2y3y41x1x2x31解得 :x*=(1/3,1/3,1/3), v=2/3, y*=(1/6,1/3,1/3,1/6)即甲均以 1/3 的概率取两个师同走第一条路、 各走一条路及同走第二条路。 攻入城的机会为 2/

13、3 。乙分别以 1/6,1/3,1/3,1/6 的概率取三个师同守第一条路、两师守第一条路和另一师守第二条路、 一师守第一条路和两师守第二条路、 以及三个师同守第二条路。12设矩阵博弈Gl=(S1,S2,)和 bij =k aijG2=(S1,S2,B)，其中 A=(aij )m n, B=(bij )m n。如果i 1,2,mj 1,2,n其中 k0，试证明有关系：Gl和G2 具有相同的最优策略且它们的博弈值V 1 和V2 之间V 2= kV 1证 : 设 G* 1=(X,Y,E1), G* 2=(X,Y,E2)为 G1,G2 的混合扩充 ,则对 X 和 Y 中任意的 x,y,有 :mnmn

14、mnE2 (x, y)bij xi yjkaij xi yjkaij xi y jkE1(x, y)i 1j1i1j1i1j 1maxmin E2 (x, y)xXy Yk max min E1xXy Y(x, y)因此 (x * ,y * ) 是 G1 的最优策略当且仅当 (x *,y * ) 是G2 的最优策略, 且V2=kV113甲、乙二人游戏，每人出一个或两个手指，同时又把猜测对方所出的指数叫出来如果只有一个人猜测正确， 则他所赢得的数目为二人所出指数之和， 如果两个人都猜对或都猜错， 则算平局，都不得分。写出该博弈中各局中人的策略集合及甲的赢得矩阵。解 :若令 (i,j) 中 i 为

15、出的指数 ,j 为叫的数目 ,则甲乙的策略集均为 : (1,1),(1,2),(2,1),(2,2)甲的赢得矩阵为 :(1,1)(1,2)(2,1)(2,2)(1,1)0230A (1,2)2003(2,1)3004(2,2)034014 甲、乙两个企业生产同一种产品，两个企业都想通过改革管理获取更多的市场销售份额甲企业的策略措施有：降低产品价格；提高产品质量，延长保修年限：推出新产品乙企业考虑的措施有：增加广告费用；增设维修网点，扩大维修服务；改进产品性能。假定市场份额一定，由于各自采取的策略措施不同，通过预测，今后两个企业的市场占有份额变动情况如下表所示(正值为甲企业增加的市场占有份额，负

16、值为减少的市场占有份额 )试通过博弈分析，确定两个企业各自的最优策略。乙企业策略123甲企业策略110-1121210-53685解 : 求矩阵的鞍点 (3,3),即甲乙均采用策略 315. 某企业有甲、乙两个公司，每年的税额分别是400 万元和 1200 万元。对于每个公司，企业可以如实申报税款，或者篡改帐目，称税额为零。而国家税务局由于人力所限， 对该企业每年只能检查一个公司的帐目。 如果税务局发现有偷税现象，则该公司不但要如数缴纳税款，而且将被处以相当于一半税款的罚金。（ 1） 试将此问题写成一个矩阵博弈模型， 并求出税务局和企业的最优策略及税务局从该企业收到的平均税款（含罚金） 。（

17、2） 税务局应将罚金提高到税款的多少倍，才能迫使该企业不敢漏税？解: (1) 税务局有两个策略： 查甲公司和查乙公司。 企业有 4 个策略： (T,T),(F,F),(T,F),(F,T).其中 T 表示如实申报， F 表示偷税，括号内的一对字母依次表示公司甲和乙的做法。 例如 (T,F) 表示公司甲如实申报， 公司乙偷税。 下表给出税务局从该企业征收的税款和罚金之和， 这是一个有限二人零和搏弈。企业(T,T)(F,F)(T,F)(F,T)税务局查甲166418查乙16182212这个搏弈没有鞍点。考虑下述线性规划：maxus.t.16 x116x2u6x118x2u4x122x2u18x11

18、2 x2ux1x21x1 , x20*解得： u=14,x 1 =1/3,x 2 =2/316 y16 y24 y318 y4 14y1y2y3y41*) 处，线性规划中第1和第 3个约束为：由于 x=(x 1,x 2*16x1 +16x2 =16u4x1 * +22x2* =16u*故 y1 =0,y 3 =0, 解得： y2 =1/3,y 4 =2/3所以， 当罚金是税款的一半时，税务局的最优策略是以1/3 的概率检查公司甲，以 2/3 的概率检查公司乙。 而企业的最优策略是以1/3 的概率让两个公司都偷税，以 2/3 的概率让公司甲偷税，公司乙如实申报税款。这样企业上缴的税款和罚金之和的

19、平均值是1400 万元。（2） 设罚金是应交税款的a 倍，令 k=a+1，税务局从该企业收得的税收与罚金之和如下表：企业(T,T)(F,F)(T,F)(F,T)税务局查甲164k44k+12查乙1612k4+12k12考虑线性规划 :minx1 x2 s.t.16x1 16x2 14kx112 kx2 14x1 (4 12k) x2 1(4k12) x1 12x2 1x1, x2 0和maxy1 y2 y3 y4 s.t.16 y1 4ky2 4 y3(4k 12) y4 116 y112 y2 (412k) y3 12 y4 1y j 0j1,2,3,4用单纯形法解上式, 经过计算得到下表

20、:cj111100CBYBby1y2y3y4z1z11y 1/161k/4+1/60k/4+5/61/6+1/48k1/48k11y 002/31-1/3-1/12k1/123j01/2-k/401/2-k/41/16k-1/6-1/16k企业不敢漏税相当于只能采用策略(T,T),*=1, y*=0, 由上表 ,只须即 y12=0, y 3 =0, y 41/2-k/4 0, 即 k 2, 得 a 1, 故为了使企业不敢偷税, 应规定罚金不少于应缴税款。那是心与心的交汇，是相视的莞尔一笑，是一杯饮了半盏的酒，沉香在喉，甜润在心。红尘中，我们会相遇一些人，一些事，跌跌撞撞里，逐渐懂得了这世界，懂

21、得如何经营自己的内心，使它柔韧，更适应这风雨征途，而不会在过往的错失里纠结懊悔一生。时光若水，趟过岁月的河，那些旧日情怀，或温暖或痛楚，总会在心中烙下深深浅浅的痕。生命是一座时光驿站，人们在那里来来去去。一些人若长亭古道边的萋萋芳草，沦为泛泛之交；一些人却像深山断崖边的幽兰，只一株，便会馨香满谷。人生，唯有品格心性相似的人，才可以在锦瑟华年里相遇相知，互为欣赏，互为懂得，并沉淀下来，做一生的朋友。试问，你的生命里，有无来过这样一个人呢？张爱玲说 “因为懂得，所以慈悲”.于千万人群中，遇见你要遇见的人，没有早一步，也没有晚一步，四目相对，只淡淡的问候一句：哦！原来你也在这里，这便足够。世间最近与最遥远的距离，来自于心灵与心灵。相遇了，可以彼此陌生，人在咫尺心在天涯，也可初见如旧，眼光交汇的那一刻，抵得人间万般暖。