数学建模讲座（2004年7月8月江西）优化模型与LINDO/LINGO优化软件谢金星 清华大学数学科学系 Tel: 010-62787812 Email:jxiemath.tsinghua.edu.cn http:/faculty.math.tsinghua.edu.cn/jxie简要提纲 优化模型简介 LINDO公司的主要软件产品及功能简介 LINDO软件的使用简介 LINGO软件的使用简介 建模与求解实例（结合软件使用）优化模型 实际问题中 的优化模型x决策变量f(x)目标函数gi(x)0约束条件数学规划线性规划(LP) 二次规划(QP) 非线性规划(NLP)纯整数规划(PIP) 混合整数规划(MIP)整数规划(IP)0-1整数规划一般整数规划连续规划LINDO 公司软件产品简要介绍 美国芝加哥(Chicago)大学的Linus Schrage教授于1980 年前后开发, 后来成立 LINDO系统公司（LINDO Systems Inc.）， 网址：http:/www.lindo.com 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)演示(试用)版、学生版、高级版、超级版、工业版、 扩展版 （求解问题规模和选件不同）LINDO和LINGO软件能求解的优化模型LINGOLINDO优化模型线性规划 (LP)非线性规划 (NLP)二次规划 (QP)连续优化整数规划(IP)LP QP NLP IP 全局优化(选 ) ILP IQP INLPLINDO/LINGO软件的求解过程 LINDO/LINGO预处理程序线性优化求解程序非线性优化求解程序分枝定界管理程序1. 确定常数2. 识别类型1. 单纯形算法2. 内点算法(选)1、顺序线性规划法(SLP) 2、广义既约梯度法(GRG) (选) 3、多点搜索(Multistart) (选) 建模时需要注意的几个基本问题 1、尽量使用实数优化，减少整数约束和整数变量2、尽量使用光滑优化，减少非光滑约束的个数 如：尽量少使用绝对值、符号函数、多个变量求最 大/最小值、四舍五入、取整函数等3、尽量使用线性模型，减少非线性约束和非线性变量 的个数 （如x/y ”（或“=”（或“: 2 0 2, GUBS = 0 SINGLE COLS= 0 REDUNDANT COLS= 0LINDO行命令、命令脚本文件批处理：可以采用命令脚本（行命令序列）WINDOWS环境下行命令的意义不大Example 演示用FILE / TAKE COMMANDS (F11) 命令调入必须是以LINDO PACKED形式 （压缩）保存的文件FILE / SAVE命令SAVE行命令LINGO软件简介目标与约束段 集合段（SETS ENDSETS） 数据段（DATA ENDDATA） 初始段（INIT ENDINIT）LINGO模型的构成：4个段LINGO模型的优点包含了LINDO的全部功能提供了灵活的编程语言（矩阵生成器）LINGO模型 例：选址问题某公司有6个建筑工地，位置坐标为(ai, bi) (单位：公里), 水泥日用量di (单位：吨）假设：料场 和工地之间 有直线道路用例中数 据计算， 最优解为总吨公里数为总吨公里数为136.2136.2线性规划模型决策变量：ci j ( 料场j到工地i的 运量）12维选址问题：NLP2）改建两个新料场，需要确定新料场位置(xj,yj)和 运量cij ，在其它条件不变下使总吨公里数最小。决策变量： ci j，(xj,yj)16维非线性规划模型LINGO模型的构成：4个段集合段（SETS ENDSETS）数据段（DATA ENDDATA）初始段（INIT ENDINIT） 目标与约束段局部最优：89.8835(吨公里 )LP：移到数据段边界集合的类型集合派生集合 基本集合稀疏集合 稠密集合元素列表法 元素过滤法 直接列举法 隐式列举法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; ENDSETSSETS:STUDENTS /S1S8/;PAIRS( STUDENTS, STUDENTS) | ENDSETS集合元素的隐式列举类型隐式列举格式示例示例集合的元素 数字型 1n151, 2, 3, 4, 5 字符- 数字型stringMstringNCar101car208 Car101, car102, , car208星期型 dayMdayNMONFRIMON, TUE, WED, THU, FRI月份型 monthMmonthN OCTJANOCT, NOV, DEC, JAN年份- 月份型monthYearMmo nthYearNOCT2001JAN 2002OCT2001, NOV2001, DEC2001, JAN2002运算符的优先级 优先级运算符 最高#NOT# （负负号） * / + （减法） #EQ# #NE# #GT# #GE# #LT# #LE# #AND# #OR#最低(=)三类运算符：算术运算符 逻辑运算符 关系运算符集合循环函数四个集合循环函数：FOR、SUM 、 MAX、MINfunction( setname ( set_index_list) | condition : expression_list);objective MAX = SUM( PAIRS( I, J): BENEFIT( I, J) * MATCH( I, J);FOR(STUDENTS( I): constraintsSUM( 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:状态窗口Solver Type: B-and-B Global MultistartModel Class:LP， QP，ILP ， IQP，PILP, PIQP，NLP， INLP，PINLP State: Global Optimum Local Optimum Feasible Infeasible Unbounded Interrupted Undetermined7个选项卡(可设置80-90个控制参数)程序与数据分离文本文件使用外部数据文件 Cut (or Copy) Paste 方法 FILE 输入数据、TEXT输出数据（文本文件） OLE函数与电子表格软件（如EXCEL）连接 ODBC函数与数据库连接 LINGO命令脚本文件 LG4 （LONGO模型文件） LNG （LONGO模型文件） LTF （LONGO脚本文件） LDT （LONGO数据文件） LRP （LONGO报告文件）常用文件后缀FILE和TEXT：文本文件输入输出MODEL: SETS:MYSET / FILE(myfile.txt) / : FILE(myfile.txt); ENDSETS MIN = SUM( MYSET( I):SHIP( I) * COST( I);FOR( MYSET( I): CON1 SHIP( I) NEED( I);CON2 SHIP( I) NEED( I);CON2 SHIP( I) SUPPLY( I); DATA:MYSET =OLE(D:JXIEBJ2004MCMmydata.xls,CITIES); COST,NEED,SUPPLY =OLE(mydata.xls); OLE(mydata.xls,SOLUTION)=SHIP; ENDDATA ENDmydata.xls文件中必 须有下列名称(及数 据)：CITIES， COST， NEED，SUPPLY， SOLUTION 在EXCEL中还可以通过“宏”自动调用LINGO(略) 也可以将EXCEL表格嵌入到LINGO模型中(略)演示 MydataExample.lg4ODBC ：与数据库连接输入基本集合元素： setname/ODBC(datasource , tablename , columnname)/ 输入派生集合元素： setname/ODBC(source,table , column1, column2)/目前支持下列DBMS: (如为其他数据库，则需自行安装驱动) ACCESS， DBASE，EXCEL，FOXPRO，ORACLE， PARADOX，SQL SERVER， TEXE FILES使用数据库之前，数据源需要在ODBC管理器注册输入数据： Attr_list=ODBC(source,table , column1, column2) 输出数据： ODBC(source,table , column1, column2)= Attr_list具体例子略建模实例与求解最短路问题下料问题露天矿的运输问题钢管运输问题最短路问题求各点到T的最短路56774968658336C1B1C2B2A1A2A3TS6shortestPath.lg4问题1. 如何下料最节省 ? 例 钢管下料 问题2. 客户增加需求：原料钢管:每根19米 4米50根 6米20根 8米15根 客户需求节省的标准是什么？由于采用不同切割模式太多，会增加生产和管理成本 ，规定切割模式不能超过3种。如何下料最节省？5米10根 按照客户需要在一根原料钢管上安排切割的一种组合。 切割模式余料1米 4米1根 6米1根 8米1根 余料3米 4米1根 6米1根 6米1根 合理切割模式的余料应小于客户需要钢管的最小尺寸余料3米 8米1根 8米1根 钢管下料 为满足客户需要，按照哪些种合理模式，每种模式 切割多少根原料钢管，最为节省？合理切割模式2. 所用原料钢管总根数最少 模式 4米钢管根数6米钢管根数8米钢管根数余料(米) 1400323101 3201341203 51111 60301 70023钢管下料问题1 两种 标准1. 原料钢管剩余总余量最小xi 按第i 种模式切割的原料钢管根数(i=1,2,7) 约束满足需求 决策变量