数学建模讲座（ 2008 年 7 月，湖南） 优化建模与 LINGO 优化软件 谢金星 清华大学数学科学系 Tel: 010-62787812

Presentation on theme: "数学建模讲座（ 2008 年 7 月，湖南） 优化建模与 LINGO 优化软件 谢金星 清华大学数学科学系 Tel: 010-62787812"— Presentation transcript:

1 数学建模讲座（ 2008 年 7 月，湖南） 优化建模与 LINGO 优化软件 谢金星 清华大学数学科学系 Tel: 010-62787812 Email: jxie@math.tsinghua.edu.cn http://faculty.math.tsinghua.edu.cn/~jxie/lindo

2 简要提纲 1. 优化模型简介 2. LINGO 软件简介 3. 建模与求解实例

3 1. 优化模型简介

4 优化模型和优化软件的重要意义 解决优化 / 决策问题的手段 经验积累，主观判断 作试验，比优劣 建立数学模型 ( 优化模型 ) ，求最优策略 ( 决策 ) ( 最 ) 优化 : 在一定条件下, 寻求使目标最大 ( 小 ) 的决策 CUMCM 赛题： ~50% 与优化有关，规模大，需软件求 解 OR/MS/DS 的基础 :OR( 运筹学, Operations/-al Research ) MS( 管理科学,Management Science) DS( 决策科学,Decision Science) 工程技术 / 经济管理 / 科学研究 / 社会生活中经常遇到

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

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

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

8 无约束优化无约束优化 优化 (Optimization), 规划 (Programming) 线性规划线性规划 非线性规划非线性规划 网络优化网络优化 组合优化组合优化 整数规划整数规划 不确定规划不确定规划 多目标规划多目标规划 目标规划目标规划 动态规划动态规划 连续优化离散优化从其他角度分类

9 Optimization Tree http://www-fp.mcs.anl.gov/otc/Guide/OptWeb/

10 优化建模如何创新？ 方法 1 ：大胆创新，别出心裁 ---- 采用有特色的目标函数、约束条件等 ---- 你用非线性规划，我用线性规划 ---- 你用整数 / 离散规划，我用连续规划 / 网络优化 ---- …… 方法 2 ：细致入微，滴水不漏 ---- 对目标函数、约束条件处理特别细致 ---- 有算法设计和分析，不仅仅是简单套用软件 ---- 敏感性分析详细 / 全面 ---- ……

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

12 常用优化软件 1. LINGO 软件 2. MATLAB 优化工具箱 3. EXCEL 软件的优化功能 4. SAS( 统计分析 ) 软件的优化功能 5. 其他

13 MATLAB 优化工具箱能求解的优化模型 优化工具箱 3.0 (MATLAB 7.0 R14) 连续优化离散优化 无约束优化 非线性 极小 fminunc 非光滑 ( 不可 微 ) 优化 fminsearch 非线性 方程 ( 组 ) fzero fsolve 全局 优化 暂缺 非线性 最小二乘 lsqnonlin lsqcurvefit 线性规划 linprog 纯 0-1 规划 bintprog 一般 IP( 暂缺 ) 非线性规划 fmincon fminimax fgoalattain fseminf 上下界约束 fminbnd fmincon lsqnonlin lsqcurvefit 约束线性 最小二乘 lsqnonneg lsqlin 约束优化 二次规划 quadprog

14 2. LINGO 软件简介

15 LINDO 公司软件产品简要介绍 美国芝加哥 (Chicago) 大学的 Linus Schrage 教授于 1980 年前后开发, 后来成立 LINDO 系统公司（ LINDO Systems Inc. ）， 网址： http://www.lindo.com LINGO: Linear INteractive General Optimizer (V11.0) LINDO API: LINDO Application Programming Interface (V4.0) What’s Best!: (SpreadSheet e.g. EXCEL) (V8.0) 演示 ( 试用 ) 版、学生版、高级版、超级版、工业版、 扩展版 … （求解问题规模和选件不同）

16 LINDO 和 LINGO 软件能求解的优化模型 LINGO LINDO( 将被淘汰 ) 优化模型 线性规划 (LP) 非线性规划 (NLP) 二次规划 (QP) 连续优化 整数规划 (IP)

17 LINGO 软件简介 LINGO 模型的优点 集成了线性 ( 非线性 ) / 连续 ( 整数 ) 优化功能 运行速度较快 具有多点搜索 / 全局优化功能 提供了灵活的编程语言 ( 矩阵生成器 ) ，可方便地输 入模型 提供与其他数据文件的接口 ( 如 TEXT, EXCEL, ODBC 数据库接口 ) 提供与其他编程语言的接口 LINDO API 可用于自主开发

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

19 目标与约束段 集合段（ SETS ENDSETS ） 数据段（ DATA ENDDATA ） 初始段（ INIT ENDINIT ） 计算段（ CALC ENDCALC ） ---- 9.0+ 子模型（ SUBMODEL ENDSUBMODEL ） ---- 10.0+ LINGO 模型的构成： 6 个段

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

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

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

23 选址问题： NLP 2 ）改建两个新料场，需要确定新料场位置 (x j,y j ) 和 运量 c ij ，在其它条件不变下使总吨公里数最小。 决策变量： c i j ， (x j,y j )~16 维 非线性规划模型 演示 Location.lg4

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

25 边界

26 集合的类型 集合 派生集合 基本集合 稀疏集合 稠密集合 元素列表法 元素过滤法 直接列举法 隐式列举法 setname [/member_list/] [: attribute_list]; setname(parent_set_list) [/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

27 集合元素的隐式列举 类型隐式列举格式示例示例集合的元素 数字型 1..n1..51, 2, 3, 4, 5 字符 - 数字型 stringM..stringNCar101..car208Car101, car102, …, car208 星期型 dayM..dayNMON..FRIMON, TUE, WED, THU, FRI 月份型 monthM..monthNOCT..JANOCT, NOV, DEC, JAN 年份 - 月份型 monthYearM..mo nthYearN OCT2001..JAN 2002 OCT2001, NOV2001, DEC2001, JAN2002

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

29 集合循环函数 四个集合循环函数： FOR 、 SUM 、 MAX 、 MIN @function( setname [ ( set_index_list)[ | condition]] : expression_list); [objective] MAX = @SUM( 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, J): @BIN( MATCH( I, J))); MAXB=@MAX(PAIRS( I, J): BENEFIT( I, J)); MINB=@MIN(PAIRS( I, J): BENEFIT( I, J)); Example:

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

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

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

33 3. 建模与求解实例（结合软件使用）

34 建模实例与求解 最短路问题 飞机定位 生产计划 DVD 租赁

35 例 最短路问题 求各点到 T 的最短路 5 6 7 7 4 9 6 8 6 5 8 3 3 6 C1C1 B1B1 C2C2 B2B2 A1A1 A2A2 A3A3 T S 6 shortestPath.lg4

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

37 飞机精确定位模型 xixi yiyi 原始的 ( 或 d 4 ） VOR17461393 161.2 0 （ 2.81347 弧度） 0.8 0 （ 0.0140 弧度） VOR2629375 45.1 0 （ 0.78714 弧度） 0.6 0 （ 0.0105 弧度） VOR31571259 309.0 0 （ 5.39307 弧度） 1.3 0 （ 0.0227 弧度） DME155987 d 4 =864.3 （ km ） 2.0 （ km ）

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

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

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

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

42 例：生产批量计划 背景： MRP （ MRP-II ）系统中的生产计划

43 生产批量计划：数学模型 已知： N, T, s, h, d, r, a, C Min s.t. 演示 exam0502.lg4

44 例： DVD 分配问题 背景： DVD 在线租赁，每人每次最多 3 张 已知：网站手上 100 种 DVD 的现有张数和当前需要 处理的 1000 位会员的在线订单（具体数据见 http://mcm.edu.cn/mcm05/problems2005c.asp ） 问题：如何对这些 DVD 进行分配，才能使会员获得 最大的满意度？

45 EXCEL 表格格式示例 数字越小表示会员的偏爱程度越高，数字 0 表 示对应的 DVD 当前不在会员的在线订单中 DVD 编号 D001D002D003D004… DVD 现有数量 10401520… 会员 在线 订单 C00016000… C00020000… C00030003… C00040000… ………………

46 模型 满意度 s ij 定义： 很多，如 s ij =1-a ij /11 (a ij =0 时 s ij =0) ， ， ， ， 。 或 <= 0-1 变量个数： 1000*100+1000=101000 演示 Dvd_1000_100.lg4

47 CUMCM 其他优化赛题 （ 参见 http://mcm.edu.cn ） 飞行管理问题 空洞探测问题 钻井布局问题 抢渡长江问题 等等

48 主要参考文献 谢金星, 薛毅 : 优化建模与 LINDO/LINGO 软件, 清华大学出版社, 2005 年 7 月出版. http://faculty.math.tsinghua.edu.cn/~jxie/lindo 姜启源, 邢文训, 谢金星, 杨顶辉 : 大学数学实验, 清华大学出版社, 2005 年 2 月出版. http://mathexp.math.tsinghua.edu.cn 历届竞赛优秀论文集： 《全国大学生数学建模竞赛优秀论文汇编 (1992- 2000) 》：物质出版社， 2001. 《数学的实践与认识》 (2000 年及以前 ) 《工程数学学报》 （ 2001 年及以后）

49 That’s all. Any Questions? Thank you for your attendance! 最后，祝大家 在数学建模活动中 取得更大的成绩！  清华大学数学科学系 谢金星, 2008.