运筹学7：对策论.ppt

《运筹学7：对策论.ppt》由会员分享，可在线阅读，更多相关《运筹学7：对策论.ppt（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、7 对策论7.1 引言引言7.2 矩阵对策纯策略意义下的解矩阵对策纯策略意义下的解7.3 矩阵对策混合策略意义下的解矩阵对策混合策略意义下的解7.4 矩阵对策的解法矩阵对策的解法7.1 引言 在日常生活中，经常可以看到一些具有相互斗争或竞在日常生活中，经常可以看到一些具有相互斗争或竞争性质的行为，如下棋、打牌、体育比赛等。还有企业争性质的行为，如下棋、打牌、体育比赛等。还有企业间的竞争、军队或国家间的战争、政治斗争等，都具有间的竞争、军队或国家间的战争、政治斗争等，都具有对抗的性质。这种具有竞争或对抗性质的行为称为对抗的性质。这种具有竞争或对抗性质的行为称为对策对策行为行为。在这类行为中，各方

2、具有不同的目标和利益。为。在这类行为中，各方具有不同的目标和利益。为实现自己的目标和利益，各方必须考虑对手可能采取的实现自己的目标和利益，各方必须考虑对手可能采取的行动方案，并力图选择对自己最为有利或最为合理的行行动方案，并力图选择对自己最为有利或最为合理的行动方案。动方案。例如，我国战国时期的例如，我国战国时期的“齐王赛马齐王赛马”就是典型的对就是典型的对策行为。策行为。对策问题各种各样，所以对策模型也千差万别，但本质上都对策问题各种各样，所以对策模型也千差万别，但本质上都包括三个基本要素：包括三个基本要素：(1)(1)局中人局中人 在一个对策行为中，有权决定自己行动方案的在一个对策行为中，

3、有权决定自己行动方案的对策参加者。对策参加者。(2)(2)策略集策略集 一局对策中，可供局中人选择的一个实际可行一局对策中，可供局中人选择的一个实际可行的完整的行动方案称为一个的完整的行动方案称为一个策略策略。一个局中人全体策略构成的。一个局中人全体策略构成的集合，称为此局中人的集合，称为此局中人的策略集策略集。(3)(3)赢得函数赢得函数 各局各局中人分别选定自己中人分别选定自己的策略构成的策略组的策略构成的策略组称为一个称为一个局势局势。当局当局势势出现出现后，后，对策对策的结果也就的结果也就确定确定了。了。对于对于局势局势s s，局局中人中人i i可以得到一个赢得可以得到一个赢得H Hi

4、 i(s)(s)，它是它是局势局势s s的的函数函数,称称为为局局中人中人i i的的赢得函数赢得函数。对策的分类对策的分类:1)1)按局中人的多少分为按局中人的多少分为二人对策二人对策和和多人对策多人对策。2)2)按策略集中策略的有限或无限，分为按策略集中策略的有限或无限，分为有限对策有限对策和和无限对策无限对策。3)3)按各局中人赢得函数的代数和是否为零，分为按各局中人赢得函数的代数和是否为零，分为零零和对策和对策和和非零和对策非零和对策。我们本章要学习的我们本章要学习的矩阵对策矩阵对策是指二人、有限、零和是指二人、有限、零和对策。对策。7.2 矩阵对策纯策略意义下的解 矩阵对策就是二人有限

5、零和对策。设两个局中人为矩阵对策就是二人有限零和对策。设两个局中人为、，它们各自的策略集为，它们各自的策略集为 S S11,2,m S S21,2,n当局中人当局中人选定选定纯策略纯策略i，局中人局中人选定选定纯策略纯策略j后，就后，就形成了一个形成了一个纯局势纯局势(i,j)，这样的这样的纯局势纯局势共有共有mn个。个。对任一纯局势对任一纯局势(i,j)，记局中人记局中人的赢得值为的赢得值为a aij，则得则得矩阵矩阵 A=A=（a aijij），），称为矩阵人称为矩阵人的的赢得矩阵赢得矩阵。由于是零和对。由于是零和对策，则矩阵人策，则矩阵人的赢得矩阵为的赢得矩阵为-A A。矩阵对策的名称正

6、是由矩阵对策的名称正是由此而来。通常把矩阵对策记为此而来。通常把矩阵对策记为 G G,;S,;S1,S,S2;A ;A 或或 G GSS1,S,S2;A;A 对于对于G GSS1,S,S2;A;A，若有等式若有等式 max min amax min aijmin max amin max aija ai*j*i j j i成立，则称纯局势成立，则称纯局势(i*,j*)为对策为对策G G在在纯策略纯策略意义下的意义下的解解，i*和和j*分别称局中人分别称局中人、的的最优纯策略最优纯策略。记。记V VG Ga ai*j*，称称V VG G为为对策对策G的值的值。定理定理1 1 矩阵对策矩阵对策G

7、GSS1,S,S2;A;A 在纯策略意在纯策略意义下有解义下有解,当当且仅当且仅当存在存在纯纯局势局势(i*,j*)，使使对一切对一切i=1,2,mi=1,2,m，j=1,2,nj=1,2,n，均有均有 a aij*aai*j*aai*j例：例：G=S1,S2,A -6 1 -8 S1=1,2,3,4 A=3 2 4 S2=1,2,3 9 -1 -10 -3 0 6 例如例如 6 5 6 5 1 5 2 -1A=8 5 5 5 0 2 6 27.3 矩阵对策混合策略意义下的解 先看一个简单的例子先看一个简单的例子:A=3 6 5 4 一般地，设矩阵对策一般地，设矩阵对策G GSS1,S,S2;

8、A;A，其中其中 S S11,2,m，S S21,2,n，A A（a aij）mn 若向量若向量x x(x(x1,x,x2,x,xm)T和和y y(y(y1,y,y2,y,yn)T满足满足 x xi1 1，x xi0(i=1,2,m)0(i=1,2,m)yyj1 1，y yj0(j=1,2,n)0(j=1,2,n)则则x x和和y y分别称为局中人分别称为局中人和局中人和局中人的的混合策略混合策略。定理定理 任一矩阵对策任一矩阵对策G GSS1,S,S2 2;A;A，一定存在混合策略意义一定存在混合策略意义下的解。下的解。定理定理 设有两个矩阵对策设有两个矩阵对策 G G1SS1,S,S2;A

9、;A1 G G2SS1,S,S2;A;A2 其中其中A A1(a(aij)，A A2(a(aij+L)+L)，L L为任一常数。则为任一常数。则 (1)(1)G G1与与G G2同解；同解；(2)(2)V VG2V VG1+L+L 设有矩阵对策设有矩阵对策G GSS1,S,S2;A;A，其中其中 S S11,2,m，S S21,2,n，A A(a(aij)mn 如果对一切如果对一切j j1,2,n1,2,n，都有都有a ai1jaai2j,即矩阵即矩阵A A的第的第i i1行元素行元素均大于等于第均大于等于第i i2行的对应元素，则称局中人行的对应元素，则称局中人的纯策略的纯策略i1优超于优超

10、于i2；同样，若对一切同样，若对一切i i1,2,m1,2,m，都有都有a aij1aaij2,即矩阵即矩阵A A的第的第j j1列列元素均小于等于第元素均小于等于第j j2列的对应元素，则称局中人列的对应元素，则称局中人的纯策略的纯策略j1优超优超于于j2。当局中人当局中人的某个纯策略被其它纯策略所优超时，可去掉这个的某个纯策略被其它纯策略所优超时，可去掉这个纯策略并在赢得矩阵纯策略并在赢得矩阵A A中划去对应的行。同样，当局中人中划去对应的行。同样，当局中人的某个的某个纯策略被其它纯策略所优超时，也可去掉这个纯策略并在赢得矩阵纯策略被其它纯策略所优超时，也可去掉这个纯策略并在赢得矩阵A A

11、中划去对应的列。中划去对应的列。利用利用此性质可以对矩阵对策化简。此性质可以对矩阵对策化简。例：例：7.4 矩阵对策的解法(1)22(1)22矩阵对策的线性方程组法矩阵对策的线性方程组法 所谓所谓2222矩阵对策矩阵对策是指局中人是指局中人的赢得矩阵为的赢得矩阵为2222阶的，阶的，即即 A=A=a11 a12a11 a12 a21 a22 a21 a22 如果此对策有纯策略意义下的解，则很容易求解；如果如果此对策有纯策略意义下的解，则很容易求解；如果没有纯策略意义下的解，则为求出各局中人的最优混合策略没有纯策略意义下的解，则为求出各局中人的最优混合策略可求解下列方程组：可求解下列方程组：a

12、a11x x1a a21x x2v av a11y y1a a12y y2v v a a12x x1a a22x x2v av a21y y1a a22y y2v v y y1y y21 x1 x1x x21 1当没有纯策略意义下的解时，方程组一定有严格非负解，即当没有纯策略意义下的解时，方程组一定有严格非负解，即为各局中人的最优混合策略。为各局中人的最优混合策略。例例(2)(2)线性规划法线性规划法 当当对策的值大于对策的值大于0 0时时,可利用可利用线性规划法求解矩阵对策。线性规划法求解矩阵对策。构造构造两个两个线性规划问题线性规划问题 min zmin zxxi i a aijx xi1

13、 (j=1,2,n)1 (j=1,2,n)i x xi0 (i=1,2,m)0 (i=1,2,m)max w max wyyj j a aijy yj1 (i=1,2,m)1 (i=1,2,m)j y yj0 (j=1,2,n)0 (j=1,2,n)不难验证，这两个线性规不难验证，这两个线性规划问题互为对偶问题。当它划问题互为对偶问题。当它们取得最优解时必然有相同们取得最优解时必然有相同的目标值。的目标值。设上述线性规划设上述线性规划问题的解为问题的解为x、y、z，则矩则矩阵对策的解为：阵对策的解为：对策的值对策的值 VG=1/z 局中人局中人的最优策略的最优策略 x*=VG x 局中人局中人的最优策略的最优策略 y*=VGy