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

《优化模型与LINGO软件求解ppt课件.ppt》由会员分享，可在线阅读，更多相关《优化模型与LINGO软件求解ppt课件.ppt（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题 对学生宿舍设计方案的评价另外，拟合、回归、预测(灰预测,时间序列分析)也是常用辅助手段之一。,二、优化模型与建模要点,(一)优化模型的分类,优化模型,无约束优化模型(函数极值问题),约束优化模型,线性规划,非线性规划,动态规划,目标规划(单/多),数学规划,图论与网络优化,组合优化,整数规划,0-1规

3、划,(按优化方法分),连续型优化问题离散型优化问题,二、优化模型与建模要点,(二)数学规划概述1. “数学规划”的含义利用一定的数学工具和方法，对给定实际问题进行合理的安排，“合理”通常就是要达到最优化/最佳，因此规划是基础，优化是目的。2. 数学规划模型的三要素决策变量目标函数约束条件,二、优化模型与建模要点,3. 建立数学规划模型的几条注意(1) 尽量使用实数优化，减少整数约束和整数变量。(2) 尽量使用光滑优化，减少非光滑约束的个数。 如：尽量少使用绝对值、符号函数、多个变量求最大/最小值、四舍五入、取整函数等。(3) 尽量使用线性表达式，减少非线性约束和非线性变量的个数。如：x/y 5

4、 改为 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) 利用现有软件求解LINGOMATLAB,三、典型优化问题与LINGO软件求解,(一) LINGO软件概述LINGO是用来求解线性和非线性优化问题的简易工具。LINGO内置了一种建立最优化模型的语言，可以简便地表达大规模问题，利用LINGO高效的求解器可快速求解并分析结果。,(二) LINGO软件的操作界面,主菜单工具栏,程序编辑窗口(可同时编辑多个文档),(三) 典型数学规划问题及求解,典型的线性规划问题一般的线性规划问题生产计划问题生产调度问题下料(截割)问题配料(搭配)问题两类特殊的线性规划问题运输

6、问题：平衡与不平衡运输问题、转运问题分派问题：分工问题、选址问题、设备安装问题,(三) 典型数学规划问题及求解,例1 下料(截割)问题及求解例2 运输问题及求解例3 非线性规划问题及求解例4 分派(选址)问题及求解例5 动态规划问题及求解,例1 下料(截割)问题及求解,1. 问题提出2. 建立数学模型3. 编写LINGO求解程序4. 执行程序5. 获得计算结果并分析6. 修正模型，重新求解7.课后作业8.编程小结,主要目的： (1) 再次熟悉该类问题的规划模型; (2) 学习LINGO的简单编程方法,例1 下料(截割问题)及求解,1. 问题提出某建筑工地需要做100套成品钢筋，每套为3根，其规

7、格分别为2.9m、2.1m、1.5m。现原料钢筋均为7.4m长。问应该怎样截割原料钢筋，才能使所需原料钢筋根数为最少？(设截割时截口宽度忽略不计),例1 下料(截割问题)及求解,2. 建模关键: 一根原料钢筋的截割方法,例1 下料(截割问题)及求解,以“使剩余原料最少”为目标的模型(1),例1 下料(截割问题)及求解,以“使所用原料钢筋数最少”为目标的模型(2),例1 下料(截割问题)及求解,3. 用LINGO的简单模型语言编程(模型-1)的求解程序,例1 下料(截割问题)及求解,(模型-2)的求解程序：,例1 下料(截割问题)及求解,LINGO的简单编程语言特点：(1) 以感叹号(!)开头、

8、以分号结束的行是注释；(2) 按模型表达式顺序书写程序语句；(3) 以“min=”或“max=”开始的语句是目标函数，其余为约束条件；(4) 英文字母不区分大小写;(5) 表达式中的运算符不能省略；(6) 一个语句占一行，行末用分号(;)结束。(7) LINGO软件默认所有变量均为非负，故xi0可不输入.,例1 下料(截割问题)及求解,4. 执行LINGO求解程序菜单：LINGOSolve (CTRL+U)工具栏：,例1 下料(截割问题)及求解,5. 获得求解结果并分析(1) 状态结果(2) 数值结果：最优目标值与最优解,例1 下料(截割问题)及求解,模型-1的求解结果：,(1)模型种类 LP

9、: 线性规划 NLP: 非线性规划(2)最优状态 全局全优(3)最优目标值: 10,变量情况(1)变量总数(2)非线性变量数(3)整型变量数,约束条件情况(1)约束总个数(2)非线性个数,最优目标值: 10,最优解：X4=100,按方法4X6=50, 按方法6,例1 下料(截割问题)及求解,模型-2的求解结果：,最优目标函数值：90,x1=40, 按方法1截割x2=20, 按方法2截割x6=30. 按方法6截割,例1 下料(截割问题)及求解,求解结果分析：,模型(2)的求解结果： 最优目标(原料)=90根 (x1,x2,x6)=(40,20,30) 余料 = ?,模型(1)的求解结果： 最优目

10、标(余料)=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

11、,k2,kn)的成品.例如：原料长10m, 成品有5种规格：(2.1,3.7,4.5,0.8,1.5)m。请编程将其所有可能的截割方法和截割结果列举出来。要求：能从文件导入数据，能将程序运行结果输出到文本文件或EXCEL文件中,例1 下料(截割问题)及求解,7.课后作业题2教室的紧急撤离问题某学校发生紧急情况需撤离全体人员。现考虑该校教学楼某一层楼中单侧教室的全体人员的紧急撤离情况，试建立该问题的数学模型并编程求解。,例1 下料(截割问题)及求解,8. LINGO简单编程的总结主要不足：不适于编写大规模的模型程序大规模模型：目标函数表达式较长约束条件数很多变量的取值情形比较复杂,返回,例2 运

12、输问题及求解,1. 问题提出2. 建立数学模型3. 编写LINGO求解程序4. 获得求解结果并分析5. 编程小结,主要目的：(1) 进一步熟悉运输问题的整数规划模型；(2) 学习LINGO的集合语言编程。,例2 运输问题及求解,1. 问题提出某企业有6个生产分厂和8个销售点，已知各厂的生产能力、各销售点的需求量、任意生产厂和销售点之间的单位运费如下表，求使总运输最小的商品运输方案。,例2 运输问题及求解,2. 建立模型记：cij-第i个厂到第j个点的单位运费 ai-第i个厂的产量，bj-第j个点的销量设：xij-第i个厂到第j个点的运输量,例2 运输问题及求解,产量约束共6个约束条件,销量约束

13、共8个约束条件,例2 运输问题及求解,模型说明：(1) 当全部变量xij要求取整数值时，这类模型称为纯整数规划模型(PILP).(2) 在运输问题中，当“产量总和=销量总和”时，称为平衡运输问题，此时模型的约束条件用“=”号。(3) 否则，称为不平衡运输问题，又可分为：A. 产销，此时“产量约束”可用“”号。B. 产 总销量=280,例2 运输问题及求解,3. 利用LINGO集合语言编程(1) 模型有多少变量和常数？变量：xij, 有68=48个 （可看作二维数组）常量：产量：ai，共6个 （可看作一维数组）销量：bj，共8个 （可看作一维数组）单位运费：cij，共48个 （可看作二维数组）,

14、例2 运输问题及求解,(2) LINGO模型语言的框架MODEL:SETS:ENDSETSDATA:ENDDATAEND,集(sets)：是模型中各种对象(常量和变量)聚集在一起，称为集。如: 生产厂、销售点、单位运费、运输量。(类似于数组) 集包括： A.集名: (结构体) B.成员: (结构体成员) C.属性: 成员的特征 (结构体实例) 例如：“生产厂”是一个对象(集)，有6个成员，它们都有一个“产量”属性。 定义“生产厂”集的语句： factory/fa1.fa6/:capcity; 集名 成员名 “产量”属性 (多个属性用逗号分开) 练习：定义“销售点”集及其属性,例2 运输问题及求

15、解,(2) LINGO模型语言的框架MODEL:SETS:ENDSETSDATA:ENDDATAEND,派生集：由现有的集再定义新的集 定义派生集的语句格式： 派生集名(集1,集n)/成员/:属性; 例如：“单位运费(cij)”集、“运输量(xij)”集，可看作是由“生产厂”集和“销售点”集派生出来的。 定义语句： Link(factory,vendors): cost,x,派生集名,现有集名(原始集),属性名,“成员”省略，其个数默认为68=48个,例2 运输问题及求解,(2) LINGO模型语言的框架MODEL:SETS:ENDSETSDATA:ENDDATAEND,目标函数和约束条件语句

16、 其中，以“min=”或“max=”开始的语句为目标函数。,数据部分(DATA)： 提供各类数据，主要给集的各个属性赋值。可直接列出，也可从其他文档中导入。,例2 运输问题及求解,(2) LINGO模型语言的框架MODEL:SETS:ENDSETSDATA:ENDDATAEND,直接列出数据法： capacity=60 55 51 43 41 52; demand=35 37 22 32 41 32 43 38; cost=6 2 6 7 4 2 9 5 4 9 5 3 8 5 8 2 5 2 1 9 7 4 3 3 7 6 7 3 9 2 7 1 2 3 9 5 7 2 6 5 5 5 2

17、2 8 1 4 3;,一组数据按行方式列出，数据以空格分开，行末以分号结束。一个矩阵数据以矩阵形式列出，数据的行和列即为矩阵的行和列，只在最后一行以分号结束。,例2 运输问题及求解,含集和数据的程序段,MODEL: SETS:fact/fa1.fa6/:capacity;vend/ve1.ve8/:demand;links(fact,vend):cost,x; ENDSETS,DATA: capacity=60 55 51 43 41 52; demand=35 37 22 32 41 32 43 38; cost=6 2 6 7 4 2 9 5 4 9 5 3 8 5 8 2 5 2 1 9

18、 7 4 3 3 7 6 7 3 9 2 7 1 2 3 9 5 7 2 6 5 5 5 2 2 8 1 4 3; ENDDATAEND,例2 运输问题及求解,(2) LINGO模型语言的框架MODEL:SETS:ENDSETSDATA:ENDDATAEND,从文档导入数据：借助导入数据函数： A. file(文件名) -从文本文件读取数据 B. OLE(文件名) -从EXCEL文件读取数据,例2 运输问题及求解,A. file(文件名) - 从文本文件导入数据a) 将数据输入到文本文件中b) 编写DATA段,数据之间以空格分开，以“”结束的为一条数据记录；每执行一次file()函数，只读取一

19、条数据记录。,DATA capacity=file(samp02_data.txt); demand=file(samp02_data.txt); cost=file(samp02_data.txt);ENDDATA,例2 运输问题及求解,B. OLE(文件名) - 从EXCEL文件导入数据a) 将数据输入到EXCEL文件中b) 编写DATA段,数据输入到EXCEL工作表后，还要对每个数据区域定义一个名称。 定义方法： (1) 选中每一个数据区域； (2) 选菜单“插入名称定义”，为每一个数据区域定义一个名称，如capacity, demand, cost.,例2 运输问题及求解,(2) LI

20、NGO模型语言的框架MODEL:SETS:ENDSETSDATA:ENDDATAEND,目标函数和约束条件的语句编写方法,例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 运输问题及求解,B. 约束条件的构成与书写,产量约束、销量约束： 每个式子均为累加和，共1

21、4个。方法：使用循环函数 + 求和函数 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 运输问题及求解,C. 变量约束的构成与书写,变量约束：非负且取整数：方法：使用取整函数 GIN(x) - x只能取0或正整数 其他函数： bnd(L,x,U) - LxU free(x) - x可以取任意实数 bin(x) - x只能取0或1 变量约束语句： fo

22、r(links(i,j):gin(x(i,j);或 for(links: gin(x);,例2 运输问题及求解,例2 运输问题及求解,4. “运输问题”的求解结果,最优目标值为664,例2 运输问题及求解,4. “运输问题”的求解结果,最优目标函数值为664,例2 运输问题及求解,例2 运输问题及求解,例2 运输问题及求解,例2 运输问题及求解,集合语言编程小结1. LINGO模型语文的初始化段Init: .endinit2. 简单模型语言编程的语法要求也同样适用于集合语言编程。3. 集合语言的灵活性更强，可求解的模型更多。,用于对决策变量赋初值，使能更快找到最优解.,返回,例3 非线性规划问

23、题及求解,例3 求解下面最优化问题,补充：LINGO的运算符与函数,1. 运算符(1)算术运算符+(加)，-(减)，*(乘)，/(除)，(乘方)，-(负)(2)逻辑运算符A. #not# (逻辑取反)B. #eq#, #ne#; #gt#, #ge#; #lt#, #le# ( , ; , ; , )C. #and#, #or# ( 与 ，或 ),补充：LINGO的运算符与函数,2. 常用函数abs(x)求x的绝对值; sin(x)求x的正弦值; cos(x)求x的余弦值;tan(x)求x的正切值; exp(x)求常数e的x次方; log(x)求x的自然对数sign(x)若x0，取不超过x的整

24、数；若x0，取不低于x的整数值。,补充：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,例3 非线性规划问题及求解,例3的LINGO求解程序,例3 非线性规划问题及求解,例3 非线性规划问题及求解,练习题：1. 给定一个直角三角形，求包含该三角形的最小正方形。试建立该问题的模型并求解。2. 建筑工地的位置(用平面坐标a, b表示，

25、距离单位：公里)及水泥日用量d(吨)如下表。现有两个临时料场位于P(5,1), Q(2, 7)，日储量各有20吨。(1)从P, Q两个临时料场分别向各工地运送多少吨水泥，使总的吨公里数最小。(2)若重新建两个料场，应建在何处，节省的吨公里数有多大？,例3 非线性规划问题及求解,料场P(5,1),料场Q(2,7),新料场A(?,?),新料场B(?,?),返回,例4 0-1型规划问题及求解,例4-1 选址问题某公司准备在一个城市设立3个销售部，共有7个地点可供选择，记为A1,A2,A7。经过对7个地点进行考察，确定了若选用Ai点则需投资设备bi元（投资总额不得超过B元），预计每年可赢利ci元。另外

26、，对地点的选择确定了几条要求：(A1,A2,A3)中最多选2个，(A4,A5)中至少选1个，(A6,A7)中至少选1个。问：应选择哪几个点可使年利润达到最大？,例4 0-1型规划问题及求解,例4-1 选址问题,例4 0-1型规划问题及求解,例4-1 选址问题取以下数据作计算,例4 0-1型规划问题及求解,例4-2 分派问题大众出租车公司配备有无线调度系统，现有五位客人电话要车。公司调度从卫星定位系统了解到本公司分别有五辆合适的可用车，车与客人的距离如下所示：为了使空驰数最小，如何为每一位客人安排车辆？空驰公里总数是多少？,例4 0-1型规划问题及求解,例4-2 分派问题,例4 0-1型规划问题

27、及求解,例4-2 分派问题,空驰总里程数=12公里,例4 0-1型规划问题及求解,练习题1 组队(匹配)问题某班8名同学准备分成4个调查队(每队两人)前往4个地区进行社会调查。这8名同学两两之间组队的效率如下表所示(由于对称性，只列出了严格上三角部分)，问如何组队可以使总效率最高？,例4 0-1型规划问题及求解,练习题22005年B题 DVD在线租赁问题,返回,例5 动态规划问题及求解,例5 (最短路问题)下图表示的是公路网, 节点表示货车可以停靠的城市,弧上的权表示两个城市之间的距离(百公里). 那么,货车从城市S出发到达城市T,如何选择行驶路线,使所经过的路程最短?,例5 动态规划问题及求

28、解,例5 (最短路问题)1. 建立模型记d(Y,X)为城市Y与城市X之间的直接距离(若X与Y不直接相连，令其直接距离为)。设L(X)表示城市S到城市X的最优行驶路线的路长，易知L(S)=0.则有：,“Y”是指上一步中已经计算出最短路L(Y)的那些节点,例5 动态规划问题及求解,2. (1)手工计算方法-动态规划法,最优路线长为20，最优路线为SA3B2C1T,例5 动态规划问题及求解,2. (2)LINGO程序求解,元素以枚举方式给出,在LINGO程序中，可以没有目标函数，即可用于找可行解（求解方程组或不等式组）。,对L赋值不能改为“L=0;”，这等价于将全部元素赋值为0。,index(S):返回元素S在集合中的索引值（为1），也可改写为：i #GT# 1,例5 动态规划问题及求解,2. (2)LINGO程序求解,从S到T的最优行驶路线的路长为20(进一步分析，可以得到最优行驶路线为S A3 B2 C1 T)。,返回,