优化建模与LINGO课件第09章-对-策-论

3.混合对策求解方法通常用线性规划方法求混合策略的解。设局中人A分别以x1,x2,…,xm的概率混合使用他的m种策略，局中人B分别以y1,y2,…,ym的概率混合使用他的n种策略。当A采用混合策略，B分别采用纯策略bj(j=1,2,…,n),A的赢得分别为依据最大最小原则，应有其中vA是局中人A的赢得值。将问题（9）写成线性规划问题 也就是说，线性规划问题(10)～(13)的解就是局中人A采用混合策略的解。类似可求局中人B的最优策略的解。乙石头剪子布甲石头01-1剪子-101布1-10例1.1“石头--剪子--布”中儿童甲的支付函数例9.3

用线性规划方法求解例1的 最优混合策略。按照线性规划（10）～（13）写出相应的LINGO程序，程序名：exam0903a.lg4MODEL:1]sets:2]playerA/1..3/:x;3]playerB/1..3/;4]game(playerA,playerB):C;5]endsets

6]data:7]C=01-18]-1019]1-10;10]enddata11]max=v_A;12]@free(v_A);13]@for(playerB(j):14]@sum(playerA(i):C(i,j)*x(i))>=v_A);15]@sum(playerA:x)=1;END得到最优解（只保留相关部分）Globaloptimalsolutionfoundatiteration:3Objectivevalue:0.000000VariableValueReducedCostV_A0.0000000.000000X(1)0.33333330.000000X(2)0.33333330.000000X(3)0.33333330.000000 即儿童甲以1/3的概率出石头、剪子、布中每种策略的一种，其赢得值为0.

用线性规划求出儿童乙有同样的结论。 计算到此，读者可能会产生一个问题：一个具有鞍点的对策问题，如果采用线性规划方法求解，将会出现什么情况？1.对策的基本策略---鞍点对策例9.2设A、B两人对策，各自拥有三个策略：a1,a2,a3和b1,b2,b3,局中人A的支付（收益）矩阵由表1.2所示。试求A、B各自的最优策略。b1b2b3mina11391a26575a38422max859例9.4用线性规划方法求解例2解：写出LINGO程序，程序名：exam0904.lg4MODEL:1]sets:2]playerA/1..3/:x;3]playerB/1..3/;4]game(playerA,playerB):C;5]endsets6]data:7]C=139

8]6579]842;10]enddata11]max=v_A;12]@free(v_A);13]@for(playerB(j):14]@sum(playerA(i):C(i,j)*x(i))>=v_A);15]@sum(playerA:x)=1;END计算结果为（保留有效部分）Globaloptimalsolutionfoundatiteration:0Objectivevalue:5.000000VariableValueReducedCostV_A5.0000000.000000X(1)0.0000002.000000X(2)1.0000000.000000X(3)0.0000001.000000 由结果可以看到，局中人A仍然选择纯策略。对局中人B的计算也会出现同样的情况。 从例9.3和例9.4可以看出，无论矩阵对策有无鞍点，我们均可以采用线性规划的方法求其对策，只不过具有鞍点的对策可以有更简单的算法罢了。1.2二人常数和对策 所谓常数和对策是指局中人A和局中人B所赢得的值之和为一常数.显然，二人零和对策是二人常数和的特例，即常数为零。 对于二人常数和对策，有纯策略对策和混合策略对策。其求解方法基本上是相同的。1.鞍点对策 对于二人常数和对策，仍然有鞍点对策，其求解方法与二人零和对策相同。例9.4 在晚8点至9点这个时段，两家电视台在竞争100万电视观众收看自己的电视节目，并且电视台必须实时公布自己在下一时段的展播内容。电视台1可能选择的展播方式及可能得到的观众如表所示。电视台min西部片连续剧喜剧片电视台1西部片35156015连续剧45585045喜剧片38147014max455870解：事实上，对方得到的，就是自己失去的，完全利用二人零和的方法确定最优纯策略，即 因此，电视台1选择播放连续剧，赢得45万观众，电视台2播放西部片，赢得100-45=55万观众。2.混合对策 对于常数和对策，也存在混合对策，同样可以采用线性规划方法求解，这里就不举例子了。§2二人非常数和对策 二人非常数和对策也称为双矩阵对策。在前面介绍的常数和（零和）对策中，均包含两种情况，纯策略和混合策略。对于非常数对策，也包含这两种策略。1.纯对策问题例9.6：囚徒的困境(表9.2.1)乙坦白不坦白甲坦白（-3，-3）(0,-10)不坦白（-10，0）(-1,-1)例9.6

设有甲、乙两名嫌疑犯因同一桩罪行被捕，由于希望他们坦白并提供对方的犯罪证据，规定如两人均坦白各判刑3年；如上方坦白另一方不坦白，坦白一方从轻释放，不坦白一方判刑10年；如两人均不坦白，由于犯罪事实很多不能成立，只能各判1年，见表9.2.1所示。 试分析甲、乙两犯罪嫌疑人各自采用什么策略使自己的刑期最短。例9.6给出了典型的二人非常数和对策，每人的收益矩阵是不相同的，因此称为双矩阵对策。通常规定，双矩阵中，第一个元素是局中人A的赢得值，第二个元素是局中人B的赢得值。 问题分析：这是一个二人非常数和对策问题。从表面看，两犯罪嫌疑人拒不坦白，只能被判1年徒刑，结果是最好的。但仔细分析，确无法做到这一点。因为犯罪嫌疑人甲如果采用不坦白策略，他可能被判的刑期为1到10年，而犯罪嫌疑人乙可能判的刑期为0到1年。 而甲选择坦白，他被判的刑期为0到3年，此时，犯罪嫌疑人乙可能判的刑期为3到10年。因此，犯罪嫌疑人甲一定选择坦白。 基于同样的道理，犯罪嫌疑人乙也只能选择坦白。 选择坦白是他们最好的选择，各自被判3年。 事实上，设(cijA,cijB)是甲、乙赢得值，则甲、乙采用的策略是1.纯对策问题的基本概念 按照上面的论述，对于一般纯对策问题，局中人A、B的支付（赢得）矩阵由表9.2.2所示。局中人A、B的支付矩阵β1β2…βnα1…α2…┆┆┆┆αm… 为局中人A的支付（赢得）矩阵， 为局中人B的支付（赢得）矩阵。因此，矩阵对策记为：

G={A,B;S1,S2,CA,CB}或G={S1,S2,CA,CB}定义9.5：设G={S1,S2,CA,CB}是一双矩阵对策，若等式 成立，则记vA=，并称vA为局中人A的赢得值，记vB=，并称vB为局中人B的赢得值，称（αi*,β

j*)为G在纯策略下的解（或Nash平衡点），称αi*和β

j*分别为局中人A、B的最优纯策略。2.纯对策问题的求解方法 实际上，定义9.5也同时给出了纯对策问题的求解方法。因此，对于例9.6,((1,0),,(1,0))是Nash平衡点，也就是说，坦白他们的最佳策略。再看一个例子。例：9.7（夫妻周末安排问题）一对夫妻，商量周末安排。丈夫喜欢看足球，妻子喜欢听音乐会。他们的赢得值由表9.7所示。请为这对夫妻设计最好的度周末的方案。解：由定义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}中，若存在策略对使得则称 为G的一个非合作平衡点。记则称vA,vB分别为局中人A、B的赢得值。对于混合对策问题有如下定理定理9.5

每个双矩阵对策至少存在一个非合作平衡点。定理9.6混合策略为对策G=\{S1,S2,CA,CB}的平衡点的充分必要条件是：2.混合对策问题的求解方法 由定义9.6可知，求解混合对策就是求非合作对策的平衡点。进一步，由定理9.6得到，求解非合作对策的平衡点，就是求解满足不等式约束(20)的可行点。因此，混合对策问题的求解问题就转化为求不等式约束(20)的可行点，而LINGO软件可以很容易做到这一点。例9.8

有甲、乙两支游泳队举行包括三个项目的对抗赛。这两支游泳队各有一名健将级运动员（甲队为李，乙队为王），在三个项目中成绩很突出。但规则准许他们每个人分别只能参加两项比赛，而每队的其他两名运动员则可参加全部三项比赛。各运动员的成绩如表9-8所示。甲队乙队赵钱李王张孙蝶泳54.758.252.153.656.459.8仰泳62.263.458.256.559.761.5蛙泳69.170.565.367.868.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甲、乙两队采用不同策略的得分乙1乙2乙3甲1(14,13)(13,14)(12,15)甲2(13,14)(12,15)(12,15)甲3(12,15)(12,15)(13,14) 按照定理9.6，求最优混合策略，就是求不等式约束(20)的可行解.写出相应的LINGO程序，程序名：exam0908.lg4"MODEL:1]sets:2]optA/1..3/:x;3]optB/1..3/:y;4]AXB(optA,optB):Ca,Cb;5]endsets6]data:7]Ca=1413128]131212

9]121213;10]Cb=13141511]14151512]151514;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));16]@for(optA(i):

17]@sum(optB(j):Ca(i,j)*y(j))<=Va);18]@for(optB(j):19]@sum(optA(i):Cb(i,j)*x(i))<=Vb);20]@sum(optA:x)=1;@sum(optB:y)=1;21]@free(Va);@free(Vb);END用LINGO软件求解，得到Feasiblesolutionfoundatiteration:3VariableValueVA12.50000VB14.50000X(1)0.5000000X(2)0.000000X(3)0.5000000Y(1)0.000000Y(2)0.5000000Y(3)0.5000000即甲队采用的策略是甲1、甲3方案各占50%,乙队采用的策略是乙2、乙3方案各占50%,甲队的平均得分为12.5分，乙队的平均得分为14.5分。当纯对策的解不唯一时，也存在混合对策的平衡点。例9.9

用混合对策方法求解例9.7。解：写出求不等式(20)的LINGO程序，程序名："ex0909.lg4“MODEL:1]sets:2]optA/1..2/:x;3]optB/1..2/:y;4]AXB(optA,optB):Ca,Cb;5]endsets

6]data:7]Ca=3-1-11;8]Cb=1-1-13;9]enddata10]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));12]@for(optA(i):13]@sum(optB(j):Ca(i,j)*y(j))<=Va);14]@for(optB(j):

15]@sum(optA(i):Cb(i,j)*x(i))<=Vb);16]@sum(optA:x)=1;@sum(optB:y)=1;17]@free(Va);@free(Vb);END

计算得到混合对策的平衡点((2/3,1/3),(1/3,2/3)各自的赢得值为1/3.

从上述分析来看，二人常数和对策是非常数和对策的特例，因此也可以用求解非常数和对策的方法求解常数和对策。例9.10用求解非常数和对策的方法求解例9.5解：写出相应的LINGO程序，程序名：exam0910.lg4MODEL:1]sets:2]optA/1..3/:x;3]optB/1..3/:y;4]AXB(optA,optB):Ca,Cb;5]endsets

6]data:7]Ca=3515608]4558509]381470;10]Cb=65854011]55425012]628630;13]enddata

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));16]@for(optA(i):17]@sum(optB(j):Ca(i,j)*y(j))<=Va);18]@for(optB(j):19]@sum(optA(i):Cb(i,j)*x(i))<=Vb);20]@sum(optA:x)=1;@sum(optB:y)=1;21]@free(Va);@free(Vb);END计算结果如下（只保留有效部分）Feasiblesolutionfoundatiteration:12VariableValueVA45.00000VB55.00000X(1)0.000000X(2)1.000000X(3)0.000000Y(1)1.000000Y(2)0.000000Y(3)0.000000 即局中人A采用第二种策略，赢得45万观众，局中人B采用第一种策略，赢得55万观众，与前面计算的结果相同。§3n人合作对策初步

n人合作对策在理论上较为复杂，这里只用一些例子简单介绍n人合作对策的基本思想，和用LINGO软件求解对策的方法。例9.11

甲有一匹马，对他自己来说，其价值为0,而对乙和丙（买主）来说分别价值90和100个货币单位。试建立3人合作对策，使得每人的利益最大。解：设甲、乙、丙三人的价值分别为x1,x2,x3,因此对于每个人来说，其价值为0，即v{1}=v{2}=v{3}=0

如果甲与乙合作，其价值为90，甲与丙合作，其价值为100，若乙与丙合作，其价值仍为0，因此有v{1,2}=90,v{1,3}=100,v{2,3}=0.但三人合作的总价值为100，即v{1,2,3}=100.建立相应的数学规划问题写出相应的LINGO程序，程序名：exam0909.lg4MODEL:1]sets:2]condition/1..3/:b;3]players/1..3/:x;4]constraint(condition,players):A;5]endsets6]data:7]A=110

8]1019]011;10]b=901000;11]total=100;12]enddata13]max=z;14]@for(players:z<=x);15]@for(condition(i):16]@sum(players(j):A(i,j)*x(j))>=b(i));17]@sum(players:x)<=total;END经计算得到（只保留有用部分）Globaloptimalsolutionfoundatiteration:8Objectivevalue:0.000000Variable ValueReducedCostTOTAL 100.00000.000000Z 0.0000000.000000X(1) 90.000000.000000X(2) 0.0000000.000000X(3) 10.000000.000000 即x1=90,x2=0,x3=10,也就是说，甲以90货币单位将马卖给丙，甲获利90货币单位，乙获利0货币单位，丙获利10货币单位.例9.12

有三家公司A、B、C可以独立或合作某项工程，由于三家公司的基础与优势不同，因此采用独立或合作完成项目的利润也不同，详细利润由表1所示。试求完成该项目的最优方案。完成项目的方法得到的利润A公司独立1.2B公司