《运筹学7：对策论》由会员分享，可在线阅读，更多相关《运筹学7：对策论（11页珍藏版）》请在金锄头文库上搜索。
1、7 对策论7.1 引言7.2 矩阵对策纯策略意义下的解7.3 矩阵对策混合策略意义下的解7.4 矩阵对策的解法7.1 引言在日常生活中，经常可以看到一些具有相互斗争或竞争性质的行为，如下棋、打牌、体育比赛等。还有企业间的竞争、军队或国家间的战争、政治斗争等，都具有对抗的性质。这种具有竞争或对抗性质的行为称为对策行为。在这类行为中，各方具有不同的目标和利益。为实现自己的目标和利益，各方必须考虑对手可能采取的行动方案，并力图选择对自己最为有利或最为合理的行动方案。例如，我国战国时期的“齐王赛马”就是典型的对策行为。对策问题各种各样，所以对策模型也千差万别，但本质上都 包括三个基本要素：(1)局中人
2、 在一个对策行为中，有权决定自己行动方案的 对策参加者。(2)策略集 一局对策中，可供局中人选择的一个实际可行 的完整的行动方案称为一个策略。一个局中人全体策略构成的 集合，称为此局中人的策略集。(3)赢得函数 各局中人分别选定自己的策略构成的策略组 称为一个局势。当局势出现后，对策的结果也就确定了。对于 局势s，局中人i可以得到一个赢得Hi(s)，它是局势s的函数,称 为局中人i的赢得函数。对策的分类:1)按局中人的多少分为二人对策和多人对策。2)按策略集中策略的有限或无限，分为有限对策和无限对策。3)按各局中人赢得函数的代数和是否为零，分为零和对策和非零和对策。我们本章要学习的矩阵对策是指
3、二人、有限、零和对策。7.2 矩阵对策纯策略意义下的解矩阵对策就是二人有限零和对策。设两个局中人为、 ，它们各自的策略集为S11,2,m S21,2,n当局中人选定纯策略i，局中人选定纯策略j后，就 形成了一个纯局势(i,j)，这样的纯局势共有mn个。对任一纯局势(i,j)，记局中人的赢得值为aij，则得矩阵 A=（aij），称为矩阵人的赢得矩阵。由于是零和对 策，则矩阵人的赢得矩阵为-A。矩阵对策的名称正是由 此而来。通常把矩阵对策记为G,;S1,S2;A 或 GS1,S2;A对于GS1,S2;A， 若有等式max min aijmin max aijai*j*i j j i 成立，则称纯局
4、势(i*,j*)为对策G在纯策略 意义下的解，i*和j*分别称局中人、的 最优纯策略。记VGai*j*，称VG为对策G的值。定理1 矩阵对策GS1,S2;A 在纯策略意 义下有解,当且仅当存在纯局势(i*,j*)，使 对一切i=1,2,m，j=1,2,n，均有aij*ai*j*ai*j例：G=S1,S2,A -6 1 -8S1=1,2,3,4 A= 3 2 4S2=1,2, 3 9 -1 -10-3 0 6例如6 5 6 51 5 2 -1 A= 8 5 5 50 2 6 27.3 矩阵对策混合策略意义下的解 先看一个简单的例子: A= 3 65 4一般地，设矩阵对策GS1,S2;A，其中S1
5、1,2,m，S21,2,n，A（aij）mn若向量x(x1,x2,xm)T和y(y1,y2, ,yn)T满足xi1，xi0 (i=1,2,m) yj1，yj0 (j=1,2,n)则x和y分别称为局中人和局中人的混合策略。定理 任一矩阵对策GS1,S2;A，一定存在混合策略意义下的解。 定理 设有两个矩阵对策G1S1,S2;A1 G2S1,S2;A2其中A1(aij)，A2(aij+L)，L为任一常数。则(1)G1与G2同解；(2)VG2VG1+L设有矩阵对策GS1,S2;A ，其中S11,2,m，S21,2,n，A(aij)mn如果对一切j1,2,n，都有ai1jai2j, 即矩阵A的第i1行
6、元素 均大于等于第i2行的对应元素，则称局中人的纯策略i1优超于i2 ； 同样，若对一切i1,2,m，都有aij1aij2, 即矩阵A的第j1列 元素均小于等于第j2列的对应元素，则称局中人的纯策略j1优超 于j2。当局中人的某个纯策略被其它纯策略所优超时，可去掉这个 纯策略并在赢得矩阵A中划去对应的行。同样，当局中人的某个 纯策略被其它纯策略所优超时，也可去掉这个纯策略并在赢得矩阵 A中划去对应的列。利用此性质可以对矩阵对策化简。例：7.4 矩阵对策的解法(1) 22矩阵对策的线性方程组法所谓22矩阵对策是指局中人的赢得矩阵为22阶的 ，即 A = a11 a12a21 a22如果此对策有纯
7、策略意义下的解，则很容易求解；如果 没有纯策略意义下的解，则为求出各局中人的最优混合策略 可求解下列方程组：a11x1a21x2v a11y1a12y2va12x1a22x2v a21y1a22y2vy1y21 x1x21 当没有纯策略意义下的解时，方程组一定有严格非负解，即 为各局中人的最优混合策略。例(2)线性规划法当对策的值大于0时,可利用 线性规划法求解矩阵对策。构造 两个线性规划问题min zxiiaijxi1 (j=1,2,n)ixi0 (i=1,2,m)max wyjjaijyj1 (i=1,2,m)jyj0 (j=1,2,n)不难验证，这两个线性规 划问题互为对偶问题。当它 们取得最优解时必然有相同 的目标值。 设上述线性规划 问题的解为x、y、z， 则矩 阵对策的解为：对策的值 VG=1/z局中人的最优策略x*=VG x局中人的最优策略 y*=VGy
