运筹学实验教程

《运筹学实验教程》对历年来IBM ILOG OPL语言运用到运筹学教学工作的提炼和总结，内容包括IBM ILOG OPL语言在各种优化问题中的应用以及掌握和运用这门语言一些技巧、IBM ILOG OPL语言和IBM ILOG Script语言的相关介绍。本书系统地讲述了线性规划典型案例、运输问题的典型案例、整数规划问题案例、图与网络分析问题的案例以及绍调度问题的典型案例。
   本书可以做高等院校相关专业的《运筹学》课程的实践内容的参考书或者《优化建模》课程的参考书，也可以作为工程技术人员和对优化问题感兴趣的读者学习优化问题的参考书。同时也可以作为IBM ILOG OPL语言和IBM ILOG Script语言的语言参考手册。

 

本书共分为8章的内容，绪论首先介绍IBM ILOG OPL软件产品及在物流运筹学领域的应用；*章介绍建模语言，第二和第三章介绍脚本语言，第四章介绍线性规划问题的具体应用，第五章运输问题的应用，第六章介绍整数规划问题的应用，第七章介绍图与网络分析问题的应用，第八章介绍约束规划问题的应用。

赵立新，1990年9月-1994年7月 长春理工大学机械工程学院 机电一体化，1994年9月-1997年4月 长春理工大学研究生院 测试计量技术及仪器，2005年3月-2012年3月 北京工业大学机械工程及电子技术学院 机械电子工程，讲授课程：运筹学 物流运输与配送规划 数据结构 数据库原理及应用，资格认证： 高级物流师。教研：主持校级《运筹学》精品课程建设主持院级《数据库原理及应用》教学改革主持院级《运筹学》教学改革。科研：参与《基于神经网络的嵌入式智能脱扣器的研究》，国外访学：2007年10月到2008年2月，美国University of Minnesota访问学者。

第1章绪论1
1.1建模语言介绍1
1.2预备知识2
1.2.1程序设计语言2
1.2.2关系数据库3
1.2.3算法与数据结构4
1.3IBM ILOG OPL在运筹学实践教学中的应用4
1.3.1IBM ILOG CPLEX优化器4
1.3.2IBM ILOG CP优化器5
第2章运筹学与IBM ILOG OPL语言6
2.1运筹学实践6
2.2IBM ILOG OPL简介7
2.2.1集成开发环境IDE7
2.2.2优化编程语言IBM ILOG OPL8
2.2.3脚本语言IBM ILOG Script8
2.2.4应用程序接口(APIs)8
2.3IBM ILOG CPLEX Optimization Studio简介9
2.3.1软件相关资源链接9
2.3.2软件使用10
2.3.3OPL项目简介14
2.4IBM ILOG OPL语言和代数表达式16
2.5IBM ILOG OPL模型的数据组织19
2.6IBM ILOG OPL的优势21
第3章IBM ILOG OPL语言25
3.1IBM ILOG OPL基本数据类型25
3.2IBM ILOG OPL区间26
3.3IBM ILOG OPL集合27
3.4IBM ILOG OPL数组29
3.5IBM ILOG OPL结构体32
3.6IBM ILOG OPL数据一致性34
3.7IBM ILOG OPL决策变量和决策表达式35
3.8IBM ILOG OPL运算符和表达式37
3.9IBM ILOG OPL约束条件41
3.10形参42
第4章IBM ILOG Script语言45
4.1IBM ILOG Script语言简介45
4.2IBM ILOG Script数据类型47
4.3IBM ILOG Script数值运算符49
4.4IBM ILOG Script字符串49
4.5IBM ILOG Script控制语句52
4.6IBM ILOG Script数组55
4.7IBM ILOG Script流程控制57
4.8IBM ILOG Script文件读写59
第5章线性规划61
5.1线性规划问题的数学模型61
5.2线性规划的典型应用62
第6章运输问题86
6.1运输问题的数学模型86
6.2产销平衡运输问题的OPL模型87
6.3可转化为运输问题的生产计划问题88
6.4转运问题90
6.5多品种物资调度问题98
第7章整数规划106
7.1整数规划的数学模型106
7.201整数规划107
7.3布尔型决策变量在非01规划中的应用112
7.4集合覆盖问题117
第8章图与网络分析124
8.1最短路径问题124
8.2最大流问题128
第9章网络计划133
9.1IBM ILOG CP简介133
9.2决策变量和约束条件133
9.3应用139
参考文献161

运筹学是一门将数学理论和方法应用于解决实际问题的课程。运筹学研究解决实际问题时的系统优化思想，以及从提出问题、分析建模、求解到方案实施的一整套严密的科学方法，在培养和提高人才的素养上起到重要作用。同时，该课程也是一门理论与实践相结合的课程。
IBM ILOG OPL作为优化建模语言，功能强大且精致。IBM ILOG  Script作为编程语言，集各家程序设计语言所长于一身，语言优美且易用。
本书第2章第2.6节由IBM公司的崔友志编写，其他部分均由赵立新编写。本书浅显易懂，但因为优化问题本身有难度，加上编著者能力有限，书中难免存在不足之处，诚恳欢迎读者提出([email protected])，以便再版时给予更正。
本书配有教学用PPT、实验指导书和案例答案，部分内容配有视频讲解，有需求的读者可以联系清华大学出版社索取。
非常感谢在本书的编写过程中给予我帮助和支持的我的同事、清华大学出版社的朋友、IBM公司的朋友，还有我的家人。王秀英老师对本书前4章进行了校对，清华大学出版社的多位编辑在本书的签约和出版过程中给予了莫大的支持与帮助，IBM公司的崔友志为本书增添了亮点。

编著者
2019年3月

第3章IBM ILOG OPL语言3.1IBM ILOG OPL基本数据类型
IBM ILOG OPL基本数据类型包括整型(int)、浮点型(float)、字符串型(string)和布尔型(boolean)。IBM ILOG OPL语言中的常量分为整型常量、浮点型常量、字符串型常量和布尔型常量。在其他编程语言中，代表这些常量的标识符如果允许值被改变，则称为变量，如整形变量、浮点型变量、字符串型变量和布尔型变量；如果不允许值被改变，则称为符号常量。在IBM ILOG OPL模型中，代表这些常量的标识符在模型运行过程中值保持不变(通过IBM ILOG Sricpt脚本语言修改除外)，因此在IBM ILOG OPL中这些标识符被称为数据，如整型数据、浮点型数据、字符串型数据和布尔型数据。标识符的命名原则是: 以字母(a~z和A~Z)、下划线(_)开头，由字母、数字(0~9)和下划线构成的一个符号系列。
1. 整型常量和整型数据
IBM ILOG OPL的整型常量采用十进制表示。IBM ILOG OPL预定义了一个整型符号常量maxint，代表OPL中能够存储的最大正整数，因此，IBM ILOG OPL整型数的范围为-maxint到maxint。
【例31】定义整型数i，初始化为25。int i = 25;【例32】定义整型数n，并把n初始化为3。然后，定义整型数size，并把size初始化为n2。int n = 3;
int size = nn;2. 浮点型常量和浮点型数据
IBM ILOG OPL提供了双精度的浮点型数据类型(符合IEEE 754标准)。浮点型常量采用十进制或科学计数法表示。OPL预定义了一个浮点型符号常量infinity，代表无穷大。
【例33】定义浮点数f，初始化为3.2。float f = 3.2;3. 字符串型常量和字符串型数据
OPL提供了字符串型数据类型。字符串型常量是用“”括起来的字符的集合。字符串型常量中支持转义字符。〖1〗运筹学实验教程第3章IBM ILOG OPL语言〖3〗【例34】定义一个字符串s，并初始化为“hello world!”。string s=”hello world!”;字符串主要用于定义字符串集合，做数组下标。
【例35】定义了一个字符串集合Tasks代表工序的集合，并进行了初始化，然后可以定义数组Duration存储每道工序需要的时间，集合Tasks中的字符串用作数组下标。{string} Tasks={“masonry”,”carpentry”,”plumbing”,”ceiling”, “roofing”, “painting”, “windows”, “facade”, “garden”,”moving”};
int Duration［Tasks］=［10,4,6,3,6,3,2,5,6,7］;字符串中允许包含转义字符，转义字符的表示形式和含义如表31所示。表31转义字符的表示形式和含义
转 义 字 符含义\n新行\t制表符\\\\””\’’转 义 字 符含义\b退格\f换页\r回车\xhhASCII码为十六进制数hh的字符\oooASCII码为八进制数ooo的字符4. 布尔型常量和布尔型数据
IBM ILOG OPL提供了布尔型数据类型。布尔型常量只有true和false，代表真和假。定义布尔型数据类型时使用关键字boolean。布尔型数据类型限定数据只能取true或false两个值。布尔型数据类型主要是用于定义布尔型决策变量，或者在条件约束中用于决定哪些约束条件有效。
【例36】定义一个布尔型数据flag，用于条件约束。boolean flag=true;
if (flag==true)
{
约束条件1
}
else
{
约束条件2
}
3.2IBM ILOG OPL区间
OPL提供了区间(range)这个复杂的数据结构，主要用作数组的下标、迭代区间和定义形参的取值范围。
1. 区间的定义
区间的定义是通过给定下限值和上限值的方式定义能够表达区间的数据。range区间名=区间下限..区间上限【例37】定义一个区间数据Rows，代表整数区间［1，10］。range Rows = 1..10;区间的下限值和上限值可以使用表达式。
【例38】用表达式定义区间。int n = 8;
range Rows = n 1..2n 1; 2. 区间的用途
(1) 用途1: 整型区间用作数组下标。
【例39】定义具有100个元素的整型数组A，数组下标从1到100。range R = 1..100;
int A［R］; (2) 用途2: 整型区间用作形参的迭代范围。
【例310】建立一个循环，形参迭代范围是1到100。range R = 1..100;
   forall(i in R){ 循环体… } (3) 用途3: 整型区间用作整型决策变量的取值范围。
【例311】定义一个整型决策变量i，取值在［1，100］。range R = 1..100;
dvar int i in R;(4) 用途4: 浮点型区间用于定义浮点型决策变量的取值范围。
【例312】定义一个浮点数区间［1.0，100.0］，作为决策变量x的取值范围。range float X=1.0..100.0;
dvar float x in X;
3.3IBM ILOG OPL集合
OPL提供集合(set)这个复杂的数据结构，主要用作数组的下标。集合是非索引无重复元素的集合。OPL允许定义任何类型的集合。
1. 集合的定义
假设T是个数据类型，可以使用{T}或者setof(T)定义集合数据。
【例313】定义整型集合setInt。{int} setInt = …;【例314】定义结构体类型为Precedence的集合。setof(Precedence) precedences = …;默认情况下，集合元素是按照创建的顺序排列的。
2. 集合的初始化
OPL集合的初始化可以分为两种: 一种是内部初始化，在模型文件(.mod)中完成；另一种是外部初始化，在数据文件(.dat)中完成。
(1) 集合的内部初始化。在模型文件中，定义集合的同时使用{}对集合进行赋值。这种初始化方式导致数据在脚本代码中不能使用。
【例315】初始化集合Week为”Mon”, “Tu”, “Wed”, “Thu”, “Fri”, “Sat”,”Sun”。{string} Week={“Mon”, “Tu”, “Wed”, “Thu”, “Fri”, “Sat”, “Sun”};使用asSet内置函数和区间数据初始化集合。
【例316】使用区间［1..10］初始化集合s。{int} s= asSet(1..10) ;s被初始化为{1,2,..,10}。asSet功能是将range数据转换为集合数据。
【例317】初始化集合s为{1，4，7，10}。{int} s={i| i in 10:i mod 3==1};(2) 集合的外部初始化。在独立的数据文件中使用{}给出集合元素的值。
【例318】集合的外部初始化。
在模型文件中声明整型集合a: {int} a= …; 在数据文件中进行集合的初始化: a= {10, 20, 30, 40, 50, 60};【例319】使用数据库表初始化集合。
公交车的班次信息存储在Access数据库bus.accdb的“发车时刻表”中。在IBM ILOG OPL模型中定义公交车班次时刻表结构体shift。定义shift类型的Shifts结构体集合，数据表中公交车的班次信息将存储于Shifts中。tuple shift{
string ID;
int hour;
int minute;
}
{shift} Shifts=…;在数据文件中添加如下语句: DBConnection db(“access”,”bus.accdb”);
Shifts from DBRead(db,”select ID,hour,minute from发车时刻表”);【例320】使用工作表初始化集合。
城区的交通路口信息存储于名为”cumcm2011B.xls”的Excel文件的“全市交通路口的路线”工作表中。定义结构体adj代表邻接表的结构，定义adj类型的connectionstmp结构体集合，工作表中数据将存储于connectionstmp集合中。tuple adj
{
int o;
int d;
float dist;
}
{adj}connectionstmp=…;在数据文件中添加如下语句: SheetConnection sheet(“cumcm2011B.xls”);
connectionstmp from SheetRead(sheet,”‘全市交通路口的路线’!A2:B929″);
3.4IBM ILOG OPL数组1. 数组的定义IBM ILOG OPL的数组定义必须给出数组的下标范围。下标范围可以是区间，可以是集合，可以是整数集合或字符串集合，也可以是结构体集合。
(1) 一维数组。一维数组是最简单的数组，定义一维数组需要说明数组元素的类型和下标范围。
【例321】定义具有4个元素的整型数组a，数组元素分别为10，20，30和40，4个数组元素的引用下标分别为1，2，3和4。int a［1..4］ = ［10, 20, 30, 40］; 其中，区间1..4是下标值域；10, 20, 30, 40分别是通过下标值引用的数组元素的值。
【例322】定义具有4个元素的浮点型数组f，4个元素分别为1.2，2.3，3.4和4.5，4个元素的下标分别为5，6，7和8。float f［5..8］ = ［1.2, 2.3, 3.4, 4.5］;其中，区间5..8是下标值域；1.2, 2.3, 3.4, 4.5分别是通过下标值引用的数组元素的值。
【例323】定义一个字符串数组d，其数组元素分别为d［1］= “Monday”和d［2］=”Wednesday”。string d［1..2］ = ［”Monday”, “Wednesday”］;【例324】定义一个整型数组a，数组元素的值为a［”Mon”］=10，…，a［”Sun”］=70。
首先定义一个字符串集合Week: {string} Week={“Mon”, “Tu”, “Wed”, “Thu”, “Fri”, “Sat”, “Sun”};