《优化建模与lingo第09章》由会员分享，可在线阅读，更多相关《优化建模与lingo第09章（74页珍藏版）》请在金锄头文库上搜索。
1、优化建模与LINDO/LINGO软件 第 9 章 对 策 论,原书相关信息 谢金星, 薛毅编著, 清华大学出版社, 2005年7月第1版. http:/ 2.二人非常数和对策 3.n人合作对策,第一节 二人常数和对策,对策模型和算法的重要意义,我们不就对策论模型全面的讨论，而是只介绍一些对策论模型的基本概念。重点介绍如何利用LINGO软件去解对策论模型中的有关问题。为了更好地理解LINGO软件的编程过程。,对策论（Game Theory）又称为博弈论，是研究带有竞争与对抗问题的理论与方法。对策论是现代数学的一个重要分支，也是运筹学的一个重要学科。对策论目前已在市场决策中有着广泛的应用。,1.1
2、 二人零和对策,1 二人常数和对策模型,二人零和对策是最基本的对策形式，先用一个例子来说明。,例9.1 甲、乙两名儿童玩“石头-剪子-布”的游戏。石头胜剪子，剪子胜布，布胜石头。那么，甲、乙儿童如何做，使自己获胜的可能最大？,在对策论中，应有以下要素：,(1) 局中人。是指参与对抗的各方，可以是一个人，也可以是一个集团。在例1.1的甲、乙两名儿童就是局中人。,(2) 策略。是指局中人所拥有的对付其他局中人的手段、方案的集合。如例1.1中共有石头、剪子、布三种策略。,(3) 支付函数（或收益函数）。是指一局对策后各局中人的得与失，通常用正数字表示局中人的得，用负数字表示局中人的失。在例1.1的局
3、中人甲的支付函数如表所示。,例1.1 “石头-剪子-布”中儿童甲的支付函数,当局中人得失总和为零时，称这类对策为零和对策；否则称为非零和对策。,当局中人只有两个，且对策得失总和为零，则称为二人零和对策，若总得失总和为常数，则称为二人常数和对策，若得失总和是非常数的，则称为二人非常数和对策。,若二人对策双方的得失是用矩阵形式表示，则称支付函数为支付矩阵，相应的对策称为矩阵对策。通常，支付矩阵表示局中人A的支付函数。,鞍点对策是对策的最基本策略，为更好地理解鞍点对策，先看一个简单的例子。,1. 对策的基本策略-鞍点对策,例9.2设A、B两人对策，各自拥有三个策略： a1, a2, a3和b1, b
4、2, b3, 局中人A的支付（收益） 矩阵由表1.2所示。试求A、B各自的最优策略。,问题分析： 从直观来看，局中人A应该出策略a1, 因为这样选择，他有可能得到9. 但局中人B看到了这一点，他出策略b1，这样局中人A不能得到9，而只能得到1. 因此，局中人A也充分认识到这一点，他应当出策略a3, 这样做，就有可能得到8，而这种情况下局中人B，就要出策略b3，局中人A也只能得到2.,这样做下来，局中人A只能选择策略a2, 而局中人B也只能选择策略b2，大家达到平衡，最后局中人A赢得的值为5，局中人B输掉的值为5.,从上面的分析可以看出，无论局中人A选择什么策略，他赢得的值总是小于等于5，而无论
5、局中人B选择什么策略，他输掉的值总是大于等于5，5就是支付矩阵的鞍点。,现讨论一般情况。假设局中人A的支付矩阵由表1.3所示。,其中局中人A有m个策略1 , , m, 局中人B有n个策略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在纯策略
6、下的解（或平衡局势），称 i*和 j*分别为局中人A、B的最优纯策略。,定理9.1 矩阵对策G=S1, S2, C在纯策略意义下有解的充分必要条件是：存在纯局势( i*, j*)使得,定义9.2,当矩阵对策的最优解不唯一时，有如下定理：,定理9.2,定理9.3,2. 无鞍点的对策策略-混合对策 如果支付矩阵有鞍点，选择鞍点对策是最优的对策策略，如果支付矩阵无鞍点，则需要选择混合对策。 我们回过头再看例9.1（“石头-剪子-布”），对于支付矩阵, 有,没有纯最优策略。因此无法用定理9.1来确定最优策略。在这种情况下，只能求相应的混合策略。类似于纯策略，混合策略有如下定义和定理。,定义9.3,设有
7、矩阵对策 GS1，S2，C称,分别为局中人A和B的混合策略。 称(x,y)(xS1*,yS2*)为一个混合局， 称 为局中人A的支付函数（赢得函数）。,定义9.4,设G*S1*，S2*，C是 GS1，S2，C的混合扩充，若,则称vG为对策G*的值。称使式(7)成立混合局势(x*, y*)为G在混合策略下的解，称x*和y*分别为局中人A和B的最优混合策略。,定理9.4,矩阵对策 GS1，S2，C在混合策略意义下有解的充分必要条件是：存在 (xS1*,yS2*)使(x*,y*)为函数E(x,y)的一个鞍点，即,3. 混合对策求解方法,通常用线性规划方法求混合策略的解。设 局中人A分别以x1,x2,
8、 ,xm 的概率混合使用他的m种策略，局中人B分 别以y1,y2, ,ym 的概率混合使用他的n种策略。,当A采用混合策略，B分别采用纯策略bj(j=1,2, ,n), A的赢得分别为 依据最大最小原则，应有,其中vA是局中人A的赢得值。,将问题（9）写成线性规划问题,也就是说，线性规划问题(10) (13)的解就是局中人A采用混合策略的解。类似可求局中人B的最优策略的解。,例9.3 用线性规划方法求解例1的 最优混合策略。,按照线性规划（10）（13）写出相应的LINGO程序，程序名：exam0903a.lg4MODEL: 1sets: 2 playerA/13/: x; 3 playerB
9、/13/; 4 game(playerA,playerB) : C; 5endsets,6data: 7 C = 0 1 -1 8 -1 0 1 9 1 -1 0; 10enddata 11max=v_A; 12free(v_A); 13for(playerB(j): 14 sum(playerA(i) : C(i,j)*x(i)=v_A); 15sum(playerA : x)=1; END,得到最优解（只保留相关部分）,Global optimal solution found at iteration: 3 Objective value: 0.000000 Variable Value
10、 Reduced Cost V_A 0.000000 0.000000 X( 1) 0.3333333 0.000000 X( 2) 0.3333333 0.000000 X( 3) 0.3333333 0.000000,即儿童甲以1/3的概率出石头、剪子、布中每种策略的一种，其赢得值为0. 用线性规划求出儿童乙有同样的结论。 计算到此，读者可能会产生一个问题：一个具有鞍点的对策问题，如果采用线性规划方法求解，将会出现什么情况？,例9.4用线性规划方法求解例2,解： 写出LINGO程序，程序名：exam0904.lg4,MODEL: 1sets: 2 playerA/13/: x; 3 pla
11、yerB/13/; 4 game(playerA,playerB) : C; 5endsets 6data: 7 C = 1 3 9,8 6 5 7 9 8 4 2; 10enddata 11max=v_A; 12free(v_A); 13for(playerB(j): 14 sum(playerA(i) : C(i,j)*x(i)=v_A); 15sum(playerA : x)=1; END,计算结果为（保留有效部分） Global optimal solution found at iteration: 0 Objective value: 5.000000 Variable Value
12、 Reduced Cost V_A 5.000000 0.000000 X( 1) 0.000000 2.000000 X( 2) 1.000000 0.000000 X( 3) 0.000000 1.000000,由结果可以看到，局中人A仍然选择纯策略。对局中人B的计算也会出现同样的情况。 从例9.3和例9.4可以看出，无论矩阵对策有无鞍点，我们均可以采用线性规划的方法求其对策，只不过具有鞍点的对策可以有更简单的算法罢了。,1.2 二人常数和对策,所谓常数和对策是指局中人A和局中人B所赢得的值之和为一常数. 显然，二人零和对策是二人常数和的特例，即常数为零。 对于二人常数和对策，有纯策略对策
13、和混合策略对策。其求解方法基本上是相同的。,1. 鞍点对策 对于二人常数和对策，仍然有鞍点对策，其求解方法与二人零和对策相同。,例9.4,在晚8点至9点这个时段，两家电视台在竞争100万电视观众收看自己的电视节目，并且电视台必须实时公布自己在下一时段的展播内容。电视台1可能选择的展播方式及可能得到的观众如表所示。,解：事实上，对方得到的，就是自己失去的，完全利用二人零和的方法确定最优纯策略，即 因此，电视台1选择播放连续剧，赢得45万观众，电视台2播放西部片，赢得100-45=55万观众。,2. 混合对策 对于常数和对策，也存在混合对策，同样可以采用线性规划方法求解，这里就不举例子了。,2 二
14、人非常数和对策,二人非常数和对策也称为双矩阵对策。在前面介绍的常数和（零和）对策中，均包含两种情况，纯策略和混合策略。对于非常数对策，也包含这两种策略。,1.纯对策问题,例9.6：囚徒的困境 (表9.2.1),例9.6 设有甲、乙两名嫌疑犯因同一桩罪行被捕，由于希望他们坦白并提供对方的犯罪证据，规定如两人均坦白各判刑3年；如上方坦白另一方不坦白，坦白一方从轻释放，不坦白一方判刑10年；如两人均不坦白，由于犯罪事实很多不能成立，只能各判1年，见表9.2.1所示。 试分析甲、乙两犯罪嫌疑人各自采用什么策略使自己的刑期最短。,例9.6给出了典型的二人非常数和对策，每人的收益矩阵是不相同的，因此称为双
15、矩阵对策。 通常规定，双矩阵中，第一个元素是局中人A的赢得值，第二个元素是局中人B的赢得值。 问题分析： 这是一个二人非常数和对策问题。从表面看，两犯罪嫌疑人拒不坦白，只能被判1年徒刑，结果是最好的。 但仔细分析，确无法做到这一点。因为犯罪嫌疑人甲如果采用不坦白策略，他可能被判的刑期为1到10年，而犯罪嫌疑人乙可能判的刑期为0到1年。,而甲选择坦白，他被判的刑期为0到3年，此时，犯罪嫌疑人乙可能判的刑期为3到10年。因此，犯罪嫌疑人甲一定选择坦白。 基于同样的道理，犯罪嫌疑人乙也只能选择坦白。 选择坦白是他们最好的选择，各自被判3年。,事实上，设(cijA, cijB)是甲、乙赢得值，则甲、乙采用的策略是,1. 纯对策问题的基本概念,按照上面的论述，对于一般纯对策问题，局中人A、B的支付（赢得）矩阵由表9.2.2所示。,局中人A、B的支付矩阵,为局中人A的支付（赢得）矩阵， 为局中人B的支付（赢得）矩阵。 因此，矩阵对策记为： G=A,B;S1,S2,CA,CB或G=S1,S2,CA,CB,定义9.5：设G=S1,S2,CA,CB是一双矩阵对策，若等式,成立，则记vA= ，并称vA为局中人A的赢得值，
