LINGO在数学建模中的应用.ppt

LINGO在数学建模中的应用 吉林大学数学学院全国大学生数学建模竞赛吉林赛区组委会 LINGO在数学建模中的应用 LINGO的主要功能和特点1 求解线性规划和非线性规划问题2 模型输入简练直观3 运行速度快计算能力强4 内置建模语言提供内部函数较少语句直观描述大规模优化模型5 引入集合容易建模6 数据交换方便 与EXCEL和数据库 需要掌握的几个重要方面 掌握集合 SETS 的应用 正确阅读求解报告 正确理解求解状态窗口 学会设置基本的求解选项 OPTIONS 掌握与外部文件的基本接口方法 LINGO在数学建模中的应用 LINGO的基本用法 模型窗口 LINGOModel LINGO1 用于输入模型可用基本类似数学公式的形式输入小模型 LINGO的语法规则 1 最大值MAX 最小值MIN 2 语句必须以分号 结束每行可多个语句语句可跨行3 变量名由字母 数字和下划线组成以字母开头长度不超32个字符不区分大小写4 默认决策变量非负其他要求可做说明5 模型以MODEL 开头 以END结束 例工厂有两条生产线 分别生产M和P两种型号的产品 利润分别为200元 个和300元 个 生产能力分别为100和120 生产一个产品分别需1个和2个劳动日 工厂每天能提供160个劳动日 假设原材料不受限制 如何安排生产计划 利润最大 设生产计划为生产x1个M和x2个P 数学模型为 LINGO求解 1 输入模型MODEL MAX 200 X1 300 X2 X1 100 X2 120 X1 2 X2 160 END2 模型存盘选File SaveAs3 模型求解选Lingo Solve Ctrl s LINGO求解 4 求解结果LingoSolverStatus变量个数约束条件个数优化状态非零变量个数耗费内存所用时间SolitionReport计算步数目标函数值变量值Golbaloptimalsolutionfoundatiteration 2Objectivevalue 29000 00VariablevalueReducedcost 缩减成本系数 X1100 0000 000000X230 0000 000000RowSlack 松池 orSurplus 剩余 DualPrice 影子价格 29000 0010 00000050 0000090 000000 00000040 000000150 0000注Row模型中行号Slack 右 左 LINGO编程 建模 语言 LINGO模型的基本组成1 集合定义部分集合是一组相关对象构成的组合 代表模型中的实际事物 并与数学变量和常量联系起来 实际问题到数学问题的抽象 集合使用前应定义 内容为 集合名称 集合内的成员 集合的属性 命名规则同变量 初始集合 集合名称 集合内的成员 集合的属性如 WH W1 W6 AI VD V1 V8 Dj衍生集合 集合名称对应的初始集合集合成员集合的属性集合名称 对应的初始集合 对应的初始集合 集合的属性如 LINKS WH VD C X 集合定义部分以语句SETS 开头 以语句ENDSETS结束 集合的类型 集合派生集合基本集合稀疏集合稠密集合元素列表法元素过滤法直接列举法隐式列举法 setname member list attribute list setname parent set list member list attribute list SETS CITIES A1 A2 A3 B1 B2 ROADS CITIES CITIES A1 B1A1 B2A2 B1A3 B2 D ENDSETS SETS STUDENTS S1 S8 PAIRS STUDENTS STUDENTS ENDSETS 集合元素的隐式列举 LINGO编程 建模 语言 LINGO模型的基本组成2 数据初始化部分 数据段 LINGO建模语言通过数据初始化部分来实现对已知属性赋予初始值数据初始化部分以语句DATA 开始 以语句ENDDATA结束如 DATA AI 60 55 51 43 41 52 DJ 35 37 22 32 41 32 43 38 C 6 2 6 7 4 2 5 94 9 5 3 8 5 8 2 ENDDATA LINGO编程 建模 语言 LINGO模型的基本组成3 目标函数和约束条件内部函数 SUM FOR SUM是LINGO的内部函数 功能是对某个集合的所有成员求指定表达式的和 有两个参数 其一是集合名称 指定对该集合的所有成员求和 其二是一个表达式 表示求和运算对该表达式进行 FOR是LINGO的内部函数 功能是对某个集合的所有成员分别派生一个约束表达式有两个参数 其一是集合名称 表示对该集合的所有成员分别派生一个约束表达式 其二是约束表达式的具体内容 注 SUM和 FOR可以嵌套使用 LINGO编程 建模 语言 例运输问题公司有6个供货栈 仓库 库存货物总数分别为AI 60 55 51 43 41 52 现有8个客户各要一批货 数量分别为35 37 22 32 41 32 43 38 各供货栈到8个客户的单位运价如表1 如何确定各供货栈到8个客户的货物调运量 使总的运费最小 表1各供货栈到8个客户的单位运价 LINGO编程 建模 语言 例运输问题数学模型 LINGO编程 建模 语言 例运输问题LINGO模型MODEL SETS WH W1 W6 AI VD V1 V8 Dj LINKS WH VD C X ENDSETSDATA AI 60 55 51 43 41 52 DJ 35 37 22 32 41 32 43 38 C 6 2 6 7 4 2 5 94 9 5 3 8 5 8 25 2 1 9 7 4 3 37 6 7 3 9 2 7 12 3 9 5 7 2 6 55 5 5 5 8 1 4 3ENDDATA LINGO编程 建模 语言 例运输问题LINGO模型MIN SUM LINKS I J C I J X I J FOR WH I SUM VD J X I J AI I FOR VD J SUM WH I X I J DJ J END求解Lingo SolveSolitionReportGolbaloptimalsolutionfoundatstep 17Objectivevalue 664 0000VariablevalueReducedcost 缩减成本系数 X w1 v1 0 0005 000000X w1 v2 19 0000 000000 LINGO的菜单 1 File 文件菜单 Exportfile 输出特殊格式文件 DatabaseUserInfo 用户基本信息 2 EditMenu 编辑菜单 PasteSpecial 选择性粘贴 GotoLine 光标移到某一行 MatchParenthesis 匹配括号 InsertNewObject 插入新对象 LINGO的菜单 3 LINGOSolution 求解结果 打开求解结果对话框 文本或图表方式查看结果Range 灵敏性分析 产生当前模型的灵敏性分析报告 最优解不变目标函数系数的变化范围 影子价格和缩减系数不变 约束条件右端常数的变化范围 用时需激活 Options 选项设置 Generate 生成模型展开式 Picture 生成图形 LINGO的菜单 3 LINGODebug 调试 ModelStatistics 模型资料统计 Look 查看 LINGO的菜单 4 WindowCommandWindow 命令行窗口 StatusWindow 状态窗口 5 HelpHelpTopics 帮助主题 Register 在线注册 AutoUpdate 自动更新 AboutLingo 关于Lingo Lingo运算符 1 算术运算符 乘方 乘 除 加 减2 逻辑运算符 Lingo运算符 3 关系运算符 表达式左右相等 表达式左边大于或等于右边注 Lingo没有单独的A B 是一个小的正数 Lingo函数 Lingo提供了五十几个内部函数 所有函数都以字符 开头数学函数 ABS x SIN X COS x TAN X LOG X EXP X SIGN X SMAX X1 Xn SMIN X1 Xn FLOOR X LGM X Lingo函数 集合函数集合是Lingo中最重要的概念 使用集合函数 用简单的语句可表达目标函数和约束条件 FOR S TJ E 常用在约束条件中 表示对满足TJ的S中的成员都生成一个表达式E SUM S TJ E 对集合S中的每个成员 分别得到E的值 返回所有这些值的和 MAX S TJ E 对集合S中的每个成员 分别得到E的值 返回所有这些值中的最大值 SIZE S 返回集合S中的成员个数 集合函数 四个集合循环函数 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 Lingo函数 变量定界函数该函数可以改变变量的值或界 BIN X 限制X为0或1 用于0 1规划 BND L X U 限制L X U GIN X 限制X为整数 用于整数规划 FREE X 取消对变量的默认为非负数的限制 即X可取任意实数值注 用 BND L X U 代替约束条件 一方面可提高求解速度 另一方面它不计入约束条件 整数规划例题 背包问题 某人计划外出旅游并登山 路途较远 要坐火车和飞机 要带必要的用品 如 相机 摄相机 衣服 食品 雨具和书籍等 共n件物品 重量分别为ai 能带行李的总重量为b ci表示物品的重要性 价值 该旅行者最多能带哪些物品 才能使总价值最大 该问题称为背包问题 引入0 1型决策变量 表示物品i放入背包 表示物品i不放入背包 则背包问题的数学模型是 整数规划例题 背包问题 数学模型 整数规划例题 背包问题 n 8 a 1 3 4 3 3 1 5 10 c 2 9 3 8 10 4 10 b 15kgLingo程序Model SETS WP W1 W8 A C X ENDSETSDATA A 134331510 C 2938106410 ENDDATAMAX SUM WP C X FOR WP BIN X SUM WP A X 15 END Lingo函数 文件输入输出函数 FILE FN 模型引用其他ASCII码文件中的数据文本 FN是文件名 文件中的数据之间用逗号分开 不同部分之间用 分开 ODBC N 提供LINGO与ODBC 开放数据库连接 的接口 TEXT FN 向文本文件输出数据 参数FN是文件名 通常用于将计算结果写入文件 FILE和 TEXT 文本文件输入输出 MODEL SETS MYSET FILE myfile txt FILE myfile txt ENDSETSMIN SUM MYSET I SHIP I COST I FOR MYSET I CON1 SHIP I NEED I CON2 SHIP I SUPPLY I DATA COST FILE myfile txt NEED FILE myfile txt SUPPLY FILE myfile txt TEXT result txt SHIP DUAL SHIP DUAL CON1 ENDDATAEND myfile txt文件的内容 格式 Seattle Detroit Chicago Denver COST NEED SUPPLY SHIP 12 28 15 20 1600 1800 1200 1000 1700 1900 1300 1100 Lingo函数 其他函数 WARN 文字信息 逻辑表达式 逻辑表达式的值为真时 显示文字信息 用于提示 USER IF 逻辑表达式 逻辑表达式的值为真时的值 逻辑表达式的值为假时的值 通常用来定义分段函数 优化模型 实际问题中的优化模型 x 决策变量 f x 目标函数 gi x 0 约束条件 数学规划 线性规划 LP 二次规划 QP 非线性规划 NLP 纯整数规划 PIP 混合整数规划 MIP 整数规划 IP 0 1整数规划一般整数规划 连续规划 LINDO和LINGO软件能求解的优化模型 LINGO LINDO 优化模型 线性规划 LP 非线性规划 NLP 二次规划 QP 连续优化 整数规划 IP LPQPNLPIP全局优化 选 ILPIQPINLP LINDO LINGO软件的求解过程 LINDO LINGO预处理程序 线性优化求解程序 非线性优化求解程序 分枝定界管理程序 1 确定常数2 识别类型 1 单纯形算法2 内点算法 选 1 顺序线性规划法 SLP 2 广义既约梯度法 GRG 选 3 多点搜索 Multistart 选 LINGO典型应用举例 下料问题指派问题货郎担问题最大流问题最小费用最大流问题 问题1 如何下料最节省 例钢管下料 问题2 客户增加需求 节省的标准是什么 由于采用不同切割模式太多 会增加生产和管理成本 规定切割模式不能超过3种 如何下料最节省 为满足客户需要 按照哪些种合理模式 每种模式切割多少根原料钢管 最为节省 合理切割模式 2 所用原料钢管总根数最少 钢管下料问题1 两种标准 1 原料钢管剩余总余量最小 xi 按第i种模式切割的原料钢管根数 i 1 2 7 约束 满足需求 决策变量 目标1 总余量 按模式2切割12根 按模式5切割15根 余料27米 最优解 x2 12 x5 15 其余为0 最优值 27 整数约束 xi为整数 当余料没有用处时 通常以总根数最少为目标 目标2 总根数 钢管下料问题1 约束条件不变 最优解 x2 15 x5 5 x7 5 其余为0 最优值 25 xi为整数 按模式2切割15根 按模式5切割5根 按模式7切割5根 共25根 余料35米 虽余料增加8米 但减少了2根 与目标1的结果 共切割27根 余料27米 相比 钢管下料问题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米长的钢管的数量 满足需求 模式合理 每根余料不超过3米 整数非线性规划模型 钢管下料问题2 目标函数 总根数 约束条件 整数约束 xi r1i r2i r3i r4i i 1 2 3 为整数 LINGO程序 MODEL SETS cutfa 1 2 3 x buj 1 4 L NEED SHUL CUTFA BUJ N ENDSETSDATAL 4568 NEED 50102015 ZL 19 ENDDATAMIN SUM CUTFA X FOR BUJ J SUM CUTFA I N I J0 X I NEED J FOR CUTFA I SUM BUJ J N I J L J 16 FOR SHUL GIN N FOR CUTFA GIN X END 增加约束 缩小可行域 便于求解 原料钢管总根数下界 特殊生产计划 对每根原料钢管模式1 切割成4根4米钢管 需13根 模式2 切割成1根5米和2根6米钢管 需10根 模式3 切割成2根8米钢管 需8根 原料钢管总根数上界 31 模式排列顺序可任定 钢管下料问题2 需求 4米50根 5米10根 6米20根 8米15根 每根原料钢管长19米 LINGO求解整数非线性规划模型 Localoptimalsolutionfoundatiteration 12211Objectivevalue 28 00000VariableValueReducedCostX110 000000 000000X210 000002 000000X38 0000001 000000R113 0000000 000000R122 0000000 000000R130 0000000 000000R210 0000000 000000R221 0000000 000000R230 0000000 000000R311 0000000 000000R321 0000000 000000R330 0000000 000000R410 0000000 000000R420 0000000 000000R432 0000000 000000 模式1 每根原料钢管切割成3根4米和1根6米钢管 共10根 模式2 每根原料钢管切割成2根4米 1根5米和1根6米钢管 共10根 模式3 每根原料钢管切割成2根8米钢管 共8根 原料钢管总根数为28根 例指派问题 最优匹配问题 n项任务分配给n个人 每人一项每人完成各项工作所需时间不同问题 如何分配所需总时间最少 一类重要的组合优化问题 用0 1变量 表示分配情况 表示第i个人做j工作 表示第i个人不做j工作 表示第i人做j工作时间 问题的数学模型是0 1规划 例指派问题 最优匹配问题 数学模型 例指派问题 最优匹配问题 LINGO程序 MODEL SETS WORKER W1 W5 JOB J1 J5 LINKS WORKER JOB C X ENDSETSDATA C ENDDATAMIN SUM LINKS C X FOR WORKER I SUM JOB J X I J 1 FOR JOB J SUM WORKER I X I J 1 FOR LINKS BIN X END 例货郎担问题 一个货郎 旅客 从某地出发售货 旅游 要到若干地方各一次 仅一次 最后返回出发地 问如何安排路线所走路程最短 所花费用最少 该问题也称旅行商问题 TSP 是一个重要的组合优化问题 是NP 完全问题 至今无多项式时间算法 近似解也不易求得 TSP近似算法 构造算法 改进型算法 二边逐次修正法神经网络方法 模拟退火方法 混合整数规划法 例货郎担问题 混合整数规划法