优化建模与LINGO第09章

《优化建模与LINGO第09章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、优化建模与LINDO/LINGO软件第9章　　对　策　论［原书相关信息］谢金星,薛毅编著,清华大学出版社,2005年7月第1版.http://faculty.math.tsinghua.edu.cn/~jxie/lindo内容提要1.二人常数和对策2.二人非常数和对策3.n人合作对策第一节　二人常数和对策对策模型和算法的重要意义我们不就对策论模型全面的讨论，而是只介绍一些对策论模型的基本概念。重点介绍如何利用LINGO软件去解对策论模型中的有关问题。为了更好地理解LINGO软件的编程过程。对策论（GameTheory）又称为博弈论，是研究带有竞争与对抗问题

2、的理论与方法。对策论是现代数学的一个重要分支，也是运筹学的一个重要学科。对策论目前已在市场决策中有着广泛的应用。1.1　二人零和对策§1　二人常数和对策模型二人零和对策是最基本的对策形式，先用一个例子来说明。例9.1甲、乙两名儿童玩“石头--剪子--布”的游戏。石头胜剪子，剪子胜布，布胜石头。那么，甲、乙儿童如何做，使自己获胜的可能最大？在对策论中，应有以下要素：(1)局中人。是指参与对抗的各方，可以是一个人，也可以是一个集团。在例1.1的甲、乙两名儿童就是局中人。(2)策略。是指局中人所拥有的对付其他局中人的手段、方案的集合。如例1.1中共有石头、剪子、

3、布三种策略。(3)支付函数（或收益函数）。是指一局对策后各局中人的得与失，通常用正数字表示局中人的得，用负数字表示局中人的失。在例1.1的局中人甲的支付函数如表所示。乙石头剪子布甲石头01-1剪子-101布1-10例1.1　“石头--剪子--布”中儿童甲的支付函数当局中人得失总和为零时，称这类对策为零和对策；否则称为非零和对策。当局中人只有两个，且对策得失总和为零，则称为二人零和对策，若总得失总和为常数，则称为二人常数和对策，若得失总和是非常数的，则称为二人非常数和对策。若二人对策双方的得失是用矩阵形式表示，则称支付函数为支付矩阵，相应的对策称为矩阵对策。

4、通常，支付矩阵表示局中人A的支付函数。鞍点对策是对策的最基本策略，为更好地理解鞍点对策，先看一个简单的例子。1.对策的基本策略---鞍点对策例9.2设A、B两人对策，各自拥有三个策略：a1,a2,a3和b1,b2,b3,局中人A的支付（收益）矩阵由表1.2所示。试求A、B各自的最优策略。b1b2b3mina11391a26575a38422max859问题分析：从直观来看，局中人A应该出策略a1,因为这样选择，他有可能得到9.但局中人B看到了这一点，他出策略b1，这样局中人A不能得到9，而只能得到1.因此，局中人A也充分认识到这一点，他应当出策略a3,这样

5、做，就有可能得到8，而这种情况下局中人B，就要出策略b3，局中人A也只能得到2.这样做下来，局中人A只能选择策略a2,而局中人B也只能选择策略b2，大家达到平衡，最后局中人A赢得的值为5，局中人B输掉的值为5.从上面的分析可以看出，无论局中人A选择什么策略，他赢得的值总是小于等于5，而无论局中人B选择什么策略，他输掉的值总是大于等于5，5就是支付矩阵的鞍点。现讨论一般情况。假设局中人A的支付矩阵由表1.3所示。12…n1C11C12…Cn12C21C22…Cn2┆┆┆┆mCm1Cm2…Cmn其中局中人A有m个策略α1,…,αm,局中人B有n个策

6、略β1,…,βn,分别记为S1={α1,…,αm},S2={β1,…,βn}C为局中人A的支付矩阵，而-C为局中人B的支付矩阵。因此，矩阵对策记为G={A,B;S1,S2,C},或G={S1,S2,C}对于一般矩阵对策，有如下定义和定理。定义9.1设G={S1,S2,C}是一矩阵对策，若等式成立，则记vG=,ci*j*并称vG为对策G的值。称使式(1)成立纯局势(αi*,βj*)为G在纯策略下的解（或平衡局势），称αi*和βj*分别为局中人A、B的最优纯策略。定理9.1矩阵对策G={S1,S2,C}在纯策略意义下有解的充分必要条件是：存在纯局势(αi*,β

7、j*)使得定义9.2当矩阵对策的最优解不唯一时，有如下定理：定理9.2定理9.32.无鞍点的对策策略---混合对策如果支付矩阵有鞍点，选择鞍点对策是最优的对策策略，如果支付矩阵无鞍点，则需要选择混合对策。我们回过头再看例9.1（“石头--剪子--布”），对于支付矩阵,有没有纯最优策略。因此无法用定理9.1来确定最优策略。在这种情况下，只能求相应的混合策略。类似于纯策略，混合策略有如下定义和定理。定义9.3设有矩阵对策G＝｛S1，S2，C｝称分别为局中人A和B的混合策略。称(x,y)(xS1*,yS2*)为一个混合局，称为局中人A的支付函数（赢得函数）。

8、定义9.4设G*＝｛S1*，S2*，C｝是G＝｛S1，S2，C｝的