《《对策与决策模型》ppt课件》由会员分享，可在线阅读，更多相关《《对策与决策模型》ppt课件（102页珍藏版）》请在金锄头文库上搜索。
1、第八章 对策与决策模型,浙江大学数学建模基地,第八章 对策与决策模型,对策与决策是人们生活和工作中经常会遇到的择优活动。人们在处理一个问题时，往往会面临几种情况，同时又存在几种可行方案可供选择，要求根据自己的行动目的选定一种方案，以期获得最佳的结果。 有时，人们面临的问题具有竞争性质，如商业上的竞争、体育中的比赛和军事行动、政治派别的斗争等等。这时竞争双方或各方都要发挥自己的优势，使己方获得最好结果。因而双方或各方都要根据不同情况、不同对手做出自己的决择，此时的决策称为对策。在有些情况下，如果我们把可能出现的若干种情况也看作是竞争对手可采取的几种策略，那么也可以把决策问题当作对策问题来求解。,
2、8.1 对策问题,对策问题的特征是参与者为利益相互冲突的各方，其结局不取决于其中任意一方的努力而是各方所采取的策略的综合结果。,先考察几个实际例子。,例8.1 （田忌赛马）,田忌赛马是大多数人都熟知的故事，传说战国时期齐王欲与大将田忌赛马，双方约定每人挑选上、中、下三个等级的马各一匹进行比赛，每局赌金为一千金。齐王同等级的马均比田忌的马略胜一筹，似乎必胜无疑。田忌的朋友孙膑给他出了一个主意，让他用下等马比齐王的上等马，上等马对齐王的中等马，中等马对齐王的下等马，结果田忌二胜一败，反而赢了一千金。,例8.2 （石头剪子布）,这是一个大多数人小时候都玩过的游戏。游戏双方只能选石头、剪子、布中的一种
3、，石头赢剪子，剪子赢布，而布又赢石头，赢者得一分，输者失一分，双方相同时不得分，见下表。,表8.1,例8.3 （囚犯的困惑）,警察同时逮捕了两人并分开关押，逮捕的原因是他们持有大量伪币，警方怀疑他们伪造钱币，但没有找到充分证据，希望他们能自己供认，这两个人都知道：如果他们双方都不供认，将被以使用和持有大量伪币罪被各判刑18个月；如果双方都供认伪造了钱币，将各被判刑3年；如果一方供认另一方不供认，则供认方将被从宽处理而免刑，但另一方面将被判刑7年。将嫌疑犯A、B被判刑的几种可能情况列表如下：,表8.2,表中每对数字表示嫌疑犯A、B被判刑的年数。如果两名疑犯均担心对方供认并希望受到最轻的惩罚，最保
4、险的办法自然是承认制造了伪币。,一、对策的基本要素,（1）局中人。参加决策的各方被称为决策问题的局中人，一个决策总是可以包含两名局中人（如棋类比赛、人与大自然作斗争等），也可以包含多于两名局中人（如大多数商业中的竞争、政治派别间的斗争）。局中人必须要拥用可供其选择并影响最终结局的策略，在例8.3中，局中人是A、B两名疑犯，警方不是局中人。两名疑犯最终如何判刑取决于他们各自采取的态度，警方不能为他们做出选择。,从这些简单实例中可以看出对策现象中包含的几个基本要素。,（2）策略集合。局中人能采取的可行方案称为策略，每一局中人可采取的全部策略称为此局中人的策略集合。对策问题中，对应于每一局中人存在着
5、一个策略集合，而每一策略集合中至少要有两个策略，否则该局中人可从此对策问题中删去，因为对他来讲，不存在选择策略的余地。应当注意的是，所谓策略是指在整个竞争过程中对付他方的完整方法，并非指竞争过程中某步所采取的具体局部办法。例如下棋中的某步只能看和一个完整策略的组成部分，而不能看成一个完整的策略。当然，有时可将它看成一个多阶段对策中的子对策。策略集合可以是有限集也可以是无限集。策略集为有限集时称为有限对策，否则称为无限对策。,记局中人i的策略集合为Si。当对策问题各方都从各自的策略集合中选定了一个策略后，各方采取的策略全体可用一矢量S表示，称之为一个纯局势（简称局势）。,例如，若一对策中包含A、
6、B两名局中人，其策略集合分别为SA = 1, m，SB = 1, n。若A选择策略 i而B选策略 j，则（ i, j）就构成此对策的一个纯局势。显然，SA与SB一共可构成mn个纯局势，它们构成表8.3。对策问题的全体纯局势构成的集合S称为此对策问题的局势集合。,（3）赢得函数（或称支付函数）。对策的结果用矢量表示，称之为赢得函数。赢得函数F为定义在局势集合S上的矢值函数，对于S中的每一纯局势S，F（S）指出了每一局中人在此对策结果下应赢得（或支付）的值。综上所述，一个对策模型由局中人、策略集合和赢得函数三部分组成。记局中人集合为I = 1,k，对每一iI，有一策略集合Si，当I中每一局中人i选
7、定策略后得一个局势s；将s代入赢得函数F，即得一矢量F(s) = ( F1(s),Fk(s)，其中Fi(s)为在局势s下局中人i的赢得（或支付）。,本节讨论只有两名局中人的对策问题，即两人对策，其结果可以推广到一般的对策模型中去。对于只有两名局中人的对策问题，其局势集合和赢得函数均可用表格表示。例如，表8.2就给出了例8.3的局势集合和赢得函数。,二、零和对策,存在一类特殊的对策问题。在这类对策中，当纯局势确定后，A之所得恰为B之所失，或者A之所失恰为B之所得，即双方所得之和总为零。在零和对策中，因F1(s)= F2(s)，只需指出其中一人的赢得值即可，故赢得函数可用赢得矩阵表示。例如若A有m
8、种策略，B有n种策略，赢得矩阵,表示若A选取策略i而B选取策略j，则A之所得为aij（当aij0时为支付）。,在有些两人对策的赢得表中，A之所得并非明显为B之所失，但双方赢得数之和为一常数。例如在表8.4中，无论A、B怎样选取策略，双方赢得总和均为10，此时，若将各人赢得数减去两人的平均赢得数，即可将赢得表化为零和赢得表。表8.4中的对策在转化为零和对策后，具有赢得矩阵,表8.4,给定一个两人对策只需给出局中人A、B的策略集合SA、SB及表示双方赢得值的赢得矩阵R。综上所述，当遇到零和对策或可转化为零和对策的问题时，R可用通常意义下的矩阵表示，否则R的元素为一两维矢量。,故两人对策G又可称为矩
9、阵对策并可简记成 G = SA, SB, R ,例8.4 给定G = SA, SB, R，其中SA = 1, 2, 3，SB = 1, 2, 3, 4,从R中可以看出，若A希望获得最大赢利30，需采取策略 1，但此时若B采取策略 4，A非但得不到30，反而会失去22。为了稳妥，双方都应考虑到对方有使自己损失最大的动机，在最坏的可能中争取最好的结果。局中人A采取策略 1、 2、 3时，最坏的赢得结果分别为,min 12, 6, 30, 22 = 22,min 14, 2, 18, 10 =2,min 6, 0, 10, 16 = 10,其中最好的可能为max 22,2,10=2。如果A采取策略
10、2，无论B采取什么策略，A的赢得均不会少于2.,B采取各方案的最大损失为max 12,14, 6=14，max 6,2,0=2，max 30,18, 10=30和max 22,10,16 =16。当B采取策略 2时，其损失不会超过2。注意到在赢得矩阵中，2既是所在行中的最小元素又是所在列中的最大元素。此时，只要对方不改变策略，任一局中人都不可能通过变换策略来增大赢得或减小损失，称这样的局势为对策的一个稳定点或稳定解，（注：也被称为鞍点）,定义8.1 对于两人对策G = SA, SB, R，若有 ，则称G具有稳定解，并称VG为对策G的值。若纯局势（ ）使得 ，则称（ ）为对策G的鞍点或稳定解，赢
11、得矩阵中与（ ）相对应的元素 称为赢得矩阵的鞍点， 与 分别称为局中人A与B的最优策略。,对（8.1）式中的赢得矩阵，容易发现不存在具有上述性质的鞍点。给定一个对策G，如何判断它是否具有鞍点呢？为了回答这一问题，先引入下面的极大极小原理。,定理8.1 设G = SA, SB, R ， 记 ， 则必有+0,证明 : ，,易见为A的最小赢得，为B的最小赢得，,由于G是零和对策，故+0必成立。,定理8.2 零和对策G具有稳定解的充要条件为+= 0。,证明：,（充分性） 由和的定义可知，存在一行（例如p行）为p行中的最小元素且存在一列（例如q列），为q列中的最大元素。故有 apq且apq 又因+= 0
12、，所以=，从而得出apq=，apq为赢得矩阵的鞍点，（ p, q）为G的稳定解。,（必要性）若G具有稳定解（ p , q ），则apq为赢得矩阵的鞍点。故有,从而可得+0，但根据定理8.1，+0必成立，故必有+=0。,上述定理给出了对策问题有稳定解（简称为解）的充要条件。当对策问题有解时，其解可以不唯一。例如，若,则易见，（ 2, 2），（ 2, 4），（ 4, 2），（ 4, 4）均为此对策问题的解。 一般又可以证明。,定理8.3 对策问题的解具有下列性质：,（1）无差别性。若（ , ）与（ , ）同为对策G的解，则必有 。,（2）可交换性。若（ , j1）、（ , j2）均为对策G的解，
13、则（ , j2）和（ , j1）也必为G的解。,定理8.3的证明非常容易，作为习题留给读者自己去完成。,具有稳定解的零和对策问题是一类特别简单的对策问题，它所对应的赢得矩阵存在鞍点，任一局中人都不可能通过自己单方面的努力来改进结果。然而，在实际遇到的零和对策中更典型的是+0的情况。由于赢得矩阵中不存在鞍点，至少存在一名局中人，在他单方面改变策略的情况下，有可能改善自己的收益。例如，考察（8.1）中的赢得矩阵R。若双方都采取保守的max min原则， 将会出现纯局势 （ 4, 1）或 （ 4, 3）。但如果局中人A适当改换策略，他可以增加收入。例如，如果B采用策略 1，而A改换策略 1，则A可收
14、益 3。但此时若B改换策略 2，又会使A输掉4，。此时，在只使用纯策略的范围内，对策问题无解。这类决策如果只进行一次，局中人除了碰运气以外别无办法。但如果这类决策要反复进行多次，则局中人固定采用一种策略显然是不明智的，因为一旦对手看出你会采用什么策略，他将会选用对自己最为有利的策略。这时，局中人均应根据某种概率来选用各种策略，即采用混合策略的办法，使自己的期望收益尽可能大。,设A方用概率xi选用策略 i，B方用概率yj选用策略 j， ， 且双方每次选用什么策略是随机的，不能让对方看出规律，,记X = (x1, ,xm)T，Y = (y1, ,yn)T，则A的期望赢得为,E ( X,Y) = X
15、TRY,其中，R为A方的赢得矩阵。记,分别称SA与SB为A方和B方的混合策略。,对于需要使用混合策略的对策问题，也有具有稳定解的对策问题的类似结果。,定义8.2 若存在m维概率向量和n维概率向量，使得对一切m维概率向量X和n 维概率向量y有 则称（ , ）为混合策略对策问题的鞍点。,定理8.4 （Von Neumann）任意混合策略对策问题必存在鞍点，即必存在概率向 量和，使得： （证明从略）。,使用纯策略的对策问题（具有稳定解的对策问题）可以看成使用混合策略的对策 问题的特殊情况，相当于以概率1选取其中某一策略，以概率0选取其余策略。,对于双方均只有两种策略的对策问题（即22对策），可按几何方法求解。,例8.5 A、B为作战双方，A方拟派两架轰炸机I和II去轰炸B方的指挥部，轰炸机I在前面飞行，II随后。两架轰炸机中只有一架带有炸弹，而另一架仅为护航。轰炸机飞至B方上空，受到B方战斗机的阻击。若战斗机阻击后面的轰炸机II，它仅受II的射击，被击中的
