矩阵对策的最优纯策略 .pdf

《矩阵对策的最优纯策略 .pdf》由会员分享，可在线阅读，更多相关《矩阵对策的最优纯策略 .pdf（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、授课时间授课地点实到人数授课题目矩阵对策的求解授课专业班级教学目的与教学要求了解矩阵对策问题及其求解方法，以期对大家的工作、科研、学习和生活提供帮助主要内容一、 矩阵对策的数学模型二、 矩阵对策的最优纯策略三、 矩阵对策的最优混合策略重点与难点?有鞍点的矩阵对策问题及求解?没有鞍点的矩阵对策问题及求解教学方法手段（教具）案例教学参考资料韩伯棠 管理运筹学高等教育出版社胡运权 运筹学高等教育出版社刁在筠、刘桂真运筹学高教出版社课后作业与思考题教学后记没有鞍点的矩阵对策的概念及求解的理解是一个难点，每个局中人采用每种策略的概率有何实际意义，用生活中的小故事引入使得学生更容易理解和认可。名师资料总结

2、 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 9 页 - - - - - - - - - 教学过程时间分配矩阵对策的求解在众 多的对策模型中 ，占有重 要地位的 是 二人有 限零和对策（finite two-person zero-sum game ） ，又称矩阵对策。 这类对策是到目前为止在理论研究和求解方法方面都比较完善的一个对策分支。矩阵对策可以说是一类最简单的对策模型，其研究思想和方法十分具有代表性，体现了对策论的一般思想和方法，且矩阵对策的基本结果也是研究其他对策模型的基

3、础。（一）矩阵对策的数学模型矩阵对策即为二人有限零和对策。 “二人”是指参加对策的局中人有两个；“有限”是指每个局中人的策略集均为有限集；“零和”是指在任一局势下，两个局中人的赢得之和总等于零，即一个局中人的所得值恰好等于另一局中人的所失值，双方的利益是完全对抗的。 “齐王赛马”就是一个矩阵对策的例子，齐王和田忌各有 6 个策略，一局对策后，齐王的所得必为田忌的所失。一般， 用和分别表示两个局中人， 并设局中人有 m个纯策略1,m，局 中 人 有n 个 纯 策 略1,n； 则 局 中 人 和 的 策 略 集 分 别 为11,mS和21,nS。当局中人选定纯策略i和局中人选定纯策略j后，就形成了

4、一个纯局势,ij，这样的纯局势共有m n个。对任一纯局势,ij，记局中人的赢得值为ija ，称111212122212nnmmmnaaaaaaAaaa为局中人的赢得矩阵。局中人的赢得矩阵就是A。当局中人，的策略集12,S S 及局中人的赢得矩阵A确定后，一个矩阵对策也就给定了，记为12,GS SA 。在齐王赛马的例子中，齐王的赢得矩阵为：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 9 页 - - - - - - - - - 3111111311111131111113

5、11111131111113A（二）矩阵对策的最优纯策略当矩阵对策模型给定后，各局中人面临的问题便是：如何选择对自己最有利的纯策略以取得最大的赢得（或最少的损失）？例 1、甲乙乒乓球队进行团体对抗赛，每队由三名球员组成， 双方都可排成三种不同的阵容，每一种阵容可以看作一种策略，双方各选一种策略参赛。比赛共赛三局，规定每局胜者得1 分，输者得 -1 分，可知三赛三胜得3 分，三赛二胜得 1分， 三赛一胜得 -1分， 三赛三负得 -3 分。 甲队的策略集为1123,S，乙队的策略集为2123,S。 根据以往比赛的资料， 有甲队的赢得矩阵为A，111113313A请问这次比赛各队采用哪种阵容上场最为

6、稳妥? 解：由A可看出，局中人甲队的最大赢得为3，要得到这个赢得，他就应该选择策略3。由于局中人乙队的理智，他考虑到甲队打算出3的心理，于是准备用2来对付甲队，这样使得甲队反而失掉1 分, 双方都考虑到对方为使自己尽可能的少得分而所做的努力，所以双方都不存在侥幸心理，而是从各自可能出现的最不利的情形中选择一种最为有利的情况作为决策的依据，这就是所谓的“理智行为”，也就是对策双方实际上都能接受的一种稳妥方法。甲队在各纯策略下可能得到的最少赢得，即矩阵A 中每行的最小元素分别为：1，-3，-1，其中最好的结果是1，即甲队应采取策略1，无论对手采用何种策略，甲队都能保证他得赢得不会少于1，而出其他策

7、略，都有可能使甲队的赢得少于1甚至输给对方。同理，对于乙队来说，各纯策略可能带来最不利的结果，即矩阵中没列的最大元素分别为： 3，1，3，其中最好的也是1，即乙队应采取策略2，无论对手采用何种策略，乙队名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 9 页 - - - - - - - - - 都能保证他得所失值不会超过1，而选择其他策略， 都有可能是自己的所失超过1. 上述分析表明，甲队和乙队的理智行为分别是选择纯策略1和2，这时，甲队的赢得值和乙队的所失值的绝对值相等，

8、甲队得到了其预期的最少赢得1，而乙队也不会给甲队带来比1 更多的所得，相互的竞争使对策出现了一个最稳妥的结果。因此，1和2应分别为甲队和乙队的最优纯策略。定 义1 ： 设12,GS S A为 一 矩 阵 对 策 ， 其 中11,mS，21,nS，ijm nAa。若max minmin maxijijjjiiaa（1）成立，记其值为GV ，则称GV 为对策的值，称使（ 1）成立的纯局势,ij为 G 在纯策略意义下的解（或鞍点） ，称ij和分别为局中人和的最优纯策略。定理 1： 矩阵对策12,GS SA 在纯策略意义下有解的充要条件是：存在纯局势,ij，使得对任意 ij和 ，有iji ji jaa

9、a（2）证明：先证充分性，由（ 2）有maxminiji ji jjiaaa而min maxmaxminmaxminijijjiiiji jjjiaaaa所以min maxmax minijiji jjjiiaaa（3）另一方面，对任意 ij和 ，有minmaxijijijjiaaa所以max minmin maxijijjjiiaa（4）由（3） （4）可知，名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 9 页 - - - - - - - - - max minmin

10、 maxijiji jjjiiaaa且Gi jVa再证必要性设有,ij ，使得minmaxminmaxmin maxiji jjjiijijjiiaaaa则由max minmin maxijijjjiiaa有maxminminiji ji ji ji jjjiaaaaa证毕。定理 1 中（2）式的对策意义是：一个平衡局势,ij应该具有这样的性质：当局中人选择了纯策略i后，局中人为了使其所失最少，只能选择纯策略j，否则就可能失的更多；反之，当局中人选择了纯策略j后，局中人为了得到最大的赢得也只能选择纯策略i，否则就会赢得更少，双方的竞争在局势,ij下达到一个平衡状态。【例 2】某单位采购员在秋天

11、决定冬季取暖用煤的储量问题，已知在正常的冬季气温条件下要消耗15吨煤， 在较暖和较冷的天气下要消耗10吨和 20 吨。假定冬天的煤价随天气寒冷程度而有所变化，在较暖和、正常、较冷的气候条件下每吨煤价分别为10 元、15 元、20 元。又设冬季时煤炭价格为每吨10 元。在没有关于当年冬季准确的气象预报的条件下，秋天储煤多少吨能使得单位的支出最少？解：这个问题可看成一个对策问题，局中人I 为采购员，局中人II为大自然， 采购员有三个策略， 在秋天时买 10 吨、 15 吨、 20 吨煤， 分别记为123,。大自然也有三个策略：暖、正常、冷，分别记为123,。通过计算冬季取暖用煤实际费用（为秋季购煤

12、费用和冬季不够时再补购得费用总和），作为局中人 I 采购员的赢得，得赢得矩阵为100017503000150015002500200020002000名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 9 页 - - - - - - - - - 由33max minmin max2000ijijjjiiaaa知该对策的解为33,，即秋季购煤 20 吨较好。（三）矩阵对策的混合策略1、混合策略的定义从以上的讨论可知，对矩阵对策12,GS S A 来说，局中人有把握的至少赢得是1

13、max minijjiVa，局中人有把握的至多损失的是2min maxijjiVa。局中人赢得的值不会多于局中人所失值，即总有v1v2。当 v1=v2 时，矩阵对策 G 存在纯策略意义下的解，且12GVVV ，实际中出现的更多的情形是v1v2，对策不存在的纯策略意义下的解。例如，赢得矩阵5986A,12126,2;8,2;ViVjVV ，于是，当双方根据从最不利情形中选取最有利的结果的原则选择纯策略时，应分别选取2和1，此时局中人赢得8，比其预期赢得 6 还多，原因就在于局中人选择了1，使其对手多得原来不该得的赢得，故1对局中人来说并不是最优，因而它会考虑取2。局中人亦会采取相应的办法，改取1

14、以使赢得为 9，而局中人又可能仍取策略1来对付局中人的策略。这样，局中人取1或2的可能性以及局中人取1或2的可能性都不能排除，对两个局中人来说，不存在一个双方均可以接受的平衡局势， 或者说当12VV 时，矩阵对策 G不存在纯策略意义下的解。在这种情况下， 一个比较合乎实际的想法是， 既然各局中人没有最优纯策略可取，是否可以给出一个选取不同策略的概率分布？如在上的例子中，局中人可以制定如下一种策略：分别以概率1/4 和 3/4 选取纯策略1或2，这种策略是局中人的策略集上的一个概率分布，称之为混合策略。同样局中人也名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - -

15、- - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 9 页 - - - - - - - - - 可以制定这样一中混合策略，分别以概率1/2 和 1/2 选取纯策略1或2。下面给出矩阵对策混合策略的定义。定义： 设12,GS SA 为矩阵对策，其中112,mS，212,nS，ijm nAa。 记10,1,2,1iiSxEximx20,1,2, ,1jiSyEyjny则12SS和分别称为局中人和的混合策略集（或策略集）；1xS 和2yS 分别称为局中人和的混合策略（或策略），对1xS ,2yS 称(x,y) ，为一个混合局势（或混合扩充）。一个混合策略12,m

16、xx xx可设想成当两个局中人多次重复进行对策时，局中人分别采取纯策略12,m的频率。若只进行一次时对策，混合对策可设想成局中人对各纯策略的偏爱程度。2、混合策略的求解求解混合策略的问题有图解法，迭代法、线性方程组法和线性规划法，在此我们用线性规划解法。以赢得矩阵5986A为例来建立此混合策略的线性规划模型。首先，设局中人使用1的概率为1x，使用2的概率2x，并设在最坏的情况下（即为乙出对其最有利的策略情况下），甲的赢得的平均值等于V。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第

17、7 页，共 9 页 - - - - - - - - - 建立下面的数学关系：1212121210,05896xxxxxxVxxV其次，考虑V的值，V与赢得矩阵 A中各元素的值有关，如果A中各元素的值都大于 0，即不管局中人采用什么策略，局中人的赢得都是正的。 本例中 A得所有元素都取正值，显然0V。再次，做变量替换，令1,2iixxiV，以上五个数量关系式变为1212121210,0581961xxVxxxxxx对于局中人来说，他希望V越大越好，也就是希望1V的值越小越好。建立局中人的最优混合策略的线性规划模型如下：12121212min5819610,0 xxxxxxxx求解该模型得到120

18、.0480.095xx名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 9 页 - - - - - - - - - 1211221170.0480.09570.0480.33670.0950.664VxxxVxxVx即：局中人的最优混合策略是以0.336 的概率出1策略，以 0.664 的概率出2策略，简记为0.336,0.664TX，7GV。同样可以求出局中人的最优混合策略。建立的线性规划模型如下：12121212max5918610,0yyyyxxyy求解略。上述例题中，0V，若没有办法判断出V大于零，或者在一些问题中 V本来就小于零或者等于零，此时，可以把A中的每一个元素都加上一个足够大的正数k使得所得的新赢得矩阵A的每一个元素都大于零。有定理保证这两个矩阵对策12,GS SA，12,GS SA的最优混合策略是相同的。而且有GGVVk。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 9 页 - - - - - - - - -