《建模电子教案》由会员分享，可在线阅读，更多相关《建模电子教案（65页珍藏版）》请在金锄头文库上搜索。
1、数学建模讲座（数学建模讲座（2004年年7月月8月月 江西）江西） 优化模型与优化模型与LINDO/LINGO优化软件优化软件 谢金星谢金星 清华大学数学科学系清华大学数学科学系 Tel: 010-62787812 Email: http:/ 简要提纲简要提纲 优化模型简介优化模型简介 LINDO公司的主要软件产品及功能简介公司的主要软件产品及功能简介 LINDO软件的使用简介软件的使用简介 LINGO软件的使用简介软件的使用简介 建模与求解实例（结合软件使用）建模与求解实例（结合软件使用） 优化模型优化模型 实际问题中实际问题中 的优化模型的优化模型 mixgtsxxxxfzMaxMiniT
2、 n , 2 , 1, 0)(. . ),(),()(1 或x决策变量决策变量 f(x)目标函数目标函数 gi(x) 0约束条件约束条件 数学规划数学规划 线性规划线性规划(LP) 二次规划二次规划(QP) 非线性规划非线性规划(NLP) 纯整数规划纯整数规划(PIP) 混合整数规划混合整数规划(MIP) 整数规划整数规划(IP) 0-1整数规划整数规划 一般整数规划一般整数规划 连续规划连续规划 LINDO LINDO 公司软件产品简要介绍公司软件产品简要介绍 美国芝加哥美国芝加哥(Chicago)大学的大学的Linus Schrage教授于教授于1980 年前后开发年前后开发, 后来成立后
3、来成立 LINDO系统公司（系统公司（LINDO Systems Inc.），）， 网址：网址：http:/ LINDO: Linear INteractive and Discrete Optimizer (V6.1) LINGO: Linear INteractive General Optimizer (V8.0) LINDO API: LINDO Application Programming Interface (V2.0) Whats Best!: (SpreadSheet e.g. EXCEL) (V7.0) 演演示示(试用试用)版、学生版、高级版、超级版、工业版、版、学生版、高
4、级版、超级版、工业版、 扩展版扩展版 （求解（求解问题规模问题规模和和选件选件不同）不同） LINDOLINDO和和LINGOLINGO软件能求解的优化模型软件能求解的优化模型 LINGO LINDO 优化模型优化模型 线性规划线性规划 (LP) 非线性规划非线性规划 (NLP) 二次规划二次规划 (QP) 连续优化连续优化 整数规划整数规划(IP) LP QP NLP IP 全局优化全局优化(选选) ILP IQP INLP LINDO/LINGO软件的求解过程 LINDO/LINGO预处理程序预处理程序 线性优化求解程序线性优化求解程序 非线性优化求解程序非线性优化求解程序 分枝定界管理程
5、序分枝定界管理程序 1. 确定常数确定常数 2. 识别类型识别类型 1. 单纯形算法单纯形算法 2. 内点算法内点算法(选选) 1、顺序线性规划法、顺序线性规划法(SLP) 2、广义既约梯度法、广义既约梯度法(GRG) (选选) 3、多点搜索、多点搜索(Multistart) (选选) 建模时需要注意的几个基本问题建模时需要注意的几个基本问题 1、尽量使用实数优化，减少整数约束和整数变量尽量使用实数优化，减少整数约束和整数变量 2、尽量使用光滑优化，减少非光滑约束的个数尽量使用光滑优化，减少非光滑约束的个数 如：尽量少使用绝对值、符号函数、多个变量求如：尽量少使用绝对值、符号函数、多个变量求
6、最大最大/最小值、四舍五入、取整函数等最小值、四舍五入、取整函数等 3、尽量使用线性模型，减少非线性约束和非线性变尽量使用线性模型，减少非线性约束和非线性变 量的个数量的个数 （如（如x/y ”（或“（或“=”（或“（或“: 2 0 2, GUBS = 0 SINGLE COLS= 0 REDUNDANT COLS= 0 LINDOLINDO行命令、命令脚本文件行命令、命令脚本文件 批处理：可以采用命令脚本（行命令序列）批处理：可以采用命令脚本（行命令序列） WINDOWS环境下行命令的意义不大环境下行命令的意义不大 Example 演示演示 Bat01.txt用用FILE / TAKE CO
7、MMANDS (F11) 命令调入命令调入 必须是以必须是以LINDO PACKED形式形式 （压缩）保存的文件（压缩）保存的文件 FILE / SAVE命令命令 SAVE行命令行命令 LINGO软件简介软件简介 目标与约束段目标与约束段 集合段（集合段（SETS ENDSETS） 数据段（数据段（DATA ENDDATA） 初始段（初始段（INIT ENDINIT） LINGO模型的构成：模型的构成：4个段个段 LINGO模型的优点模型的优点 包含了包含了LINDO的全部功能的全部功能 提供了灵活的编程语言（矩阵生成器）提供了灵活的编程语言（矩阵生成器） LINGOLINGO模型模型 例：选
8、址问题例：选址问题 某公司有某公司有6个建筑工地，位置坐标为个建筑工地，位置坐标为(ai, bi) (单位：公里单位：公里), 水泥日用量水泥日用量di (单位：吨）单位：吨） i a1.258.750.55.7537.25 b1.250.754.7556.57.75 d35476111)现有 2 料场，位于 A (5, 1), B (2, 7), 记(xj,yj),j=1,2, 日储量 ej各有 20 吨。假设：假设：料场料场 和工地之间和工地之间 有直线道路有直线道路 目标：制定每天的供应计划，即从 A, B 两料场分别 向各工地运送多少吨水泥，使总的吨公里数最小。用例中数 据计算， 最优
9、解为 i1234561ic（料场（料场 A）3507012ic（料场（料场 B）0040610总吨公里数为总吨公里数为136.2 2, 1,6,.,1,. .)()(min612121612/122jecidctsbyaxcjij iiij jjiijijij线性规划模型线性规划模型 决策变量：决策变量：ci j (料场料场j到到工地工地i的的 运量）运量）12维维 选址问题：选址问题：NLPNLP 2）改建两个新料场，需要确定新料场位置）改建两个新料场，需要确定新料场位置(xj,yj)和和 运量运量cij ，在其它条件不变下使总吨公里数最小。，在其它条件不变下使总吨公里数最小。 2 , 1,
10、6,.,1,. .)()(min612121612/122jecidctsbyaxcjij iiij jjiijijij决策变量：决策变量： ci j，(xj,yj)16维维 非线性规划模型非线性规划模型 LINGO模型的构成：模型的构成：4个段个段 集合段（集合段（SETS ENDSETS） 数据段（数据段（DATA ENDDATA） 初始段（初始段（INIT ENDINIT） 目标与目标与 约束段约束段 局部最优：局部最优：89.8835(吨公里吨公里 ) LP：移到数据段：移到数据段 边界 集合的类型集合的类型 集合集合 派生集合派生集合 基本集合基本集合 稀疏集合稀疏集合 稠密集合稠密
11、集合 元素列表法元素列表法 元素过滤法元素过滤法 直接列举法直接列举法 隐式列举法隐式列举法 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) | ENDSETS 集合元素的
12、集合元素的隐式列举隐式列举 类型类型 隐式列举格式隐式列举格式 示例示例 示例集合的元素示例集合的元素 数字型数字型 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.mo nthYearN OCT2001.JAN 2002 O
13、CT2001, NOV2001, DEC2001, JAN2002 运算符的优先级运算符的优先级 优先级优先级 运算符运算符 最高最高 #NOT# （负号）（负号） * / + （减法）（减法） #EQ# #NE# #GT# #GE# #LT# #LE# #AND# #OR# 最低最低 (=) 三类运算符：三类运算符： 算术运算符算术运算符 逻辑运算符逻辑运算符 关系运算符关系运算符 集合循环函数集合循环函数 四个集合循环函数：四个集合循环函数：FOR、SUM 、 MAX、MIN function( setname ( set_index_list) | condition : express
14、ion_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: PAIRSJIJIMATCHJIBENEFIT),(),(*),(1),(),(IKorIJPAIRSKJKJMATCH状态窗口状态窗口 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 Undetermine
