LINGO教程：目标规划与排队论详解

4星 · 超过85%的资源需积分: 41 42 浏览量更新于2024-07-25 3 收藏 2.4MB PDF 举报

"《LINGO教程大全》是一本深入讲解优化工具Lingo的教材，涵盖了目标规划、对策论模型和排队论模型等内容。全书共分为八章和九章，从基础概念到高级应用，全方位解析了如何在实际问题中构建和解决优化模型。第八章主要探讨目标规划模型，包括线性规划与目标规划的区别与局限性，目标规划的数学模型，如目标规划的基本概念、模型建立、一般模型以及求解方法——序贯式算法。章节中还通过实例演示了目标规划的应用，并介绍了数据包络分析这一工具，包括其基本概念、RC2模型和求解方法。第九章介绍对策论模型，重点讨论了二人常数和对策模型，区分了零和对策与常数和对策，以及纯对策和混合对策问题。随后扩展到n人合作对策的初步理解，通过习题强化理论学习。第十章深入探讨排队论模型，从基本概念开始，解释了排队服务系统的符号表示和关键数量指标，接着详细阐述了等待制、损失制、混合制排队模型，以及闭合式排队模型的特征和计算实例。最后，讲解了排队系统最优化模型，涉及服务时间和人员配置的确定。《LINGO教程大全》不仅涵盖了各种类型的优化模型，如线性、二次、非线性和整数规划，还包括了Lingo在解决这些模型中的实用技巧。通过逐章的学习，读者可以掌握如何使用Lingo进行模型构建和求解，从而解决实际工程中的复杂优化问题。此外，书中的习题设计有助于巩固理论知识，提升实践能力。"

类似地，有

，50

76521

 xxxxx

（18）

，50

76321

 xxxxx

（19）

，50

74321

 xxxxx

（20）

，80

54321

 xxxxx

（21）

，90

65432

 xxxxx

（22）

，90

76543

 xxxxx

（23）

虽然，人数总应该是整数，所以

≥0 （i=1，2，„，7）

其中

是整数。问题归结为在条件（17）～（24）下求解

zmin

的整数规划模型。由于目

标函数和约束条件关于决策变量都是线性函数，所以这是一个整数线性规划模型。

在 1.2.2 节介绍的生产和销售的二次规划模型中，如果我们要求生产的产品数量必须是证

书，那么问题将变成了一个证书二次规划模型，这是一种特殊的整数非线性规划模型。

可以用整数规划建立模型的实际问题非常多。例如，实际生活中可能遇到这样的分派或

选择问题：若干项任务分给一些候选人来完成，因为每个人的专长不同，他们完成每项任务

取得的效益或需要的资源就不一样，如何分派这些任务使获得的总效益最大，或付出的总资

源最少？也会遇到这样的选择问题：有若干种策略供选择，不同的策略得到的效益或付出的

成本不同，各个策略之间可以有相互制约关系，如何在满足一定条件下作出选择，使得收益

最大或最小或成本最小？下面介绍一个结局这种问题的 0-1 规划模型。

例 1.5 某班准备从 5 名游泳队员中选择 4 人组成接力对，参加学校的

m1004

混合泳接

力比赛。5 名队员 4 中泳姿的百米平均成绩如表 1-2 所示，问应如何选拔队员组成接力队？

表 1-2 5 名队员种泳姿的百米平均成绩

队员

甲

乙

丙

丁

戊

蝶泳

'*'06'1

2''57

''18'1

''10'1

4''07'1

仰泳

6''15'1

''06'1

8''07'1

2''14'1

''11'1

蛙泳

''27'1

4''06'1

6''24'1

6''09'1

8''23'1

自由水

6''58

''53

4''59

2''57

4''02'1

8''06'1*

表示 1 分 6.8 秒，这里沿了习惯表示法。

问题分析

问题要求从 5 名队员中选出 4 人组成接力队，每人一种泳姿，且 4 人的泳姿各不相同，

使接力队的成绩最好，容易想到的一个办法是穷举法，组成接力队的方案共有 5！=120 种，

逐一计算并作比较，即可找出最优方案，显然这不是解决这类问题的好办法，随着问题规模

的变大，空举法的计算量将是无法接受的。

可以用

可以用 0-1 变量表示一个队员是否入选接力队，从而建立这个问题的 0-1 规划模型，借

助现成的数学软件求解。

优化模型

记甲、乙、丙、丁、戊分别为队员 i=1,2,3,4,5;记蝶泳、仰泳、蛙泳、自由泳分别为泳姿

j=1,2,3,4.记队员 i 的第 j 种泳姿的百米最好成绩为

)(sc

，则表 1-2 可以表示成表 1-3.

表 1-3 5 名队员 4 种泳姿的百米平均成绩

i=1

i=2

i=3

i=4

i=5

j=1

66.8

57.2

67.4

j=2

75.6

67.8

74.2

j=3

66.4

84.60

69.6

83.8

J=4

58.6

59.4

57.2

62.4

决策变量：引入 0-1 变量

若选择队员 i 参加泳姿 j 的比赛，否则

0

xjij

，于是接

力队的成绩可以表示为



 



1j i

ijij

xcf

，这就是该问题的目标函数。

约束条件：根据组成接力队的要求，

应该满足下面两个约束条件：

（1）每人最多只能入选 4 种泳姿之一，即对于 i=1,2,3,4,5,应有







（2）每种泳姿必须有 1 人而且只能有 1 人入选，即对于 j=1,2,3,4,应有





综上所述，这个问题的优化模型可写作



 



;min

j i

ijij

xcf

}.1,0{

,4,3,2,1,1

,5,4,3,2,1,1..











ixts

这是一个线性 0-1 规划模型，它是一个特殊线性整数规划。一般来讲，对于整数规划问

题，即使是线性 0-1 规划问题，当问题的规模比较大时，求解也是非常困难的。虽然整数规

划问题的可行解通常只能有有限多个（如果可行域有界的话），可以通过枚举所有可行解比

较出最优解，但是对于规模限制，求解相应的线性规划或非线性规划问题（称为原问题对应

的松弛问题），然后将得到的解四舍五入到最接近的整数？在有些情况下，尤其当解的分量

是非常大的实数时，可能这些解对四舍五入不太敏感，那么这一策略可能是可行的，但在许

多实际应用中，整数变量的取值并不太大，如 0-1 规划问题中整数只取 0 或 1，因此这一方

法往往行不通。此外把松弛问题的解四舍五入到一个可行的整数解并非易事（参见例 1.6），

有时甚至找这样一个可行解与求解原问题本身的难度可能是一样的。

例1．6 求解整数规划问题

.0,

,4595

,6..

;85max

且为整数





IPxx

xxts

xxz

解将去掉整数限制后的松驰问题记叙 LP，其可行域为图 1-5 中由点（0，0），（6，0），

p(2.25,3.75),(0,5)围成的四边形，过 P 点的等值线（图中点划线）为

max

zz 

最优解在 P 点

取得，图中小圆点为整数点（也称为格点），四边形中的小圆点为原问题 IP 的可行解。

为了求 IP 的最优解，交款 P 舍入成整数或者找最靠近它的整数，都行不通。经过在可

行解中试探、比较可以得到表 1-4。可见 IP 的最优解不一定能从 LP 的最优解经过简单的“移

动”得到。

表 1-4 不同解的效果比较

LP 最优解为 P

P 的舍入解

最靠近 P 的可行解

IP 最优解

（2．25，3．75）

(2,4)

(2,3)

(0,5)

Z=41.25

不可行

Z=34

Z=40

求解整数规划没有统一的有效方法,不同方法的效果与问题的性质有很大关系.比较常用

的一种求解方法是分支定界法（branch and bound method），可看作对枚举法的一种改进。分

支定界法采用“分而治之”的策略求解整数规划，其基本思想是隐式地枚举一切可行解。自

然，这种枚举不是简单的完全枚举，而是以一种比较“聪明”的方式进行的，即逐次对解空

间进行划分。所谓分支，指的就是这个划分过程；而所谓定界，是指对于每个划分在求解过

程中判定是否需要对目前的解空间进一步划分，也就是尽可能去掉一些明显的非最优点，从

而避免完全枚举。分支定界算法的实际计算效果取决于具体的分支策略和定界方法，有兴趣

的读者看有关的专门书籍。

1．2．5 其他优化模型

实际中的许多优化决策问题，并不一定像上面的例子中的问题那样，很明显、很简单地

max

就能建立形如（1）、（ 2）、（3）的优化模型。这时可能需要利用较多的数学知识和技巧，才

能将决策问题转化、描述成形如（1）、（ 2）、（ 3）的优化模型。例如，和生产和运作管理中

的决策问题、经济与金融中的决策问题、图论和网络优化相关的决策问题、目标规划问题、

对策论中的决策问题、排队论中的决策问题、存储论中的决策问题，以及更加综合、更加复

杂的决策问题等。对这些方面的决策问题和优化建模方法，我们将介绍过 LINGO/LINGO 软

件的使用方法之后，从第 5 章一个专题一个专题地分别通实例进行介绍和讨论。

1．3 LINDO/LINGO 软件简介

1．3．1 LINGO/LINGO 软件的基本功能

美国芝加哥大学的 linus Schrage 教授于 1980 年前后开发了一套专门用于求解最优化问

题的软件包，后来又经过了多年的不断完善和扩充，并成立了 LINDO 系统公司（LINDO

Systens Inc.）进行商业化动作，取得了巨大成功，这套软件的主要产品有 4 种：LINDO，

LINGO，LINDO API 和 WHAT'SBEST!,在最优化软件的市场上占有很大的份额,尤其在供微

机上使用的最优化软件的市场上,上述软件产品具有绝对的优势。例如，根据 LINGO 公司主

页（HTTP://WWW.LINGO.CON）上提供的信息,位列全球《财富》杂志 500 强的企业中,一

半以上使用上述产品,其中位列全球《财富》杂志 25 强的企业中有 23 家使用上述产品，读

者可以从该公司的主页了解更多的信息，特别是可以从这个网页上下载上面 4 种软件的演示

版（试用版）和大量应用例子。演示版与正式版的基本功能是类似的，只是试用版能够求解

问题的规模（即决策变量和约束的个数）受到严格限制，对于规模稍微大些的问题就不能求

解。即使对于正式版式，通常也被分成求解包（SOLVER SUITE）、高级版（SUPER）、超级

版（HYPER）、工业版（INDUSTRIAL）、扩展版（EXTENDED）等不同档次的版式本，不

同档次的版本的区别也在于能够求解的问题的规模大小不同（参见表 1-5，只列出了 LINGO

软件的规模限制；LINGO 软件也类似，只是不能有非线性约束）。当然，规模越大的版式本

的销售价格也越昂贵（不过，所有的正式版对教育机构都有特殊的优惠价）。

表 1-5 不同版本 LINGO 程序对求解规模的限制

版本类型

总变量数

整数变量数

非线性变量数

约束数

演示版

300

150

求解包

500

250

高级版

2000

200

1000

超级版

8000

800

4000

工业版

32000

3200

16000

扩展版

无限

说明：通过“HELP|ABOUT…”菜单命令，就能知道你所安装的 LINGO/LINDO 软件

的版本和所能求解的规模了限制等相关的信息。

LINDO 是英文 LINEAR INTERACTIVE AND DIACRETE OPTIMIZER 字首的缩写形

式，即“交互式的线性离散优化求解器”，可以用来求解线性规划（LP）和二次规划

（QP）； LINGO 是英文 LINEAR INTERACTIVE AND GENERAL OPTIMIZER 字首的

缩写形式，即“交互式的线性和通用优化求解器”，它除了具有 LINGO 的全部功能外，

还可以用于求解非线性规划，也可以用于一些线性和非线性方程组的求解。LINDO 和

LINGO 软件的最大特色在于可以允许决策变量是整数（即整数规划，包括 0—1 规划），

而且执行速度很快。LINGO 实际上还是最优化问题的一种建模语言，包括许多常用的

数学函数供使用者建立优化模型时调用，并可以接受其他数据文件（如文本文件、Excel

电子表格文件、数据库文件等），即使对优化方面的专业知识了解不多的用户，也能

够方便地建模和输入、有效地求解和分析实际中遇到的大规模优化问题，并通常能够

快速得到复杂优化问题的高质量解。LINDO 和 LINGO 软件能求解的优化模型参见图

1—6。

此外，LINDO 系统公司还提供了 LINDO 和 LINGO 软件与其他开发工具（如 C++

和 Java 等语言）的接口软件 LINDO API（LINDO application program interface），

因此使 LINDO 和 LINGO 软件还能方便地融入到用户应用软件的开发中去。最后，

What‘sBest！实际上提供了 LINDO 和 LINGO 软件与电子表格软件（如 Excel 等）的

接口，能够直接集成到电子表格软件中使用。

由于上述特点，LINDO、LINGO、LINDO API 和 What‘sBest！软件在教学、科

研和工业、商业、服务等领域得到了广泛的应用。本书只详细介绍在 Microsoft windows

环境下运行的 LINDO 和 LINGO 软件最新版本（LINDO6.1、LINGO9.0）的使用方法，

并包括社会、经济、工程等方面的大量实际应用问题的数学建模和求解实例。需要指

出的是，目前 LINGO9.0 的功能完全包含了 LINDO 软件的功能（包括模型程序的书写

格式），所以 LINDO 公司已经将 LINDO 软件从产品目录中删除，这意味着以后不会

再有 LINDO 软件的新版本了。考虑到国内目前仍有不少读者使用 LINDO 软件，而且

LINDO 软件比起 LINGO 软件更容易入门和掌握，所以我们在本书中还是对 LINDO

软件进行一定的介绍，但把全书重点放在 LINGO 软件的使用上。

1.3.2 LINDO/LINGO 软件的求解过程

在进入后续章节的学习之前，先简单介绍一下 LINDO/LINGO 软件求解一个优化模

型的过程。实际上，使用 LINDO/LINGO 时，软件本身并不需要用户知道软件内部的

这些算法实际和调用方法。不过，如果对此有所了解，对于更有效地利用

LINDO/LINGO 软件解决实际问题，理解软件的运行状态和阅读结果报告、分析出错

信息等，还是有所帮助的。

LINDO/LINGO 软件内部有以下 4 个基本的求解程序用于求解不同类型的优化模

型（参见图 1—7）；

（1）直接求解程序（Direct Solver）。

（2）线性优化求解程序（Linear Solver）。

（3）非线性优化求解程序（Nonlinear Solver）。

（4）分支定界管理程序（Branch and Bound Manager）。

优化模型

整数规划

连续优化

线性规划

非线性规

划

二次规划

LINDO

LINGO

图 1-6 LINDO 和 LINGO 软件能求解的优化

模型

剩余147页未读，继续阅读

syusuke54

粉丝: 1
资源: 1

LINGO教程：目标规划与排队论详解

Lingo教程详解：从入门到建模实例

LINGO 8.0教程详解：高效解决复杂优化问题

LINGO18.0教程：交互式优化求解器详解

lingo教程大全

LINGO教程大全文档

LINGO教程大全.pdf

数学建模-LINGO教程大全.zip

lingo教程、lingo教程、lingo教程

经典lingo教程 经典lingo教程

LINGO学习教程，LINGO教程

最新资源

经典lingo教程经典lingo教程