优化建模与lingo第09章

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

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

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

4、基本策略-鞍点对策鞍点对策是对策的最基本策略，为更好地理解鞍点对策，先看一个简单的例子。例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, 这样做，就有可能得到8，而这种情况下局中人B，就要出策略b3

5、，局中人A也只能得到2.这样做下来，局中人A只能选择策略a2, 而局中人B也只能选择策略b2，大家达到平衡，最后局中人A 赢得的值为5，局中人B输掉的值为5. 优化建模从上面的分析可以看出，无论局中人A选择什么 策略，他赢得的值总是小于等于5，而无论局中人B选择什么策略，他输掉的值总是大于等于5，5就是支付矩阵的鞍点。现讨论一般情况。假设局中人A的支付矩阵由表1.3所示。b1b2bna1C11C12Cn1a2C21C22Cn2amCm1Cm2Cmn 优化建模其中局中人A有m个策略1 , , m, 局中人B有n个策略1, , n, 分别记为S1=1 , , m, S2=1, , nC为局中人A的

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

7、定义9.2 ci* j ,i = 1,2,L, m,j = 1,2,L, n.设f ( x, y)为一个定义在x A及y B上的实值函数若存在x* A, y* B, 使得f ( x, y* ) f ( x* , y* ) f ( x* , y), x A, y B则称( x* , y* )为函数f ( x, y)的一个鞍点、 优化建模当矩阵对策的最优解不唯一时，有如下定理：定理9.2若(ai1 ,b j1 )和(ai 2 ,b j 2 )是矩阵对策的两个解，则ci1 j1 = ci 2 j 2 .定理9.3若(ai1 ,b j1 )和(ai 2 ,b j 2 )是矩阵对策的两个解,则(ai1

8、,b j 2 )和(ai 2 ,b j1 )也是解. 优化建模2. 无鞍点的对策策略-混合对策如果支付矩阵有鞍点，选择鞍点对策是最优的对策 策略，如果支付矩阵无鞍点，则需要选择混合对策。我们回过头再看例9.1（“石头-剪子-布”）， 对于支付矩阵, 有max min cij= -1,min max cij= 1ijji没有纯最优策略。因此无法用定理9.1来确定最优策略。在这种情况下，只能求相应的混合策略。 类似于纯策略，混合策略有如下定义和定理。 优化建模定义9.3设有矩阵对策GS1，S2，C称m| xii =1S1= x R= 1, xi 0, i = 1,2,L, m,*m(4)n| yi

9、S2= y R= 1, y j 0, j = 1,2,L, n,*n(5)j =1分别为局中人A和B的混合策略。称(x,y)(xS1*,yS2*)为一个混合局，mnE( x, y) = xT Cy = c称x y(6)ijiji =1j=1为局中人A的支付函数（赢得函数）。 优化建模定义9.4设G*S1*，S2*，C是 GS1，S2， C的混合扩充，若maxminE( x, y) = minmax E( x, y) = vG(7)yS*yS*xS*xS*2211则称vG为对策G*的值。称使式(7)成立混合(x*, y*)为G在混合策略下的解，称x*和y*分别为局中人A和B的最优混合策略。 优化

10、建模定理9.4GS1，S2，C在混合策略意矩阵对策义下有解的充分必要条件是：存在 (xS1*,yS2*)使(x*,y*)为函数E(x,y)的一个鞍点，即E(x, y *) E(x*, y *) E(x*, y),x S * , y S* .(8)12 优化建模3. 混合对策求解方法通常用线性规划方法求混合策略的解。设mi =1局中人A分别以x1,x2, ,xmx= 1, x 0ii的概率混合使用他的m种策略，局中人B分n yij =1别以y1,y2, ,ym= 1, y j 0的概率混合使用他的n种策略。 优化建模当A采用混合策略，B分别采用纯策略m cij xi ( j = 1,2,L, n

11、)i =1bj(j=1,2, ,n), A的赢得分别为依据最大最小原则，应有miji= max minvAcx ,xji =1m xi= 1,(9) i =1 xi 0, i = 1,2,L, m,其中vA是局中人A的赢得值。 优化建模将问题（9）写成线性规划问题maxvA ; cij xi(10)m v A , j = 1,2,L, n,s.t(11)i = jm xi= 1(12)i =1xi 0i = 1,2,L, m.(13)也就是说，线性规划问题(10) (13)的解就是局中人A采用混合策略的解。类似可求局中 人B的最优策略的解。 优化建模用线性规划方法求解例1的最优混合策略。例9.

12、3按照线性规划（10）（13）写出相应的LINGO程序，程序名：exam0903a.lg4MODEL:1sets:234playerA/1.3/: x;playerB/1.3/; game(playerA,playerB) : C;5endsets 优化建模6data:789C = 01 -110;-101 -110enddata 11max=v_A; 12free(v_A);13for(playerB(j):14sum(playerA(i) : C(i,j)*x(i)=v_A);15sum(playerA : x)=1;END 优化建模得到最优解（只保留相关部分）Global optimal

13、 solution found at iteration:3Objective value:VariableV_A X( 1)X( 2)X( 3)0.000000Reduced Cost 0.0000000.0000000.0000000.000000Value 0.0000000.33333330.33333330.3333333 优化建模即儿童甲以1/3的概率出石头、剪子、布中每种策略的一种，其赢得值为0.用线性规划求出儿童乙有同样的结论。计算到此，读者可能会产生一个问题：一个具有鞍点的对策问题，如果采用线性规划方法求解， 将会出现什么情况？ 优化建模例9.4用线性规划方法求解例2 解：

14、写出LINGO程序，程序名：exam0904.lg4MODEL:1 sets:2 playerA/1.3/: x;3 playerB/1.3/;4 game(playerA,playerB) : C; 5endsets6data:7C = 139 优化建模86579842;10enddata 11max=v_A; 12free(v_A); 13for(playerB(j):14 sum(playerA(i) : C(i,j)*x(i)=v_A);15 sum(playerA : x)=1; END 优化建模计算结果为（保留有效部分）Global optimal solution found a

15、t iteration:0Objective value:VariableV_A X( 1)X( 2)X( 3)5.000000Reduced Cost 0.0000002.0000000.0000001.000000Value 5.0000000.0000001.0000000.000000 优化建模由结果可以看到，局中人A仍然选择纯策略。对局中人B的计算也会出现同样的情况。从例9.3和例9.4可以看出，无论矩阵对策有无鞍点，我们均可以采用线性规划的方法求其对策，只不过具有鞍点的对策可以有更简单的算法罢了。 优化建模1.2 二人常数和对策所谓常数和对策是指局中人A和局中人B所赢得的值之和为一

16、常数. 显然，二人零和对策是二人常数和的特例，即常数为零。对于二人常数和对策，有纯策略对策和混合策略对策。其求解方法基本上是相同的。1. 鞍点对策对于二人常数和对策，仍然有鞍点对策，其求解方法与二人零和对策相同。 优化建模例9.4在晚8点至9点这个时段，两家电视台在竞争100万电视观众收看自己的电视节目，并且电视台必须实时公布自己在下一时段的展播内容。电 视台1可能选择的展播方式及可能得到的观众如表所示。电视台min西部片连续剧喜剧片电视台1西部片35156015连续剧45585045喜剧片38147014max455870 优化建模解：事实上，对方得到的，就是自己失去的，完全利用二人零和的方

17、法确定最优纯策略，即maxminc A = minmax c A = 45ijijjjii因此，电视台1选择播放连续剧，赢得45万观众，电视台2播放西部片，赢得100-45=55万观 众。2. 混合对策对于常数和对策，也存在混合对策，同样可以采用线性规划方法求解，这里就不举例子了。 优化建模2二人非常数和对策二人非常数和对策也称为双矩阵对策。在前面介绍的常数和（零和）对策中，均包含两种情 况，纯策略和混合策略。对于非常数对策，也包 含这两种策略。1.纯对策问题例9.6：(表9.2.1)徒的困境乙坦白不坦白甲坦白（-3，-3）(0,-10)不坦白（-10，0）(-1,-1) 优化建模例9.6设有

18、甲、乙两名嫌疑犯因同一桩罪行，由于希望他们坦白并提供对方的犯罪证据，规定如两人均坦白各判刑3年；如上方坦白另一方不坦白， 坦白一方从轻释放，不坦白一方判刑10年；如两人均不坦白，由于犯罪事实很多不能成立，只能各判1年，见表9.2.1所示。试分析甲、乙两犯罪嫌疑人各自采用什么策略使自己的刑期最短。 优化建模例9.6给出了典型的二人非常数和对策，每人的收益矩阵是不相同的，因此称为双矩阵对策。通常规定，双矩阵中，第一个元素是局中人A的 赢得值，第二个元素是局中人B的赢得值。问题分析： 这是一个二人非常数和对策问题。但仔细分析，确无法做到这一点。因为犯罪嫌疑人甲如果采用不坦白策略，他可能被判的刑期为1

19、到10年，而犯罪嫌疑人乙可能判的刑期为0到1年。 优化建模而甲选择坦白，他被判的刑期为0到3年，此时，犯罪嫌疑人乙可能判的刑期为3到10年。 因此，犯罪嫌疑人甲一定选择坦白。基于同样的道理，犯罪嫌疑人乙也只能选择坦白。选择坦白是他们最好的选择，各自被判3年。 优化建模事实上，设(cijA, cijB)是甲、乙赢得值，则甲、乙采用的策略是- 3 = min max c A= c Aij11ji- 3 = min max c B= c Bij11ij1. 纯对策问题的基本概念按照上面的论述，对于一般纯对策问题，局中人A、B的支付（赢得）矩阵由表9.2.2所示。 优化建模局中人A、B的支付矩阵12n

20、1(c A , c B )1111(c A , c B )1212(c A , cB )1n1n2(c A , c B )2121(c A , c B )2222(c A , cB )2n2nm(c A , cB)m1m1(c A, cB)m 2m 2(c A, cB)mnmn 优化建模()=cC AA为局中人A的支付（赢得）矩阵，ijmn()=cCBB为局中人B的支付（赢得）矩阵。ijmn因此，矩阵对策记为：G=A,B;S1,S2,CA,CB或G=S1,S2,CA,CB 优化建模定义9.5：设G=S1,S2,CA,CB是一双矩阵对策，若等式= minmax c A ,cB= minmax c

21、Bc Ai* j*iji* j*ijjiijc A成立，则记v=，并称v为局中人i* j*AA，并称vB为局中人BBA的赢得值，记v=cBi* j*的赢得值，称（i*, j*)为G在纯策略下的解（或Nash平衡点），称i*和 j*分别为局中人A、B的最优纯策略。 优化建模2. 纯对策问题的求解方法实际上，定义9.5也同时给出了纯对策问题的求解方法。因此，对于例9.6, (1,0),(1,0)是Nash平衡点，也就是说，坦白他们的最佳策略。再看一个例子。例：9.7（夫妻周末安排问题）一对夫妻，商量周末安排。丈夫喜欢看足球，妻子喜欢听音乐会。他们的赢得值由表9.7所示。请为这对夫妻设计最好的度 周

22、末的方案。 优化建模解：由定义9.5可知，对于策略 (1,0),(1,0)或策略(0,1),(0,1) 均是Nash平衡点，也就是最优解，即他们选择是共同看足球，或共同听音乐会。表中带有下划线是他们采用策略的赢得值。妻足球音乐会夫足球(3,1)(-1,-1)音乐会(-1,-1)(1,3) 优化建模2. 混合对策问题如果不存在使式(18)成立的对策，则需要求混合对策。类似于二人常数和对策情况，需要给 出混合对策的最优解。1. 混合对策问题的基本概念定义9.6 在对策G=S1, S2, CA, CB中，若存在策略对x , y B 使得 xT C A y xT C A y, x A,(19)xCy

23、xCy, y BTBTB 优化建模为G的一个非合作平衡点。记(x, y)则称v A= xCy, vTAB= xT C B y则称vA, vB分别为局中人A、B的赢得值。 对于混合对策问题有如下定理定理9.5 每个双矩阵对策至少存在一个非合作平衡点。定理9.6混合策略 (x, y) 为对策G=S1, S2, CA, CB的平衡点的充分必要条件是：ncy j xCy,i = 1,2,L, m,ATAij j =1(20)mcx xT C B yj = 1,2,L, n,Biji i =1 优化建模2. 混合对策问题的求解方法由定义9.6可知，求解混合对策就是求非合作对策的平衡点。进一步，由定理9.

24、6得到，求解非合作对策的平衡点，就是求解满足不等式约束(20) 的可行点。因此，混合对策问题的求解问题就转化为求不等式约束(20)的可行点，而LINGO软件可以很容易做到这一点。 优化建模例9.8有甲、乙两支游泳队举行包括三个项目的对抗赛。这两支游泳队各有一名健将级运动员（甲队为李，乙队为王），在三个项目中成绩很突出。但规则准许他们每个人分别只能参加两项比赛，而每队的其他两名运动员则可参加全部三项比赛。各运动员的成绩如表9-8所示。甲队乙队赵钱李王张孙蝶泳54.756.459.8仰泳62.263.458.256.559.761.5蛙泳69.170.565.367.868

25、.471.3 优化建模解： 分别用甲1、甲2和甲3表示甲队中李姓健将不参加蝶泳、仰泳、蛙泳比赛的策略，分别用乙1、乙2和 乙3表示乙队中王姓健将不参加蝶泳、仰泳、蛙泳比赛的策略。当甲队采用策略甲1，乙队采用策略乙1时， 在100米蝶泳中，甲队中赵获第一、钱获第三得6分， 乙队中张获第二，得3分；在100米仰泳中，甲队中李 获第二，得3分， 乙队中王获第一，张获第三，得6分； 在100米蛙泳中，甲队中李获第一，得5分，乙队中王 获第二、张获第三，得4分。也就是说，对应于策略（甲1，乙1），甲、乙两队各自的得分为(14,13). 表9-9中给出了在全部策略下各队的得分。 优化建模表9-9甲、乙两队

26、采用不同策略的得分按照定理9.6，求最优混合策略，就是求不等式约束(20)的可行解. 写出相应的LINGO程序，程序名：exam0908.lg4乙1乙2乙3甲1(14,13)(13,14)(12,15)甲2(13,14)(12,15)(12,15)甲3(12,15)(12,15)(13,14) 优化建模MODEL:1sets:234optA/1.3/: x;optB/1.3/: y; AXB(optA,optB) : Ca, Cb;5endsets6data:78Ca = 14 13 1213 12 12 优化建模910111212 12 13;Cb = 13 14 1514 15 1515

27、15 14;13 enddata14 Va=sum(AXB(i,j): Ca(i,j)*x(i)*y(j);15 Vb=sum(AXB(i,j): Cb(i,j)*x(i)*y(j); 16for(optA(i): 优化建模17sum(optB(j) : Ca(i,j)*y(j)=Va);18for(optB(j):19sum(optA(i) : Cb(i,j)*x(i)=Vb);20sum(optA : x)=1; sum(optB : y)=1; 21free(Va); free(Vb);END用LINGO软件求解，得到 优化建模Feasible solution found at ite

28、ration:3VariableVA VB X( 1)X( 2)X( 3)Y( 1)Y( 2)Y( 3)Value 12.5000014.500000.50000000.0000000.50000000.0000000.50000000.5000000 优化建模 即甲队采用的策略是甲1、甲3方案各占50%,乙队采用的策略是乙2、乙3方案各占50%, 甲队的平均得分为12.5分，乙队的平均得分为14.5分。 当纯对策的解不唯一时，也存在混合对策的平衡点。 优化建模例9.9 用混合对策方法求解例9.7。解： 写出求不等式(20)的LINGO程序，程序名：ex0909.lg4“ MODEL:1set

29、s:234optA/1.2/: x;optB/1.2/: y; AXB(optA,optB) : Ca, Cb;5endsets 优化建模6data:78Ca = 3 -1 -1 1;Cb = 1 -1 -1 3;9enddata10 Va=sum(AXB(i,j): Ca(i,j)*x(i)*y(j);11 Vb=sum(AXB(i,j): Cb(i,j)*x(i)*y(j); 12for(optA(i):13sum(optB(j) : Ca(i,j)*y(j)=Va);14for(optB(j): 优化建模15sum(optA(i) : Cb(i,j)*x(i)=Vb);16sum(opt

30、A : x)=1; sum(optB : y)=1; 17free(Va);free(Vb);END计算得到混合对策的平衡点(2/3,1/3),(1/3,2/3) 各自的赢得值为1/3.从上述分析来看，二人常数和对策是非常数和 对策的特例，因此也可以用求解非常数和对策的方法求解常数和对策。 优化建模例9.10用求解非常数和对策的方法求解例9.5 解：写出相应的LINGO程序，程序名：exam0910.lg4 MODEL:1sets:234optA/1.3/: x;optB/1.3/: y; AXB(optA,optB) : Ca, Cb;5endsets 优化建模6data:789101112

31、Ca = 351550604538581470;8550Cb = 65405562428630;13enddata 优化建模14 Va=sum(AXB(i,j): Ca(i,j)*x(i)*y(j);15 Vb=sum(AXB(i,j): Cb(i,j)*x(i)*y(j); 16for(optA(i):17sum(optB(j) : Ca(i,j)*y(j)=Va);18for(optB(j):19sum(optA(i) : Cb(i,j)*x(i)=Vb);20sum(optA : x)=1; sum(optB : y)=1; 21free(Va);free(Vb);END 优化建模计算结

32、果如下（只保留有效部分）Feasible solution found at iteration:12VariableVA VB X( 1)X( 2)X( 3)Y( 1)Y( 2)Y( 3)Value 45.0000055.000000.0000001.0000000.0000001.0000000.0000000.000000 优化建模即局中人A采用第二种策略，赢得45万观众，局中人B采用第一种策略，赢得55万观众， 与前面计算的结果相同。 优化建模3 n人合作对策初步n人合作对策在理论上较为复杂，这里只用一些例子简单介绍n人合作对策的基本思想， 和用LINGO软件求解对策的方法。例9.11

33、甲有一匹马，对他自己来说，其价值为0, 而对乙和丙（买主）来说分别价值90和100个 货币单位。试建立3人合作对策，使得每人的利益最大。 优化建模解：设甲、乙、丙三人的价值分别为x1, x2, x3, 因此对于每个人来说，其价值为0，即v1=v2=v3=0如果甲与乙合作，其价值为90，甲与丙合作， 其价值为100，若乙与丙合作，其价值仍为0，因此有v1,2=90, v1,3=100, v2,3=0.但三人合作的总价值为100，即v 1, 2, 3=100.建立相应的数学规划问题 优化建模maxs.t.z;z xi , x1 + x2 x1 + x3 x2 + x3x1 + x2i = 1,2,3, 90 100 0+ x3 100x1 0, i = 1,2,3, 优化建模写出相应的LINGO程序，程序名：exam0909.lg4MODEL:1sets:234condition/1.3/: b;players/1.3/: x;constraint(condition,players) : A;5endsets6data:7A = 110 优化建模891011100111;b= 90 100 0;total = 100;12enddata 13max=z;14 for(players: z=b(i);17sum(players: x)=tot