优化建模与lingo第09章 对　策　论

《优化建模与lingo第09章 对　策　论》由会员分享，可在线阅读，更多相关《优化建模与lingo第09章 对　策　论（74页珍藏版）》请在金锄头文库上搜索。

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

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

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

4、。优 化 建 模鞍点对策是对策的最基本策略，为更好地 理解鞍点对策，先看一个简单的例子。1. 对策的基本策略-鞍点对策例9.2设A、B两人对策，各自拥有三个策略： a1, a2, a3和b1, b2, b3, 局中人A的支付（收益） 矩阵由表1.2所示。试求A、B各自的最优策略。b1b2b3min a11391 a26575 a38422 max859优 化 建 模问题分析：从直观来看，局中人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所示。12n 1C11C12Cn1 2C21C22Cn2 mCm1Cm2Cmn优 化 建 模其中局中人A有m个策略1 , , m, 局中人B 有n个策略1, , n,

6、分别记为S1=1 , , m, S2= 1, , nC为局中人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*, j*)使

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

8、 建 模定义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, ,xm的概率混合使用他的m种策略，局中人 B分别以y1,y2, ,ym的概率混合使用他的n种策略。优 化 建 模当A

9、采用混合策略，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/1.3/: x;3 playerB/1.3/;4 game(playerA,playerB) : C;5endsets优 化

10、建 模6data:7 C = 0 1 -18 -1 0 19 1 -1 0;10enddata11max=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: 3Objective value: 0.000000Variable Value Reduced CostV_A 0.000000 0.000000X( 1) 0.333333

11、3 0.000000X( 2) 0.3333333 0.000000X( 3) 0.3333333 0.000000优 化 建 模即儿童甲以1/3的概率出石头、剪子、布中每 种策略的一种，其赢得值为0. 用线性规划求出儿童乙有同样的结论。计算到此，读者可能会产生一个问题：一个具有鞍点的对策问题，如果采用线性规划方法求解 ，将会出现什么情况？优 化 建 模 例9.4用线性规划方法求解例2解： 写出LINGO程序，程序名：exam0904.lg4MODEL:1sets:2 playerA/1.3/: x;3 playerB/1.3/;4 game(playerA,playerB) : C;5end

12、sets6data:7 C = 1 3 9优 化 建 模8 6 5 79 8 4 2;10enddata11max=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: 0Objective value: 5.000000Variable Value Reduced CostV_A 5.000000 0.000000X( 1) 0.00

13、0000 2.000000X( 2) 1.000000 0.000000X( 3) 0.000000 1.000000优 化 建 模由结果可以看到，局中人A仍然选择纯策略 。对局中人B的计算也会出现同样的情况。从例9.3和例9.4可以看出，无论矩阵对策有无鞍点，我们均可以采用线性规划的方法求其对 策，只不过具有鞍点的对策可以有更简单的算法 罢了。优 化 建 模1.2 二人常数和对策所谓常数和对策是指局中人A和局中人 B所赢得的值之和为一常数. 显然，二人零和对策是二人常数和的特例，即常数为零。对于二人常数和对策，有纯策略对策和混合策略对策。其求解方法基本上是相同的。1. 鞍点对策对于二人常数和

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

15、5万观 众。2. 混合对策对于常数和对策，也存在混合对策，同样可 以采用线性规划方法求解，这里就不举例子了。优 化 建 模2 二人非常数和对策二人非常数和对策也称为双矩阵对策。在前面介绍的常数和（零和）对策中，均包含两种 情况，纯策略和混合策略。对于非常数对策，也包 含这两种策略。 1.纯对策问题 例9.6：囚徒的困境 (表9.2.1) 乙 坦白不坦白 甲 坦白（-3，-3 ）(0,-10)不坦白（-10，0 ）(-1,-1)优 化 建 模例9.6设有甲、乙两名嫌疑犯因同一桩罪行被捕，由于希望他们坦白并提供对方的犯罪证据，规定如 两人均坦白各判刑3年；如上方坦白另一方不坦白 ，坦白一方从轻释放，不坦白一方判刑10年；如两人均不坦白，由于犯罪事实很多不能成立，只能各 判1年，见