浙大城院数学建模7

11:05:39MCM1第七章、对策与决策模型前言§7.1对策问题§7.2、决策问题§7.3层次分析法建模11:05:39MCM2前言对策与决策是人们在日常生活和工作中经常碰到的择优活动。人们在处理某一问题时，往往会面临多种可能出现的情形，同时又存在多种可供选择的行动方案，要求根据自己的行动目的从中选定一种方案，以期获得最佳的结果。有时，人们面临的问题具有竞争或对抗性质，如商业上的竞争、体育中的比赛和军事对抗、政治派别的斗争等等。这时竞争双方或各方都希望发挥自己的优势，使己方获得最好结果。因而双方或各方都要根据不同情况、不同对手作出各自的决择，此时遇到的问题被称为对策。11:05:39MCM3在有些情况下，我们面临的并非竞争对手而是可能出现的多种情况，我们不知道究竟哪一种情况会发生，但希望我们的决策能获得最好的结果，此时，我们面临的问题被称为决策问题，不过，如果我们将可能出现的若干种情况也看作是竞争对手可采取的几种策略，那么也可以把决策问题当作对策问题来处理。11:05:39MCM4§7.1对策问题对策问题的特征是参与者为利益相互冲突的各方，其结局并不取决于其中任何一方的努力，而是各方所采取的策略的综合结果。先考察几个实际例子。例7.1（田忌赛马）田忌赛马是大多数人都熟知的故事。事情发生在战国时期，据说齐王欲与大将田忌赛马，双方约定每人从自己的上、中、下三个等级的马中各挑选赛马一匹来进行三局比赛，进行每局比赛时，双方11:05:39MCM5各派赛马一匹比试，每局的败者要付给胜者一千两黄金。当时，齐王的每一等级的马都比田忌同等级的马要强，因而，如果田忌用自己的上等马与齐王的上等马比试，用自己的中等马与齐王的中等马比试，用自己的下等马与齐王的下等马比试，则田忌要输三局，因而要输掉黄金三千两。但是结果田忌并没有输，反而赢了一千两黄金。这是因为田忌的谋士孙膑给他出了一个主意，让他用下等马对齐王的上等马，上等马对齐王的中等马，中等马对齐王的下等马，结果田忌二胜一败，反而赢了一千两黄金。11:05:39MCM6例7.2（石头—剪刀—布）这是一个大多数人小时候都玩过的游戏。游戏双方每次出拳只能选石头、剪刀、布中的一种，石头赢剪刀，剪刀赢布，而布又赢石头，赢者得一分，输者失一分，双方相同时不得分，见下表。AB石头剪子布石头01－1剪子－101布1－10表7-111:05:39MCM7例7.3（嫌犯的困惑）警察同时拘捕了两嫌疑犯，为防止串供，将他们分开关押。逮捕的原因是他们持有大量伪币。警方怀疑他们伪造钱币，但没有找到充分的证据，希望他们能自己供认。这两个人都知道：如果他们双方都不供认，将被以使用和持有大量伪币罪被各判刑18个月；如果双方都供认伪造了钱币，将以伪造钱币罪被各被判刑3年；如果一方供认而另一方不供认，则供认方将被从宽处理而免予刑事处分，但另一方则将被判刑7年。将嫌疑犯A、B被判刑的几种可能情况列表如下：11:05:39MCM8表7-2AB供认不供认供认（3，3）（0，7）不供认（7，0）（1.5，1.5）表中每对数字是嫌疑犯A、B分别被判刑的年数的组合。如果两名嫌疑犯均担心对方供认并希望受到最轻的惩罚，最保险的办法自然是承认制造了伪币。从这些简单实例中可以看出对策现象中包含着几个基本要素。11:05:39MCM9（对策的基本要素）（1）局中人。参加决策的各方被称为对策问题的局中人，一个决策问题至少包含着两名局中人（如棋类比赛等），也可以包含多于两名局中人（如大多数商业中的竞争、政治派别间的斗争等）。局中人必须拥有可供其选择并影响最终结局的策略，在例7.1中，田忌的朋友孙膑不能称之为局中人，他只是给田忌了提供了可供参考的策略，而没有做出决策的权利，最终的决策只能由局中人田忌本人来做出。同样，在例7.3中，局中人是A、B两名嫌疑犯，警方并非局中人。两名嫌犯最终被如何判刑，取决于他们各自采取的态度，警方并不能代替他们做出选择。11:05:39MCM10（2）策略集。局中人所能采取的每一可行方案均被称为策略，某局中人可采取的全部策略称为该局中人的策略集。对策问题中，对应于每一局中人均存在着一个策略集，而每一策略集中至少要求有两个策略，否则，该局中人可从此对策问题中删去，因为对他来讲，他只有唯一的方案，不存在任何选择策略的余地。应当注意的是，所谓策略是指在整个竞争过程中对付他方的整套策略，并非指竞争过程中某个步骤所采取的具体局部办法。例如田忌先出下等马比赛只能看成其完整策略的组成部分，而不能看成一个完整的策略。11:05:39MCM11因为首先出下等马比赛，比赛还没有结束，接下来还必须继续为剩余的比赛寻找应对方法。只有当比赛全部结束，各比赛方案组合在一起才能构成一个策略，比如，先出下等马，再出上等马，后出中等马就构成了一个策略。当然，有时也可将具体的局部方法看成一个多阶段对策中的子对策。策略集合可以是有限集也可以是无限集，策略集为有限集时的对策问题被称为有限对策，否则被称为无限对策。11:05:39MCM12iiS记局中人的策略集为。对策时，对策问题的各方都从各自的策略集合中选定了一个策略。各方都采取了自己的策略后，对策问题将产生一个结果，该结果可用一个矢量S表示，称之为一个纯局势（简称局势）。m12,,,mn1,,n例如，若一对策中包含A、B两名局中人，A有种策略，B有种策略11:05:39MCM1312,,,AmS1,,BnSA、B的策略集合分别为和ij(,)ij如果局中人A选择策略而局中人B选择策略则对策结果就成为此对策的一个纯局势。ASBSmnS显然，策略集与共构成个纯局势，它们构成表7.3。由对策问题的全体纯局势构成的集合称为此对策问题的局势集合。11:05:39MCM14表7-311:05:39MCM15在例7.1中，齐王和田忌双方都要各选派自己的三匹分属上、中、下三个等级的马分别参加一局比赛。如果用1、2、3分别代替齐王的上等马、中等马、下等马，而用三个数字排列的先后顺序表示参赛次序，例如（1，2，3）表示齐王用上等马参加第一局比赛，中等马参加第二局比赛，下等马参加第三局比赛，那么齐王的策略集AS也包含（1，3，2）、（2，1，3）、（2，3，1）、（3，2，1）、（3，1，2）六个策略，分别记为126、、、（此处仍用1、2、3分别代替田忌的上等马、中等马、下等马）。局势集合S包含了由双方的策略两两组合而成36个纯局势。11:05:39MCM16BS同样，田忌的策略集126、、、也包含（1，3，2）、（2，1，3）、（2，3，1）、（3，2，1）、（3，1，2）六个策略，分别记为（此处仍用1、2、3分别代替田忌的上等马、中等马、下等马）。局势集合S包含了由双方的策略两两组合而成36个纯局势。11:05:39MCM17（3）赢得函数（或称支付函数）。对策的结果要体现到每位局中人身上，所以一般用矢量表示，称之为赢得函数。赢得函数F为定义在局势集S上的矢值函数，对于S中的每一纯局势s，F（s）指出了每一局中人在此对策结果下应赢得（或支付）的值。iIiS记局中人集合为I=（1，…，k），对每一有一策略集,当I中每一局中人选定自己的策略后得一个局势s；将s代入赢得函数F，即得一矢量1()((),,())kFsFsFs其中()iFs为在局势s下局中人i的赢得（或支付）。11:05:39MCM1811111((,))F211((,))F如例7.1在局势(,)下齐王的赢得值为＝3，而田忌的赢得值为＝－3（以1千两黄金为单位）。综上所述，一个对策模型由局中人、策略集和赢得函数三部分组成。本节讨论只有两名局中人的对策问题，其结果可以推广到一般的对策模型中去。一般的对策问题讨论起来相当繁琐，为简单起见，本节只讨论仅有两名局中人的对策问题（简称为两人对策）。11:05:39MCM19对于只有两名局中人的对策问题，其局势集和赢得函数均可用表格表示。例如，表7.2就给出了例7.3的局势集和赢得函数，为方便起见，我们不妨仍用),(jiij来记一方采用，另一方采用时双方的赢得。（两人零和对策）一类特殊的两人对策问题被称为零和对策问题，在这类对策中，当纯局势确定后，局中人A之所得恰为另一局中人B之所失，或者A之所失恰为B之所得，即双方所得之和总为零。如例8.1的赛马比赛结果，齐王之所得必为田忌之所失，齐王之所失必为田忌之所得，因此例7.1中的两人对策问题就属于零和对策问题。11:05:39MCM20在零和对策中，因)()(21sFsF要指出对策结果只需指出其中一人的赢得即可，故赢得函数可用赢得矩阵来表示。例如若A有m种策略，B有n种策略，赢得矩阵可写成111212122212nnmnmmmnaaaaaaRaaaija表示若A选取策略i而B选取策略j，则A之所得为ija0ijaB之所失为（当时为赢得）。11:05:39MCM21例7.1中的两人零和对策问题，赢得函数可以使用齐王或者田忌的赢得矩阵来表示。齐王的赢得矩阵（以1千两黄金为单位）为：12345612345631111-11311-111-13111-11131111-1131111-113R而田忌的赢得矩阵为-R。11:05:39MCM22在有些两人对策的赢得表中，A之所得并非明显为B之所失，但双方赢得数之和为一常数。例如在表7.4中，无论A、B怎样选取策略，双方赢得总和均为10。这种对策问题可以很容易地转化为A之所的即为B之所失的零和对策问题。表7.4局中人A局中人B1231(8,2)(1,9)(7,3)2(4,6)(9,1)(3,7)3(2,8)(6,4)(8,2)4(6,4)(4,6)(6,4)11:05:39MCM23此时，若分别把两人的赢得数各减去平均赢得数，即可将赢得表化为零和赢得表，从而可用赢得矩阵来表达。表8.4中的对策在转化为零和对策后，具有赢得矩阵342142313111R（7.1）ASBS一个两人对策需要给出局中人A、B的策略集和以及表示双方赢得值的赢得矩阵R。11:05:39MCM24特别地，当遇到零和对策或可转化为零和对策的问题时，由以上分析，R可用通常意义下的矩阵来表示，否则R的元素应为一个二维矢量。故两人对策G又可称为矩阵对策，并可简记成RSSGBA,,例7.4给定二人对策RSSGBA,,，其中123,,AS和14,,BS123123412630221421810601016R11:05:39MCM25从R中可以看出，A的最大可能赢利为30。若A希望获得最大赢利30，需采取策略1但此时若B采取策略4，A非但得不到30，反而会失去22。为了稳妥，A在决策前应事先考虑到对方可能有使自己损失最大的动机，应该在最坏的可能中争取最好的结果，B也应该做同样的考虑。如果情况果真如此，局中人A会这样来考虑问题：、采取策略123时，最坏的赢得结果分别为min{12,-6,30,-22}=-2211:05:39MCM26min{14,2,18,10}=2min{-6,0,-10,16}=-10其中最好的可能为max{-22,2,-10}=2那么如果A采取策略2无论B采取什么策略，A的赢得均不会少于2。B采取各方案的最大损失为max{12,14,-6}=14max{-6,2,0}=2max{30,18,-10}=30max{-22,10,16}=16当B采取策略2时，其损失不会超过2。11:05:39MCM27注意到在赢得矩阵中，2既是所在行中的最小元素又是所在列中的最大元素。此时，只要对方不改变策略，任一局中人都不可能通过变换自己的策略来增大赢得或减小损失。在这种情况下，看来，对双方而言这一结果都应当被看成是最好的结果，应当采用什么策略似乎并无悬念，称这样的局势为对策问题的