1、 第七章对策与决策模型浙江大学数学建模基地浙江大学数学建模基地 对策与决策是人们生活和工作中经常会遇到的择优活动。对策与决策是人们生活和工作中经常会遇到的择优活动。人们在处理一个问题时，往往会面临几种情况，同时又存在人们在处理一个问题时，往往会面临几种情况，同时又存在几种可行方案可供选择，要求根据自己的行动目的选定一种几种可行方案可供选择，要求根据自己的行动目的选定一种方案，以期获得最佳的结果。方案，以期获得最佳的结果。有时，人们面临的问题具有竞争性质，如商业上的竞争有时，人们面临的问题具有竞争性质，如商业上的竞争、体育中的比赛和军事行动、政治派别的斗争等等。这时竞、体育中的比赛和军事行动、政
2、治派别的斗争等等。这时竞争双方或各方都要发挥自己的优势，使己方获得最好结果。争双方或各方都要发挥自己的优势，使己方获得最好结果。因而双方或各方都要根据不同情况、不同对手做出自己的决因而双方或各方都要根据不同情况、不同对手做出自己的决择，此时的决策称为对策。在有些情况下，如果我们把可能择，此时的决策称为对策。在有些情况下，如果我们把可能出现的若干种情况也看作是竞争对手可采取的几种策略，那出现的若干种情况也看作是竞争对手可采取的几种策略，那么也可以把决策问题当作对策问题来求解。么也可以把决策问题当作对策问题来求解。7.1 7.1 对策问题对策问题 对策问题的特征是参与者为利益相互冲突的各方，其结局
3、对策问题的特征是参与者为利益相互冲突的各方，其结局不取决于其中任意一方的努力而是各方所采取的策略的综合不取决于其中任意一方的努力而是各方所采取的策略的综合结果。结果。先考察几个实际例子。先考察几个实际例子。例例7.1 （田忌赛马）（田忌赛马）田忌赛马是大多数人都熟知的故事，传说战国时期齐王欲与田忌赛马是大多数人都熟知的故事，传说战国时期齐王欲与大将田忌赛马，双方约定每人挑选上、中、下三个等级的马大将田忌赛马，双方约定每人挑选上、中、下三个等级的马各一匹进行比赛，每局赌金为一千金。齐王同等级的马均比各一匹进行比赛，每局赌金为一千金。齐王同等级的马均比田忌的马略胜一筹，似乎必胜无疑。田忌的朋友孙膑
4、给他出田忌的马略胜一筹，似乎必胜无疑。田忌的朋友孙膑给他出了一个主意，让他用下等马比齐王的上等马，上等马对齐王了一个主意，让他用下等马比齐王的上等马，上等马对齐王的中等马，中等马对齐王的下等马，结果田忌二胜一败，反的中等马，中等马对齐王的下等马，结果田忌二胜一败，反而赢了一千金。而赢了一千金。例例7.2 （石头（石头剪子剪子布）布）这是一个大多数人小时候都玩过的游戏。游戏双方只能选石这是一个大多数人小时候都玩过的游戏。游戏双方只能选石头、剪子、布中的一种，石头赢剪子，剪子赢布，而布又赢头、剪子、布中的一种，石头赢剪子，剪子赢布，而布又赢石头，赢者得一分，输者失一分，双方相同时不得分，见下石头，
5、赢者得一分，输者失一分，双方相同时不得分，见下表。表。表表7.17.1石头石头剪子剪子布布石头石头011剪子剪子101布布110例例7.3 （囚犯的困惑）（囚犯的困惑）警察同时逮捕了两人并分开关押，逮捕的原因是他们持有大警察同时逮捕了两人并分开关押，逮捕的原因是他们持有大量伪币，警方怀疑他们伪造钱币，但没有找到充分证据，希量伪币，警方怀疑他们伪造钱币，但没有找到充分证据，希望他们能自己供认，这两个人都知道：如果他们双方都不供望他们能自己供认，这两个人都知道：如果他们双方都不供认，将被以使用和持有大量伪币罪被各判刑认，将被以使用和持有大量伪币罪被各判刑1818个月；如果双个月；如果双方都供认伪造
6、了钱币，将各被判刑方都供认伪造了钱币，将各被判刑3 3年；如果一方供认另一方年；如果一方供认另一方不供认，则供认方将被从宽处理而免刑，但另一方面将被判不供认，则供认方将被从宽处理而免刑，但另一方面将被判刑刑7 7年。将嫌疑犯年。将嫌疑犯A A、B B被判刑的几种可能情况列表如下被判刑的几种可能情况列表如下：表表7.27.2嫌疑犯嫌疑犯B供认供认不供认不供认嫌疑犯嫌疑犯A供认供认不供认不供认（3，3）（0，7）（7，0）（1.5，1.5）表中每对数字表示嫌疑犯表中每对数字表示嫌疑犯A A、B B被判刑的年数。如果两名疑犯均担心对方被判刑的年数。如果两名疑犯均担心对方供认并希望受到最轻的惩罚，最保
7、险的办法自然是承认制造了伪币。供认并希望受到最轻的惩罚，最保险的办法自然是承认制造了伪币。一、对策的基本要素一、对策的基本要素（1 1）局中人局中人。参加决策的各方被称为决策问题的局中人，。参加决策的各方被称为决策问题的局中人，一个决策总是可以包含两名局中人（如棋类比赛、人与大自一个决策总是可以包含两名局中人（如棋类比赛、人与大自然作斗争等），也可以包含多于两名局中人（如大多数商业然作斗争等），也可以包含多于两名局中人（如大多数商业中的竞争、政治派别间的斗争）。局中人必须要拥用可供其中的竞争、政治派别间的斗争）。局中人必须要拥用可供其选择并影响最终结局的策略，在例选择并影响最终结局的策略，在例
8、8.38.3中，局中人是中，局中人是A A、B B两两名疑犯，警方不是局中人。两名疑犯最终如何判刑取决于他名疑犯，警方不是局中人。两名疑犯最终如何判刑取决于他们各自采取的态度，警方不能为他们做出选择。们各自采取的态度，警方不能为他们做出选择。从这些简单实例中可以看出对策现象从这些简单实例中可以看出对策现象中包含的几个基本要素。中包含的几个基本要素。（2 2）策略集合策略集合。局中人能采取的可行方案称为策略，每一。局中人能采取的可行方案称为策略，每一局中人可采取的全部策略称为此局中人的策略集合。对策问局中人可采取的全部策略称为此局中人的策略集合。对策问题中，对应于每一局中人存在着一个策略集合，而
9、每一策略题中，对应于每一局中人存在着一个策略集合，而每一策略集合中至少要有两个策略，否则该局中人可从此对策问题中集合中至少要有两个策略，否则该局中人可从此对策问题中删去，因为对他来讲，不存在选择策略的余地。应当注意的删去，因为对他来讲，不存在选择策略的余地。应当注意的是，所谓策略是指在整个竞争过程中对付他方的完整方法，是，所谓策略是指在整个竞争过程中对付他方的完整方法，并非指竞争过程中某步所采取的具体局部办法。例如下棋中并非指竞争过程中某步所采取的具体局部办法。例如下棋中的某步只能看和一个完整策略的组成部分，而不能看成一个的某步只能看和一个完整策略的组成部分，而不能看成一个完整的策略。当然，有
10、时可将它看成一个多阶段对策中的子完整的策略。当然，有时可将它看成一个多阶段对策中的子对策。策略集合可以是有限集也可以是无限集。策略集为有对策。策略集合可以是有限集也可以是无限集。策略集为有限集时称为有限对策，否则称为无限对策。限集时称为有限对策，否则称为无限对策。记局中人记局中人i i的策略集合为的策略集合为SiSi。当对策问题各方都从各自的策略。当对策问题各方都从各自的策略集合中选定了一个策略后，各方采取的策略全体可用一矢量集合中选定了一个策略后，各方采取的策略全体可用一矢量S S表示，称之为一个纯局势（简称局势）。表示，称之为一个纯局势（简称局势）。例如例如，若一对策中包含，若一对策中包含
11、A、B两名局中人，其策略集合分别为两名局中人，其策略集合分别为SA=1,m，SB=1,n。若。若A选择策略选择策略 i而而B选策选策略略 j，则（，则（i,j）就构成此对策的一个纯局势。显然，）就构成此对策的一个纯局势。显然，SA与与SB一共可构成一共可构成mn个纯局势，它们构成表个纯局势，它们构成表8.3。对策问题的全。对策问题的全体纯局势构成的集合体纯局势构成的集合S称为此对策问题的局势集合。称为此对策问题的局势集合。(m,n)(m,j)(m,2)(m,1)m(i,n)(i,j)(i,2)(i,1)i(2,n)(2,j)(2,2)(2,1)2(1,n)(1,j)(1,2)(1,1)1A的的
12、策策略略nJ21B的策略的策略（3 3）赢得函数（或称支付函数）。对策的结果用矢量表示，赢得函数（或称支付函数）。对策的结果用矢量表示，称之为赢得函数。赢得函数称之为赢得函数。赢得函数F F为定义在局势集合为定义在局势集合S S上的矢值函上的矢值函数，对于数，对于S S中的每一纯局势中的每一纯局势S S，F F（S S）指出了每一局中人在此）指出了每一局中人在此对策结果下应赢得（或支付）的值。综上所述，一个对策模对策结果下应赢得（或支付）的值。综上所述，一个对策模型由局中人、策略集合和赢得函数三部分组成。记局中人集型由局中人、策略集合和赢得函数三部分组成。记局中人集合为合为I I=1,=1,k
13、 k，对每一，对每一i iI I，有一策略集合，有一策略集合S Si i，当，当I I中每中每一局中人一局中人i i选定策略后得一个局势选定策略后得一个局势s s；将；将s s代入赢得函数代入赢得函数F F，即，即得一矢量得一矢量F F(s s)=()=(F F1 1(s s),),F Fk k(s s)，其中，其中F Fi i(s s)为在局势为在局势s s下下局中人局中人i i的赢得（或支付）。的赢得（或支付）。本节讨论只有两名局中人的对策问题，即两人对策，其结果可本节讨论只有两名局中人的对策问题，即两人对策，其结果可以推广到一般的对策模型中去。对于只有两名局中人的对策问以推广到一般的对策
14、模型中去。对于只有两名局中人的对策问题，其局势集合和赢得函数均可用表格表示。例如，表题，其局势集合和赢得函数均可用表格表示。例如，表8.28.2就就给出了例给出了例8.38.3的局势集合和赢得函数。的局势集合和赢得函数。二、零和对策二、零和对策存在一类特殊的对策问题。在这类对策中，当纯局势确定后，存在一类特殊的对策问题。在这类对策中，当纯局势确定后，A A之所得恰为之所得恰为B B之所失，或者之所失，或者A A之所失恰为之所失恰为B B之所得，即双方所得之所得，即双方所得之和总为零。在零和对策中，因之和总为零。在零和对策中，因F F1 1(s s)=)=F F2 2(s s)，只需指出其，只需
15、指出其中一人的赢得值即可，故赢得函数可用赢得矩阵表示。例如若中一人的赢得值即可，故赢得函数可用赢得矩阵表示。例如若A A有有m m种策略，种策略，B B有有n n种策略，赢得矩阵种策略，赢得矩阵 111212122212nnm nmmmnaaaaaaRaaa表示若表示若A A选取策略选取策略i i而而B B选取策略选取策略j j，则，则A A之所得为之所得为a aijij（当（当a aijij00时为支付）。时为支付）。在有些两人对策的赢得表中，在有些两人对策的赢得表中，A A之所得并非明显为之所得并非明显为B B之所失，但之所失，但双方赢得数之和为一常数。例如在表双方赢得数之和为一常数。例如
16、在表7 7.4.4中，无论中，无论A A、B B怎样选怎样选取策略，双方赢得总和均为取策略，双方赢得总和均为1010，此时，若将各人赢得数减去两，此时，若将各人赢得数减去两人的平均赢得数，即可将赢得表化为零和赢得表。表人的平均赢得数，即可将赢得表化为零和赢得表。表7 7.4.4中的中的对策在转化为零和对策后，具有赢得矩阵对策在转化为零和对策后，具有赢得矩阵表表7.47.4局中人局中人B123局中人局中人A1(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)342142313111R给定一个两人对策只需给出局中人给定一个
17、两人对策只需给出局中人A A、B B的策略集合的策略集合S SA A、S SB B及表示双方赢得值的赢得矩阵及表示双方赢得值的赢得矩阵R R。综上所述，当遇到零和。综上所述，当遇到零和对策或可转化为零和对策的问题时，对策或可转化为零和对策的问题时，R R可用通常意义下的矩可用通常意义下的矩阵表示，否则阵表示，否则R R的元素为一两维矢量。的元素为一两维矢量。故两人对策故两人对策G G又可称为矩阵对策并可简记成又可称为矩阵对策并可简记成G G=S SA A,S SB B,R R 例例7.4 给定给定G=SA,SB,R，其中，其中SA=1,2,3，SB=1,2,3,4 1234123 126302
18、21421810601016R从从R R中可以看出，若中可以看出，若A A希望获得最大赢利希望获得最大赢利3030，需采取策略，需采取策略 1 1，但此时若，但此时若B B采采取策略取策略 4 4，A A非但得不到非但得不到3030，反而会失去，反而会失去2222。为了稳妥，双方都应考虑到。为了稳妥，双方都应考虑到对方有使自己损失最大的动机，在最坏的可能中争取最好的结果。局中人对方有使自己损失最大的动机，在最坏的可能中争取最好的结果。局中人A A采取策略采取策略 1 1、2 2、3 3时，最坏的赢得结果分别为时，最坏的赢得结果分别为 min 12,6,30,22 =22min 14,2,18,
19、10=2min 6,0,10,16=10其中最好的可能为其中最好的可能为max max 22,2,22,2,10=210=2。如果。如果A A采取策略采取策略 2 2，无论，无论B B采采取什么策略，取什么策略，A A的赢得均不会少于的赢得均不会少于2.2.B B采取各方案的最大损失为采取各方案的最大损失为max 12,14,max 12,14,6=146=14，max max 6,2,0=26,2,0=2，max max 30,18,30,18,10=3010=30和和max max 22,10,16=1622,10,16=16。当。当B B采取策略采取策略 2 2时，其损失时，其损失不会超
20、过不会超过2 2。注意到在赢得矩阵中，。注意到在赢得矩阵中，2 2既是所在行中的最小元素又是所在列既是所在行中的最小元素又是所在列中的最大元素。此时，只要对方不改变策略，任一局中人都不可能通过变中的最大元素。此时，只要对方不改变策略，任一局中人都不可能通过变换策略来增大赢得或减小损失，称这样的局势为对策的一个稳定点或稳定换策略来增大赢得或减小损失，称这样的局势为对策的一个稳定点或稳定解，（注：也被称为鞍点）解，（注：也被称为鞍点）定义8.1 对于两人对策对于两人对策G=SA,SB,R，若有，若有，则称，则称G具有稳定解，并称具有稳定解，并称VG为对策为对策G的值。若纯局势（的值。若纯局势（）使
21、得）使得，则称（，则称（）为对策）为对策G的鞍点或稳定解，赢得矩阵中与（的鞍点或稳定解，赢得矩阵中与（）相对应的元素相对应的元素 称为赢得矩阵的鞍点，称为赢得矩阵的鞍点，与与 分别称为局中人分别称为局中人A与与B的的最优策略。最优策略。maxminminmaxijijGjjiiaaV*,ij*minmaxi jijGjjaaV*,ij*,ij*i ja*i*j对（对（7 7.1.1）式中的赢得矩阵，容易发现不存在具有上述性质的鞍点。给定）式中的赢得矩阵，容易发现不存在具有上述性质的鞍点。给定一个对策一个对策G G，如何判断它是否具有鞍点呢？为了回答这一问题，先引入下，如何判断它是否具有鞍点呢？
22、为了回答这一问题，先引入下面的极大极小原理。面的极大极小原理。定理定理7 7.1.1 设设G=SA,SB,R，记记 ，则必有则必有+0maxminminmaxijijjjiiaa，证明:，maxmin(ijija)易见易见为为A的最小赢得，的最小赢得，为为B的最小赢得，的最小赢得，由于由于G是零和对策，故是零和对策，故+0必成立。必成立。定理定理7 7.2.2 零和对策零和对策G G具有稳定解的充要条件为具有稳定解的充要条件为+=0=0。证明：（充分性）（充分性）由由和和的定义可知，存在一行（例如的定义可知，存在一行（例如p p行）行）为为p p行中的最小元素且存在一列（例如行中的最小元素且存
23、在一列（例如q q列），列），为为q q列中的列中的最大元素。故有最大元素。故有 a apqpq且且a apqpq又因又因+=0=0，所以，所以=，从而得出，从而得出a apqpq=，a apqpq为赢得矩为赢得矩阵的鞍点，（阵的鞍点，（p p,q q）为）为G G的稳定解。的稳定解。（必要性）（必要性）若若G G具有稳定解（具有稳定解（p p,q q），则），则a apqpq为赢得矩阵的鞍点。故有为赢得矩阵的鞍点。故有 maxminminijpjpqjjiaaaminmaxmaxijiqpqjiiaaa 从而可得从而可得+0+0，但根据定理，但根据定理8.18.1，+0+0必成立，故必有必成
24、立，故必有+=0=0。上述定理给出了对策问题有稳定解（简称为解）的充要条件。当对策问上述定理给出了对策问题有稳定解（简称为解）的充要条件。当对策问题有解时，其解可以不唯一。例如，若题有解时，其解可以不唯一。例如，若 123451234 94311010115185182641513R则易见，（则易见，（2,2），（），（2,4），（），（4,2），（），（4,4）均为此对策问题的解。）均为此对策问题的解。一般又可以证明。一般又可以证明。定理定理7 7.3 .3 对策问题的解具有下列性质：对策问题的解具有下列性质：（1）无差别性。若（）无差别性。若（,）与（）与（,）同为对策）同为对策G的解，则
25、必有的解，则必有 。1i1i2i2i1 12 2i ji jaa（2 2）可交换性。若（）可交换性。若（,j1j1）、（）、（,j2j2）均为对策）均为对策G G的解，的解，则（则（,j2j2）和（）和（,j1j1）也必为）也必为G G的解。的解。1i2i1i2i定理定理7.3的证明非常容易，作为习题的证明非常容易，作为习题留给读者自己去完成。留给读者自己去完成。具有稳定解的零和对策问题是一类特别简单的对策问题，它所对应的赢具有稳定解的零和对策问题是一类特别简单的对策问题，它所对应的赢得矩阵存在鞍点，任一局中人都不可能通过自己单方面的努力来改进结得矩阵存在鞍点，任一局中人都不可能通过自己单方面
26、的努力来改进结果。然而，在实际遇到的零和对策中更典型的是果。然而，在实际遇到的零和对策中更典型的是+0的情况。由于赢得的情况。由于赢得矩阵中不存在鞍点，至少存在一名局中人，在他单方面改变策略的情况矩阵中不存在鞍点，至少存在一名局中人，在他单方面改变策略的情况下，有可能改善自己的收益。例如，考察（下，有可能改善自己的收益。例如，考察（7.1）中的赢得矩阵）中的赢得矩阵R。若双。若双方都采取保守的方都采取保守的max min原则，将会出现纯局势原则，将会出现纯局势（4,1）或）或（4,3）。但如果局中人）。但如果局中人A适当改换策略，他可以增加收入。例如，如适当改换策略，他可以增加收入。例如，如果
27、果B采用策略采用策略 1，而，而A改换策略改换策略 1，则，则A可收益可收益 3。但此时若。但此时若B改换策略改换策略 2，又会使，又会使A输掉输掉4，。此时，在只使用纯策略的范围内，对策问题。此时，在只使用纯策略的范围内，对策问题无解。这类决策如果只进行一次，局中人除了碰运气以外别无办法。但无解。这类决策如果只进行一次，局中人除了碰运气以外别无办法。但如果这类决策要反复进行多次，则局中人固定采用一种策略显然是不明如果这类决策要反复进行多次，则局中人固定采用一种策略显然是不明智的，因为一旦对手看出你会采用什么策略，他将会选用对自己最为有智的，因为一旦对手看出你会采用什么策略，他将会选用对自己最
28、为有利的策略。这时，局中人均应根据某种概率来选用各种策略，即采用混利的策略。这时，局中人均应根据某种概率来选用各种策略，即采用混合策略的办法，使自己的期望收益尽可能大。合策略的办法，使自己的期望收益尽可能大。设设A方用概率方用概率xi选用策略选用策略 i，B方用概率方用概率yj选用策略选用策略 j，且双方每次选用什么策略是随机的，不能让对方看出规律，且双方每次选用什么策略是随机的，不能让对方看出规律，111mnijij记记X=(x1,xm)T，Y=(y1,yn)T，则，则A的期望赢得为的期望赢得为E(X,Y)=XTRY其中，其中，R为为A方的赢得矩阵方的赢得矩阵。记记 SA:策略策略1,mSB
29、:策略策略1,n概率概率x1,xm概率概率y1,yn分别称分别称SA与与SB为为A方和方和B方的混合策略。方的混合策略。对于需要使用混合策略的对策问题，也有具有稳定解的对策问题的类似结果。对于需要使用混合策略的对策问题，也有具有稳定解的对策问题的类似结果。定义定义7.2 若存在若存在m维概率向量和维概率向量和n维概率向量，使得对一切维概率向量，使得对一切m维概率向量维概率向量X和和n维概率向量维概率向量y有有 则称（则称（,）为混合策略对策问题的鞍点。）为混合策略对策问题的鞍点。maxminTTTxyX RYX RYx RYXY定理定理7.4 （Von Neumann）任意混合策略对策问题必存
30、在鞍点，即必存在概率向）任意混合策略对策问题必存在鞍点，即必存在概率向量和，使得：量和，使得：（证明从略）。（证明从略）。maxminminmaxTTTxxyyX RYX RYX RY使用纯策略的对策问题（具有稳定解的对策问题）可以看成使用混合策略的对策使用纯策略的对策问题（具有稳定解的对策问题）可以看成使用混合策略的对策问题的特殊情况，相当于以概率问题的特殊情况，相当于以概率1选取其中某一策略，以概率选取其中某一策略，以概率0选取其余策略。选取其余策略。对于双方均只有两种策略的对策问题（即对于双方均只有两种策略的对策问题（即22对策），可按几何方法求解。对策），可按几何方法求解。例例7.57
31、.5 A A、B B为作战双方，为作战双方，A A方拟派两架轰炸机方拟派两架轰炸机I I和和IIII去轰炸去轰炸B B方的指挥方的指挥部，轰炸机部，轰炸机I I在前面飞行，在前面飞行，IIII随后。两架轰炸机中只有一架带有炸弹，随后。两架轰炸机中只有一架带有炸弹，而另一架仅为护航。轰炸机飞至而另一架仅为护航。轰炸机飞至B B方上空，受到方上空，受到B B方战斗机的阻击。若方战斗机的阻击。若战斗机阻击后面的轰炸机战斗机阻击后面的轰炸机IIII，它仅受，它仅受IIII的射击，被击中的概率为的射击，被击中的概率为0.30.3（I I来不及返回击它）。若战斗机阻击来不及返回击它）。若战斗机阻击I I，
32、它将同时受到两架轰炸机的，它将同时受到两架轰炸机的射击，被击中的概率为射击，被击中的概率为0.70.7。一旦战斗机未被击落，它将以。一旦战斗机未被击落，它将以0.60.6的概率的概率击毁其选中的轰炸机。请为击毁其选中的轰炸机。请为A A、B B双方各选择一个最优策略，即：对于双方各选择一个最优策略，即：对于A A方应选择哪一架轰炸机装载炸弹？对于方应选择哪一架轰炸机装载炸弹？对于B B方战斗机应阻击哪一架轰炸机？方战斗机应阻击哪一架轰炸机？解：解：双方可选择的策略集分别为双方可选择的策略集分别为SA=1,2,1：轰炸机：轰炸机 I 装炸弹，装炸弹，II 护航护航 2：轰炸机：轰炸机 II 装炸
33、弹，装炸弹，I 护航护航SA=1,2,1：阻击轰炸机：阻击轰炸机 I 2：阻击轰炸机：阻击轰炸机 II赢得矩阵赢得矩阵R=（aij）22，aij为为A方采取策略方采取策略 i而而B方采取策略方采取策略 j 时，轰时，轰炸机轰炸炸机轰炸B方指挥部的概率，由题意可计算出：方指挥部的概率，由题意可计算出：a11=0.7+0.3(10.6)=0.82a12=1,a21=1a22=0.3+0.7(10.6)=0.58即即0.82110.58R易求得易求得 ，。由于由于+0，矩阵，矩阵R不存在鞍点，应当求最佳混合策略。不存在鞍点，应当求最佳混合策略。maxmin0.82ijjiaminmax1ijjia
34、现设现设A以概率以概率x1取策略取策略 1、概率、概率x2取策略取策略 2；B以概率以概率y1取策略取策略 1、概率、概率y2取策略取策略 2。先从先从B方来考虑问题。方来考虑问题。B采用采用 1时，时，A方轰炸机攻击指挥部的概率的期方轰炸机攻击指挥部的概率的期望值为望值为E（1）=0。82x1+x2，而，而B采用采用 2时，时，A方轰炸机攻击指挥部的方轰炸机攻击指挥部的概率的期望值为概率的期望值为E（2）=x1+0.58x2。若。若E（1）E（2），不妨设），不妨设E（1）2且且n2时，采用几何方法求解就变得相当麻烦，时，采用几何方法求解就变得相当麻烦，此时通常采用线性规划方法求解。此时通常
35、采用线性规划方法求解。现设现设A以概率以概率x2采取策略采取策略 2，若，若B采取策略采取策略 2，则，则A的期望赢得为的期望赢得为a11(1x2)+a21x2。对应。对应x2的不同取值（的不同取值（0 x21），），a11(1x2)+a12x2恰好构成连恰好构成连接两个接两个B1的直线段。类似地，连接两个的直线段。类似地，连接两个B2的直线段恰好对应当的直线段恰好对应当B取取 2而而A以概率以概率x2取取2时的赢得时的赢得a12(1x2)+a22x2。设两直线段相交于。设两直线段相交于N，并设并设N对应于对应于 。若。若A以小于以小于 的的x2取策略取策略 2，则，则B可以采取可以采取 1使
36、使A的期望赢的期望赢得减小；反之，若得减小；反之，若x2 ，则，则B又可采取又可采取 2而使而使A的赢得减小。故的赢得减小。故A的的最佳混合策略为以最佳混合策略为以 =1 概率取概率取 1，以概率取，以概率取 2（注：（注：B的最佳混的最佳混合策略可类似用几何方法求得）。合策略可类似用几何方法求得）。2x2x2x2x1xA方选择混合策略方选择混合策略 的目的是使得的目的是使得XminmaxTTXYX RYX RY1minmax()nTjjXYjX Ry e1minmaxnjjXYjE y其中其中ej为只有第为只有第j个分量为个分量为1而其余分量均为零的向量，而其余分量均为零的向量，Ej=XTR
37、ej。记记 ，由于，由于 ，在在yk=1，yj=0（jk）时达到最大值）时达到最大值u，maxKjjuEE11njjy1maxnjjyjE y故故 应为线性规划问题应为线性规划问题 X1nijiia xumin u ,j=1,2,n(即即EjEk)11miixxi0,i=1,2,mS.t的解。的解。同理，同理，应为线性规划应为线性规划Y1nijiia ymax ,i=1,2,m11nijyyj0,i=1,2,nS.t的解。的解。由线性规划知识，（由线性规划知识，（7.2）与（）与（7.3）互为对偶线性规划，它们具有相同的最优目）互为对偶线性规划，它们具有相同的最优目标函数值。关于线性规划对偶理
38、论，有兴趣的读者可以参阅有关书籍，例如鲁恩标函数值。关于线性规划对偶理论，有兴趣的读者可以参阅有关书籍，例如鲁恩伯杰的伯杰的“线性与非线性规划引论线性与非线性规划引论”。为了寻找例为了寻找例7.5中中A方的最优混合策略，求解线性规划方的最优混合策略，求解线性规划min uS.t 0.82x1+x2 u x1+0.58x2 u x1+x2=1 x1,x2 0可得最优混合策略可得最优混合策略x1=0.7,x2=0.3。类似求解线性规划。类似求解线性规划max S.t 0.82y1+y2 y1+0.58y2 y1+y2=1 y1,y2 0可得可得B方最优混合策略：方最优混合策略：y1=0.7,y2=
39、0.3。三、非零和对策三、非零和对策除了零和对策外，还存在着另一类对策问题，局中人获利之和并非常数。除了零和对策外，还存在着另一类对策问题，局中人获利之和并非常数。例例7 7.4.4 现有一对策问题，双方获利情况见表现有一对策问题，双方获利情况见表7 7.5.5。表表7 7.5.5B方方A方方1231234（8,2）（3,4）（1,6）（4,2）（0,9）（9,0）（6,2）（4,6）（7,3）（2,7）（8,1）（5,1）假如假如A、B双方仍采取稳妥的办法，双方仍采取稳妥的办法，A发现如采取策略发现如采取策略4，则至少可获利，则至少可获利4，而，而B发现如采取策略发现如采取策略1，则至少可获
40、利，则至少可获利2。因而，这种求稳妥的想法。因而，这种求稳妥的想法将导至出现局势（将导至出现局势（4，2）。）。容易看出，从整体上看，结果并不是最好的，因为双方的总获利有可能容易看出，从整体上看，结果并不是最好的，因为双方的总获利有可能达到达到10。不难看出，依靠单方面的努力不一定能收到良好的效果。看来，。不难看出，依靠单方面的努力不一定能收到良好的效果。看来，对这一对策问题，双方最好还是握手言和，相互配合，先取得总体上的对这一对策问题，双方最好还是握手言和，相互配合，先取得总体上的最大获利，然后再按某一双方均认为较为合理的方式来分享这一已经获最大获利，然后再按某一双方均认为较为合理的方式来分
41、享这一已经获得的最大获利。得的最大获利。例例8.4说明，总获利数并非常数的对策问题（即不能转化为零和对策的问说明，总获利数并非常数的对策问题（即不能转化为零和对策的问题），是一类存在着合作基础的对策问题。当然，这里还存在着一个留待题），是一类存在着合作基础的对策问题。当然，这里还存在着一个留待解决而又十分关键的问题：如何分享总获利，如果不能达到一个双方（或解决而又十分关键的问题：如何分享总获利，如果不能达到一个双方（或各方）都能接受的各方）都能接受的“公平公平”的分配原则，则合作仍然不能实现。怎样建立的分配原则，则合作仍然不能实现。怎样建立一个一个“公平公平”的分配原则是一个较为困难的问题，将
42、在第八章中介绍。的分配原则是一个较为困难的问题，将在第八章中介绍。最后，我们来考察几个对策问最后，我们来考察几个对策问题的实例。题的实例。例例7 7.6.6（战例分析）（战例分析）1944年年8月，美军第一军和英军占领法国诺曼第不久，月，美军第一军和英军占领法国诺曼第不久，立即从海防前线穿过海峡，向立即从海防前线穿过海峡，向Avranches进军。美军第一军和英军的行动进军。美军第一军和英军的行动直接威胁到德军第九军。美军第三军也开到了直接威胁到德军第九军。美军第三军也开到了Avranches的南部，双方军的南部，双方军队所处的地理位置如图队所处的地理位置如图8.2所示。所示。美军方面的指挥官
43、是美军方面的指挥官是Bradley将军，德军指挥官是将军，德军指挥官是Von Kluge将军。将军。Von Kluge将军面临的问题是或者向西将军面临的问题是或者向西进攻，加强他的西部防线，切断美军进攻，加强他的西部防线，切断美军援助；或者撤退到东部，占据塞那河援助；或者撤退到东部，占据塞那河流域的有利地形，并能得到德军第十流域的有利地形，并能得到德军第十五军的援助。五军的援助。Bradley将军的问题是如何调动他的后将军的问题是如何调动他的后备军，后备军驻扎在海峡南部。备军，后备军驻扎在海峡南部。Bradley将军有三种可供选择的策略：将军有三种可供选择的策略：他可以命令后备军原地待命，当海
44、峡他可以命令后备军原地待命，当海峡形势危急时支援第一军或出击东部敌形势危急时支援第一军或出击东部敌人，以减轻第一军的压力。人，以减轻第一军的压力。双方应如何决策，使自己能有较大的机会赢得战争的胜利呢？双方应如何决策，使自己能有较大的机会赢得战争的胜利呢？我们将用建立矩阵对策模型的方法，来试图求得双方的最优策略。模型假设：我们将用建立矩阵对策模型的方法，来试图求得双方的最优策略。模型假设：1、Bradley将军和将军和Von Kluge将军分别为对策问题的局中人将军分别为对策问题的局中人A和和B。2、局中人、局中人A的策略集合为的策略集合为SA=1,2,3，其中：，其中：1为后备军增援保为后备军
45、增援保卫海峡；卫海峡；2为后备军东征，切断德军后路；为后备军东征，切断德军后路；3为后备军待命为后备军待命 3、局中人、局中人B的策略集合为的策略集合为SB=1,2，其中：，其中：1为德国向西进攻海峡，为德国向西进攻海峡，切断美军援助；切断美军援助；2为德军撤退到东部，占领塞纳河流域有利地形。为德军撤退到东部，占领塞纳河流域有利地形。4、SA、SB构成六种纯局势，综合双方实力，各种局势估计结果如下。若构成六种纯局势，综合双方实力，各种局势估计结果如下。若B采取采取策略策略 1，即德军采取攻势，则有，即德军采取攻势，则有（1）（）（1,1），估计美军击败德军并占领海峡的可能性（即概率）为），估计
46、美军击败德军并占领海峡的可能性（即概率）为13（2）（）（2,1），估计美军取胜的可能为），估计美军取胜的可能为 。德军很可能打破美军第一军。德军很可能打破美军第一军的防线，并切断美军的退路。的防线，并切断美军的退路。16（3）（）（3,1），估计美军可以根据需要增援。如不需增援，后备军可东进），估计美军可以根据需要增援。如不需增援，后备军可东进绕行到德军后方。这样，美军将占领海峡并彻底歼灭德军第九军。绕行到德军后方。这样，美军将占领海峡并彻底歼灭德军第九军。情况（情况（1 1）、（）、（2 2）、（）、（3 3）如图）如图8.38.3（1 1）、（）、（2 2）、（）、（3 3）所示。）所示
47、。若若B采取策略采取策略 2，即德军第九军东撤，占据塞纳河流域有利地形，则有，即德军第九军东撤，占据塞纳河流域有利地形，则有（4）（）（1,2），美方扩大了战线，德军虽占据了有利地形，美军仍有击败），美方扩大了战线，德军虽占据了有利地形，美军仍有击败 德军的可能性。德军的可能性。（5）（）（2,2），美后备军东进给德军东撤造成压力并挫伤德军，使美军击败），美后备军东进给德军东撤造成压力并挫伤德军，使美军击败德军的可能性增大到德军的可能性增大到 。56（6）（）（3,2），美后备军待命。在发现德军撤退后，奉命向东扰乱敌方撤退，），美后备军待命。在发现德军撤退后，奉命向东扰乱敌方撤退，为以后歼灭德
48、第九军创造条件，估计是美军击败德军的可能性为以后歼灭德第九军创造条件，估计是美军击败德军的可能性 。23情况（情况（4）、（）、（5）、（）、（6）见图）见图8.3（4）、（）、（5）（）（6）所示。）所示。上述分析估计是由上述分析估计是由Bradley将军作出的，据此构造出将军作出的，据此构造出A方赢得矩阵方赢得矩阵12123 113215 66213BA这是一个这是一个32对策矩阵。可以求得对策矩阵。可以求得 ，不存在稳定解，不存在稳定解，需要考虑其他解法。需要考虑其他解法。1656 0定义定义7.3 对于赢得矩阵对于赢得矩阵R，如果对所有，如果对所有j，aijakj均成立，且至少存在一个
49、均成立，且至少存在一个 使使得得 则称则称i行优于行优于k行（策略行（策略ai优于优于ak）。同样，如对一切）。同样，如对一切i有有aijakl，且至少有一个且至少有一个i0使得使得 ，则称，则称j列优于列优于l例（局中人例（局中人B的策略的策略 j优于优于 l）。）。0j0ijkjaa00i ji laa易见，若一个对策矩阵的第易见，若一个对策矩阵的第i行优于第行优于第k行，则无论局中人行，则无论局中人B选择哪种策略，局中选择哪种策略，局中人人A采取策略采取策略 i的获利总优于（至少不次于）采取策略的获利总优于（至少不次于）采取策略 k的获利。的获利。定理定理7.5 对于矩阵对策对于矩阵对策
50、G=SA,SB,R，若矩阵，若矩阵R的某行优于第的某行优于第i1,ik行，行，则局中人则局中人A在选取最优策略时，必取在选取最优策略时，必取 。令令 ，R为从为从R中划去第中划去第i1行，行，ik行后剩下的矩行后剩下的矩阵，则阵，则 的最优策略即原对策的最优策略即原对策G的最优策略，对于的最优策略，对于R中中列的最优关系也有类似的结果。列的最优关系也有类似的结果。10kiipp1,kAAiiSS,ABGSSR利用这一定理，有时对策问题可先进行化简，降低矩阵的阶数。利用这一定理，有时对策问题可先进行化简，降低矩阵的阶数。现在回过来讨论美、德军队对策问题。在现在回过来讨论美、德军队对策问题。在Br
