对策论运筹学
习题解答
1. 已知矩阵博弈局中人I 的赢得矩阵如下，求最优纯策略及博弈值。
（1） ??
???????
???8354
66756544
3494 （2） ?????
?
?
??
???------------21221
405126331222
210 解: (1) ()
8
695 354
38354667565443494?
????????
??? 所以),(13βα,V=5
(2) 2
- 3 2- 2 2 2562)2(1)2(214051263312)2(2)2(10----?
??
?????????------------
所以 ),(31βα,),(51βα,),(33βα,),(53βα,V=-2
2． 甲乙两国进行乒乓球团体赛，每国由三个人组成一个队参加比赛。甲国的人员根据不同的组合可组成4个队，乙国的人员可组成3个队，根据以往的比赛记
解:
62828276128184)2(3715---???
?????????------ 所以),(22βα,V=2 答: 双方应均派第2队出场
3. 对任意一个m 行n 列的实数矩阵A=（a ij ）,试证有下式成立
ij m
i n j ij n
j m i a a ≤≤≤≤≤≤≤≤≤1111max min min max
证:
ij
m
i n j ij n
j m i ij
m
i ij n
j m i ij
ij n
j a a a a j a a n j m i j i ≤≤≤≤≤≤≤≤≤≤≤≤≤≤≤≤≤∴≤?∴≤≤≤≤≤?11111111max min min max max min max ,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(),(),(),(??
????????C B C A B A C
B A 所以甲选(A,B)或(A,C),占70%份额。乙选A,占30%份额.
5． 一个病人的症状说明他可能患a ，b ，c 三种病中的一种，有两种药C ，D 可
解: 8.04.07.01.04
.08.01.07.06.0)4.0(5.0?????? 最优策略为),(21βα
答:应开C 药较为稳妥.
6．设矩阵博弈局中人I 的赢得为
A=??
??
?
?????--203233
(1) 当局中人I 采用策略x=(0.2，0.5，0.3)时，Ⅱ应采用什么策略? (2) 当局中人Ⅱ采用策略y=(5/7，2/7)时，I 应采用什么策略?
(2) x 和y 是否是最优策略?为什么?若是，试给出另一个局中人的最优策略和
博弈值。
解: (1)设II 的策略为Y=(y 1,y 2),则
3
.023.0)3(5.033.04
.003.025.0)3(2.0-=?+-?+?=?+?+-?
1
y y s.t.0.3y -0.4y min 2121=+
得:y 1=0,y 2=1,V 1=-0.3,所以最优解为(0,1),V=-0.3 (2) 设II 的策略为X=(x 1,x 2,x 3),则
74275074)3(7227579372)3(75=
?+=-?+?-=?+-? 1
x s.t.x 74x 74x 79- max 3213
21=++++x x 所以13211],1,0[,0x x x x -=∈=,即I 的最优策略为7/4],1,0[),1,,0(=∈-V ααα (3) 对于(x 1,x 2,x 3)=(0.2,0.5,0.3),因为∑∑==-=≠==≠3
1
23
1
133),1,0(*,0i j j i j j i y a y a Y x 但
所以(0.2,0.5,0.3)不是最优解.
对于(y 1,y 2)=(5/7,2/7),因为)1,,0(*,0αα-=≠X y i 满足:
7
2
,52252)1(2)3()3(02)1(02)3(0=
-=-=-?+?-+?=-?+?+-?ααααααα
αα得令
所以(5/7,2/7)是II 的最优解,对应I 的最优策略为(0,2/7,5/7),V=4/7
7.给定矩阵博弈局中人I 的赢得为
A=??
??
?
?????-113331135
试验证x*=(1/2，1/2，0)和y*=(1/4，0，3/4)分别是局中人I 和Ⅱ的最优混合策略，井求博弈值。 解:可验证满足:
(1)若;,01
**V y a
x n
j j ij
i
=≠∑=则
(2)若V x a y m
i i ij j
=≠∑=1
**
,0则
(3)若
;0,*
1
*=<∑=i n
j j ij
x V y a
则
(4)若
0,*1
*=>∑=j m
i i ij y V x
a 则
且V=2
8. 已知矩阵博弈的赢得矩阵如下，试用线性方程组法求最优混合策略及博弈值。
（1） ??????????2282102622 （2） ??
??
?
?????021102210 解: (1)将矩阵中各元素减2得:
A- 2=??
??
?
?????006080400 ??????
?=++===1486321123x x x v x v x v x ??
?????=++===1
68432112
3y y y v y v y v y 解得: X *=(6/13,3/13,4/13),Y *=(4/13,3/13,6/13),V=50/13
(2)
??????
?=++=+=+=+1222321213132x x x v x x v x x v x x ???????=++=+=+=+1
222321213
132y y y v y y v y y v y y 解得: X *=(1/3,1/3,1/3),Y *=(1/3,1/3,1/3),V=1
9．用简便方法（降阶或化零元）求给定矩阵博弈的解与值，赢得矩阵如下
（1） ?????
??
??
???--031
12210204
302
31 （2） ???
????
????
?????06838
7476837599
05592
43300
解: (1) 用优超法简化矩阵得:
???? ??03204
2
4
3ααββ ?????=+==1234224x x v x v x ???
??=+==12343
43y y v y v y 解方程组得: X *=(0,3/5,0,2/5),Y *=(0,0,2/5,3/5),V=6/5 (2) 用优超法则简化矩阵得:
???
? ??74374
35
4ααββ 各元素减7得: ???? ??--0340435
4ααββ 则 ?????=+=-=-1434334x x v x v x ???
??=+=-=-14354
54y y v y v
y 解方程组得: 7/3,7/4,7/12,7/3,7/45434==-===y y v x x
所以得X *=(0,0,3/7,4/7,0),Y *=(0,0,0,4/7,3/7),V=37/7
10．用线性规划求下述矩阵博弈的混合策略解及博弈值，已知其赢得矩阵为
（1） ??????????112103220 （2） ??
??
?
?????--622241423 解: (1) 线性规划:
x ,x ,x 1x x x v x x 2x v x 2x v
2x 3x s.t.max v 3213213213132≥=++≥++≥+≥+ 0
y ,y ,y 1y y y v y y 2y v y 3y v 2y 2y s.t.min v
3213213213132≥=++≤++≤+≤+
解得: X *=(1/3,0,2/3),Y *=(1/3,1/3,1/3),V=4/3 (2) 矩阵各元素加2得:
A+2=??
??
?
?????844461605 线性规划为:
x ,x ,x 1x x x v x 8x 46x v x 46x v 4x x 5x s.t.max v
32132132132321≥=++≥++≥+≥++ 0
y ,y ,y 1y y y v y 8y 44y v y 46y v 6y 5y s.t.min v
32132132132131≥=++≤++≤++≤+y
解得: X *=(0,0,1),Y *=(2/5,3/5,0),V=4-2=2
11. 甲、乙两方交战。乙方用三个师守城，有两条公路通入该城，甲方用两个师攻城，可能两个师各走一条公路，也可能从一条公路进攻。乙方可用三个师防守某一条公路，也可用两个师防守一条公路，用第三个师防守另一条公路．哪方军队在一条公路上数量多，哪方军队就控制住这条公路．如果双方在同一条公路上的数量相同，则乙方控制住公路和甲方攻入城的机会各半，试把这个问题构成一个博弈模型。并求甲、乙双方的最优策略以及甲方攻入城的可能性。 解: 设两条路为A,B
甲方攻城的策略集为:{2A,AB,2B}
乙方宁城的策略集为:{3A,2AB,A2B,3B}, 甲方赢得矩阵为:
????
? ??=00.51110.50.51110.50A
线性方程组为: ????
?????
=++=+=++=++=+15.05.05.05.03212132132132x x x v
x x v x x x v
x x x v x x ??????
?=+++=++=+++=++15.05.05.05.043213214
321432y y y y v y y y v y y y y v y y y 解得: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．设矩阵博弈G l =(S 1,S 2,Ａ)和G 2=(S 1,S 2,B)，其中A=(a ij )m ╳n , B=(b ij )m ╳n 。如果
b ij =k a ij i ＝1,2,…,m j ＝1,2,…,n
其中k>0，试证明G l 和G 2具有相同的最优策略且它们的博弈值V 1和V 2之间有关系：
V 2= kV 1
证: 设G *1=(X,Y ,E 1), G *2=(X,Y ,E 2)为G 1,G 2的混合扩充,则对X 和Y 中任意的x,y,有:
y)
(x,E min max y)(x,E min max y)
(x,E y)(x,E 1y X
x 2y X
x 111
11
11
2Y
Y
m i n j m i n
j j i ij j i ij m i n j j i ij k k y x a k y x ka y x b ∈∈∈∈=======∴====∑∑∑∑∑∑
因此(x *,y *)是G 1的最优策略当且仅当(x *,y *)是G 2的最优策略,且V 2=kV 1
13．甲、乙二人游戏，每人出一个或两个手指，同时又把猜测对方所出的指数叫出来．如果只有一个人猜测正确，则他所赢得的数目为二人所出指数之和，如果两个人都猜对或都猜错，则算平局，都不得分。写出该博弈中各局中人的策略集合及甲的赢得矩阵。
解:若令(i,j)中i 为出的指数,j 为叫的数目,则甲乙的策略集均为: {(1,1),(1,2),(2,1),(2,2)} 甲的赢得矩阵为:
??
???
?
??????----=043040033002 0 3 2 0 )2,2()1,2()2,1()1,1()
2,2( )1,2( )2,1( )1,1(A 14． 甲、乙两个企业生产同一种产品，两个企业都想通过改革管理获取更多的市场销售份额．甲企业的策略措施有：①降低产品价格；②提高产品质量，延长保修年限：③推出新产品．乙企业考虑的措施有：①增加广告费用；②增设维修网点，扩大维修服务；③改进产品性能。假定市场份额一定，由于各自采取的策略措施不同，通过预测，今后两个企业的市场占有份额变动情况如下表所示(正值为甲企业增加的市场占有份额，负值为减少的市场占有份额)．试通过博弈分
解
15. 某企业有甲、乙两个公司，每年的税额分别是400万元和1200万元。对于每个公司，企业可以如实申报税款，或者篡改帐目，称税额为零。而国家税务局由于人力所限，对该企业每年只能检查一个公司的帐目。如果税务局发现有偷税现象，则该公司不但要如数缴纳税款，而且将被处以相当于一半税款的罚金。 （1） 试将此问题写成一个矩阵博弈模型，并求出税务局和企业的最优策略及税
务局从该企业收到的平均税款（含罚金）。
（2） 税务局应将罚金提高到税款的多少倍，才能迫使该企业不敢漏税？
解: (1) 税务局有两个策略：查甲公司和查乙公司。企业有4个策略：(T,T),(F,F),(T,F),(F,T).其中T 表示如实申报，F 表示偷税，括号内的一对字母依次表示公司甲和乙的做法。例如(T,F)表示公司甲如实申报，公司乙偷税。下表给出税务局从该企业征收的税款和罚金之和，这是一个有限二人零和搏弈。
这个搏弈没有鞍点。考虑下述线性规划：
,112182241861616.
.max 212121212121≥=+≥+≥+≥+≥+x x x x u x x u x x u x x u x x t s u
解得：u=14,x 1*
=1/3,x 2*
=2/3 再考虑：
1
1418461643214321=+++=+++y y y y y y y y
由于x=(x 1*
,x 2*
)处，线性规划中第1和第3个约束为：
16x 1*+16x 2*
=16>u 4x 1*+22x 2*
=16>u
故y 1*=0,y 3*=0,解得：y 2*=1/3,y 4*
=2/3
所以，当罚金是税款的一半时，税务局的最优策略是以1/3的概率检查公司甲，以2/3的概率检查公司乙。而企业的最优策略是以1/3的概率让两个公司都偷税，以2/3的概率让公司甲偷税，公司乙如实申报税款。这样企业上缴的税款和罚金之和的平均值是1400万元。 （2） 设罚金是应交税款的a 倍，令k=a+1，税务局从该企业收得的税收与罚金之和如下表：
考虑线性规划:
','1'12')124(1')124('41'12'41'16'16.
.''min 212121212121≥≥++≥++≥+≥++x x x x k x k x kx kx x x t s x x
和
4
,3,2,10
'1'12')124('12'161')124('4'4'16.
.'
'''max 432143214321=≥≤++++≤+++++++j y y y k y y y k y ky y t s y y y y j
用单纯形法解上式,经过计算得到下表:
12341/2-k/4≤0,即k ≥2,得a ≥1,故为了使企业不敢偷税,应规定罚金不少于应缴税款。
运筹学参考文献
参考文献 [1] 胡运权．运筹学教程．北京：高等教育出版社，2005 [2] 胡运权．运筹学基础及应用．哈尔滨：哈尔滨工业大学出版社，1998 [3] 《运筹学》编写组．运筹学．北京：清华大学出版社， 1990 [4] 张莹．运筹学基础．北京：清华大学出版社，2002 [5] 袁亚湘，孙文瑜．最优化理论与方法．北京：科学出版社，1999 [6] 何坚勇．运筹学基础．北京：清华大学出版社， 2000 [7] 马振华等．现代应用数学手册—运筹学与最优化理论卷．北京：清华大学出版社，2000 [8] 牛映武．运筹学．西安：西安交通大学出版社，1993 [9] 梁工谦．运筹学- 典型题解析集自测试题。西安：西北工业大学出版社，2002 [10] 徐永仁．运筹学试题精选与答题技巧．哈尔滨：哈尔滨工业大学出版社，2000 [11] 徐玖平，胡知能，王緌．运筹学(第二版)．北京：科学出版社，2004 [12] 刘满风，傅波，聂高辉．运筹学模型与方法教程- 例题分析与题解．北京：清华大学出版社，2001 [13] 胡运权．运筹学习题集．北京：清华大学出版社，2002 [14] 盛昭瀚，朱乔，吴广谋．DEA理论、方法与应用．北京：科学出版社，1996 [15] Frederick ~S．Hillier，Gerald~J．Lieberman．Introduction to Operations Research (6th Ed．)．Beijing：China Machine Press/ McGraw - Hill，1999 [16] J．D．Wiest，F．K．Levy．统筹方法管理指南．北京：机械工业出版社，1983 [17] 王元等．华罗庚科普著作选集．上海：上海教育出版社，1984 [18] 江景波等．网络计划技术．北京：冶金工业出版社，1983 [19] David R．Anderson，Dennis J．Sweeney，Thomas A．Williams．数据、模型与决策．北京：机械工业出版社，2003 [20] Frederick S．Hillier，Mark S．Hillier，Jerald J．Lieberman．Introduction to Management Science．Beijing：McGraw - Hill Comanies，Inc．，2001
对策论_运筹学
习题解答 1. 已知矩阵博弈局中人I 的赢得矩阵如下，求最优纯策略及博弈值。 （1） ?? ??????? ???83 54 66756544 3494 （2） ????? ? ??? ???------------21221405126331222 210 解: (1) () 8 695 354 38354667565443494? ???????? ??? 所以),(13βα,V=5 (2) 2 - 3 2- 2 2 2562)2(1)2(214051263312)2(2)2(10----??? ?????????------------ 所以 ),(31βα,),(51βα,),(33βα,),(53βα,V=-2 2． 甲乙两国进行乒乓球团体赛，每国由三个人组成一个队参加比赛。甲国的人员根据不同的组合可组成4个队，乙国的人员可组成3个队，根据以往的比赛记 解: 6 282 8276128184)2(3715---??? ?????????------ 所以),(22βα,V=2 答: 双方应均派第2队出场 3. 对任意一个m 行n 列的实数矩阵A=（a ij ）,试证有下式成立
ij m i n j ij n j m i a a ≤≤≤≤≤≤≤≤≤1111max min min max 证: ij m i n j ij n j m i ij m i ij n j m i ij ij n j a a a a j a a n j m i j i ≤≤≤≤≤≤≤≤≤≤≤≤≤≤≤≤≤∴≤?∴≤≤≤≤≤?11111111max min min max max min max ,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(),(),(),(?? ????????C B C A B A C B A 所以甲选(A,B)或(A,C),占70%份额。乙选A,占30%份额. 5． 一个病人的症状说明他可能患a ，b ，c 三种病中的一种，有两种药C ，D 可 解: 8.04.07.01.04 .08.01.07.06.0)4.0(5.0?????? 最优策略为),(21βα 答:应开C 药较为稳妥. 6．设矩阵博弈局中人I 的赢得为 A=?? ?? ? ?????--203233
运筹学第六章作业的参考答案
第六章作业的参考答案 233P 6. 证明：若树T 的最大次k ≥，则T 至少有k 个次为1的点。 证：任给树)E ,N (T =，因为 T 连通，所以 T 中每个点的次至少为1，即任给N i ∈，都有1)i (d ≥。 （反证）设T 中次为1的点有m 个，k m <。则 )1|(|2)1|(|2)1|(|2)(->-+-=+--+≥∑∈N m k N k m N m i d N i 另一方面， ),1|(|2||2)(-==∑∈N E i d N i 矛盾。所以，k m ≥。即，T 至少有k 个次为1的点。 233P 7、用Kruskal 算法求下图所示网络中的最小树。 解：
上图中粗线部分为所求的最小树，其权为1+2+3+5=11. 233P 9、用Dijkstra 算法求下图所示有向网络中自点①到其它各点的最短有向路.
解：
上图中粗线部分为点①到其它各点的最短有向路. 233P 10、用Ford-Fulkerson 算法求下图所示有向网络中从①到⑥的最大流。 解： ② 1 ④ 3 2 4 3 ① 2 ⑥ 3 3 ③ 4 ⑤ ② 1,0 ④ 3,0 2,0 4,0 3,0 ① 2,0 ⑥ 3,0 3,0 ③ 4,0 ⑤
(+1,3) ② 1,0 ④ 3,0 2,0 4,0 3,0 (+5,3) ① 2,0 ⑥ 3,0 3,0 ③ 4,0 ⑤ (+1,3) (+3,3) (+1,3) (+2,1) ② 1,0 ④ 3,0 2,0 4,0 3,0 (+4,1) ① 2,0 ⑥ 3,3 3,3 ③ 4,3 ⑤ (+1,2) ② 1,1 ④ 3,1 2,0 4,0 3,1 ① 2,0 ⑥ 3,3 3,3 ③ 4,3 ⑤ ),(∞- ),(∞- ),(∞- 所以，最大流的值为4.