优化建模与LINGO第09章

优化建模与LINDO/LINGO软件第　9　章 对　策　论

［原书相关信息］

谢金星, 薛毅编著, 清华大学出版社, 2005年7月第1版.

https://www.wendangku.net/doc/b011969371.html,/~jxie/lindo

内容提要

1.二人常数和对策

2.二人非常数和对策

3.3.n n人合作对策

第一节　二人常数和对策

对策模型和算法的重要意义

我们不就对策论模型全面的讨论，而是只介绍一些对策论模型的基本概念。重点介绍如何利用

LINGO 软件去解对策论模型中的有关问题。为了更好地理解LINGO 软件的编程过程。

对策论（Game Theory）又称为博弈论，是研究带有竞争与对抗问题的理论与方法。对策论是现代数学的一个重要分支，也是运筹学的一个重要学科。对策论目前已在市场决策中有着广泛的应用。

1.11.1　二　二　二人零和人零和人零和对策

对策§1　二人常数和对策模型

二人零和对策是最基本的对策形式，先用一个例子来说明。

例9.1 甲、乙两名儿童玩“石头--剪子--布”的游戏。石头胜剪子，剪子胜布，布胜石头。那么，甲、乙儿童如何做，使自己获胜的可能最大？

在对策论中，应有以下要素：

(1) 局中人。是指参与对抗的各方，可以是一个人，也可以是一个集团。在例1.1的甲、乙两名儿

童就是局中人。

(2)策略。是指局中人所拥有的对付其他局中人的手段、方案的集合。如例1.1中共有石头、剪子、

布三种策略。

(3) 支付函数（或收益函数）。是指一局对策后各局中人的得与失，通常用正数字表示局中人的得，用负数字表示局中人的失。在例1.1的局中人甲的支付函数如表所示。

-110石头

甲

-1

1

布

10-1剪子布剪子石头

乙

例1.1　“石头--剪子--布”中儿童甲的支付函数

?当局中人得失总和为零时，称这类对策为零和对策；否则称为非零和对策。

?当局中人只有两个，且对策得失总和为零，则称为二人零和对策，若总得失总和为常数，则称为二人常数和对策，若得失总和是非常数的，则称为二人非常数和对策。

?若二人对策双方的得失是用矩阵形式表示，则称支付函数为支付矩阵，相应的对策称为矩阵对策。通常，支付矩阵表示局中人A的支付函数。

鞍点对策是对策的最基本策略，为更好地理解鞍点对策，先看一个简单的例子。

1. 对策的基本策略---鞍点对策

例9.2设A、B两人对策，各自拥有三个策略：a1, a2, a3和b1, b2, b3, 局中人A的支付（收益）矩阵由表1.2所示。试求A、B各自的最优策略。

9

5

8

max 2

2

4

8

a35

7

5

6

a21

9

3

1

a1min

b3

b2

b1

?问题分析：

从直观来看，局中人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，而无论局中人B 选择什么策略，他输掉的值总是大于等于5，5就是支付矩阵的鞍点。

现讨论一般情况。假设局中人A 的支付矩阵由表1.3所示。

Cmn

…

Cm2

Cm1

αm

┆┆┆┆Cn2…C22C21α2Cn1…C12C11α1βn …β2β1

其中局中人A有m个策略α

, , ……,αm, 局中人B

1

有n个策略β

, , ……, βn, 分别记为S1={α1 , , ……,αm}, S2=

1

{β1, , ……, βn}

C为局中人A的支付矩阵，而-C为局中人B的

, S2, C}, 支付矩阵。因此，矩阵对策记为G={A,B; S

1

, S2, C}

或G= {S

1

对于一般矩阵对策，有如下定义和定理。

定义9.1设G= {S 1, S 2, C} 是一矩阵对策，若等式

成立，则记v G =, c i * j j*

*并称v G 为对策G 的值。称使式(1)成立纯局势 (α i *, β j *)为G 在纯策略下的解（或平衡局势），称α i *和β j *分别为局中人A 、B 的最优纯策略。

*

*max min min max j i ij i

j

ij j

i

c c c ==

定理9.1

矩阵对策G={S1, S2, C}在纯策略意义下有解的充分必要条件是：存在纯局势(α i *, β j *)使得

.

,,2,1,,,2,1,****n j m i c c c j i j i ij L L ==≤≤定义9.2

的一个鞍点、

为函数则称使得

若存在上的实值函数，及为一个定义在设),(),(,),,(),(),(,,),(*

*

*

****

*

y x f y x B

y A x y x f y x f y x f B y A x B y A x y x f ∈?∈?≤≤∈∈∈∈

当矩阵对策的最优解不唯一时，有如下定理：定理9.2

定理9.3

.

),(),(22112211j i j i j i j i c c =βαβα则

是矩阵对策的两个解，和若.

),(),(,),(),(12212211也是解和则是矩阵对策的两个解和若j i j i j i j i βαβαβαβα

2. 无鞍点的对策策略---混合对策

如果支付矩阵有鞍点，选择鞍点对策是最优的对策策略，如果支付矩阵无鞍点，则需要选择混合对策。我们回过头再看例9.1（“石头--剪子--布”），对于支付矩阵, 有

1

max min ,1min max =?=ij i

j

ij j

i

c c 没有纯最优策略。因此无法用定理9.1来确定最优策略。在这种情况下，只能求相应的混合策略。类似于纯策略，混合策略有如下定义和定理。

定义9.3

设有矩阵对策　G ＝｛S 1，S 2，C ｝称

)

5(,,,2,1,0,1|)

4(,,,2,1,0,1|1*21

*1?

?????=≥=∈=??????=≥=∈=∑∑==n j j i n

m

i i i m

n j y y R y S m i x x R x S L L 分别为局中人A 和B 的混合策略。称(x,y )(x ∈S 1*,y ∈S 2*)为一个混合局，称

为局中人A 的支付函数（赢得函数）。

)

6(),(11∑∑====m

i n

j j

i ij T

y x c Cy x y x E

定义9.4

设G *＝｛S 1*，S 2*，C ｝是 G ＝｛S 1，S 2，C ｝的混合扩充，若

)

7(),(max min ),(min max *

1

*2*2

*1

G S x S y S y S x v y x E y x E ==∈∈∈∈则称v G 为对策G *的值。称使式(7)成立混合局势

(x *, y , y*

*)为G 在混合策略下的解，称x *和y *分别为局中人A 和B 的最优混合策略。

定理9.4

矩阵对策　G ＝｛S 1，S 2，C ｝在混合策略意义下有解的充分必要条件是：存在 (x ∈S 1*,y ∈S 2*)

使(x *,y ,y*

*)为函数E (x,y )的一个鞍点，即()()())

8(.

,,

*,**,*,*2

*

1

S y S x y x E y x E y x E ∈?∈?≤≤

3. 混合对策求解方法

通常用线性规划方法求混合策略的解。设局中人A 分别以x 1,x 2, , …

…,x m 的概率混合使用他的m 种策略，局中人B 分别以y 1,y 2, , …

…,y m 的概率混合使用他的n 种策略。

∑=≥=m

i i i

x x

1

,1∑=≥=n

j j i

y y

1

,1

优化模型讲解 附LINGO程序

数学建模培训讲义 ——优化模型与LINGO软件 二○一一年七 目录 1 静态优化模型 (1) 1.1 最优生产计划问题 (1) 1.2 存贮模型 (2) 2 线性规划模型 (2) 2.1 LINGO简介 (2) 2.2 配料问题 (3) 2.3 练习：运输问题 (4) 3 整数规划模型 (4) 3.1 电影院广告问题 (4) 3.2 练习：生产计划问题 (5) 4 0-1规划 (5) 4.1 背包问题 (5) 4.2 矿井选址问题 (6) 4.3 练习：混合泳接力队的选拔问题 (7) 5 LINGO应用 (8) 5.1 变量定界函数 (8) 5.2 集合 (8) 5.3 帆船生产问题 (9)

5.4 派生集合 (11) 5.5 通过电子表格（Excel）文件传递数据 (12) 5.6 旅游问题 (13)

优化模型与LINGO 软件 优化问题是计划管理工作中经常要碰到的问题，比如，出门旅行就要考虑选择什么样的路线和交通工具，才能使旅行费用最省或使所花费的时间最少。在工厂技术、经济管理和科学研究等领域中，最优化问题就更多，一个工厂要怎样安排产品的生产，才能获得最大利润？一个设计部门要考虑在满足结构强度的要求下怎样使得所用的材料的总重量最轻？ 比较有效的求解优化问题的一个方法使数学规划，它包括：线性规划、非线性规划、整数规划、动态规划和多目标规划等等。 用数学建模的方法来处理一个优化问题的时候，首先要确定优化的目标是什么，寻求的决策是什么，决策受到哪些条件的限制（如果有限制的话），然后用数学工具（变量、函数等）表示它们。 1 静态优化模型 静态优化模型，归结为微积分中的函数极值问题，可以直接用微分法求解。 1.1 最优生产计划问题 一计算机公司引进A 、B 两种类型的芯片技术，总耗资400000元，准备生产这两种类型的芯片出售。生产一片A 芯片的成本为1950元，而市场售价为3390元，生产一片B 芯片的成本为2250元，而市场售价3990元。由于市场存在竞争，每售出一片A 芯片，A 芯片就会降价0.1元，并且令B 芯片降低0.04元，每售出一片B 芯片，B 芯片就会降价0.1元，并且令A 芯片降价0.03元。假设生产的芯片都能卖出，求一生产计划，以获得最大利润。 模型分析： 假设A 、B 两种芯片的数量分别是1x 和2x ，市场价格分别是1p 和2p ，用R 表示出售芯片的总收入，用C 表示生存芯片的总费用，用P 表示总利润。 根据题意，上述变量有如下关系： 11233900.10.03p x x =-- 21239900.040.1p x x =-- 1122R p x p x =+ 1240000019502250C x x =++ P R C =- 模型建立： 根据上述分析，可得优化模型

优化建模与lingo软件

问题一：LP 问题在lindo 和lingo 中不同的输入形式 （1）将目标函数的表示方式从“MAX ”变成了“MAX=” （2）“ST ”在LINGO 模型中不再需要，所以被删除了 （3）每个系数与变量间增加了运算符“*”（即乘号不能省略） （4）每行（目标、约束和说明语句）后面均增加了一个分号“;”(英文状态下) （5）模型结束标志“END ”也被删除了（LINGO 中只有当模型以“MODEL ：”开始时才能以“END ”结束）。 （6）英文状态下!后面的文字为说明文字，不参与模型的求解。 问题二：状态窗口的参数解释 variable adj 异变的，变量的 n 变量

问题三优化建模的实例： 1. 线性规划模型 2. 二次规划模型 3. 非线性规划模型 目标函数：()()∑∑--==+= 2161 22min j i bi yi ai xi cij f 约束条件:6,5,4,3,2,1,21 ∑===j i di cij ∑==<=6 1 2,1,i j ej cij 4. 整数规划模型（线性0-1规划模型是特殊的线性整数规划） 1) 目标函数：7654321min x x x x x x x z ++++++= 2) 约束条件: ???????????>=++++>=++++>=++++>=++++>=++++>=++++>=++++. 5076543,5065432,5054321,5074321,5076321,5076521,5076541x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x )7,,2,1(0 =>=i xi

运用LINGO进行优化模型求解,并与EXCEL进行连接

实验报告（二） 课程名称数学实验 实验项目运用LINGO进行优化模型求解，并与EXCEL进行连接实验环境PC机、LINGO 班级/学号/姓名 指导教师 实验日期2013-11-5 成绩

一、实验名称:运用LINGO 进行优化模型求解，并与EXCEL 进行连接 二、实验目的： 1、掌握Lingo 求解线性规划模型的方法及回看求解结果报告； 2、掌握Lingo 进行灵敏度分析的方法； 3、掌握Lingo 求解整数规划和0-1规划的方法； 4、掌握Lingo 中集合的定义方法； 5、掌握Lingo 与Excel 之间的链接方法； 三、实验内容： 习题四： 1.用LINGO 求解下列线性规划问题 （1）?????? ?=≥≤++≤++≤++++=. 4,...,1,0x 103x x 2x -4x 258x 2x 3x -3x 204x -4x -6x 5x ..8x 10x 2x 6x z max i 4321432143214 321i t s 程序： model : max =6*x1+2*x2+10*x3+8*x4; 5*x1+6*x2-4*x3-4*x4<=20; 3*x1-3*x2+2*x3+8*x4<=25; 4*x1-2*x2+x3+3*x4<=10; end 结果：

（2） ??? ??≥≤++≤++++=0,,x 9010x 4x 12x 20 3x x x -s.t.13x 5x -5x z max 3 213213213 21x x 程序： model : max =-5*x1+5*x2+13*x3; -1*x1+x2+3*x3<=20; 12*x1+4*x2+10*x3<=90; end 结果： （3）?? ???>=++<=+<=+=010y 4x 011-7y x 0 23-5y -7x ..y 2x z min t s 程序： model : min =2*x+y; 7*x-5*y-23<=0; x+7*y-11<=0; 4*x+y+10>=0; @free (x); @free (y); end 结果：

用lingo编程解决运输问题大全

LINGO是用来求解线性和非线性优化问题的简易工具。LINGO内置了一种建立最优化模型的语言，可以简便地表达大规模问题，利用LINGO高效的求解器可快速求解并分析结果。 当你在windows下开始运行LINGO系统时，会得到类似下面的一个窗口： 外层是主框架窗口，包含了所有菜单命令和工具条，其它所有的窗口将被包含在主窗口之下。在主窗口内的标题为LINGO Model –LINGO1的窗口是LINGO的默认模型窗口，建立的模型都都要在该窗口内编码实现。下面举两个例子。 例如何在LINGO中求解如下的LP问题：

,6002100 350. .32min 21211 2121≥≤+≥≥++x x x x x x x t s x x 在模型窗口中输入如下代码： min =2*x1+3*x2; x1+x2>=350; x1>=100; 2*x1+x2<=600; 然后点击工具条上的按钮 即可。 例 使用LINGO 软件计算6个发点8个收点的最小费用运输问题。产销单位运价如下表。 销地 产地 B 1 B 2 B 3 B 4 B 5 B 6 B 7 B 8 产量 A 1 6 2 6 7 4 2 5 9 60 A 2 4 9 5 3 8 5 8 2 55 A 3 5 2 1 9 7 4 3 3 51 A 4 7 6 7 3 9 2 7 1 43 A 5 2 3 9 5 7 2 6 5 41 A 6 5 5 2 2 8 1 4 3 52 销量 35 37 22 32 41 32 43 38

使用LINGO软件，编制程序如下： model: !6发点8收点运输问题; sets: warehouses/wh1..wh6/: capacity; vendors/v1..v8/: demand; links(warehouses,vendors): cost, volume; endsets !目标函数; min=@sum(links: cost*volume); !需求约束; @for(vendors(J): @sum(warehouses(I): volume(I,J))=demand(J)); !产量约束; @for(warehouses(I): @sum(vendors(J): volume(I,J))<=capacity(I)); !这里是数据; data: capacity=60 55 51 43 41 52; demand=35 37 22 32 41 32 43 38; cost=6 2 6 7 4 2 9 5 4 9 5 3 8 5 8 2 5 2 1 9 7 4 3 3 7 6 7 3 9 2 7 1 2 3 9 5 7 2 6 5