#优化模型与LINGO软件求解

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