《外校优化模型及lingo软件求解》由会员分享,可在线阅读,更多相关《外校优化模型及lingo软件求解(77页珍藏版)》请在金锄头文库上搜索。
1、优化模型与LINGO软件求解,竞赛题中的优化模型总结 优化模型与建模要点 典型优化问题与LINGO求解,谭代伦 (15351279580) 2012年7月数模竞赛培训,一、竞赛题中的优化模型总结,1.竞赛题中的优化问题实例 2011年B题 交巡警服务平台的设置与调度 2007年B题 乘公交,看奥运 2006年A题 出版社的资源配置 2005年B题 DVD在线租赁 2004年B题 电力市场的输电阻塞管理 2003年B题 露天矿生产的车辆安排,一、竞赛题中的优化模型总结,2.优化类竞赛题小结 在全国数模竞赛中,优化问题是出现频率最高的一类竞赛题。 从1992-2011年全国大学生数模竞赛试题的解题
2、方法统计结果来看,优化模型共出现了17次以上,占到了50%。 即每两道竞赛题中就有一道涉及到利用优化理论来建模和求解。,一、竞赛题中的优化模型总结,特别提示: 近年来,评价模型有逐渐增多的趋势。 2005年A题 长江水质的评价与预测 2008年B题 高等教育学费标准探讨 2010年B题 上海世博会影响力的定量评估 2010年D题 对学生宿舍设计方案的评价 另外,拟合、回归、预测(灰预测,时间序列分析)也是常用辅助手段之一。,二、优化模型与建模要点,(一)优化模型的分类,优化模型,无约束优化模型(函数极值问题),约束优化模型,线性规划,非线性规划,动态规划,目标规划(单/多),数学规划,图论与网
3、络优化,组合优化,整数规划,0-1规划,(按优化方法分),连续型优化问题 离散型优化问题,二、优化模型与建模要点,(二)数学规划概述 1. “数学规划”的含义 利用一定的数学工具和方法,对给定实际问题进行合理的安排,“合理”通常就是要达到最优化/最佳,因此规划是基础,优化是目的。 2. 数学规划模型的三要素 决策变量 目标函数 约束条件,二、优化模型与建模要点,3. 建立数学规划模型的几条注意 (1) 尽量使用实数优化,减少整数约束和整数变量。 (2) 尽量使用光滑优化,减少非光滑约束的个数。 如:尽量少使用绝对值、符号函数、多个变量求最大/最小值、四舍五入、取整函数等。 (3) 尽量使用线性
4、表达式,减少非线性约束和非线性变量的个数。如:x/y 5 改为 x5y (4) 合理设定变量上下界,尽可能给出变量初始值 (5) 模型中使用的参数数量级要适当 (如小于103) (6) 巧用0-1变量变换约束。,二、优化模型与建模要点,“巧用0-1变量变换约束”的示例 示例1:在生产计划问题中,有要求:某产品若要生产则至少达到M0。 基本表达方法:x0 或 M0 方法1: 分别取约束“x0”和“xM0”,加入原模型分别求解 方法2: 引入0-1变量y=0,1,则表示为: x80y, y=0,1. 方法3: 化为非线性约束x(x-80)0 . (尽量少用非线性),二、优化模型与建模要点,练习题:
5、 在生产计划问题中,某产品的成本(或利润)是分段函数,例如:,请按上述约束变换思路改写约束条件。,二、优化模型与建模要点,4. 优化模型的求解 (1) 自编程序求解 (2) 利用现有软件求解 LINGO MATLAB,三、典型优化问题与LINGO软件求解,(一) LINGO软件概述 LINGO是用来求解线性和非线性优化问题的简易工具。 LINGO内置了一种建立最优化模型的语言,可以简便地表达大规模问题,利用LINGO高效的求解器可快速求解并分析结果。,(二) LINGO软件的操作界面,主菜单 工具栏,程序编辑窗口(可同时编辑多个文档),(三) 典型数学规划问题及求解,典型的线性规划问题 一般的
6、线性规划问题 生产计划问题 生产调度问题 下料(截割)问题 配料(搭配)问题 两类特殊的线性规划问题 运输问题:平衡与不平衡运输问题、转运问题 分派问题:分工问题、选址问题、设备安装问题,(三) 典型数学规划问题及求解,例1 下料(截割)问题及求解 例2 运输问题及求解 例3 非线性规划问题及求解 例4 分派(选址)问题及求解 例5 动态规划问题及求解,例1 下料(截割)问题及求解,1. 问题提出 2. 建立数学模型 3. 编写LINGO求解程序 4. 执行程序 5. 获得计算结果并分析 6. 修正模型,重新求解 7.课后作业 8.编程小结,主要目的: (1) 再次熟悉该类问题的规划模型; (
7、2) 学习LINGO的简单编程方法,例1 下料(截割问题)及求解,1. 问题提出 某建筑工地需要做100套成品钢筋,每套为3根,其规格分别为2.9m、2.1m、1.5m。现原料钢筋均为7.4m长。 问应该怎样截割原料钢筋,才能使所需原料钢筋根数为最少?(设截割时截口宽度忽略不计),例1 下料(截割问题)及求解,2. 建模关键: 一根原料钢筋的截割方法,例1 下料(截割问题)及求解,以“使剩余原料最少”为目标的模型(1),例1 下料(截割问题)及求解,以“使所用原料钢筋数最少”为目标的模型(2),例1 下料(截割问题)及求解,3. 用LINGO的简单模型语言编程 (模型-1)的求解程序,例1 下
8、料(截割问题)及求解,(模型-2)的求解程序:,例1 下料(截割问题)及求解,LINGO的简单编程语言特点: (1) 以感叹号(!)开头、以分号结束的行是注释; (2) 按模型表达式顺序书写程序语句; (3) 以“min=”或“max=”开始的语句是目标函数,其余为约束条件; (4) 英文字母不区分大小写; (5) 表达式中的运算符不能省略; (6) 一个语句占一行,行末用分号(;)结束。 (7) LINGO软件默认所有变量均为非负,故xi0可不输入.,例1 下料(截割问题)及求解,4. 执行LINGO求解程序 菜单:LINGOSolve (CTRL+U) 工具栏:,例1 下料(截割问题)及求
9、解,5. 获得求解结果并分析 (1) 状态结果 (2) 数值结果:最优目标值与最优解,例1 下料(截割问题)及求解,模型-1的求解结果:,(1)模型种类 LP: 线性规划 NLP: 非线性规划 (2)最优状态 全局全优 (3)最优目标值: 10,变量情况 (1)变量总数 (2)非线性变量数 (3)整型变量数,约束条件情况 (1)约束总个数 (2)非线性个数,最优目标值: 10,最优解: X4=100,按方法4 X6=50, 按方法6,例1 下料(截割问题)及求解,模型-2的求解结果:,最优目标函数值:90,x1=40, 按方法1截割 x2=20, 按方法2截割 x6=30. 按方法6截割,例1
10、 下料(截割问题)及求解,求解结果分析:,模型(2)的求解结果: 最优目标(原料)=90根 (x1,x2,x6)=(40,20,30) 余料 = ?,模型(1)的求解结果: 最优目标(余料)=10m (x4,x6)=(100,50) 耗用原料 = 150根,是否符合原问题要求?,不符合。 (1)问题出在哪里? (2)如何修正?,符合原问题要求是否?,符。 (1)余料 = 16m 合(2)是否唯一最优解?,在追求“余料最少”目标时,“”约束把条件放宽了。 修正方法:改为“=”约束,例1 下料(截割问题)及求解,6.修正模型,再次求解,将模型(1)中约束条件的“=”改为=”后,再次求解的结果为:
11、最少余料 = 16m (x1,x2,x4)=(10,50,30) 耗用原料 = 90根,例1 下料(截割问题)及求解,7.课后作业题1 设一根原料的长度为L米,需截割成n种规格为(k1,k2,kn)的成品.例如:原料长10m, 成品有5种规格:(2.1,3.7,4.5,0.8,1.5)m。请编程将其所有可能的截割方法和截割结果列举出来。 要求:能从文件导入数据,能将程序运行结果输出到文本文件或EXCEL文件中,例1 下料(截割问题)及求解,7.课后作业题2 教室的紧急撤离问题 某学校发生紧急情况需撤离全体人员。现考虑该校教学楼某一层楼中单侧教室的全体人员的紧急撤离情况,试建立该问题的数学模型并
12、编程求解。,例1 下料(截割问题)及求解,8. LINGO简单编程的总结 主要不足:不适于编写大规模的模型程序 大规模模型: 目标函数表达式较长 约束条件数很多 变量的取值情形比较复杂,返回,例2 运输问题及求解,1. 问题提出 2. 建立数学模型 3. 编写LINGO求解程序 4. 获得求解结果并分析 5. 编程小结,主要目的: (1) 进一步熟悉运输问题的整数规划模型; (2) 学习LINGO的集合语言编程。,例2 运输问题及求解,1. 问题提出 某企业有6个生产分厂和8个销售点,已知各厂的生产能力、各销售点的需求量、任意生产厂和销售点之间的单位运费如下表,求使总运输最小的商品运输方案。,
13、例2 运输问题及求解,2. 建立模型 记:cij-第i个厂到第j个点的单位运费 ai-第i个厂的产量,bj-第j个点的销量 设:xij-第i个厂到第j个点的运输量,例2 运输问题及求解,产量约束 共6个约束条件,销量约束 共8个约束条件,例2 运输问题及求解,模型说明: (1) 当全部变量xij要求取整数值时,这类模型称为纯整数规划模型(PILP). (2) 在运输问题中,当“产量总和=销量总和”时,称为平衡运输问题,此时模型的约束条件用“=”号。 (3) 否则,称为不平衡运输问题,又可分为: A. 产销,此时“产量约束”可用“”号。 B. 产 总销量=280,例2 运输问题及求解,3. 利用
14、LINGO集合语言编程 (1) 模型有多少变量和常数? 变量: xij, 有68=48个 (可看作二维数组) 常量: 产量:ai,共6个 (可看作一维数组) 销量:bj,共8个 (可看作一维数组) 单位运费:cij,共48个 (可看作二维数组),例2 运输问题及求解,(2) LINGO模型语言的框架 MODEL: SETS: ENDSETS DATA: ENDDATA END,集(sets):是模型中各种对象(常量和变量)聚集在一起,称为集。如: 生产厂、销售点、单位运费、运输量。(类似于数组) 集包括: A.集名: (结构体) B.成员: (结构体成员) C.属性: 成员的特征 (结构体实例
15、) 例如:“生产厂”是一个对象(集),有6个成员,它们都有一个“产量”属性。 定义“生产厂”集的语句: factory/fa1fa6/:capcity; 集名 成员名 “产量”属性 (多个属性用逗号分开) 练习:定义“销售点”集及其属性,例2 运输问题及求解,(2) LINGO模型语言的框架 MODEL: SETS: ENDSETS DATA: ENDDATA END,派生集:由现有的集再定义新的集 定义派生集的语句格式: 派生集名(集1,集n)/成员/:属性; 例如:“单位运费(cij)”集、“运输量(xij)”集,可看作是由“生产厂”集和“销售点”集派生出来的。 定义语句: Link(factory,vendors): cost,x,派生集名,现有集名(原始集),属性名,“成员”省略,其个数默认为68=48个,例2 运输问题及求解,(2) LINGO模型语言的框架 MODEL: SETS: ENDSETS DATA: ENDDATA END,目标函数和约束条件语句 其中,以“min=”或“max=”开始的语句为目标函数。,数据部分(DATA): 提供各类数据,主要给集的各个属性赋值。可直接列出,也可从其他文档中导入。,例2 运输问题及求解,(2) LINGO模型语言的框架 MODEL: SETS: ENDSETS DATA: ENDDATA END,直接列出数据法: cap