优化模型与LINGO软件求解课件

优化模型与LINGO软件求解竞赛题中的优化模型总结优化模型与建模要点典型优化问题与LINGO求解谭代伦2012年7月数模竞赛培训优化模型与LINGO软件求解竞赛题中的优化模型总结谭代伦1一、竞赛题中的优化模型总结1.竞赛题中的优化问题实例2011年B题交巡警服务平台的设置与调度2007年B题乘公交,看奥运2006年A题出版社的资源配置2005年B题DVD在线租赁2004年B题电力市场的输电阻塞管理2003年B题露天矿生产的车辆安排一、竞赛题中的优化模型总结1.竞赛题中的优化问题实例2一、竞赛题中的优化模型总结2.优化类竞赛题小结在全国数模竞赛中，优化问题是出现频率最高的一类竞赛题。从1992-2011年全国大学生数模竞赛试题的解题方法统计结果来看，优化模型共出现了17次以上，占到了50%。即每两道竞赛题中就有一道涉及到利用优化理论来建模和求解。一、竞赛题中的优化模型总结2.优化类竞赛题小结3一、竞赛题中的优化模型总结特别提示：近年来，评价模型有逐渐增多的趋势。2005年A题长江水质的评价与预测2008年B题高等教育学费标准探讨2010年B题上海世博会影响力的定量评估2010年D题对学生宿舍设计方案的评价另外，拟合、回归、预测(灰预测,时间序列分析)也是常用辅助手段之一。一、竞赛题中的优化模型总结特别提示：4二、优化模型与建模要点(一)优化模型的分类优化模型无约束优化模型(函数极值问题)约束优化模型线性规划非线性规划动态规划目标规划(单/多)数学规划图论与网络优化组合优化整数规划0-1规划(按优化方法分)连续型优化问题离散型优化问题二、优化模型与建模要点(一)优化模型的分类优化模型无约束优化5二、优化模型与建模要点(二)数学规划概述1.“数学规划”的含义利用一定的数学工具和方法，对给定实际问题进行合理的安排，“合理”通常就是要达到最优化/最佳，因此规划是基础，优化是目的。2.数学规划模型的三要素决策变量目标函数约束条件二、优化模型与建模要点(二)数学规划概述6二、优化模型与建模要点3.建立数学规划模型的几条注意(1)尽量使用实数优化，减少整数约束和整数变量。(2)尽量使用光滑优化，减少非光滑约束的个数。如：尽量少使用绝对值、符号函数、多个变量求最大/最小值、四舍五入、取整函数等。(3)尽量使用线性表达式，减少非线性约束和非线性变量的个数。如：x/y<5改为x<5y(4)合理设定变量上下界，尽可能给出变量初始值(5)模型中使用的参数数量级要适当(如小于103)(6)巧用0-1变量变换约束。二、优化模型与建模要点3.建立数学规划模型的几条注意7二、优化模型与建模要点“巧用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.(尽量少用非线性)二、优化模型与建模要点“巧用0-1变量变换约束”的示例8二、优化模型与建模要点练习题：在生产计划问题中，某产品的成本(或利润)是分段函数，例如：请按上述约束变换思路改写约束条件。二、优化模型与建模要点练习题：请按上述约束变换思路改写约束条9二、优化模型与建模要点4.优化模型的求解(1)自编程序求解(2)利用现有软件求解LINGOMATLAB二、优化模型与建模要点4.优化模型的求解10三、典型优化问题与LINGO软件求解(一)LINGO软件概述LINGO是用来求解线性和非线性优化问题的简易工具。LINGO内置了一种建立最优化模型的语言，可以简便地表达大规模问题，利用LINGO高效的求解器可快速求解并分析结果。

三、典型优化问题与LINGO软件求解(一)LINGO软件概11(二)LINGO软件的操作界面主菜单工具栏程序编辑窗口(可同时编辑多个文档)(二)LINGO软件的操作界面主菜单程序编辑窗口(可同时编12(三)典型数学规划问题及求解典型的线性规划问题一般的线性规划问题生产计划问题生产调度问题下料(截割)问题配料(搭配)问题两类特殊的线性规划问题运输问题：平衡与不平衡运输问题、转运问题分派问题：分工问题、选址问题、设备安装问题整数规划0-1规划(三)典型数学规划问题及求解典型的线性规划问题整数规划0-13(三)典型数学规划问题及求解例1下料(截割)问题及求解例2运输问题及求解例3非线性规划问题及求解例4分派(选址)问题及求解例5动态规划问题及求解(三)典型数学规划问题及求解例1下料(截割)问题及求解14[例1]下料(截割)问题及求解1.问题提出2.建立数学模型3.编写LINGO求解程序4.执行程序5.获得计算结果并分析6.修正模型，重新求解7.课后作业8.编程小结主要目的：(1)再次熟悉该类问题的规划模型;(2)学习LINGO的简单编程方法[例1]下料(截割)问题及求解1.问题提出主要目的：15[例1]下料(截割问题)及求解1.问题提出某建筑工地需要做100套成品钢筋，每套为3根，其规格分别为2.9m、2.1m、1.5m。现原料钢筋均为7.4m长。问应该怎样截割原料钢筋，才能使所需原料钢筋根数为最少？(设截割时截口宽度忽略不计)[例1]下料(截割问题)及求解1.问题提出16[例1]下料(截割问题)及求解2.建模关键:一根原料钢筋的截割方法成品钢筋及根数截割方法123456782.9m(根数)2.1m(根数)1.5m(根数)201120111103030022013004剩余材料(m)0.10.30.901.10.20.81.4决策变量：设第i种截割方法使用了xi次，相应地耗用原材料为xi根。目标函数：根据目标不同，可建立两种模型(1)和(2).[例1]下料(截割问题)及求解2.建模关键:一根原料钢17[例1]下料(截割问题)及求解以“使剩余原料最少”为目标的模型(1)[例1]下料(截割问题)及求解以“使剩余原料最少”为目标18[例1]下料(截割问题)及求解以“使所用原料钢筋数最少”为目标的模型(2)[例1]下料(截割问题)及求解以“使所用原料钢筋数最少”19[例1]下料(截割问题)及求解3.用LINGO的简单模型语言编程(模型-1)的求解程序[例1]下料(截割问题)及求解3.用LINGO的简单模20[例1]下料(截割问题)及求解(模型-2)的求解程序：[例1]下料(截割问题)及求解(模型-2)的求解程序：21[例1]下料(截割问题)及求解LINGO的简单编程语言特点：(1)以感叹号(!)开头、以分号结束的行是注释；(2)按模型表达式顺序书写程序语句；(3)以“min=”或“max=”开始的语句是目标函数，其余为约束条件；(4)英文字母不区分大小写;(5)表达式中的运算符不能省略；(6)一个语句占一行，行末用分号(;)结束。(7)LINGO软件默认所有变量均为非负，故xi≥0可不输入.[例1]下料(截割问题)及求解LINGO的简单编程语言特点22[例1]下料(截割问题)及求解4.执行LINGO求解程序菜单：LINGOSolve(CTRL+U)工具栏：[例1]下料(截割问题)及求解4.执行LINGO求解程23[例1]下料(截割问题)及求解5.获得求解结果并分析(1)状态结果(2)数值结果：最优目标值与最优解[例1]下料(截割问题)及求解5.获得求解结果并分析24[例1]下料(截割问题)及求解[模型-1]的求解结果：(1)模型种类LP:线性规划NLP:非线性规划(2)最优状态全局全优(3)最优目标值:10变量情况(1)变量总数(2)非线性变量数(3)整型变量数约束条件情况(1)约束总个数(2)非线性个数最优目标值:10最优解：X4=100,按方法4X6=50,按方法6[例1]下料(截割问题)及求解[模型-1]的求解结果：(125[例1]下料(截割问题)及求解[模型-2]的求解结果：最优目标函数值：90x1=40,按方法1截割x2=20,按方法2截割x6=30.按方法6截割[例1]下料(截割问题)及求解[模型-2]的求解结果：最优26[例1]下料(截割问题)及求解求解结果分析：模型(2)的求解结果：最优目标(原料)=90根(x1,x2,x6)=(40,20,30)余料=?模型(1)的求解结果：最优目标(余料)=10m(x4,x6)=(100,50)耗用原料=150根是否符合原问题要求?不符合。(1)问题出在哪里?(2)如何修正?符合原问题要求是否?符。(1)余料=16m合(2)是否唯一最优解?在追求“余料最少”目标时，“≥”约束把条件放宽了。修正方法：改为“=”约束[例1]下料(截割问题)及求解求解结果分析：模型(2)的求27[例1]下料(截割问题)及求解6.修正模型，再次求解将模型(1)中约束条件的“>=”改为=”后，再次求解的结果为：最少余料=16m(x1,x2,x4)=(10,50,30)耗用原料=90根[例1]下料(截割问题)及求解6.修正模型，再次求解将模28[例1]下料(截割问题)及求解7.课后作业题1设一根原料的长度为L米，需截割成n种规格为(k1,k2,…,kn)的成品.例如：原料长10m,成品有5种规格：(2.1,3.7,4.5,0.8,1.5)m。请编程将其所有可能的截割方法和截割结果列举出来。要求：能从文件导入数据，能将程序运行结果输出到文本文件或EXCEL文件中[例1]下料(截割问题)及求解7.课后作业题129[例1]下料(截割问题)及求解7.课后作业题2教室的紧急撤离问题某学校发生紧急情况需撤离全体人员。现考虑该校教学楼某一层楼中单侧教室的全体人员的紧急撤离情况，试建立该问题的数学模型并编程求解。[例1]下料(截割问题)及求解7.课后作业题230[例1]下料(截割问题)及求解8.LINGO简单编程的总结主要不足：不适于编写大规模的模型程序大规模模型：目标函数表达式较长约束条件数很多变量的取值情形比较复杂返回[例1]下料(截割问题)及求解8.LINGO简单编程的总31[例2]运输问题及求解1.问题提出2.建立数学模型3.编写LINGO求解程序4.获得求解结果并分析5.编程小结主要目的：(1)进一步熟悉运输问题的整数规划模型；(2)学习LINGO的集合语言编程。[例2]运输问题及求解1.问题提出主要目的：32[例2]运输问题及求解1.问题提出某企业有6个生产分厂和8个销售点，已知各厂的生产能力、各销售点的需求量、任意生产厂和销售点之间的单位运费如下表，求使总运输最小的商品运输方案。B1B2B3B4B5B6B7B8产量A16267425960A24953858255A35219743351A47673927143A52395726541A65522814352销量3537223241324338

[例2]运输问题及求解1.问题提出B1B2B3B4B5B33[例2]运输问题及求解2.建立模型记：cij---第i个厂到第j个点的单位运费ai---第i个厂的产量，bj---第j个点的销量设：xij---第i个厂到第j个点的运输量B1B2B3B4B5B6B7B8产量A160A255A3(xij)51A443A541A652销量3537223241324338

[例2]运输问题及求解2.建立模型B1B2B3B4B5B34[例2]运输问题及求解产量约束共6个约束条件销量约束共8个约束条件[例2]运输问题及求解产量约束销量约束35[例2]运输问题及求解模型说明：(1)当全部变量xij要求取整数值时，这类模型称为纯整数规划模型(PILP).(2)在运输问题中，当“产量总和=销量总和”时，称为平衡运输问题，此时模型的约束条件用“=”号。(3)否则，称为不平衡运输问题，又可分为：A.产>销，此时“产量约束”可用“≤”号。B.产<销，此时“销量约束”可用“≤”号。本题中：总产量=302>总销量=280[例2]运输问题及求解模型说明：36[例2]运输问题及求解3.利用LINGO集合语言编程(1)模型有多少变量和常数？变量：xij,有6×8=48个（可看作二维数组）常量：产量：ai，共6个（可看作一维数组）销量：bj，共8个（可看作一维数组）单位运费：cij，共48个（可看作二维数组）[例2]运输问题及求解3.利用LINGO集合语言编程37[例2]运输问题及求解(2)LINGO模型语言的框架MODEL:SETS:……ENDSETS…………DATA:……ENDDATAEND

集(sets)：是模型中各种对象(常量和变量)聚集在一起，称为集。如:生产厂、销售点、单位运费、运输量。(类似于数组)

集包括：A.集名:(结构体)B.成员:(结构体成员)C.属性:成员的特征(结构体实例)

例如：“生产厂”是一个对象(集)，有6个成员，它们都有一个“产量”属性。定义“生产厂”集的语句：factory/fa1..fa6/:capcity;集名成员名“产量”属性(多个属性用逗号分开)

练习：定义“销售点”集及其属性[例2]运输问题及求解(2)LINGO模型语言的框架38[例2]运输问题及求解(2)LINGO模型语言的框架MODEL:SETS:……ENDSETS…………DATA:……ENDDATAEND

派生集：由现有的集再定义新的集

定义派生集的语句格式：派生集名(集1,…,集n)/[成员]/:[属性];

例如：“单位运费(cij)”集、“运输量(xij)”集，可看作是由“生产厂”集和“销售点”集派生出来的。定义语句：Link(factory,vendors):cost,x

派生集名现有集名(原始集)属性名“成员”省略，其个数默认为6×8=48个[例2]运输问题及求解(2)LINGO模型语言的框架39[例2]运输问题及求解(2)LINGO模型语言的框架MODEL:SETS:……ENDSETS…………DATA:……ENDDATAEND目标函数和约束条件语句其中，以“min=”或“max=”开始的语句为目标函数。数据部分(DATA)：

提供各类数据，主要给集的各个属性赋值。可直接列出，也可从其他文档中导入。[例2]运输问题及求解(2)LINGO模型语言的框架目标40[例2]运输问题及求解(2)LINGO模型语言的框架MODEL:SETS:……ENDSETS…………DATA:……ENDDATAEND直接列出数据法：capacity=605551434152;demand=3537223241324338;cost=626742954953858252197433767392712395726555228143;

一组数据按行方式列出，数据以空格分开，行末以分号结束。一个矩阵数据以矩阵形式列出，数据的行和列即为矩阵的行和列，只在最后一行以分号结束。[例2]运输问题及求解(2)LINGO模型语言的框架直接41[例2]运输问题及求解含集和数据的程序段MODEL:SETS:fact/fa1..fa6/:capacity;vend/ve1..ve8/:demand;links(fact,vend):cost,x;ENDSETS……DATA:capacity=605551434152;demand=3537223241324338;cost=626742954953858252197433767392712395726555228143;

ENDDATAEND[例2]运输问题及求解含集和数据的程序段MODEL:D42[例2]运输问题及求解(2)LINGO模型语言的框架MODEL:SETS:……ENDSETS…………DATA:……ENDDATAEND

从文档导入数据：借助导入数据函数：

A.@file(‘文件名’)---从文本文件读取数据B.@OLE(‘文件名’)---从EXCEL文件读取数据[例2]运输问题及求解(2)LINGO模型语言的框架43[例2]运输问题及求解A.@file(‘文件名’)---从文本文件导入数据a)将数据输入到文本文件中b)编写DATA段数据之间以空格分开，以“~”结束的为一条数据记录；每执行一次@file()函数，只读取一条数据记录。DATAcapacity=@file(‘samp02_data.txt’);demand=@file(‘samp02_data.txt’);cost=@file(‘samp02_data.txt’);ENDDATA[例2]运输问题及求解A.@file(‘文件名’)--44[例2]运输问题及求解B.@OLE(‘文件名’)---从EXCEL文件导入数据a)将数据输入到EXCEL文件中b)编写DATA段数据输入到EXCEL工作表后，还要对每个数据区域定义一个名称。定义方法：(1)选中每一个数据区域；(2)选菜单“插入名称定义”，为每一个数据区域定义一个名称，如capacity,demand,cost.[例2]运输问题及求解B.@OLE(‘文件名’)---45[例2]运输问题及求解(2)LINGO模型语言的框架MODEL:SETS:……ENDSETS…………DATA:……ENDDATAEND目标函数和约束条件的语句编写方法[例2]运输问题及求解(2)LINGO模型语言的框架目标46[例2]运输问题及求解A.目标函数的构成与书写方法1：Min=c(1,1)*x(1,1)+c(1,2)*x(1,2)+…+c(6,8)*x(6,8);方法2：利用求和函数@sum()Min=@sum(links:cost*x);LINGO的数组：(1)一维数组:a(1),a(2)(2)二维数组：a(1,1)a(2,1)集名属性名两个数组或矩阵的对应元素相乘，再累加[例2]运输问题及求解A.目标函数的构成与书写LINGO47[例2]运输问题及求解B.约束条件的构成与书写产量约束、销量约束：每个式子均为累加和，共14个。方法：使用循环函数+求和函数@FOR(),@SUM()约束语句：!按fact集的成员顺序生成sum表达式@for(fact(i):@sum(vend(j):x(i,j))<=capacity(i));!按vend集的成员顺序生成sum表达式@for(vend(j):@sum(fact(i):x(i,j))=demand(j));[例2]运输问题及求解B.约束条件的构成与书写产量约束、48[例2]运输问题及求解C.变量约束的构成与书写变量约束：非负且取整数：方法：使用取整函数@GIN(x)--x只能取0或正整数其他函数：@bnd(L,x,U)--L≤x≤U@free(x)--x可以取任意实数@bin(x)--x只能取0或1

变量约束语句：@for(links(i,j):@gin(x(i,j)));或@for(links:@gin(x));[例2]运输问题及求解C.变量约束的构成与书写变量约束：49[例2]运输问题及求解[例2]运输问题及求解50[例2]运输问题及求解4.“运输问题”的求解结果最优目标值为664[例2]运输问题及求解4.“运输问题”的求解结果最优目标51[例2]运输问题及求解4.“运输问题”的求解结果最优目标函数值为664[例2]运输问题及求解4.“运输问题”的求解结果最优目标52[例2]运输问题及求解xij12345678∑1194160213233311405145384353474162227352∑3537223241324338[例2]运输问题及求解xij12345678∑11941653[例2]运输问题及求解[例2]运输问题及求解54[例2]运输问题及求解[例2]运输问题及求解55[例2]运输问题及求解集合语言编程小结1.LINGO模型语文的初始化段Init:….endinit2.简单模型语言编程的语法要求也同样适用于集合语言编程。3.集合语言的灵活性更强，可求解的模型更多。用于对决策变量赋初值，使能更快找到最优解.返回[例2]运输问题及求解集合语言编程小结用于对决策变56例3非线性规划问题及求解[例3]求解下面最优化问题例3非线性规划问题及求解[例3]求解下面最优化问题57补充：LINGO的运算符与函数1.运算符(1)算术运算符+(加)，-(减)，*(乘)，/(除)，^(乘方)，-(负)(2)逻辑运算符A.#not#(逻辑取反)B.#eq#,#ne#;#gt#,#ge#;#lt#,#le#(＝,≠;＞,≥;＜,≤)C.#and#,#or#(与，或)补充：LINGO的运算符与函数1.运算符58补充：LINGO的运算符与函数2.常用函数@abs(x)—求x的绝对值;@sin(x)—求x的正弦值;@cos(x)—求x的余弦值;@tan(x)—求x的正切值;@exp(x)—求常数e的x次方;@log(x)—求x的自然对数@sign(x)—若x<0则返回-1，否则返回1@floor(x)—取得x的整数部分：若x>0，取不超过x的整数；若x<0，取不低于x的整数值。补充：LINGO的运算符与函数2.常用函数59补充：LINGO的运算符与函数@mod(x,y)—求x除以y的余数，x,y均为整数。@pow(x,y)—求x的y次方。@sqr(x)—求x的平方函数@sqrt(x)—求x的开平方函数@smax(x1,x2,…,xn)—返回n个数中的最大者@smin(x1,x2,…,xn)—返回n个数中的最小者@IF(条件,值1，值2)—若条件为真取值1,否则取值2补充：LINGO的运算符与函数@mod(x,y)—求x除以y60例3非线性规划问题及求解[例3]的LINGO求解程序例3非线性规划问题及求解[例3]的LINGO求解程序61例3非线性规划问题及求解例3非线性规划问题及求解62例3非线性规划问题及求解练习题：1.给定一个直角三角形，求包含该三角形的最小正方形。试建立该问题的模型并求解。2.建筑工地的位置(用平面坐标a,b表示，距离单位：公里)及水泥日用量d(吨)如下表。现有两个临时料场位于P(5,1),Q(2,7)，日储量各有20吨。(1)从P,Q两个临时料场分别向各工地运送多少吨水泥，使总的吨公里数最小。(2)若重新建两个料场，应建在何处，节省的吨公里数有多大？例3非线性规划问题及求解练习题：63例3非线性规划问题及求解工地１２３４５６坐标a(公里)1.258.750.55.7537.25坐标b(公里)1.250.754.7556.57.75需求量d(吨)3547611料场P(5,1)料场Q(2,7)新料场A(?,?)新料场B(?,?)返回例3非线性规划问题及求解工地１２３４５６坐标a(公里)164例40-1型规划问题及求解例4-1[选址问题]某公司准备在一个城市设立3个销售部，共有7个地点可供选择，记为A1,A2,…,A7。经过对7个地点进行考察，确定了若选用Ai点则需投资设备bi元（投资总额不得超过B元），预计每年可赢利ci元。另外，对地点的选择确定了几条要求：(A1,A2,A3)中最多选2个，(A4,A5)中至少选1个，(A6,A7)中至少选1个。问：应选择哪几个点可使年利润达到最大？

例40-1型规划问题及求解例4-1[选址问题]65例40-1型规划问题及求解例4-1[选址问题]例40-1型规划问题及求解例4-1[选址问题]66例40-1型规划问题及求解例4-1[选址问题]取以下数据作计算B=18A1A2A3A4A5A6A7bi6573454ci16131714151615例40-1型规划问题及求解例4-1[选址问题]B=167例40-1型规划问题及求解例4-2[分派问题]大众出租车公司配备有无线调度系统，现有五位客人电话要车。公司调度从卫星定位系统了解到本公司分别有五辆合适的可用车，车与客人的距离如下所示：为了使空驰数最小，如何为每一位客人安排车辆？空驰公里总数是多少？客A客B客C客D客E车1车2车3车4车53421535214532144321534123例40-1型规划问题及求解例4-2[分派问题]客A68例40-1型规划问题及求解例4-2[分派问题]客A客B客C客D客E车1车2车3车4车53421535214532144321534123客A客B客C客D客E车1车2车3车4车5x11

x12

x13

x14

x15……..……