LINGO软件与数学建模 陈国华 湖南人文科技学院数学系

Presentation on theme: "LINGO软件与数学建模 陈国华 湖南人文科技学院数学系"— Presentation transcript:

1 LINGO软件与数学建模 陈国华 湖南人文科技学院数学系
数学建模讲座（2006年8月） LINGO软件与数学建模 陈国华 湖南人文科技学院数学系

2 提 纲 LINGO软件功能简介 2. LINGO软件的使用简介 3.建模与求解实例（结合软件使用）

3 1. LINGO软件功能简介

4 LINGO软件的求解过程 1. 确定常数 2. 识别类型 LINGO预处理程序 LP QP NLP IP 全局优化(选)
ILP IQP INLP 分枝定界管理程序 线性优化求解程序 非线性优化求解程序 1、顺序线性规划法(SLP) 2、广义既约梯度法(GRG) (选) 3、多点搜索(Multistart) (选) 1. 单纯形算法 2. 内点算法(选)

5 2. LINGO软件的使用简介

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

7 利用LINGO求解简单的LP问题： 在模型窗口中输入如下代码： min=2*x1+3*x2; x1+x2>=350;
然后点击工具条上的按钮 即可。

8 Global optimal solution found at iteration: 4
Objective value: Variable Value Reduced Cost X X Row Slack or Surplus Dual Price

9 LINGO模型 — 例：选址问题 某公司有6个建筑工地，位置坐标为(ai, bi) (单位：公里),水泥日用量di (单位：吨）
假设：料场和工地之间有直线道路

10 决策变量：ci j (料场j到工地i的运量）~12维
线性规划模型 用例中数据计算，最优解为 总吨公里数为136.2

11 选址问题：NLP 2）改建两个新料场，需要确定新料场位置(xj,yj)和运量cij ，在其它条件不变下使总吨公里数最小。 决策变量：
ci j，(xj,yj)~16维 非线性规划模型

12 LINGO模型的构成：4个段 局部最优：89.8835(吨公里 ) 集合段（SETS ENDSETS） 数据段（DATA ENDDATA）
LP：移到数据段 初始段（INIT ENDINIT） 目标与 约束段 局部最优： (吨公里 )

13 边界

14 LINGO需要掌握的几个重要方面 掌握集合(SETS)的应用； 正确阅读求解报告； 正确理解求解状态窗口； 学会设置基本的求解选项(OPTIONS) ； 掌握与外部文件的基本接口方法

15 LINGO软件简介 LINGO模型的优点 LINGO模型的构成：5个段 包含了LINDO的全部功能 提供了灵活的编程语言（矩阵生成器）
目标与约束段 集合段（SETS ENDSETS） 数据段（DATA ENDDATA） 初始段（INIT ENDINIT） 计算段 (CALC ENDCALC) - LINGO9.0

16 LINGO中的集 集是一群相联系的对象，这些对象也称为集的成员。一个集可能是一系列产品、卡车或雇员。每个集成员可能有一个或多个与之有关联的特征，我们把这些特征称为属性。属性值可以预先给定，也可以是未知的，有待于LINGO求解。例如，产品集中的每个产品可以有一个价格属性；卡车集中的每辆卡车可以有一个牵引力属性；雇员集中的每位雇员可以有一个薪水属性，也可以有一个生日属性等等。 LINGO有两种类型的集：原始集(primitive　set)和派生集(derived set)。 一个原始集是由一些最基本的对象组成的。 一个派生集是用一个或多个其它集来定义的，也就是说，它的成员来自于其它已存在的集。

17 模型的集部分:定义原始集 集部分是LINGO模型的一个可选部分。在LINGO模型中使用集之前，必须在集部分事先定义。集部分以关键字“sets:”开始，以“endsets”结束。一个模型可以没有集部分，或有一个简单的集部分，或有多个集部分。一个集部分可以放置于模型的任何地方，但是一个集及其属性在模型约束中被引用之前必须定义了它们 . 定义一个原始集，用下面的语法： setname[/member_list/][:attribute_list]; 注意：用“[]”表示该部分内容可选。下同，不再赘述。 Setname是你选择的来标记集的名字，最好具有较强的可读性。集名字必须严格符合标准命名规则：以拉丁字母或下划线（_）为首字符，其后由拉丁字母（A—Z）、下划线、阿拉伯数字（0，1，…，9）组成的总长度不超过32个字符的字符串，且不区分大小写。 注意：该命名规则同样适用于集成员名和属性名等的命名。

18 集的显示方式 Member_list是集成员列表。如果集成员放在集定义中，那么对它们可采取显式罗列和隐式罗列两种方式。如果集成员不放在集定义中，那么可以在随后的数据部分定义它们。 ① 当显式罗列成员时，必须为每个成员输入一个不同的名字，中间用空格或逗号搁开，允许混合使用。 例1 可以定义一个名为students的原始集，它具有成员John、Jill、Rose和Mike，属性有sex和age： sets: students/John Jill, Rose Mike/: sex, age; endsets

19 ② 当隐式罗列成员时，不必罗列出每个集成员。可采用如下语法：
setname/member1..memberN/[: attribute_list]; 这里的member1是集的第一个成员名，memberN是集的最末一个成员名。LINGO将自动产生中间的所有成员名。LINGO也接受一些特定的首成员名和末成员名，用于创建一些特殊的集。列表如下：

20 集合元素的隐式列举 类型 隐式列举格式 示例 示例集合的元素 数字型 1..n 1..5 1, 2, 3, 4, 5 字符-数字型
stringM..stringN Car101..car208 Car101, car102, … , car208 星期型 dayM..dayN MON..FRI MON, TUE, WED, THU, FRI 月份型 monthM..monthN OCT..JAN OCT, NOV, DEC, JAN 年份-月份型 monthYearM..monthYearN OCT2001..JAN2002 OCT2001, NOV2001, DEC2001, JAN2002

21 ③ 集成员不放在集定义中，而在随后的数据部分来定义。
例 !集部分; sets: students:sex,age; endsets !数据部分; data: students,sex,age= John 1 16 Jill Rose Mike ; enddata 注意：开头用感叹号（!），末尾用分号（;）表示注释，可跨多行。 在集部分只定义了一个集students，并未指定成员。在数据部分罗列了集成员John、Jill、Rose和Mike，并对属性sex和age分别给出了值

22 定义派生集 setname(parent_set_list)[/member_list/][:attribute_list];
用下面的语法定义一个派生集： setname(parent_set_list)[/member_list/][:attribute_list]; setname是集的名字。parent_set_list是已定义的集的列表，多个时必须用逗号隔开。如果没有指定成员列表，那么LINGO会自动创建父集成员的所有组合作为派生集的成员。派生集的父集既可以是原始集，也可以是其它的派生集。 例 sets: product/A /; machine/M N/; allowed(product,machine):x; endsets LINGO生成了2个父集的所有组合共2组作为allowed集的成员。列表如下： 编号 成员 (A,M) 2                          (A,N)

23 成员列表被忽略时，派生集成员由父集成员所有的组合构成，这样的派生集成为稠密集。如果限制派生集的成员，使它成为父集成员所有组合构成的集合的一个子集，这样的派生集成为稀疏集。同原始集一样，派生集成员的声明也可以放在数据部分。一个派生集的成员列表有两种方式生成：①显式罗列；②设置成员资格过滤器。当采用方式①时，必须显式罗列出所有要包含在派生集中的成员，并且罗列的每个成员必须属于稠密集。使用前面的例子，显式罗列派生集的成员： allowed(product,machine,week)/A M 1,A N 2,B N 1/; 如果需要生成一个大的、稀疏的集，那么显式罗列就很讨厌。幸运地是许多稀疏集的成员都满足一些条件以和非成员相区分。我们可以把这些逻辑条件看作过滤器，在LINGO生成派生集的成员时把使逻辑条件为假的成员从稠密集中过滤掉。

24 例 sets: !学生集：性别属性sex，1表示男性，0表示女性；年龄属性age. ; students/John,Jill,Rose,Mike/:sex,age; !男学生和女学生的联系集：友好程度属性friend，[0，1]之间的数。 ; linkmf(students,students)|sex(&1) #eq# 1 #and# sex(&2) #eq# 0: friend; !男学生和女学生的友好程度大于0.5的集; linkmf2(linkmf) | friend(&1,&2) #ge# 0.5 : x; endsets data: sex,age = 1 16 0 14 0 17 0 13; friend = ; enddata

25 用竖线（|）来标记一个成员资格过滤器的开始。#eq#是逻辑运算符，用来判断是否“相等”，&1可看作派生集的第1个原始父集的索引，它取遍该原始父集的所有成员；&2可看作派生集的第2 个原始父集的索引，它取遍该原始父集的所有成员；&3，&4，……，以此类推。注意如果派生集B的父集是另外的派生集A，那么上面所说的原始父集是集A向前回溯到最终的原始集，其顺序保持不变，并且派生集A的过滤器对派生集B仍然有效。因此，派生集的索引个数是最终原始父集的个数，索引的取值是从原始父集到当前派生集所作限制的总和。

26 总的来说，LINGO可识别的集只有两种类型：原始集和派生集。
另一方面，派生集是由其它的集来创建。这些集被称为该派生集的父集（原始集或其它的派生集）。一个派生集既可以是稀疏的，也可以是稠密的。稠密集包含了父集成员的所有组合（有时也称为父集的笛卡尔乘积）。稀疏集仅包含了父集的笛卡尔乘积的一个子集，可通过显式罗列和成员资格过滤器这两种方式来定义。显式罗列方法就是逐个罗列稀疏集的成员。成员资格过滤器方法通过使用稀疏集成员必须满足的逻辑条件从稠密集成员中过滤出稀疏集的成员。不同集类型的关系见下图。

27 集合的类型 集合 派生集合 基本集合 稀疏集合 稠密集合 元素列表法 元素过滤法 直接列举法 隐式列举法
setname(parent_set_list) [/member_list/] [: attribute_list]; setname [/member_list/] [: attribute_list]; 集合 派生集合 基本集合 稀疏集合 稠密集合 元素列表法 元素过滤法 直接列举法 隐式列举法 SETS: CITIES /A1,A2,A3,B1,B2/; ROADS(CITIES, CITIES)/ A1,B1 A1,B2 A2,B1 A3,B2/:D; ENDSETS SETS: STUDENTS /S1..S8/; PAIRS( STUDENTS, STUDENTS) | &2 #GT# &1: BENEFIT, MATCH; ENDSETS

28 模型的数据部分 数据部分以关键字“data:”开始，以关键字“enddata”结束。在这里，可以指定集成员、集的属性。其语法如下：
object_list = value_list; 对象列（object_list）包含要指定值的属性名、要设置集成员的集名，用逗号或空格隔开。一个对象列中至多有一个集名，而属性名可以有任意多。如果对象列中有多个属性名，那么它们的类型必须一致。如果对象列中有一个集名，那么对象列中所有的属性的类型就是这个集。 数值列（value_list）包含要分配给对象列中的对象的值，用逗号或空格隔开。注意属性值的个数必须等于集成员的个数。

29 例4 sets: set1/A,B,C/: X,Y; endsets data: X=1,2,3; Y=4,5,6; enddata 在集set1中定义了两个属性X和Y。X的三个值是1、2和3，Y的三个值是4、5和6。

30 可采用如下例子中的复合数据声明(data statement)实现同样的功能。
sets: set1/A,B,C/: X,Y; endsets data: X,Y=1 4 2 5 3 6; enddata 看到这个例子，可能会认为X被指定了1、4和2三个值，因为它们是数值列中前三个，而正确的答案是1、2和3。假设对象列有n个对象，LINGO在为对象指定值时，首先在n个对象的第1个索引处依次分配数值列中的前n个对象，然后在n个对象的第2个索引处依次分配数值列中紧接着的n个对象，……，以此类推。 模型的所有数据——属性值和集成员——被单独放在数据部分，这可能是最规范的数据输入方式。

31 参数 在数据部分也可以指定一些标量变量（scalar variables）。当一个标量变量在数据部分确定时，称之为参数。看一例，假设模型中用利率8.5%作为一个参数，就可以象下面一样输入一个利率作为参数。 例6 data: interest_rate = .085; (interest_rate ,inflation_rate= ) enddata 也可以同时指定多个参数。

32 模型的初始部分 初始部分是LINGO提供的另一个可选部分。在初始部分中，可以输入初始声明（initialization statement），和数据部分中的数据声明相同。对实际问题的建模时，初始部分并不起到描述模型的作用，在初始部分输入的值仅被LINGO求解器当作初始点来用，并且仅仅对非线性模型有用。和数据部分指定变量的值不同，LINGO求解器可以自由改变初始部分初始化的变量的值。 一个初始部分以“init:”开始，以“endinit”结束。初始部分的初始声明规则和数据部分的数据声明规则相同。也就是说，我们可以在声明的左边同时初始化多个集属性，可以把集属性初始化为一个值，可以用问号实现实时数据处理，还可以用逗号指定未知数值。

33 lingo运算符的优先级 三类运算符： 算术运算符 逻辑运算符 关系运算符 优先级 运算符 最高 #NOT# —（负号） ^ * /
算术运算符 逻辑运算符 关系运算符 优先级 运算符 最高 #NOT# —（负号） ^ * / + —（减法） #EQ# #NE# #GT# #GE# #LT# #LE# #AND# #OR# 最低 <(=) = >(=)

34 变量界定函数 变量界定函数实现对变量取值范围的附加限制，共4种： @bin(x) 限制x为0或1 @bnd(L,x,U) 限制L≤x≤U
@free(x) 取消对变量x的默认下界为0的限制，即x可以取任意实数 @gin(x) 限制x为整数

35 集操作函数 1．@in(set_name,primitive_index_1 [,primitive_index_2,…])
如果元素在指定集中，返回1；否则返回0。 例 全集为I，B是I的一个子集，C是B的补集。 sets: I/x1..x4/; B(I)/x2/; endsets primitive_set_element) 该函数返回在集set_name中原始集成员primitive_set_element的索引。如果set_name被忽略，那么LINGO将返回与primitive_set_element匹配的第一个原始集成员的索引。如果找不到，则产生一个错误。 例 如何确定集成员(B,Y)属于派生集S3。 S1/A B C/; S2/X Y Z/; S3(S1,S2)/A X, A Z, B Y, C X/;

36 该函数返回j=index-k*limit，其中k是一个整数，取适当值保证j落在区间[1，limit]内。该函数相当于index模limit再加1。该函数在循环、多阶段计划编制中特别有用。 该函数返回集set_name的成员个数。在模型中明确给出集大小时最好使用该函数。它的使用使模型更加数据中立，集大小改变时也更易维护。

37 集循环函数 集循环函数遍历整个集进行操作。其语法为
@function(setname[(set_index_list)[|conditional_qualifier]]: expression_list); @function相应于FOR、SUM 、 MAX、MIN四个集循环函数之一；setname是要遍历的集；set_

38 1．@for 该函数用来产生对集成员的约束。基于建模语言的标量需要显式输入每个约束，不过@for函数允许只输入一个约束，然后LINGO自动产生每个集成员的约束。
例 产生序列{1,4,9,16,25} model: sets: number/1..5/:x; endsets @for(number(I): x(I)=I^2); end 例 求向量[5，1，3，4，6，10]前5个数的和。 data: N=6; enddata number/1..N/:x; x = ; | I #le# 5: x);

39 返回指定的集成员的一个表达式的最小值或最大值。 例 求向量[5，1，3，4，6，10]前5个数的最小值，后3个数的最大值。 model: data: N=6; enddata sets: number/1..N/:x; endsets x = ; | I #le# 5: x); | I #ge# N-2: x); End 看一个稍微复杂的例子

40 集合循环函数 四个集合循环函数：FOR、SUM 、 MAX、MIN Example:
@function( setname [ ( set_index_list)[ | condition]] : expression_list); Example: [objective] MAX PAIRS( I, J): BENEFIT( I, J) * MATCH( I, J)); @FOR(STUDENTS( I): [constraints] @SUM( PAIRS( J, K) | J #EQ# I #OR# K #EQ# I: MATCH( J, K)) =1); @FOR(PAIRS( I, MATCH( I, J))); I, J): BENEFIT( I, J)); I, J): BENEFIT( I, J));

41 状态窗口 Model Class: LP， QP，ILP， IQP，PILP, PIQP，NLP，INLP，PINLP State:
Global Optimum Local Optimum Feasible Infeasible Unbounded Interrupted Undetermined Solver Type: B-and-B Global Multistart

42 7个选项卡(可设置80-90个控制参数)

43 使用外部数据文件 Cut (or Copy) – Paste 方法 @FILE 输入数据、@TEXT输出数据（文本文件）
@OLE函数与电子表格软件（如EXCEL）连接 @ODBC函数与数据库连接 LINGO命令脚本文件 程序与数据分离 LG4 （LONGO模型文件） LNG （LONGO模型文件） LTF （LONGO脚本文件） LDT （LONGO数据文件） LRP （LONGO报告文件） 文 本 件 常用文件后缀

44 @FILE和@TEXT：文本文件输入输出
MODEL: SETS: MYSET / ENDSETS MIN MYSET( I): SHIP( I) * COST( I)); @FOR( MYSET( I): [CON1] SHIP( I) > NEED( I); [CON2] SHIP( I) < SUPPLY( I)); DATA: COST NEED SUPPLY @DUAL(CON1); ENDDATA END myfile.txt文件 的内容、格式： Seattle,Detroit,Chicago,Denver~ COST,NEED,SUPPLY,SHIP~ 12,28,15,20~ 1600,1800,1200,1000~ 1700,1900,1300,1100 演示 MyfileExample.lg4

45 @OLE函数 @OLE只能在lingo模型中的集合段，数据段和初始段使用
格式为： @OLE(speadsheet_file[,range_name_list]) 其中speadsheet_file是电子表格名称应当包括扩展名（如mydata.xls），

46 @OLE可以同时读集成员和集属性，集成员最好用文本格式，集属性最好用数值格式。原始集每个集成员需要一个单元(cell)，而对于n元的派生集每个集成员需要n个单元，这里第一行的n个单元对应派生集的第一个集成员，第二行的n个单元对应派生集的第二个集成员，依此类推。 @OLE只能读一维或二维的Ranges（在单个的EXCEL工作表(sheet)中），但不能读间断的或三维的Ranges。Ranges是自左而右、自上而下来读。

47 例 sets: PRODUCT; !产品; MACHINE; !机器; WEEK; !周; ALLOWED(PRODUCT,MACHINE,WEEK):x,y; !允许组合及属性; endsets data: rate=0.01; @OLE('D:\IMPORT.XLS')=rate; enddata 代替在代码文本的数据部分显式输入形式，我们把相关数据全部放在如下电子数据表中来输入。下面是D:\IMPORT.XLS的图表。

48 除了输入数据之外，我们也必须定义Ranges名：PRODUCT，MACHINE，WEEK，ALLOWED，x，y
除了输入数据之外，我们也必须定义Ranges名：PRODUCT，MACHINE，WEEK，ALLOWED，x，y. 明确的，我们需要定义如下的Ranges名： Name Range PRODUCT B3:B4 MACHINE C3:C4 WEEK D3:D5 ALLOWED B8:D10 X F8:F10 Y G8:G10 rate C13 为了在EXCEL中定义Ranges名： ① 按鼠标左键拖曳选择Range， ② 释放鼠标按钮， ③ 选择“插入|名称|定义”， ④ 输入希望的名字， ⑤ 点击“确定”按钮。

49

50 我们在模型的数据部分用如下代码从EXECL中引入数据：
@OLE('D:\IMPORT.XLS')=rate; 等价的描述为 PRODUCT,MACHINE,WEEK,ALLOWED,x,y PRODUCT,MACHINE,WEEK,ALLOWED,x,y); @OLE('D:\IMPORT.XLS',rate)=rate; 这一等价描述使得变量名和Ranges不同亦可。

51 @OLE ：与EXCEL连接 mydata.xls文件中必须有下列名称(及数据)：
MODEL: SETS: MYSET: COST,SHIP,NEED,SUPPLY; ENDSETS MIN MYSET( I): SHIP( I) * COST( I)); @FOR( MYSET( I): [CON1] SHIP( I) > NEED( I); [CON2] SHIP( I) < SUPPLY( I)); DATA: MYSET COST,NEED,SUPPLY @OLE(mydata.xls,'SOLUTION')=SHIP; ENDDATA END mydata.xls文件中必须有下列名称(及数据)： CITIES， COST，NEED，SUPPLY，SOLUTION 演示 MydataExample.lg4 在EXCEL中还可以通过“宏”自动调用LINGO(略) 也可以将EXCEL表格嵌入到LINGO模型中(略)

52 @ODBC ：与数据库连接 使用数据库之前，数据源需要在ODBC管理器注册 具体例子略
目前支持下列DBMS: (如为其他数据库，则需自行安装驱动) ACCESS， DBASE，EXCEL，FOXPRO，ORACLE， PARADOX，SQL SERVER， TEXE FILES 输入基本集合元素： [, ‘tablename’ [, ‘columnname’]]])/ 输入派生集合元素： [, ‘column1’[, ‘column2’…]]]])/ 输入数据： [, ‘column1’[, ‘column2’…]]]]) 输出数据： @ODBC([‘source’[,‘table’ [, ‘column1’[, ‘column2’…]]]])= Attr_list 具体例子略

53 LINGO菜单 1． 求解模型（Slove） 从LINGO菜单中选用“求解”命令、单击“Slove”按钮或按Ctrl+S组合键可以将当前模型送入内存求解。 2． 求解结果．．．（Solution．．．） 从LINGO菜单中选用“Solution．．．”命令、单击“Solution．．．”按钮或直接按Ctrl+O组合键可以打开求解结果的对话框。这里可以指定查看当前内存中求解结果的那些内容。 3． 查看．．．（Look．．．） 从LINGO菜单中选用“Look．．．”命令或直接按Ctrl+L组合键可以查看全部的或选中的模型文本内容。 4． 灵敏性分析（Range，Ctrl+R） 用该命令产生当前模型的灵敏性分析报告：研究当目标函数的费用系数和约束右端项在什么范围（此时假定其它系数不变）时，最优基保持不变。灵敏性分析是在求解模型时作出的，因此在求解模型时灵敏性分析是激活状态，但是默认是不激活的。为了激活灵敏性分析，运行LINGO|Options…，选择General Solver Tab， 在Dual Computations列表框中，选择Prices and Ranges选项。灵敏性分析耗费相当多的求解时间，因此当速度很关键时，就没有必要激活它。

54 3. 建模与求解实例（结合软件使用） 最短路问题 下料问题 飞机定位 露天矿的运输问题 钢管运输问题

55 数学建模结构是核心： 同一个集合，不同结构，原型的意义不同。 例 语言 下雨天，留客天，留我不留？ 下雨天留客，天留我不留！

56 例.文学体裁的不同结构是不同涵义的原型 宋词 清明时节雨， 纷纷路上行人， 欲断魂。 借问酒家何处， 有牧童， 遥指杏花村。 唐诗 清明时节雨纷纷， 路上行人欲断魂。 借问酒家何处有？ 牧童遥指杏花村。 剧本(元曲) [清明时节][雨纷纷] [路上] 行人（欲断魂）： 借问酒家何处有？ 牧童（遥指）: 杏花村。

57 抽象出结构: 宋词 元曲 时间、地点、 情景、人物、 动作、言语 等。用语白话，易懂。 比较规整,适于言志 错落有序,用语活跃,适于抒情
七言唐诗 × × × × × × × 宋词 × × × × × × × × × × × × × × 元曲 时间、地点、 情景、人物、 动作、言语 等。用语白话，易懂。 比较规整,适于言志 错落有序,用语活跃,适于抒情 百姓故事 专业模型 数学模型？ 乔姆斯基的形式语言？

58

59

60

61 建立数学模型(优化模型)，求最优策略(决策)
优化模型和优化软件的重要意义 (最)优化:在一定条件下,寻求使目标最大(小)的决策 最优化是工程技术、经济管理、科学研究、社会生活中经常遇到的问题, 如: 结构设计 资源分配 生产计划 运输方案 解决优化问题的手段 经验积累，主观判断 作试验，比优劣 建立数学模型(优化模型)，求最优策略(决策) CUMCM赛题：约一半以上与优化有关，需用软件求解

62 优化(Optimization), 规划(Programming)
(最)优化理论是运筹学的基本内容 运筹学(OR: Operations/Operational Research) 管理科学(MS: Management Science) 决策科学 (DS: Decision Science) OR/MS/DS 优化(Optimization), 规划(Programming) 无约束优化 非线性规划 不确定规划 多目标规划 线性规划 整数规划 组合优化 目标规划 网络优化 动态规划

63 优化问题的一般形式 优化问题三要素：决策变量；目标函数；约束条件 目标函数 约束条件 决策变量 可行解（满足约束）与可行域（可行解的集合）
　可行解（满足约束）与可行域（可行解的集合） 　最优解（取到最小／大值的可行解）

64 给定一个函数 f(x),寻找 x* 使得 f(x*)最小，即 最优解在可行域边界上取得时不能用无约束优化方法求解
无约束优化:最优解的分类和条件 给定一个函数 f(x),寻找 x* 使得 f(x*)最小，即 其中 x * f(x) xl xg o 全局最优解 局部最优解 必要条件 充分条件 Hessian阵 最优解在可行域边界上取得时不能用无约束优化方法求解

65 约束优化的 简单分类 数学规划 连续优化 线性规划(LP) 目标和约束均为线性函数 非线性规划(NLP) 目标或约束中存在非线性函数
二次规划(QP) 目标为二次函数、约束为线性 整数规划(IP) 决策变量(全部或部分)为整数 整数线性规划(ILP)，整数非线性规划(INLP) 纯整数规划(PIP), 混合整数规划(MIP) 一般整数规划，0-1（整数）规划 离散优化

66 建模时需要注意的几个基本问题 1、尽量使用实数优化，减少整数约束和整数变量 2、尽量使用光滑优化，减少非光滑约束的个数
如：尽量少使用绝对值、符号函数、多个变量求最大/最小值、四舍五入、取整函数等 3、尽量使用线性模型，减少非线性约束和非线性变量的个数 （如x/y <5 改为x<5y） 4、合理设定变量上下界，尽可能给出变量初始值 5、模型中使用的参数数量级要适当 (如小于103)

67 例 钢管下料 原料钢管:每根19米 客户需求 4米50根 6米20根 8米15根 问题1. 如何下料最节省 ? 节省的标准是什么？
问题1. 如何下料最节省 ? 节省的标准是什么？ 问题2. 客户增加需求： 5米10根 由于采用不同切割模式太多，会增加生产和管理成本，规定切割模式不能超过3种。如何下料最节省？

68 钢管下料 切割模式 按照客户需要在一根原料钢管上安排切割的一种组合。 余料1米 4米1根 6米1根 8米1根 余料3米 4米1根 6米1根
合理切割模式的余料应小于客户需要钢管的最小尺寸

69 钢管下料问题1 合理切割模式 为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节省？ 两种标准
模式  4米钢管根数 6米钢管根数 8米钢管根数 余料(米) 1 4 3 2 5 6 7 为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节省？ 两种标准 1. 原料钢管剩余总余量最小 2. 所用原料钢管总根数最少

70 xi ~按第i 种模式切割的原料钢管根数(i=1,2,…7)
决策变量 xi ~按第i 种模式切割的原料钢管根数(i=1,2,…7) 目标1（总余量） 模 式 4米 根数 6米 8米 余 料 1 4 3 2 5 6 7 需 求 50 20 15 约束 满足需求 整数约束： xi 为整数 最优解：x2=12, x5=15, 其余为0； 最优值：27 按模式2切割12根,按模式5切割15根，余料27米

71 钢管下料问题1 目标2（总根数） 约束条件不变 xi 为整数 最优解：x2=15, x5=5, x7=5, 其余为0； 最优值：25。
按模式2切割15根，按模式5切割5根，按模式7切割5根，共25根，余料35米 与目标1的结果“共切割27根，余料27米” 相比 虽余料增加8米，但减少了2根 当余料没有用处时，通常以总根数最少为目标

72 钢管下料问题2 增加一种需求：5米10根；切割模式不超过3种。
现有4种需求：4米50根，5米10根，6米20根，8米15根，用枚举法确定合理切割模式，过于复杂。 对大规模问题，用模型的约束条件界定合理模式 决策变量 xi ~按第i 种模式切割的原料钢管根数(i=1,2,3) r1i, r2i, r3i, r4i ~ 第i 种切割模式下，每根原料钢管生产4米、5米、6米和8米长的钢管的数量

73 钢管下料问题2 目标函数（总根数） 模式合理：每根余料不超过3米 约束条件 满足需求
整数约束： xi ,r1i, r2i, r3i, r4i (i=1,2,3)为整数 整数非线性规划模型

74 钢管下料问题2 增加约束，缩小可行域，便于求解 需求：4米50根，5米10根，6米20根，8米15根 每根原料钢管长19米
原料钢管总根数下界： 特殊生产计划：对每根原料钢管 模式1：切割成4根4米钢管，需13根； 模式2：切割成1根5米和2根6米钢管，需10根； 模式3：切割成2根8米钢管，需8根。 原料钢管总根数上界：31 模式排列顺序可任定

75 LINGO求解整数非线性规划模型 演示cut02a.lg4； cut02b.lg4
Local optimal solution found at iteration: Objective value: Variable Value Reduced Cost X X X R R R R R R R R R R R R 演示cut02a.lg4； cut02b.lg4 模式1：每根原料钢管切割成3根4米和1根6米钢管，共10根； 模式2：每根原料钢管切割成2根4米、1根5米和1根6米钢管，共10根； 模式3：每根原料钢管切割成2根8米钢管，共8根。 原料钢管总根数为28根。

76 飞机与监控台（图中坐标和测量距离的单位是“公里”）
实例: 飞机精确定位问题 VOR1 x=764, y=1393 北 (0.80) DME x=155, y=987 864.3(2.0) 飞机 x=?, y=? VOR3 x=1571, y=259 45.10 (0.60) y VOR2 x=629, y=375 x (1.30) 飞机与监控台（图中坐标和测量距离的单位是“公里”）

77 飞机精确定位模型 xi yi 原始的 (或d4） VOR1 746 1393 161.20（2.81347弧度）
0.80（0.0140弧度） VOR2 629 375 45.10 （ 弧度） 0.60（0.0105弧度） VOR3 1571 259 309.00（ 弧度） 1.30（0.0227弧度） DME 155 987 d4=864.3（km） 2.0（km）

78 飞机精确定位模型 第1类模型: 不考虑误差因素 超定方程组， 非线性最小二乘！ 量纲不符！ ？

79 ？ 误差非均匀分布！ ？ 飞机精确定位模型 第2类模型: 考虑误差因素(作为硬约束) 非线性规划
Min x; Min y; Max x; Max y. 有人也可能会采用其他目标，如： 以距离为约束，优化角度误差之和（或平方和）； 或以角度为约束，优化距离误差. ？ 仅部分考虑误差! 角度与距离的“地位”不应不同！

80 飞机坐标(978.31，723.98), 误差平方和0.6685 (<< 4)
飞机精确定位模型 第3类模型: 考虑误差因素(作为软约束); 且归一化 误差一般服从什么分布？ 不同的量纲如何处理？ 正态分布！ 归一化处理！ 无约束非线性最小二乘模型 角度需要进行预处理，如利用 Matlab的atan2函数, 值域(-pi, pi) shili0702.m 飞机坐标(978.31，723.98), 误差平方和 (<< 4)

81 飞机精确定位模型 小技巧: LINGO中没有atan2函数, 怎么办？ 可以直接利用@tan函数！ exam0507c.lg4
同前面的模型/结果 exam0507d.lg4 最后: 思考以下模型: 飞机坐标(980.21， ), 误差平方和2.6 与前面的结果有所不同, 为什么? 哪个模型合理些?

82 露天矿生产的车辆安排(CUMCM-2003B) 露天矿里铲位已分成矿石和岩石: 平均铁含量不低于25%的为矿石，否则为岩石。每个铲位的矿石、岩石数量，以及矿石的平均铁含量（称为品位）都是已知的。每个铲位至多安置一台电铲，电铲平均装车时间5分钟 矿石卸点需要的铁含量要求都为29.5%1%(品位限制），搭配量在一个班次（8小时）内满足品位限制即可。卸点在一个班次内不变。卡车载重量为154吨，平均时速28km,平均卸车时间为3分钟。 卡车在等待时所耗费的能量也是相当可观的，原则上在安排时不应发生卡车等待的情况。 问题：出动几台电铲，分别在哪些铲位上；出动几辆卡车，分别在哪些路线上各运输多少次 ?

83 平面示意图

84 问题数据 距离 铲位1 铲位2 铲位3 铲位4 铲位5 铲位6 铲位7 铲位8 铲位9 铲位10 矿石漏 5.26 5.19 4.21
4.00 2.95 2.74 2.46 1.90 0.64 1.27 倒装Ⅰ 0.99 1.13 2.25 1.48 2.04 3.09 3.51 岩场 5.89 5.61 4.56 3.65 1.06 0.57 岩石漏 1.76 1.83 2.60 3.72 5.05 6.10 倒装Ⅱ 4.42 3.86 3.16 2.81 0.78 1.62 0.50 铲位1 铲位2 铲位3 铲位4 铲位5 铲位6 铲位7 铲位8 铲位9 铲位10 矿石量 0．95 1．05 1．00 1．10 1．25 1．30 1．35 岩石量 1．15 铁含量 30% 28% 29% 32% 31% 33%

85 问题分析 与典型的运输问题明显有以下不同： 这是运输矿石与岩石两种物资的问题； 属于产量大于销量的不平衡运输问题；
为了完成品位约束，矿石要搭配运输； 产地、销地均有单位时间的流量限制； 运输车辆只有一种，每次满载运输，154吨/车次； 铲位数多于铲车数意味着要最优的选择不多于7个产地作为最后结果中的产地； 最后求出各条路线上的派出车辆数及安排。 近似处理： 先求出产位、卸点每条线路上的运输量(MIP模型) 然后求出各条路线上的派出车辆数及安排

86 模型假设 卡车在一个班次中不应发生等待或熄火后再启动的情况；
在铲位或卸点处由两条路线以上造成的冲突问题面前，我们认为只要平均时间能完成任务，就认为不冲突。我们不排时地进行讨论； 空载与重载的速度都是28km/h，耗油相差很大； 卡车可提前退出系统，等等。 如理解为严格不等待，难以用数学规划模型来解 个别参数队找到了可行解 （略）

87 符号 (近似) xij ：从i铲位到j号卸点的石料运量 （车） 单位： 吨； cij ：从i号铲位到j号卸点的距离 公里；
Tij :从i号铲位到号j卸点路线上运行一个周期平均时间 分； Aij ：从号铲位到号卸点最多能同时运行的卡车数 辆； Bij ：从号铲位到号卸点路线上一辆车最多可运行的次数 次； pi：i号铲位的矿石铁含量 p=(30,28,29,32,31,33,32,31,33,31) % qj : j号卸点任务需求，q=(1.2,1.3,1.3,1.9,1.3)* 吨 cki ：i号铲位的铁矿石储量 万吨 cyi ：i号铲位的岩石储量 万吨 fi :描述第i号铲位是否使用的0-1变量，取1为使用；0为关闭。 (近似)

88 优化模型 （1）道路能力(卡车数)约束 （2）电铲能力约束 （3）卸点能力约束 （4）铲位储量约束 （5）产量任务约束 （6）铁含量约束
（7）电铲数量约束 （8）整数约束 . xij为非负整数 fi 为0-1整数

89 计算结果（LINGO软件） cumcm2003b1.lg4 注: LINGO8.0本来是可以得到最优解的，但有些
LINGO8.0可能出现系统错误, 可能是系统BUG 铲位1 铲位2 铲位3 铲位4 铲位5 铲位6 铲位7 铲位8 铲位9 铲位10 矿漏 13 54 11 倒Ⅰ 42 43 岩场 70 15 岩漏 81 倒Ⅱ 2 铲位1 铲位2 铲位3 铲位4 铲位5 铲位6 铲位7 铲位8 铲位9 铲位10 矿石漏 0.867 1.862 0.314 倒场Ⅰ 1.077 1.162 岩场 1.892 0.326 岩石漏 1.841 1.229 倒场Ⅱ 0.684 0.1 1.489

90 计算结果（派车） 此外：6辆联合派车（方案略） 结论： 铲位1、2、3、4、8、9、10处各放置一台电铲。
铲位2 铲位3 铲位4 铲位5 铲位6 铲位7 铲位8 铲位9 铲位10 矿石漏 1 (29) 倒场Ⅰ 1 (39) 1 (37) 岩场 岩石漏 1(44) 1 (35) 倒场Ⅱ 1 (47) 此外：6辆联合派车（方案略） 结论： 铲位1、2、3、4、8、9、10处各放置一台电铲。 一共使用了13辆卡车；总运量为 吨公里； 岩石产量为32186吨；矿石产量为38192吨。

91 主要参考文献 1，谢金星, 薛毅: 优化建模与LINDO/LINGO软件, 清华大学出版社, 2005年7月出版.
4，梦大志，数学建模培训班报告，(2005年8月5日北戴河)

92 七律 李尚志 咏数学模型 数学精微何处寻，纷纭世界有模型。 描摹万象得神韵，识破玄机算古今。 岂是空文无实效，能生妙策济苍生。
借李尚志教授的一首七律结尾 七律 李尚志 咏数学模型 数学精微何处寻，纷纭世界有模型。 描摹万象得神韵，识破玄机算古今。 岂是空文无实效，能生妙策济苍生。 经天纬地展身手，七十二行任纵横。 祝大家数学建模取得好成绩