《外校优化模型及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
