优化建模与LINGO第09章

《优化建模与LINGO第09章》由会员分享，可在线阅读，更多相关《优化建模与LINGO第09章（74页珍藏版）》请在装配图网上搜索。

1、 优优 化化 建建 模模优化建模与优化建模与LINDO/LINGO软件软件第第9章对策论章对策论原书相关信息原书相关信息谢金星谢金星,薛毅编著薛毅编著,清华大学出版社清华大学出版社,2005年年7月第月第1版版.http:/ 优优 化化 建建 模模内容提要内容提要1.二人常数和对策二人常数和对策2.二人非常数和对策二人非常数和对策3.n人合作对策人合作对策 优优 化化 建建 模模第一节二人常数和对策第一节二人常数和对策 优优 化化 建建 模模对策模型和算法的重要意义对策模型和算法的重要意义我们不就对策论模型全面的讨论，而是只介绍一我们不就对策论模型全面的讨论，而是只介绍一些对策论模型的基本概念

2、。重点介绍如何利用些对策论模型的基本概念。重点介绍如何利用LINGO软件去解对策论模型中的有关问题。为了更软件去解对策论模型中的有关问题。为了更好地理解好地理解LINGO软件的编程过程。软件的编程过程。对策论（对策论（Game TheoryGame Theory）又称为博弈论，是研究）又称为博弈论，是研究带有竞争与对抗问题的理论与方法。对策论是现代数带有竞争与对抗问题的理论与方法。对策论是现代数学的一个重要分支，也是运筹学的一个重要学科。对学的一个重要分支，也是运筹学的一个重要学科。对策论目前已在市场决策中有着广泛的应用。策论目前已在市场决策中有着广泛的应用。优优 化化 建建 模模1.11.1

3、二人零和对策二人零和对策1 1二人常数和对策模型二人常数和对策模型二人零和对策是最基本的对策形式，先用一二人零和对策是最基本的对策形式，先用一个例子来说明。个例子来说明。例例9.1 甲、乙两名儿童玩甲、乙两名儿童玩“石头石头-剪子剪子-布布”的游的游戏。石头胜剪子，剪子胜布，布胜石头。那么，戏。石头胜剪子，剪子胜布，布胜石头。那么，甲、乙儿童如何做，使自己获胜的可能最大？甲、乙儿童如何做，使自己获胜的可能最大？优优 化化 建建 模模在对策论中，应有以下要素：在对策论中，应有以下要素：(1)局中人。局中人。是指参与对抗的各方，可以是一个人，是指参与对抗的各方，可以是一个人，也可以是一个集团。在例

4、也可以是一个集团。在例1.1的甲、乙两名儿童就的甲、乙两名儿童就是局中人。是局中人。(2)策略。策略。是指局中人所拥有的对付其他局中人的是指局中人所拥有的对付其他局中人的手段、方案的集合。如例手段、方案的集合。如例1.1中共有石头、剪子、中共有石头、剪子、布三种策略。布三种策略。(3)支付函数（或收益函数）。支付函数（或收益函数）。是指一局对策后各局是指一局对策后各局中人的得与失，通常用正数字表示局中人的得，用中人的得与失，通常用正数字表示局中人的得，用负数字表示局中人的失。在例负数字表示局中人的失。在例1.1的局中人甲的支付的局中人甲的支付函数如表所示。函数如表所示。优优 化化 建建 模模乙

5、乙石头石头剪子剪子布布甲甲石头石头01-1剪子剪子-101布布1-10例例1.1“石头石头-剪子剪子-布布”中儿童甲的支付函数中儿童甲的支付函数 优优 化化 建建 模模当局中人得失总和为零时，称这类对策为当局中人得失总和为零时，称这类对策为零和对策零和对策；否则称为否则称为非零和对策非零和对策。当局中人只有两个，且对策得失总和为零，则称为当局中人只有两个，且对策得失总和为零，则称为二人零和对策，若总得失总和为常数，则称为二人零和对策，若总得失总和为常数，则称为二人常二人常数和对策数和对策，若得失总和是非常数的，则称为，若得失总和是非常数的，则称为二人非常二人非常数和对策数和对策。若二人对策双方

6、的得失是用矩阵形式表示，则称支若二人对策双方的得失是用矩阵形式表示，则称支付函数为支付矩阵，相应的对策称为付函数为支付矩阵，相应的对策称为矩阵对策矩阵对策。通。通常，支付矩阵表示局中人常，支付矩阵表示局中人A的支付函数。的支付函数。优优 化化 建建 模模鞍点对策是对策的最基本策略，为更好地鞍点对策是对策的最基本策略，为更好地理解鞍点对策，先看一个简单的例子。理解鞍点对策，先看一个简单的例子。1.对策的基本策略对策的基本策略-鞍点对策鞍点对策例例9.2设设A、B两人对策，各自拥有三个策略：两人对策，各自拥有三个策略：a1,a2,a3和和b1,b2,b3,局中人局中人A的支付（收益）的支付（收益）

7、矩阵由表矩阵由表1.2所示。试求所示。试求A、B各自的最优策略。各自的最优策略。b1b2b3mina11391a26575a38422max859 优优 化化 建建 模模问题分析：问题分析：从直观来看，局中人从直观来看，局中人A应该出策略应该出策略a1,因为这样因为这样选择，他有可能得到选择，他有可能得到9.但局中人但局中人B看到了这一点，他看到了这一点，他出策略出策略b1，这样局中人，这样局中人A不能得到不能得到9，而只能得到，而只能得到1.因因此，局中人此，局中人A也充分认识到这一点，他应当出策略也充分认识到这一点，他应当出策略a3,这样做，就有可能得到这样做，就有可能得到8，而这种情况下

8、局中人，而这种情况下局中人B，就，就要出策略要出策略b3，局中人，局中人A也只能得到也只能得到2.这样做下来，局中人这样做下来，局中人A只能选择策略只能选择策略a2,而局中而局中人人B也只能选择策略也只能选择策略b2，大家达到平衡，最后局中人，大家达到平衡，最后局中人A赢得的值为赢得的值为5，局中人，局中人B输掉的值为输掉的值为5.优优 化化 建建 模模从上面的分析可以看出，无论局中人从上面的分析可以看出，无论局中人A选择什么选择什么策略，他赢得的值总是小于等于策略，他赢得的值总是小于等于5，而无论局中人，而无论局中人B选选择什么策略，他输掉的值总是大于等于择什么策略，他输掉的值总是大于等于5

9、，5就是支付就是支付矩阵的矩阵的鞍点。鞍点。现讨论一般情况。假设局中人现讨论一般情况。假设局中人A的支付矩阵由的支付矩阵由表表1.3所示。所示。12n1C11C12Cn12C21C22Cn2mCm1Cm2Cmn 优优 化化 建建 模模其中局中人其中局中人A有有m个策略个策略1,m,局中人局中人B有有n个策略个策略1,n,分别记为分别记为S1=1,m,S2=1,nC为局中人为局中人A的支付矩阵，而的支付矩阵，而-C为局中人为局中人B的的支付矩阵。因此，矩阵对策记为支付矩阵。因此，矩阵对策记为G=A,B;S1,S2,C,或或G=S1,S2,C对于一般矩阵对策，有如下定义和定理。对于一般矩阵对策，有

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

11、局势(i*,j*)使得使得.,2,1,2,1,*njmicccjijiij 定义定义9.2的一个鞍点、的一个鞍点、为函数为函数则称则称使得使得若存在若存在上的实值函数，上的实值函数，及及为一个定义在为一个定义在设设),(),(,),(),(),(,),(*yxfyxByAxyxfyxfyxfByAxByAxyxf 优优 化化 建建 模模当矩阵对策的最优解不唯一时，有如下定理：当矩阵对策的最优解不唯一时，有如下定理：定理定理9.2定理定理9.3.),(),(22112211jijijijicc 则则是矩阵对策的两个解，是矩阵对策的两个解，和和若若.),(),(,),(),(12212211也是解

12、也是解和和则则是矩阵对策的两个解是矩阵对策的两个解和和若若jijijiji 优优 化化 建建 模模2.无鞍点的对策策略无鞍点的对策策略-混合对策混合对策 如果支付矩阵有鞍点，选择鞍点对策是最优的对策如果支付矩阵有鞍点，选择鞍点对策是最优的对策策略，如果支付矩阵无鞍点，则需要选择混合对策。策略，如果支付矩阵无鞍点，则需要选择混合对策。我们回过头再看例我们回过头再看例9.1（“石头石头-剪子剪子-布布”），），对于支付矩阵对于支付矩阵,有有1maxmin,1minmax ijijijjicc没有纯最优策略。因此无法用定理没有纯最优策略。因此无法用定理9.1来确定最来确定最优策略。在这种情况下，只能

13、求相应的混合策略。优策略。在这种情况下，只能求相应的混合策略。类似于纯策略，混合策略有如下定义和定理。类似于纯策略，混合策略有如下定义和定理。优优 化化 建建 模模定义定义9.3设有矩阵对策设有矩阵对策GS1，S2，C称称)5(,2,1,0,1|)4(,2,1,0,1|1*21*1 njjinmiiimnjyyRySmixxRxS分别为局中人分别为局中人A和和B的的混合策略。混合策略。称称(x,y)(x S1*,y S2*)为一个为一个混合局混合局，称称为局中人为局中人A的的支付函数支付函数（赢得函数）。（赢得函数）。)6(),(11 minjjiijTyxcCyxyxE 优优 化化 建建 模

14、模定义定义9.4 设设G*S1*，S2*，C是是 GS1，S2，C的混合扩充，若的混合扩充，若)7(),(maxmin),(minmax*1*2*2*1GSxSySySxvyxEyxE 则称则称vG为对策为对策G*的值。称使式的值。称使式(7)成立混合局势成立混合局势(x*,y*)为为G在混合策略下的解，称在混合策略下的解，称x*和和y*分别为分别为局中人局中人A和和B的最优混合策略。的最优混合策略。优优 化化 建建 模模定理定理9.4矩阵对策矩阵对策GS1，S2，C在混合策略意在混合策略意义下有解的充分必要条件是：存在义下有解的充分必要条件是：存在(x S1*,y S2*)使使(x*,y*)

15、为函数为函数E(x,y)的一个鞍点，即的一个鞍点，即 )8(.,*,*,*,*2*1SySxyxEyxEyxE 优优 化化 建建 模模3.混合对策求解方法混合对策求解方法通常用线性规划方法求混合策略的解。设通常用线性规划方法求混合策略的解。设局中人局中人A分别以分别以x1,x2,xm的概率混合使用他的的概率混合使用他的m种策略，局中人种策略，局中人B分分别以别以y1,y2,ym的概率混合使用他的的概率混合使用他的n种策略。种策略。miiixx10,1 njjiyy10,1 优优 化化 建建 模模当当A采用混合策略，采用混合策略，B分别采用纯策略分别采用纯策略bj(j=1,2,n),A的赢得分别

16、为的赢得分别为依据最大最小原则，应有依据最大最小原则，应有 miiijnjxc1),2,1(,2,1,0)9(,1,minmax11mixxxcvimiimiiijjxA其中其中vA是局中人是局中人A的赢得值。的赢得值。优优 化化 建建 模模将问题（将问题（9）写成线性规划问题）写成线性规划问题)13(.,2,10)12(1 )11(,2,1,.)10(;max1mixxnjvxctsvimiimjiAiijA 也就是说，线性规划问题也就是说，线性规划问题(10)(13)的解的解就是局中人就是局中人A采用混合策略的解。类似可求局中采用混合策略的解。类似可求局中人人B的最优策略的解。的最优策略的

17、解。优优 化化 建建 模模例例9.39.3用线性规划方法求解例用线性规划方法求解例1 1的的最优混合策略。最优混合策略。按照线性规划（按照线性规划（10）（）（13）写出相应的）写出相应的LINGO程程序，程序名：序，程序名：exam0903a.lg4MODEL:1sets:2 playerA/1.3/:x;3 playerB/1.3/;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):1

18、4 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 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 优优 化化 建建 模模即儿童甲

19、以即儿童甲以1/3的概率出石头、剪子、布中每的概率出石头、剪子、布中每种策略的一种，其赢得值为种策略的一种，其赢得值为0.用线性规划求出儿童乙有同样的结论。用线性规划求出儿童乙有同样的结论。计算到此，读者可能会产生一个问题：一个计算到此，读者可能会产生一个问题：一个具有鞍点的对策问题，如果采用线性规划方法求解，具有鞍点的对策问题，如果采用线性规划方法求解，将会出现什么情况？将会出现什么情况？优优 化化 建建 模模例例9.49.4用线性规划方法求解例用线性规划方法求解例2 2解：解：写出写出LINGOLINGO程序，程序名：程序，程序名：exam0904.lg4exam0904.lg4MODEL

20、:1sets:2 playerA/1.3/:x;3 playerB/1.3/;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 itera

21、tion:0 Objective value:5.000000 Variable Value 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可以看出，无论矩阵对策有可以看出，无论矩阵对策有无鞍点，我们均可以采用线性规划的方法求其对无鞍点，我们均可

22、以采用线性规划的方法求其对策，只不过具有鞍点的对策可以有更简单的算法策，只不过具有鞍点的对策可以有更简单的算法罢了。罢了。优优 化化 建建 模模1.2 二人常数和对策二人常数和对策所谓常数和对策是指局中人所谓常数和对策是指局中人A和局中人和局中人B所所赢得的值之和为一常数赢得的值之和为一常数.显然，二人零和对策是显然，二人零和对策是二人常数和的特例，即常数为零。二人常数和的特例，即常数为零。对于二人常数和对策，有纯策略对策和混合对于二人常数和对策，有纯策略对策和混合策略对策。其求解方法基本上是相同的。策略对策。其求解方法基本上是相同的。1.鞍点对策鞍点对策对于二人常数和对策，仍然有鞍点对策，对

23、于二人常数和对策，仍然有鞍点对策，其求解方法与二人零和对策相同。其求解方法与二人零和对策相同。优优 化化 建建 模模例例9.4在晚在晚8点至点至9点这个时段，两家电视台在竞争点这个时段，两家电视台在竞争100万电视观众收看自己的电视节目，并且电视万电视观众收看自己的电视节目，并且电视台必须实时公布自己在下一时段的展播内容。电台必须实时公布自己在下一时段的展播内容。电视台视台1可能选择的展播方式及可能得到的观众如可能选择的展播方式及可能得到的观众如表所示。表所示。电视台电视台min西部片西部片 连续剧连续剧 喜剧片喜剧片电视台电视台1西部片西部片35156015连续剧连续剧45585045喜剧片

24、喜剧片38147014max455870 优优 化化 建建 模模解：事实上，对方得到的，就是自己失去的，完解：事实上，对方得到的，就是自己失去的，完全利用二人零和的方法确定最优纯策略，即全利用二人零和的方法确定最优纯策略，即因此，电视台因此，电视台1选择播放连续剧，赢得选择播放连续剧，赢得45万观万观众，电视台众，电视台2播放西部片，赢得播放西部片，赢得100-45=55万观万观众。众。45maxminminmax AijijAijjicc2.混合对策混合对策对于常数和对策，也存在混合对策，同样可对于常数和对策，也存在混合对策，同样可以采用线性规划方法求解，这里就不举例子了。以采用线性规划方法

25、求解，这里就不举例子了。优优 化化 建建 模模2 二人非常数和对策二人非常数和对策二人非常数和对策也称为双矩阵对策。在前二人非常数和对策也称为双矩阵对策。在前面介绍的常数和（零和）对策中，均包含两种情面介绍的常数和（零和）对策中，均包含两种情况，纯策略和混合策略。对于非常数对策，也包况，纯策略和混合策略。对于非常数对策，也包含这两种策略。含这两种策略。1.纯对策问题纯对策问题例例9.6：囚徒的困境：囚徒的困境 (表表9.2.1)乙乙坦白坦白不坦白不坦白甲甲坦白坦白（-3，-3）(0,-10)不坦白不坦白（-10，0）(-1,-1)优优 化化 建建 模模例例9.6设有甲、乙两名嫌疑犯因同一桩罪行

26、被捕，设有甲、乙两名嫌疑犯因同一桩罪行被捕，由于希望他们坦白并提供对方的犯罪证据，规定如由于希望他们坦白并提供对方的犯罪证据，规定如两人均坦白各判刑两人均坦白各判刑3年；如上方坦白另一方不坦白，年；如上方坦白另一方不坦白，坦白一方从轻释放，不坦白一方判刑坦白一方从轻释放，不坦白一方判刑10年；如两人年；如两人均不坦白，由于犯罪事实很多不能成立，只能各判均不坦白，由于犯罪事实很多不能成立，只能各判1年，见表年，见表9.2.1所示。所示。试分析甲、乙两犯罪嫌疑人各自采用什么策试分析甲、乙两犯罪嫌疑人各自采用什么策略使自己的刑期最短。略使自己的刑期最短。优优 化化 建建 模模例例9.6给出了典型的二

27、人非常数和对策，每人的收给出了典型的二人非常数和对策，每人的收益矩阵是不相同的，因此称为双矩阵对策。益矩阵是不相同的，因此称为双矩阵对策。通常规定，双矩阵中，第一个元素是局中人通常规定，双矩阵中，第一个元素是局中人A的的赢得值，第二个元素是局中人赢得值，第二个元素是局中人B的赢得值。的赢得值。问题分析：问题分析：这是一个二人非常数和对策问题。这是一个二人非常数和对策问题。从表面看，两犯罪嫌疑人拒不坦白，只能被判从表面看，两犯罪嫌疑人拒不坦白，只能被判1年徒年徒刑，结果是最好的。刑，结果是最好的。但仔细分析，确无法做到这一点。因为犯罪嫌疑但仔细分析，确无法做到这一点。因为犯罪嫌疑人甲如果采用不坦

28、白策略，他可能被判的刑期为人甲如果采用不坦白策略，他可能被判的刑期为1到到10年，而犯罪嫌疑人乙可能判的刑期为年，而犯罪嫌疑人乙可能判的刑期为0到到1年。年。优优 化化 建建 模模而甲选择坦白，他被判的刑期为而甲选择坦白，他被判的刑期为0到到3年，年，此时，犯罪嫌疑人乙可能判的刑期为此时，犯罪嫌疑人乙可能判的刑期为3到到10年。年。因此，犯罪嫌疑人甲一定选择坦白。因此，犯罪嫌疑人甲一定选择坦白。基于同样的道理，犯罪嫌疑人乙也只能选基于同样的道理，犯罪嫌疑人乙也只能选择坦白。择坦白。选择坦白是他们最好的选择，各自被判选择坦白是他们最好的选择，各自被判3年。年。优优 化化 建建 模模事实上，设事实

29、上，设(cijA,cijB)是甲、乙赢得值，则是甲、乙赢得值，则甲、乙采用的策略是甲、乙采用的策略是BBijjiAAijijcccc1111maxmin3maxmin3 1.纯对策问题的基本概念纯对策问题的基本概念按照上面的论述，对于一般纯对策问题，按照上面的论述，对于一般纯对策问题，局中人局中人A、B的支付（赢得）矩阵由表的支付（赢得）矩阵由表9.2.2所示。所示。优优 化化 建建 模模局中人局中人A、B的支付矩阵的支付矩阵12n12m),(1111BAcc),(1212BAcc),(2121BAcc),(2222BAcc),(11BnAncc),(22BnAncc),(11BmAmcc),

30、(22BmAmcc),(BmnAmncc 优优 化化 建建 模模为局中人为局中人A的支付（赢得）矩阵，的支付（赢得）矩阵，为局中人为局中人B的支付（赢得）矩阵。的支付（赢得）矩阵。因此，矩阵对策记为：因此，矩阵对策记为：G=A,B;S1,S2,CA,CB或或G=S1,S2,CA,CB nmAijAcC nmBijBcC 优优 化化 建建 模模定义定义9.5：设设G=S1,S2,CA,CB是一双矩阵对策，若等式是一双矩阵对策，若等式BijjiBjiAijijAjiccccmaxmin,maxmin*成立，则记成立，则记vA=，并称，并称vA为局中人为局中人A的赢得值，记的赢得值，记vB=，并称，

31、并称vB为局中人为局中人B的赢得值，称（的赢得值，称（i*,j*)为为G在纯策略下的解（或在纯策略下的解（或Nash平衡点），称平衡点），称i*和和 j*分别为局中人分别为局中人A、B的的最优纯策略。最优纯策略。Ajic*Bjic*优优 化化 建建 模模2.纯对策问题的求解方法纯对策问题的求解方法实际上，定义实际上，定义9.5也同时给出了纯对策问题也同时给出了纯对策问题的求解方法。因此，对于例的求解方法。因此，对于例9.6,(1,0),(1,0)是是Nash平衡点，也就是说，坦白他们的最佳策略。平衡点，也就是说，坦白他们的最佳策略。再看一个例子。再看一个例子。例：例：9.7（夫妻周末安排问题）

32、一对夫妻，商量周末（夫妻周末安排问题）一对夫妻，商量周末安排。丈夫喜欢看足球，妻子喜欢听音乐会。他们安排。丈夫喜欢看足球，妻子喜欢听音乐会。他们的赢得值由表的赢得值由表9.7所示。请为这对夫妻设计最好的度所示。请为这对夫妻设计最好的度周末的方案。周末的方案。优优 化化 建建 模模解：由定义解：由定义9.5可知，对于策略可知，对于策略(1,0),(1,0)或策略或策略(0,1),(0,1)均是均是Nash平衡点，也就是最优解，即他们平衡点，也就是最优解，即他们选择是共同看足球，或共同听音乐会。表中带有下划选择是共同看足球，或共同听音乐会。表中带有下划线是他们采用策略的赢得值。线是他们采用策略的赢

33、得值。妻妻足球足球音乐会音乐会夫夫足球足球(3,1)(-1,-1)音乐会音乐会(-1,-1)(1,3)优优 化化 建建 模模2.混合对策问题混合对策问题如果不存在使式如果不存在使式(18)成立的对策，则需要求成立的对策，则需要求混合对策。类似于二人常数和对策情况，需要给混合对策。类似于二人常数和对策情况，需要给出混合对策的最优解。出混合对策的最优解。1.混合对策问题的基本概念混合对策问题的基本概念定义定义9.6 在对策在对策G=S1,S2,CA,CB中，若存中，若存在策略对在策略对 使得使得Byx ,)19(,ByyCxyCxAxyCxyCxBTBTATAT 优优 化化 建建 模模则称则称 为

34、为G的一个非合作平衡点。记的一个非合作平衡点。记 则称则称vA,vB分别为局中人分别为局中人A、B的赢得值。的赢得值。yx,yCxvyCxvBTBATA ,对于混合对策问题有如下定理对于混合对策问题有如下定理定理定理9.5 每个双矩阵对策至少存在一个非合作平衡点。每个双矩阵对策至少存在一个非合作平衡点。定理定理9.6混合策略混合策略 为对策为对策G=S1,S2,CA,CB的平衡点的充分必要条件是：的平衡点的充分必要条件是：yx,)20(,2,1,2,1,11 njyCxxcmiyCxycBTmiiBijATnjjAij 优优 化化 建建 模模2.混合对策问题的求解方法混合对策问题的求解方法由定

35、义由定义9.6可知，求解混合对策就是求非合作可知，求解混合对策就是求非合作对策的平衡点。进一步，由定理对策的平衡点。进一步，由定理9.6得到，求解非得到，求解非合作对策的平衡点，就是求解满足不等式约束合作对策的平衡点，就是求解满足不等式约束(20)的可行点。因此，混合对策问题的求解问题就转的可行点。因此，混合对策问题的求解问题就转化为求不等式约束化为求不等式约束(20)的可行点，而的可行点，而LINGO软件软件可以很容易做到这一点。可以很容易做到这一点。优优 化化 建建 模模例例9.8 有甲、乙两支游泳队举行包括三个项目的有甲、乙两支游泳队举行包括三个项目的对抗赛。这两支游泳队各有一名健将级运

36、动员对抗赛。这两支游泳队各有一名健将级运动员（甲队为李，乙队为王），在三个项目中成绩（甲队为李，乙队为王），在三个项目中成绩很突出。但规则准许他们每个人分别只能参加很突出。但规则准许他们每个人分别只能参加两项比赛，而每队的其他两名运动员则可参加两项比赛，而每队的其他两名运动员则可参加全部三项比赛。各运动员的成绩如表全部三项比赛。各运动员的成绩如表9-8所示。所示。甲队甲队乙队乙队赵赵钱钱李李王王张张孙孙蝶泳蝶泳54.758.252.153.656.459.8仰泳仰泳62.263.458.256.559.761.5蛙泳蛙泳69.170.565.367.868.471.3 优优 化化 建建 模模解

37、：解：分别用甲分别用甲1、甲、甲2和甲和甲3表示甲队中李姓健将不参表示甲队中李姓健将不参加蝶泳、仰泳、蛙泳比赛的策略，分别用乙加蝶泳、仰泳、蛙泳比赛的策略，分别用乙1、乙、乙2和和乙乙3表示乙队中王姓健将不参加蝶泳、仰泳、蛙泳比表示乙队中王姓健将不参加蝶泳、仰泳、蛙泳比赛的策略。当甲队采用策略甲赛的策略。当甲队采用策略甲1，乙队采用策略乙，乙队采用策略乙1时，时，在在100米蝶泳中，甲队中赵获第一、钱获第三得米蝶泳中，甲队中赵获第一、钱获第三得6分，分，乙队中张获第二，得乙队中张获第二，得3分；在分；在100米仰泳中，甲队中李米仰泳中，甲队中李获第二，得获第二，得3分，分，乙队中王获第一，张获

38、第三，得乙队中王获第一，张获第三，得6分；分；在在100米蛙泳中，甲队中李获第一，得米蛙泳中，甲队中李获第一，得5分，乙队中王分，乙队中王获第二、张获第三，得获第二、张获第三，得4分。也就是说，对应于策略分。也就是说，对应于策略（甲（甲1，乙，乙1），甲、乙两队各自的得分为），甲、乙两队各自的得分为(14,13).表表9-9中给出了在全部策略下各队的得分。中给出了在全部策略下各队的得分。优优 化化 建建 模模表表9-9甲、乙两队采用不同策略的得分甲、乙两队采用不同策略的得分乙乙1乙乙2乙乙3甲甲1(14,13)(13,14)(12,15)甲甲2(13,14)(12,15)(12,15)甲甲3(

39、12,15)(12,15)(13,14)按照定理按照定理9.6，求最优混合策略，就是求不等，求最优混合策略，就是求不等式约束式约束(20)的可行解的可行解.写出相应的写出相应的LINGO程序，程程序，程序名：序名：exam0908.lg4 优优 化化 建建 模模MODEL:1sets:2 optA/1.3/:x;3 optB/1.3/:y;4 AXB(optA,optB):Ca,Cb;5endsets 6data:7 Ca=14 13 12 8 13 12 12 优优 化化 建建 模模 9 12 12 13;10 Cb=13 14 15 11 14 15 15 12 15 15 14;13en

40、ddata 14Va=sum(AXB(i,j):Ca(i,j)*x(i)*y(j);15Vb=sum(AXB(i,j):Cb(i,j)*x(i)*y(j);16for(optA(i):优优 化化 建建 模模 17 sum(optB(j):Ca(i,j)*y(j)=Va);18for(optB(j):19 sum(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 itera

41、tion:3 Variable Value VA 12.50000 VB 14.50000 X(1)0.5000000 X(2)0.000000 X(3)0.5000000 Y(1)0.000000 Y(2)0.5000000 Y(3)0.5000000 优优 化化 建建 模模即甲队采用的策略是甲即甲队采用的策略是甲1、甲、甲3方案各占方案各占50%,乙队采用的策略是乙乙队采用的策略是乙2、乙、乙3方案各占方案各占50%,甲队的平均得分为甲队的平均得分为12.5分，乙队的平均得分为分，乙队的平均得分为14.5分。分。当纯对策的解不唯一时，也存在混合对策的平当纯对策的解不唯一时，也存在混合对策的

42、平衡点。衡点。优优 化化 建建 模模例例9.9 用混合对策方法求解例用混合对策方法求解例9.7。解：解：写出求不等式写出求不等式(20)的的LINGO程序，程序名：程序，程序名：ex0909.lg4“MODEL:1sets:2 optA/1.2/:x;3 optB/1.2/:y;4 AXB(optA,optB):Ca,Cb;5endsets 优优 化化 建建 模模 6data:7 Ca=3-1-1 1;8 Cb=1-1-1 3;9enddata 10Va=sum(AXB(i,j):Ca(i,j)*x(i)*y(j);11Vb=sum(AXB(i,j):Cb(i,j)*x(i)*y(j);12f

43、or(optA(i):13 sum(optB(j):Ca(i,j)*y(j)=Va);14for(optB(j):优优 化化 建建 模模 15 sum(optA(i):Cb(i,j)*x(i)=Vb);16sum(optA:x)=1;sum(optB:y)=1;17free(Va);free(Vb);END计算得到混合对策的平衡点计算得到混合对策的平衡点(2/3,1/3),(1/3,2/3)各自的赢得值为各自的赢得值为1/3.从上述分析来看，二人常数和对策是非常数和从上述分析来看，二人常数和对策是非常数和对策的特例，因此也可以用求解非常数和对策的方对策的特例，因此也可以用求解非常数和对策的方法

44、求解常数和对策。法求解常数和对策。优优 化化 建建 模模例例9.10用求解非常数和对策的方法求解例用求解非常数和对策的方法求解例9.5解：写出相应的解：写出相应的LINGO程序，程序名：程序，程序名：exam0910.lg4MODEL:1sets:2 optA/1.3/:x;3 optB/1.3/:y;4 AXB(optA,optB):Ca,Cb;5endsets 优优 化化 建建 模模 6data:7 Ca=35 15 60 8 45 58 50 9 38 14 70;10 Cb=65 85 40 11 55 42 50 12 62 86 30;13enddata 优优 化化 建建 模模 1

45、4Va=sum(AXB(i,j):Ca(i,j)*x(i)*y(j);15Vb=sum(AXB(i,j):Cb(i,j)*x(i)*y(j);16for(optA(i):17 sum(optB(j):Ca(i,j)*y(j)=Va);18for(optB(j):19 sum(optA(i):Cb(i,j)*x(i)=Vb);20sum(optA:x)=1;sum(optB:y)=1;21free(Va);free(Vb);END 优优 化化 建建 模模计算结果如下计算结果如下（只保留有效部分）（只保留有效部分）Feasible solution found at iteration:12 Va

46、riable Value VA 45.00000 VB 55.00000 X(1)0.000000 X(2)1.000000 X(3)0.000000 Y(1)1.000000 Y(2)0.000000 Y(3)0.000000 优优 化化 建建 模模即局中人即局中人A采用第二种策略，赢得采用第二种策略，赢得45万观万观众，局中人众，局中人B采用第一种策略，赢得采用第一种策略，赢得55万观众，万观众，与前面计算的结果相同。与前面计算的结果相同。优优 化化 建建 模模3 n人合作对策初步人合作对策初步n人合作对策在理论上较为复杂，这里只用人合作对策在理论上较为复杂，这里只用一些例子简单介绍一些例

47、子简单介绍n人合作对策的基本思想，人合作对策的基本思想，和用和用LINGO软件求解对策的方法。软件求解对策的方法。例例9.11甲有一匹马，对他自己来说，其价值为甲有一匹马，对他自己来说，其价值为0,而对乙和丙（买主）来说分别价值而对乙和丙（买主）来说分别价值90和和100个个货币单位。试建立货币单位。试建立3人合作对策，使得每人的人合作对策，使得每人的利益最大。利益最大。优优 化化 建建 模模解：解：设甲、乙、丙三人的价值分别为设甲、乙、丙三人的价值分别为x1,x2,x3,因此对因此对于每个人来说，其价值为于每个人来说，其价值为0，即，即v1=v2=v3=0如果甲与乙合作，其价值为如果甲与乙合

48、作，其价值为90，甲与丙合作，甲与丙合作，其价值为其价值为100，若乙与丙合作，其价值仍为，若乙与丙合作，其价值仍为0，因此有，因此有v1,2=90,v1,3=100,v2,3=0.但三人合作的总价值为但三人合作的总价值为100，即，即v 1,2,3=100.建立相应的数学规划问题建立相应的数学规划问题 优优 化化 建建 模模,3,2,1,0 100 0 100 90 ,3,2,1,.;max1321323121 ixxxxxxxxxxixztszi 优优 化化 建建 模模写出相应的写出相应的LINGO程序，程序名：程序，程序名：exam0909.lg4 MODEL:1sets:2 condi

49、tion/1.3/:b;3 players /1.3/:x;4 constraint(condition,players):A;5endsets 6data:7 A=1 1 0 优优 化化 建建 模模8 1 0 1 9 0 1 1;10 b=90 100 0;11 total=100;12enddata 13max=z;14for(players:z=b(i);17sum(players:x)=total;END 优优 化化 建建 模模经计算得到经计算得到（只保留有用部分）（只保留有用部分）Global optimal solution found at iteration:8 Objecti

50、ve value:0.000000 Variable Value Reduced Cost TOTAL 100.0000 0.000000 Z 0.000000 0.000000 X(1)90.00000 0.000000 X(2)0.000000 0.000000 X(3)10.00000 0.000000即即x1=90,x2=0,x3=10,也就是说，甲以也就是说，甲以90货币货币单位将马卖给丙，甲获利单位将马卖给丙，甲获利90货币单位，乙获利货币单位，乙获利0货货币单位，丙获利币单位，丙获利10货币单位货币单位.优优 化化 建建 模模例例9.12有三家公司有三家公司A、B、C可以独立或合

51、作某项可以独立或合作某项工程，由于三家公司的基础与优势不同，因此采用工程，由于三家公司的基础与优势不同，因此采用独立或合作完成项目的利润也不同，详细利润由表独立或合作完成项目的利润也不同，详细利润由表1所示。试求完成该项目的最优方案。所示。试求完成该项目的最优方案。完成项目的方法完成项目的方法得到的利润得到的利润A公司独立公司独立1.2B公司独立公司独立0C公司独立公司独立1A公司与公司与B公司合作公司合作4A公司与公司与C公司合作公司合作3B公司与公司与C公司合作公司合作4A,B,C三家公司合作三家公司合作7 优优 化化 建建 模模解：解：列出相应的数学规划问题列出相应的数学规划问题.3,2

52、,1,0,1,2.1,7,4,3,4,3,2,1.;max31321323121 ixxxxxxxxxxxxixztszii 优优 化化 建建 模模相应的相应的LINGO程序，程序名：程序，程序名：exam0910.lg4MODEL:1sets:2 condition/1.5/:b;3 players /1.3/:x;4 constraint(condition,players):A;5endsets 6data:7 A=1 1 0 8 1 0 1 优优 化化 建建 模模 9 0 1 1 10 1 0 0 11 0 0 1;12 b=4 3 4 1.2 1;13 total=7;14endda

53、ta 15max=z;16for(players:z=b(i);19sum(players:x)=total;END 优优 化化 建建 模模经计算得到（保留有用部分）经计算得到（保留有用部分）Global optimal solution found at iteration:14 Objective value:2.333333 Variable Value Reduced Cost TOTAL 7.000000 0.000000 Z 2.333333 0.000000 X(1)2.333333 0.000000 X(2)2.333333 0.000000 X(3)2.333333 0.000000即即x1=x2=x3=2.333,也就是说，三家公司共同合也就是说，三家公司共同合作承担此项目，每个公司盈利作承担此项目，每个公司盈利2.333万元万元 优优 化化 建建 模模习题习题9 99.19.19.49.4布置作业内容布置作业内容Thank you very much!Thank you very much!