资源预览内容
第1页 / 共60页
第2页 / 共60页
第3页 / 共60页
第4页 / 共60页
第5页 / 共60页
第6页 / 共60页
第7页 / 共60页
第8页 / 共60页
第9页 / 共60页
第10页 / 共60页
亲,该文档总共60页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
优化模型与Lingo软件的使用,蔡永军 林晓佳,简要提纲,优化模型简介 建模与求解实例 LINGO软件的使用简介,一 优化模型的意义,在工程技术、经济管理、科学研究和日常生活等诸多领域中,人们经常遇到的一类决策问题:在一系列客观或主观限制条件下,寻求所关注的某个或多个指标达到最大(或最小)的决策。例如,生产计划要按照产品工艺流程和顾客需求,制定原料、零件、部件等订购、投产的日期和数量,尽量降低成本使利润最高;运输方案要在满足物资需求和装载条件下安排从各供应点到需求点的运量和路线,使运输总费用最低。,它们的特点是:在若干可能的方案中寻求某种意义下的最优方案。数学上称为最优化问题,而研究处理这种问题的方法叫最优化的方法。,(1)决策变量,它通常是该问题求解的那些未知量。 (2)目标函数,通常是该问题要最优化(最大或最小)的那个目标的数学表达式,它是决策变量的函数。 (3)约束条件,由该问题对决策变量的限制条件给出。,优化模型是一类既重要又特殊的数学模型,而优化建模方法也是一种特殊的数学建模方法。,优化模型的数学描述,二 优化模型的分类,1.根据是否存在约束条件 有约束问题和无约束问题。 2.根据设计变量的性质 静态问题和动态问题。 3.根据目标函数和约束条件表达式的性质 线性规划,非线性规划,二次规划,多目标规划等。,模型的基本类型,问题求解难度增加,优化,连续优化,整数优化,非线性优化,线性优化,二次优化,(1)线性规划(LP),目标函数和所有约束条件都是设计变量的线性函数。,1.1 线性规的求解的几种情况,线性规划问题,有可行解,无可行解,有最优解,无最优解,能找出一组满足约束条件的向量。,不存在可行解或最优趋向无限大。,可行域中使目标函数值达到最优的可行解。,1.2 线性规划模型的实例,例1 家具生产的安排 家具公司生产桌子和椅子,用于生产劳力工450个工时,木材工有4立方米,每张桌子使用15个小时,0.2立方的木材售价80元。每张椅子要使用10个工时,0.05立方木材售价45元。问为达到最大收益,应如何安排生产?,分析: 1.求什么? 生产多少张桌子? X1 生产多少张椅子? x2 2.优化什么? 收益最大 Max f=80*x1+45*x2 3.限制条件? 原料总量 0.2*x1+0.05*x2=4 劳力总量 15*x1+10*x2=450,模型:以产值为目标取得最大收益。,决策变量,目标函数,约束条件,生产桌子 x1张,生产椅子 x2张。,收益最大f=80*x1+45*x2,原料总量0.2*x1+0.05*x2=4 劳力总量15*x1+10*x2=450,最优解: 生产桌子 14张,生产椅子 24张,最大收益为2200。.,(2)非线性规划(NLP),目标函数和所有约束条件至少有一个是未知量的非线性函数。,例如:钢管下料问题,问题1. 如何下料最节省 ?,节省的标准是什么?,问题2. 客户增加需求:,由于采用不同切割模式太多,会增加生产和管理成本,规定切割模式不能超过3种。如何下料最节省?,钢管下料问题1,合理切割模式,为满足客户需要,按照哪些种合理模式,每种模式切割多少根原料钢管,最为节省?,两种标准,1. 原料钢管剩余总余量最小,2. 所用原料钢管总根数最少,决策变量,xi 按第i 种模式切割的原料钢管根数(i=1,2,7),目标函数1,约束条件,整数约束: xi 为整数,最优解:x2=12, x5=15, 其余为0; 最优值:27,按模式2切割12根,按模式5切割15根,余料27米,目标2(总根数),决策变量和约束条件不变目标函数按第二种标准,最优解:x2=15, x5=5, x7=5, 其余为0; 最优值:25。,按模式2切割15根,按模式5切割5根,按模式7切割5根,共25根,余料35米,与目标1的结果“共切割27根,余料27米” 相比虽余料增加8米,但减少了2根当余料没有用处时,通常以总根数最少为目标,(3)二次规划(QP),目标函数为二次函数,所有约束条件为线性函数。,例如:2000全国大学生数学建模竞赛B题。钢管订购和运输计划的优化 。,Lingo软件使用简介,LINGO快速入门 LINGO中的集 模型的数据部分和初始部分 LINGO函数 LINGO WINDOWS命令 综合举例,LINGO快速入门,简单了解LINGO运行窗口,LINGO模式,Model: Sets: !定义集合 Endsets Data:!定义数据 Enddata 调用函数与计算 end,Sets: Items/1.8/:include,weight,rating; Endsets Data: Weight= 1 3 4 3 3 1 5 10; Rating= 2 9 3 8 10 6 4 10; Capacity=15; Enddata Max = sum(items:rating*include); sum(items:weight*include)=capacity; for(items:bin(include);,LINGO中的集,为什么使用集,集是LINGO建模语言的基础,是程序设计最强有力的基本构件。借助于集,能够用一个单一的、长的、简明的复合公式表示一系列相似的约束,从而可以快速方便地表达规模较大的模型。,什么是集,集是一群相联系的对象,这些对象也称为集的成员。一个集可能是一系列产品、卡车或雇员。每个集成员可能有一个或多个与之有关联的特征,我们把这些特征称为属性。属性值可以预先给定,也可以是未知的,有待于LINGO求解。例如,产品集中的每个产品可以有一个价格属性;卡车集中的每辆卡车可以有一个牵引力属性;雇员集中的每位雇员可以有一个薪水属性,也可以有一个生日属性等等。 LINGO有两种类型的集:原始集(primitiveset)和派生集(derived set)。 一个原始集是由一些最基本的对象组成的。 一个派生集是用一个或多个其它集来定义的,也就是说,它的成员来自于其它已存在的集。,模型的集部分,集部分是LINGO模型的一个可选部分。在LINGO模型中使用集之前,必须在集部分事先定义。集部分以关键字“sets:”开始,以“endsets”结束。一个模型可以没有集部分,或有一个简单的集部分,或有多个集部分。一个集部分可以放置于模型的任何地方,但是一个集及其属性在模型约束中被引用之前必须定义了它们。,1.定义原始集,为了定义一个原始集,必须详细声明: 集的名字 可选,集的成员 可选,集成员的属性 定义一个原始集,用下面的语法: setname/member_list/:attribute_list; 注意:用“”表示该部分内容可选。 Setname是你选择的来标记集的名字,最好具有较强的可读性。 集名字必须严格符合标准命名规则:以拉丁字母或下划线(_)为首字符, 其后由拉丁字母(AZ)、下划线、阿拉伯数字(0,1,9)组成的总 长度不超过32个字符的字符串,且不区分大小写。 注意:该命名规则同样适用于集成员名和属性名等的命名。,Member_list是集成员列表。如果集成员放在集定义中,那么对它们可采取显式罗列和隐式罗列两种方式。如果集成员不放在集定义中,那么可以在随后的数据部分定义它们。 当显式罗列成员时,必须为每个成员输入一个不同的名字,中间用空格或逗号搁开,允许混合使用。,例:可以定义一个名为students的原始集,它具有成员John、Jill、Rose和Mike,属性有sex和age: sets: students/John Jill, Rose Mike/: sex, age; endsets, 当隐式罗列成员时,不必罗列出每个集成员。可采用如下语法: setname/member1.memberN/: attribute_list; 这里的member1是集的第一个成员名,memberN是集的最末一个成员名。LINGO将自动产生中间的所有成员名。LINGO也接受一些特定的首成员名和末成员名,用于创建一些特殊的集 。, 集成员不放在集定义中,而在随后的数据部分来定义。,2.定义派生集,为了定义一个派生集,必须详细声明: 集的名字 父集的名字 可选,集成员 可选,集成员的属性,可用下面的语法定义一个派生集: setname(parent_set_list)/member_list/:attribute_list; setname是集的名字。parent_set_list是已定义的集的列表,多个时必须用逗号隔开。如果没有指定成员列表,那么LINGO会自动创建父集成员的所有组合作为派生集的成员。派生集的父集既可以是原始集,也可以是其它的派生集。,例: sets: product/A B/; machine/M N/; week/1.2/; allowed(product,machine,week):x; endsets,成员列表被忽略时,派生集成员由父集成员所有的组合构成,这样的派生集成为稠密集。如果限制派生集的成员,使它成为父集成员所有组合构成的集合的一个子集,这样的派生集成为稀疏集。同原始集一样,派生集成员的声明也可以放在数据部分。一个派生集的成员列表有两种方式生成:显式罗列;设置成员资格过滤器。当采用方式时,必须显式罗列出所有要包含在派生集中的成员,并且罗列的每个成员必须属于稠密集。使用前面的例子,显式罗列派生集的成员: allowed(product,machine,week)/A M 1,A N 2,B N 1/; 如果需要生成一个大的、稀疏的集,那么显式罗列就很讨厌。幸运地是许多稀疏集的成员都满足一些条件以和非成员相区分。我们可以把这些逻辑条件看作过滤器,在LINGO生成派生集的成员时把使逻辑条件为假的成员从稠密集中过滤掉。,总的来说,LINGO可识别的集只有两种类型:原始集和派生集。 在一个模型中,原始集是基本的对象,不能再被拆分成更小的组分。原始集可以由显式罗列和隐式罗列两种方式来定义。当用显式罗列方式时,需在集成员列表中逐个输入每个成员。当用隐式罗列方式时,只需在集成员列表中输入首成员和末成员,而中间的成员由LINGO产生。 另一方面,派生集是由其它的集来创建。这些集被称为该派生集的父集(原始集或其它的派生集)。一个派生集既可以是稀疏的,也可以是稠密的。稠密集包含了父集成员的所有组合(有时也称为父集的笛卡尔乘积)。稀疏集仅包含了父集的笛卡尔乘积的一个子集,可通过显式罗列和成员资格过滤器这两种方式来定义。显式罗列方法就是逐个罗列稀疏集的成员。成员资格过滤器方法通过使用稀疏集成员必须满足的逻辑条件从稠密集成员中过滤出稀疏集的成员。,不同集类型的关系见下图。,模型的数据部分和初始部分,在处理模型的数据时,需要为集指派一些成员并且在LINGO求解模型之前为集的某些属性指定值。为此,LINGO为用户提供了两个可选部分:输入集成员和数据的数据部分(Data Section)和为决策变量设置初始值的初始部分(Init Section)。,模型的数据部分,1.数据部分入门,数据部分以关键字“data:”开始,以关键字“enddata”结束。在这里,可以指定集成员、集的属性。其语法如下: object_list = value_list;,对象列(object_list)包含要指定值的属性名、要设置集成员的集名,用逗号或空格隔开。一个对象列中至多有一个集名,而属性名可以有任意多。如果对象列中有多个属性名,那么它们的类型必须一致。如果对象列中有一个集名,那么对象列中所有的属性的类型就是这个集。 数值列(value_list)包含要分配给对象列中的对象的值,用逗号或空格隔开。注意属性值的个数必须等于集成员的个数。,例: sets: set1/A,B,C/: X,Y; endsets data: X=1,2,3; Y=4,5,6; enddata,在集set1中定义了两个属性X和Y。X的三个值是1、2和3,Y的三个值
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号