《对策论运筹学.docx》由会员分享，可在线阅读，更多相关《对策论运筹学.docx（17页珍藏版）》请在三一办公上搜索。
1、对策论运筹学 习题解答 1. 已知矩阵博弈局中人I的赢得矩阵如下，求最优纯策略及博弈值。 44 549475456330-1-22-21-336 2-1-50682-2-11-2-6 -4-244解: (1) (5)4 5943345647665 所以(a3,b1),V=5 53839680-1(-2)2(-2)-2-21-33-6-6(2) 2-1-50-4-5 12(-2)-1(-2)-2 2 2 -2 3 -2所以 (a1,b3),(a1,b5),(a3,b3),(a3,b5),V=-2 2 甲乙两国进行乒乓球团体赛，每国由三个人组成一个队参加比赛。甲国的人员根据不同的组合可组成4个队，
2、乙国的人员可组成3个队，根据以往的比赛记录，已知各种组成队法相遇后甲国的得分如下表所示 1队 2队 3队 甲 乙 1队 -5 1 -7 2队 3 2 4 3队 8 -1 -8 4队 -2 -1 6 问双方应各派哪个队上场是最优决策? 解: -51-7-73(2)428-1-8-8 所以(a2,b2),V=2 -2-16-2826答: 双方应均派第2队出场 3. 对任意一个m行n列的实数矩阵A=,试证有下式成立 - 1 - maxminaijminmaxaij 1im1jn1jn1im证: i,j,1im,1jn 有:minaijaij1jnj,有 maxminaijmaxaij1im1jn1i
3、m maxminaijminmaxaij1im1jn1jn1im4. 某城区有A、B、C三个居民小区，分别居住着40，30%，30%的居民，有两个公司甲和乙都计划在区内建造超市，公司甲计划建两个，公司乙计划建一个，每个公司都知道，如果在某个小区内设有两个超市，那么这两个超市将平分该区的消费，如果在某个小区只有一个超市，则该超市将独揽这个小区的消费。如果在一个小区没有超市，则该小区的消费将平分给三个超市。每个公司都想使自己的营业额尽可能地多试把这个问题表示成一个矩阵博弈，写出公司甲的赢得矩阵，井求两个公司的最优策略以及各占有多大的市场份额。 解: 甲公司的策略集为(A,B), (A,C), (B
4、,C) 乙公司的策略集为A,B,C ABC(A,B)(0.7)0.750.70.70.7 (0.7)0.70.75甲的赢得矩阵为: (A,C)(B,C)0.60.7170.7170.60.70.750.75所以甲选(A,B)或(A,C),占70%份额。乙选A,占30%份额. 5 一个病人的症状说明他可能患a，b，c三种病中的一种，有两种药C，D可用，这两种药对这三种病的治愈率为 病 a b c 药 C 0.5 0.4 0.6 D 0.7 0.1 0.8 问医生应开哪一种药才能最稳妥? 0.5(0.4)0.60.4解: 0.70.10.80.1 最优策略为(a1,b2) 0.70.40.8答:应
5、开C药较为稳妥. 6设矩阵博弈局中人I的赢得为 -33 2-3A=20- 2 - (1) 当局中人I采用策略x=(0.2，0.5，0.3)时，应采用什么策略? (2) 当局中人采用策略y=(5/7，2/7)时，I应采用什么策略? (2) x和y是否是最优策略?为什么?若是，试给出另一个局中人的最优策略和博弈值。 解: (1)设II的策略为Y=(y1,y2),则 0.2(-3)+0.52+0.30=0.40.33+0.5(-3)+0.32=-0.3min 0.4y1-0.3y2s.t. y1+y2=1得:y1=0,y2=1,V1=-0.3,所以最优解为(0,1),V=-0.3 (2) 设II的策
6、略为X=(x1,x2,x3),则 529(-3)+3=-777524 2+(-3)=777540+2=77944max -x1+x2+x3777 s.t. x1+x2+x3=1所以x1=0,x20,1,x3=1-x1,即I的最优策略为(0,a,1-a),a0,1,V=4/7 (3) 对于(x1,x2,x3)=(0.2,0.5,0.3),因为xi0,Y*=(0,1),但a1jyj=3a2jyj=-3 i=1i=133所以(0.2,0.5,0.3)不是最优解. 对于(y1,y2)=(5/7,2/7),因为yi0,X*=(0,a,1-a)满足: 0(-3)+2a+0(1-a)=2a0(3)+(-3)
7、a+2(1-a)=2-5a 令2a=2-5a,得a=27所以(5/7,2/7)是II的最优解,对应I的最优策略为(0,2/7,5/7),V=4/7 7.给定矩阵博弈局中人I的赢得为 531 -133A=311- 3 - 试验证x*=(1/2，1/2，0)和y*=(1/4，0，3/4)分别是局中人I和的最优混合策略，井求博弈值。 解:可验证满足: (1)若x0,则*iayijj=1mn*j=V; (2)若y0,则n*j*axiji=V i=1(3)若ayijj=1m*jV,则y*j=0 且V=2 8. 已知矩阵博弈的赢得矩阵如下，试用线性方程组法求最优混合策略及博弈值。 226012 201 2
8、102 120822解: (1)将矩阵中各元素减2得: 004 080A- 2=6004y3=v6x3=v8y=v8x=v22 6y1=v4x1=vy1+y2+y3=1x1+x2+x3=1解得: X*=(6/13,3/13,4/13),Y*=(4/13,3/13,6/13),V=50/13 (2) y2+2y3=v2x2+x3=v2y+y=vx+2x=v1133 y+2y=v2x+x=v2121y1+y2+y3=1x1+x2+x3=1解得: X*=(1/3,1/3,1/3),Y*=(1/3,1/3,1/3),V=1 9用简便方法求给定矩阵博弈的解与值，赢得矩阵如下 - 4 - 020202 9
9、2-28308解: (1) 用优超法简化矩阵得: 1334 0-111033495509573 67473860a2a43x4=v3y3=v02 2x2=v 2y4=v 解方程组得: 30x+x=1y+y=14423b3b4X*=(0,3/5,0,2/5),Y*=(0,0,2/5,3/5),V=6/5 (2) 用优超法则简化矩阵得: a3a473 各元素减7得: a347a4b4b5-3x4=v-3y4=v0-4 则 -4x3=v -4y5=v -30x+x=1y+y=14534b4b5解方程组得: x4=4/7,x3=3/7,v=-12/7,y4=4/7,y5=3/7 所以得X*=(0,0,
10、3/7,4/7,0),Y*=(0,0,0,4/7,3/7),V=37/7 10用线性规划求下述矩阵博弈的混合策略解及博弈值，已知其赢得矩阵为 0223-24 -142 301 262112解: (1) 线性规划: max vmin vs.t. 2y2+2y3v 3y1+y3v 2y1+y2+y3v y1+y2+y3=1y1,y2,y30s.t. 3x2+2x3v 2x1+x3v 2x1+x2+x3v x1+x2+x3=1x1,x2,x30解得: X*=(1/3,0,2/3),Y*=(1/3,1/3,1/3),V=4/3 (2) 矩阵各元素加2得: 506 线性规划为: 164A+2=448-
11、5 - max vs.t. 5x1+x2+4x3v 6x2+4x3v 6x1+4x2+8x3v x1+x2+x3=1x1,x2,x30min vs.t. 5y1+6y3v y1+6y2+4y3v 4y1+4y2+8y3v y1+y2+y3=1y1,y2,y30解得: X*=(0,0,1),Y*=(2/5,3/5,0),V=4-2=2 11. 甲、乙两方交战。乙方用三个师守城，有两条公路通入该城，甲方用两个师攻城，可能两个师各走一条公路，也可能从一条公路进攻。乙方可用三个师防守某一条公路，也可用两个师防守一条公路，用第三个师防守另一条公路哪方军队在一条公路上数量多，哪方军队就控制住这条公路如果双
12、方在同一条公路上的数量相同，则乙方控制住公路和甲方攻入城的机会各半，试把这个问题构成一个博弈模型。并求甲、乙双方的最优策略以及甲方攻入城的可能性。 解: 设两条路为A,B 甲方攻城的策略集为:2A,AB,2B 乙方宁城的策略集为:3A,2AB,A2B,3B, 甲方赢得矩阵为: 00.511A=10.50.51 110.50线性方程组为: x2+x3=v0.5y2+y3+y4=v0.5x+0.5x+x=v123y+0.5y+0.5y+y=v1234 x1+0.5x2+0.5x3=v y1+y2+0.5y3=vx1+x2=vy1+y2+y3+y4=1x1+x2+x3=1解得:x*=(1/3,1/3
13、,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)mn, B=(bij)mn。如果 bij=k aij i1,2,m j1,2,n 其中k0，试证明Gl和G2具有相同的最优策略且它们的博弈值V1和V2之间有关系： V2= kV1 证: 设G*1=(X
14、,Y,E1), G*2=(X,Y,E2)为G1,G2的混合扩充,则对X和Y中任意的x,y,有: - 6 - E2(x,y)=bijxiyj=kaijxiyj=kaijxiyj=kE1(x,y)i=1j=1i=1j=1i=1j=1mnmnmn maxminE2(x,y)=k maxminE1(x,y)xXyYxXyY因此(x*,y*)是G1的最优策略当且仅当(x*,y*)是G2的最优策略,且V2=kV1 13甲、乙二人游戏，每人出一个或两个手指，同时又把猜测对方所出的指数叫出来如果只有一个人猜测正确，则他所赢得的数目为二人所出指数之和，如果两个人都猜对或都猜错，则算平局，都不得分。写出该博弈中各
15、局中人的策略集合及甲的赢得矩阵。 解:若令(i,j)中i为出的指数,j为叫的数目,则甲乙的策略集均为: (1,1),(1,2),(2,1),(2,2) 甲的赢得矩阵为: (1,1) (1,2) (2,1) (2,2)(1,1) 0 2 -3 0 003A=(1,2)-2 (2,1)300-4(2,2)0-34014 甲、乙两个企业生产同一种产品，两个企业都想通过改革管理获取更多的市场销售份额甲企业的策略措施有：降低产品价格；提高产品质量，延长保修年限：推出新产品乙企业考虑的措施有：增加广告费用；增设维修网点，扩大维修服务；改进产品性能。假定市场份额一定，由于各自采取的策略措施不同，通过预测，今
16、后两个企业的市场占有份额变动情况如下表所示(正值为甲企业增加的市场占有份额，负值为减少的市场占有份额)试通过博弈分析，确定两个企业各自的最优策略。 乙企业策略 1 2 3 甲企业策略 1 10 -1 1 2 12 10 -5 3 6 8 5 解:求矩阵的鞍点(3,3),即甲乙均采用策略3 15. 某企业有甲、乙两个公司，每年的税额分别是400万元和1200万元。对于每个公司，企业可以如实申报税款，或者篡改帐目，称税额为零。而国家税务局由于人力所限，对该企业每年只能检查一个公司的帐目。如果税务局发现有偷税现象，则该公司不但要如数缴纳税款，而且将被处以相当于一半税款的罚金。 试将此问题写成一个矩阵
17、博弈模型，并求出税务局和企业的最优策略及税务局从该企业收到的平均税款。 税务局应将罚金提高到税款的多少倍，才能迫使该企业不敢漏税？ 解: (1) 税务局有两个策略：查甲公司和查乙公司。企业有4个策略：(T,T),(F,F),(T,F),(F,T).其中T表示如实申报，F表示偷税，括号内的一对字母依次表示公司甲和乙的做法。例如(T,F)表示公司甲如实申报，公司乙偷税。下表给出税务局从该企业征收的税款和罚金之和，这是一个有限二人零和搏弈。 - 7 - 企业 税务局 查甲 查乙 (T,T) 16 16 (F,F) 6 18 (T,F) 4 22 (F,T) 18 12 这个搏弈没有鞍点。考虑下述线性
18、规划： maxus.t.16x1+16x2u6x1+18x2u4x1+22x2u 18x1+12x2ux1+x2=1x1,x20解得：u=14,x1=1/3,x2=2/3 再考虑： *16y1+6y2+4y3+18y4=14y1+y2+y3+y4=1*由于x=(x1,x2)处，线性规划中第1和第3个约束为： *16x1+16x2=16u *4x1+22x2=16u *故y1=0,y3=0,解得：y2=1/3,y4=2/3 所以，当罚金是税款的一半时，税务局的最优策略是以1/3的概率检查公司甲，以2/3的概率检查公司乙。而企业的最优策略是以1/3的概率让两个公司都偷税，以2/3的概率让公司甲偷税
19、，公司乙如实申报税款。这样企业上缴的税款和罚金之和的平均值是1400万元。 设罚金是应交税款的a倍，令k=a+1，税务局从该企业收得的税收与罚金之和如下表： 企业 税务局 查甲 查乙 考虑线性规划: (T,T) 16 16 (F,F) 4k 12k (T,F) 4 4+12k (F,T) 4k+12 12 mins.t.x1+x216x1+16x214kx1+12kx214x1+(4+12k)x21(4k+12)x1+12x21x1,x20和 - 8 - maxs.t.y1+y2+y3+y416y1+4ky2+4y3+(4k+12)y4116y1+12y2+(4+12k)y3+12y41yj0j=1,2,3,4用单纯形法解上式,经过计算得到下表: cj CB 1 1 j YB y1 y3 b 1/16 0 1 1 1 1 0 0 y1 1 0 0 y2 2/3 *y3 1 *y4 -1/3 *z1 -1/12k z1 1/12 k/4+1/6 0 1/2-k/4 0 k/4+5/6 1/6+1/48k 1/48k 1/2-k/4 1/16k-1/6 -1/16k 企业不敢漏税相当于只能采用策略(T,T),即y1=1, y2=0, y3=0, y4=0,由上表,只须 1/2-k/40,即k2,得a1,故为了使企业不敢偷税,应规定罚金不少于应缴税款。 - 9 -
