1701018070
这样的问题如何解？有一种专门用来解0—1规划的方法，由匈牙利数学家库尼格提供了有关理论的基础。它通过一系列简约矩阵求得最优解，故也称为简约矩阵法。具体解法这里从略。
1701018071
1701018072
现在回到前面的甲、乙、丙的工作安排问题。用目标函数来衡量，最合理的安排是让丙做电工（因为物理成绩为最高的10分）。然后让甲任图书管理员（语文成绩为7分），乙做木工（也充分利用他的制图成绩7分）。这样分配工作，反映个人的才能利用水平的目标函数达到了10+7+7=24分。而原来按总成绩安排工作，其目标函数值只有5+8+5=18分。
1701018073
1701018074
1701018075
1701018076
1701018077
数学文化教程 [:1701013762]
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