1701018070
这样的问题如何解?有一种专门用来解0—1规划的方法,由匈牙利数学家库尼格提供了有关理论的基础。它通过一系列简约矩阵求得最优解,故也称为简约矩阵法。具体解法这里从略。
1701018071
1701018072
现在回到前面的甲、乙、丙的工作安排问题。用目标函数来衡量,最合理的安排是让丙做电工(因为物理成绩为最高的10分)。然后让甲任图书管理员(语文成绩为7分),乙做木工(也充分利用他的制图成绩7分)。这样分配工作,反映个人的才能利用水平的目标函数达到了10+7+7=24分。而原来按总成绩安排工作,其目标函数值只有5+8+5=18分。
1701018073
1701018074
1701018075
1701018076
1701018078
数学文化教程 第三节 田忌赛马和对策论
1701018079
1701018080
竞争是当代社会的一个特征。在竞争中讲究科学的对策是十分重要的。经济活动中的经营决策、市场竞争,政治活动中的竞标、竞选、谈判、联盟,军事活动中对抗、谋略等,都和选择合适的对策有关。20世纪40—50年代创立的对策论(又称博弈论),研究了一系列社会经济中的对策问题。此处我们介绍其中最简单的对策问题:田忌赛马的故事。
1701018081
1701018082
田忌赛马是一个非常有名的谋略故事。传说战国时代齐国的齐威王经常与大将田忌赛马。赛马的规则是这样:每次双方各出三匹马,一对一共比赛三个回合,每个回合的输方要给赢方一千斤铜。齐威王的三匹马和田忌的三匹马按实力强弱都可分为上、中、下三等。齐威王的上、中、下三匹马分别比田忌的上、中、下三匹马略强一些。因此,每次赛马田忌都是连输三个回合,输掉铜三千斤。后来,田忌手下的谋士孙膑给田忌出了个主意:要田忌用他的下马和齐威王的上马比赛,用他的上马和齐威王的中马比赛,用中马和齐威王的下马比赛。这样,虽然第一回合田忌必输无疑,却赢了后面的两个回合;二胜一负,田忌赢了齐威王一千斤铜。同样的马,输赢却发生了变化。这个故事说明了策略的重要性。在双方实力、条件不变的情况下,适当地调度和运用现有的条件会取得更好的结果。
1701018083
1701018084
这个故事中,齐威王实际上把自己放在一个不公平的地位上。因为他自恃实力强大,总是先出马,给了田忌采取有利的对策的机会。如果他每次比赛以前能放下国君的架子谦让一下:“田将军,您先请”,也许又是他连赢三场了。
1701018085
1701018086
公平比赛条件应该是:齐威王和田忌双方都清楚各自马的实力和对方马的实力,每个人都可以按自己的意愿决定自己马匹出场的次序,而两人出马的对策应该是同时的,不能总让某个人先出马。
1701018087
1701018088
这时,对齐威王来说,最理想的情况是:各回合的马匹与田忌所出的马匹等级都相同,即不管先后次序如何,总是以自己的上马比田忌的上马,以自己的中马比田忌的中马,以自己的下马比田忌的下马。这样,他总能赢铜三千斤。次佳的是:三场中有一场是同等级的马比赛,例如,齐威王的下马对田忌的下马(齐威王赢),而上马、中马要和田忌的中马、上马比,此时齐威王的上马必赢,三场比赛至少两胜一负。对齐威王来说,最坏的情况是故事中孙膑所建议的对策:他的上、中、下马分别对田忌的下、上、中马,一胜二负,最终要输铜一千斤。
1701018089
1701018090
为了把齐威王与田忌赛马的故事引申成一个对策问题,我们先把双方出三匹马简化成各出两匹马,分别称为上马、下马。问题的假设如下:
1701018091
1701018092
(1)该对策问题中有两方,即齐威王和田忌,齐威王的上、下马分别优于田忌的上、下马;
1701018093
1701018094
(2)双方可选择的对策是己方马匹的出场次序,由于两匹马的排列次序共有2种,因此每一方各有2种可选择的对策;
1701018095
1701018096
(3)双方都预先知道对方所有可能的对策,并且预先知道双方每一种对策组合的结果;
1701018097
1701018098
(4)在比赛之前双方都不能预先知道对方究竟会采取什么对策,双方同时选择对策,没有先后次序关系,而且一场比赛的对策一旦选定就不允许变更;
1701018099
1701018100
(5)把赢铜一千斤记收益为“1”,输铜一千斤记收益为“-1”,则对策的一方齐威王在各种对策组合下的收益如下表所示:
1701018101
1701018102
表中的数字是在比赛双方采取相应对策时齐威王的收益。齐威王的收益就是田忌的损失,因而把表中的数字全部改变符号后就可以得到田忌的收益。那么在这个对策问题中齐威王和田忌应该怎样选择自己的对策,而最终的结果又会是怎样的呢?为了回答这些问题,我们先来看看问题有什么特点。
1701018103
1701018104
首先,由前面的分析可知,双方都不能让对方知道或猜中自己的对策,因为一旦自己的对策被对方知道,则对方就可以有针对性地采取适当的对策,自己就处于不利的地位。这也意味着任何一方的选择不能一成不变,对策的变动要使得对方无法预测为好。这就意味着选择对策必须要有一定的随机性。其次,无论对齐威王还是对田忌,两种可选择的对策相互之间没有优劣之分。如对齐威王来讲,每一种对策都可能有两种可能的结果,包括一种收益为2,一种收益为0。实际究竟得到哪种结果,要看双方对策的组合情况,而不仅取决某一方的对策。同样,对于田忌来说,他的两种对策也无好坏之分,每种对策也有两个可能的结果,可能的收益为0或-2。总之,比赛双方在选取对策时,对己方的可选对策并无偏爱,应以相同的可能性选用。实际上,偏向于某种对策的结果往往对自己不利,因为当对方得知你的偏爱后就可以针对性选择对策,从而有更多的机会取得有利的结果。这种对策游戏如果只进行一次,则双方的选择和最终的结果都无法确定,只能完全靠运气。由于齐威王的马的实力比田忌的马略高,他赢的机会比田忌要大得多。如果这样的对策游戏重复进行多次,则上面的讨论给我们指出了各方选择对策的原则,而且进一步讨论还能告诉我们多次比赛后的平均结果。这种对策问题称为随机对策问题,我们可以应用平均数来作计算。计算的方法如下。
1701018105
1701018106
齐威王的收益表
1701018107
1701018108
1701018109
1701018110
1701018111
表中各种对策组合出现的4种可能性都相同,概率都等于0.25。由表中数据,齐威王的收益为0和2的概率都是0.5。于是齐威王的平均收益为
1701018112
1701018113
0×0.5+2×0.5=1.
1701018114
1701018115
即齐威王和田忌若按随机对策方法赛上下两匹马,则齐威王平均每次赢田忌一千斤铜。
1701018116
1701018117
1701018118
1701018119
[
上一页 ]
[ :1.70101807e+09 ]
[
下一页 ]