购买

¥30.0

加入VIP
  • 专属下载券
  • 上传内容扩展
  • 资料优先审核
  • 免费资料无限下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 优化模型与Lingo软件

优化模型与Lingo软件.ppt

优化模型与Lingo软件

中小学精品课件
2019-04-27 0人阅读 举报 0 0 0 暂无简介

简介:本文档为《优化模型与Lingo软件ppt》,可适用于高等教育领域

优化模型与Lingo软件穆国旺河北工业大学理学院内容提要一、优化模型简介二、LINDO公司的主要软件产品及功能简介三、LINDO软件的使用四、LINGO软件的使用五、建模与求解实例(结合软件使用)一、优化模型简介许多生产计划与管理问题都可以归纳为最优化问题,最优化模型是数学建模中应用最广泛的模型之一其内容包括线性规划、整数线性规划、非线性规划、动态规划、变分法、最优控制等。近几年来的全国大学生数学建模竞赛中几乎每次都有一道题要用到此方法。优化(数学规划)模型的一般形式:x~决策变量f(x)~目标函数gi(x)~约束条件分类:线性规划(LP)二次规划(QP)非线性规划(NLP)纯整数规划(PIP)混合整数规划(MIP)整数规划(IP)整数规划一般整数规划连续规划建立优化模型的关键步骤:确定决策变量确定决策的目标将目标函数用决策变量表示出来确定约束条件将约束条件用包含决策变量的等式或不等式表示出来。建模时需要注意的几个基本问题尽量使用实数优化减少整数约束和整数变量尽量使用光滑优化减少非光滑约束的个数如:尽量少使用绝对值、符号函数、多个变量求最大最小值、四舍五入、取整函数等尽量使用线性模型减少非线性约束和非线性变量的个数(如xy<改为x<y)合理设定变量上下界尽可能给出变量初始值模型中使用的参数数量级要适当(如小于)模型的求解:我们遇到的实际问题一般规模都较大即使建立了模型找到了解的方法对于庞大的计算量也是望而却步。“工欲善其事必先利其器”手中有一个方便的求解最优化问题的工具就显得很重要。LINGO系列优化软件包就给我们提供了理想的选择。二、LINDO公司软件产品简要介绍LINGO系列软件是專門用於求解數學規劃問題的套裝軟體。由於執行速度很快、易於方便輸入、求解和分析數學規劃問題,因此在數學、科研和工業界得到廣泛應用。美国芝加哥(Chicago)大学的LinusSchrage教授于年前后开发,后来成立LINDO系统公司(LINDOSystemsInc)网址:http:wwwlindocomLINDO:LinearINteractiveandDiscreteOptimizer(V)LINGO:LinearINteractiveGeneralOptimizer(V)LINDOAPI:LINDOApplicationProgrammingInterface(V)What’sBest!:(SpreadSheetegEXCEL)(V)LINGO软件包有多种版本但其软件内核和使用方法类似。教学版和发行版的主要区别在于对优化问题的规模(变量和约束的个数)有不同的限制。详细情况可上网访问LINGO软件网站:wwwlindocomLINDO和LINGO软件能求解的优化模型LINGOLINDO优化模型线性规划(LP)非线性规划(NLP)二次规划(QP)连续优化整数规划(IP)LINGO主要用於解線性規劃、非線性規劃、二次規劃和整數規劃等題。也可以用於一些非線性和線性方程組的求解以及代數方程求根等。LINGO中包含了一種建模語言和許多常用的數學函數可供使用者建立規劃問題使用。需要掌握的几个重要方面、LINDO:正确阅读求解报告(尤其要掌握敏感性分析)、LINGO:掌握集合(SETS)的应用正确阅读求解报告正确理解求解状态窗口学会设置基本的求解选项(OPTIONS)掌握与外部文件的基本接口方法三、LINDO软件的使用LINDO(LinearINteractiveandDiscreteOptimizer)可以用来求解线性规划(LP)、整数规划(IP)和二次规划(QP)问题。两个简单的例子:例求解如下的LP问题:Maxz=xystxy≤xy≤x,y≥用Lindo来描述:MAXxyST)xy<=)xy<=END例奶制品的生产计划桶牛奶时间小时至多加工公斤A制订生产计划使每天获利最大元可买到桶牛奶买吗?若买每天最多买多少可聘用临时工人付出的工资最多是每小时几元A的获利增加到元公斤应否改变生产计划?每天:x桶牛奶生产Ax桶牛奶生产A获利×x获利×x原料供应劳动时间加工能力决策变量目标函数每天获利约束条件非负约束线性规划模型(LP)时间小时至多加工公斤A模型求解Maxxxstxx<xx<x<endOBJECTIVEFUNCTIONVALUE)VARIABLEVALUEREDUCEDCOSTXXROWSLACKORSURPLUSDUALPRICES)))NOITERATIONS=DORANGE(SENSITIVITY)ANALYSISNo桶牛奶生产A,桶生产A利润元。模型求解reducedcost值表示当该非基变量增加一个单位时(其他非基变量保持不变)目标函数减少的量(对max型问题)OBJECTIVEFUNCTIONVALUE)VARIABLEVALUEREDUCEDCOSTXXROWSLACKORSURPLUSDUALPRICES)))NOITERATIONS=也可理解为:为了使该非基变量变成基变量目标函数中对应系数应增加的量OBJECTIVEFUNCTIONVALUE)VARIABLEVALUEREDUCEDCOSTXXROWSLACKORSURPLUSDUALPRICES)))原料无剩余时间无剩余加工能力剩余Maxxxstxx<xx<x<end三种资源“资源”剩余为零的约束为紧约束(有效约束)结果解释OBJECTIVEFUNCTIONVALUE)VARIABLEVALUEREDUCEDCOSTXXROWSLACKORSURPLUSDUALPRICES)))结果解释最优解下“资源”增加单位时“效益”的增量原料增单位,利润增时间加单位,利润增能力增减不影响利润影子价格元可买到桶牛奶要买吗?<,应该买!聘用临时工人付出的工资最多每小时几元?元!RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEXXRIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASEINFINITY最优解不变时目标系数允许变化范围DORANGE(SENSITIVITY)ANALYSISYesx系数范围(,)x系数范围(,)A获利增加到元千克应否改变生产计划x系数由=增加为=在允许范围内不变!(约束条件不变)结果解释结果解释RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEXXRIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASEINFINITY影子价格有意义时约束右端的允许变化范围原料最多增加时间最多增加元可买到桶牛奶每天最多买多少?最多买桶?(目标函数不变)注意:充分但可能不必要LINDO模型的格式:按线性规划的自然形式输入,格式如下:MAX(或MIN)目标函数ST(或ST或SUCHTHAT或SUBJECTTO)约束约束约束约束nEND使用Lindo的一些注意事项:“>”(或“<”)号与“>=”(或“<=”)功能相同变量与系数间可有空格(甚至回车),但无运算符变量名以字母开头不能超过个字符变量名不区分大小写(包括LINDO中的关键字)目标函数所在行是第一行第二行起为约束条件行号(行名)自动产生或人为定义。行名以“)”结束行中注有“!”符号的后面部分为注释。如:!It’sComment在模型的任何地方都可以用“TITLE”对模型命名(最多个字符)如:TITLEThisModelisonlyanExample变量不能出现在一个约束条件的右端表达式中不接受括号“()”和逗号“,”等任何符号,例:(XX)需写为XX表达式应化简如XXX应写成XX缺省假定所有变量非负可在模型的“END”语句后用“FREEname”将变量name的非负假定取消可在“END”后用“SUB”或“SLB”设定变量上下界例如:“subx”的作用等价于“x<=”但用“SUB”和“SLB”表示的上下界约束不计入模型的约束也不能给出其松紧判断和敏感性分析。“END”后对变量说明:INTn或INTname“END”后对整数变量说明:GINn或GINname四、LINGO软件的使用LINGO是用来求解线性和非线性优化问题的简易工具。LINGO内置了一种建立最优化模型的语言可以简便地表达大规模问题利用LINGO高效的求解器可快速求解并分析结果。包含了LINDO的全部功能提供了灵活的编程语言(矩阵生成器)几个简单的例子例用Lingo求解线性规划(奶制品的生产计划)Lindo模型:Maxxxstxx<xx<x<end对应的Lingo模型:Model:Max=*x*xxx<*x*x<*x<end例用Lingo求解二次规划MODEL:MAX=*X^Y^X*Y*X*Y*XY=X>Y>END例用Lingo非线性规划Model:min=*D*X*D*X*D*DD=((X)^(Y)^)^D=((X)^(Y)^)^D=(X^(Y)^)^D=((X)^Y^)^gin(X)!gin(X)表示X为整数gin(Y)!gin(Y)表示X为整数bin(X)!bin(X)表示X为变量bin(X)!bin(X)表示X为变量end问题如何下料最节省例钢管下料问题问题客户增加需求:节省的标准是什么?由于采用不同切割模式太多会增加生产和管理成本规定切割模式不能超过种。问如何下料最节省?按照客户需要在一根原料钢管上安排切割的一种组合。切割模式合理切割模式的余料应小于客户需要钢管的最小尺寸钢管下料为满足客户需要按照哪些种合理模式每种模式切割多少根原料钢管最为节省?合理切割模式所用原料钢管总根数最少钢管下料问题两种标准原料钢管剩余总余量最小xi~按第i种模式切割的原料钢管根数(i=,,…)约束满足需求决策变量目标(总余量)按模式切割根,按模式切割根余料米最优解:x=,x=,其余为最优值:整数约束:xi为整数当余料没有用处时通常以总根数最少为目标目标(总根数)钢管下料问题约束条件不变最优解:x=,x=,x=,其余为最优值:。按模式切割根按模式切割根按模式切割根共根余料米虽余料增加米但减少了根与目标的结果“共切割根余料米”相比钢管下料问题对大规模问题用模型的约束条件界定合理模式增加一种需求:米根切割模式不超过种。现有种需求:米根米根米根米根用枚举法确定合理切割模式过于复杂。决策变量xi~按第i种模式切割的原料钢管根数(i=,,)ri,ri,ri,ri~第i种切割模式下每根原料钢管生产米、米、米和米长的钢管的数量满足需求模式合理:每根余料不超过米整数非线性规划模型钢管下料问题目标函数(总根数)约束条件整数约束:xi,ri,ri,ri,ri(i=,,)为整数增加约束缩小可行域便于求解原料钢管总根数下界:特殊生产计划:对每根原料钢管模式:切割成根米钢管需根模式:切割成根米和根米钢管需根模式:切割成根米钢管需根。原料钢管总根数上界:模式排列顺序可任定钢管下料问题需求:米根米根米根米根每根原料钢管长米LINGO求解整数非线性规划模型Localoptimalsolutionfoundatiteration:Objectivevalue:VariableValueReducedCostXXXRRRRRRRRRRRR模式:每根原料钢管切割成根米和根米钢管共根模式:每根原料钢管切割成根米、根米和根米钢管共根模式:每根原料钢管切割成根米钢管共根。原料钢管总根数为根。演示cutalgcutblg例:SAILCO公司需要决定下四个季度的帆船生产量。下四个季度的帆船需求量分别是条条条条。每个季度正常的生产能力是条帆船每条船的生产费用为美元。如果加班生产每条船的生产费用为美元。每个季度末每条船的库存费用为美元。假定生产提前期为初始库存为条船。如何安排生产可使总费用最小?用DEM,RP,OP,INV分别表示需求、正常生产的产量、加班生产的产量、库存量则DEM,RP,OP,INV对每个季度都应该有一个对应的值也就说他们都应该是一个由个元素组成的数组其中DEM是已知的而RP,OP,INV是未知数。用Lingo求解模型:MODEL:SETS:QUARTERS:Demand,RP,OP,InvENDSETSDATA:Demand=,,,ENDDATA!目标:总费用最小MIN=SUM(QUARTERS(I):*RP(I)*OP(I)*Inv(I))!正常生产能力的限制FOR(QUARTERS(I):RP(I)<=)!产品数量的平衡关系FOR(QUARTERS(I)|I#GT#:Inv(I)=Inv(I)RP(I)OP(I)Demand(I))Inv()=RP()OP()Demand()END计算结果:模型的组成:Model:集合段(SETS:定义集合ENDSETS)数据段(DATA:给已知的数据赋值ENDDATA)初始段(INIT:给变量赋初值ENDINIT)目标与约束段end集合段(SetsSection)SETS:集合的定义集合的定义集合n的定义ENDSETS集合的类型集合派生集合基本集合稀疏集合稠密集合元素列表法元素过滤法直接列举法隐式列举法setnamememberlist:attributelistsetname(parentsetlist)memberlist:attributelistSETS:CITIESA,A,A,B,BROADS(CITIES,CITIES)A,BA,BA,BA,B:DENDSETSSETS:STUDENTSSSPAIRS(STUDENTS,STUDENTS)|#GT#:BENEFIT,MATCHENDSETS基本集合的定义格式:setnamememberlist:attributelistSetname是你选择的来标记集的名字最好具有较强的可读性。集名字必须严格符合标准命名规则:以英文字母或下划线()为首字符其后由英文字母(AZ)、下划线、阿拉伯数字(…)组成的总长度不超过个字符的字符串且不区分大小写。Memberlist是集成员列表。如果集成员放在集定义中那么对它们可采取显式罗列和隐式罗列两种方式。如果集成员不放在集定义中那么可以在随后的数据部分定义它们。①当显式罗列成员时必须为每个成员输入一个不同的名字中间用空格或逗号搁开(允许混合使用)。例可以定义一个名为students的原始集它具有成员John、Jill、Rose和Mike属性有sex和age:sets:studentsJohnJill,RoseMike:sex,ageendsets②当隐式罗列成员时不必罗列出每个集成员。可采用如下语法:setnamemembermemberN:attributelist这里的member是集的第一个成员名memberN是集的最末一个成员名。LINGO将自动产生中间的所有成员名。LINGO也接受一些特定的首成员名和末成员名用于创建一些特殊的集。集合元素的隐式列举类型隐式列举格式示例示例集合的元素数字型n,,,,字符数字型stringMstringNCarcarCar,car,…,car星期型dayMdayNMONFRIMON,TUE,WED,THU,FRI月份型monthMmonthNOCTJANOCT,NOV,DEC,JAN年份月份型monthYearMmonthYearNOCTJANOCT,NOV,DEC,JAN③集成员不放在集定义中而在随后的数据部分来定义。例!集部分sets:students:sex,ageendsets!数据部分data:students,sex,age=JohnJillRoseMikeenddata注意:开头用感叹号(!)末尾用分号()表示注释可跨多行。在集部分只定义了一个集students并未指定成员。在数据部分罗列了集成员John、Jill、Rose和Mike并对属性sex和age分别给出了值。集成员无论用何种字符标记,它的索引都是从开始连续计数。在attributelist可以指定一个或多个集成员的属性属性之间必须用逗号隔开。派生集合的定义为了定义一个派生集必须详细声明:·集的名字·父集的名字·集成员(可选)·集成员的属性(可选)可用下面的语法定义一个派生集:setname(parentsetlist)memberlist:attributelistsetname是集的名字。parentsetlist是已定义的集的列表多个时必须用逗号隔开。如果没有指定成员列表那么LINGO会自动创建父集成员的所有组合作为派生集的成员。例sets:productABmachineMNweekallowed(product,machine,week):xendsetsLINGO生成了三个父集的所有组合共八组作为allowed集的成员。列表如下:编号成员(A,M,)(A,M,)(A,N,)(A,N,)(B,M,)(B,M,)(B,N,)(B,N,)成员列表被忽略时派生集成员由父集成员所有的组合构成这样的派生集成为稠密集。如果限制派生集的成员使它成为父集成员所有组合构成的集合的一个子集这样的派生集成为稀疏集。一个派生集的成员列表有两种方式生成:①显式罗列②设置成员资格过滤器。当采用方式①时必须显式罗列出所有要包含在派生集中的成员并且罗列的每个成员必须属于稠密集。例:allowed(product,machine,week)AM,AN,BN如果需要生成一个大的、稀疏的集那么显式罗列就很讨厌。幸运地是许多稀疏集的成员都满足一些条件以和非成员相区分。我们可以把这些逻辑条件看作过滤器在LINGO生成派生集的成员时把使逻辑条件为假的成员从稠密集中过滤掉。例sets:!学生集:性别属性sex表示男性表示女性studentsJohn,Jill,Rose,Mike:sex,age!男学生和女学生的联系集:友好程度属性friend之间linkmf(students,students)|sex()#eq##and#sex()#eq#:friend!男学生和女学生的友好程度大于的集linkmf(linkmf)|friend(,)#ge#:xendsetsdata:sex,age=friend=enddata用竖线(|)来标记一个成员资格过滤器的开始。#eq#是逻辑运算符用来判断是否“相等”可看作派生集的第个原始父集的索引它取遍该原始父集的所有成员可看作派生集的第个原始父集的索引它取遍该原始父集的所有成员……以此类推。注意如果派生集B的父集是另外的派生集A那么上面所说的原始父集是集A向前回溯到最终的原始集其顺序保持不变并且派生集A的过滤器对派生集B仍然有效。因此派生集的索引个数是最终原始父集的个数索引的取值是从原始父集到当前派生集所作限制的总和。数据段(datasection)ThedatasectionallowsyoutoisolatedatafromtherestofyourmodelThedatasectionbeginswiththekeywordDATA:(includingthecolon)andendswiththekeywordENDDATA格式:DATA:objectlist=valuelistENDDATA对象列(objectlist)包含要指定值的属性名、要设置集成员的集名用逗号或空格隔开。一个对象列中至多有一个集名而属性名可以有任意多。如果对象列中有多个属性名那么它们的类型必须一致。如果对象列中有一个集名那么对象列中所有的属性的类型就是这个集。数值列(valuelist)包含要分配给对象列中的对象的值用逗号或空格隔开。注意属性值的个数必须等于集成员的个数。例sets:setA,B,C:X,Yendsetsdata:X=,,Y=,,enddata例sets:setA,B,C:X,Yendsetsdata:X,Y=enddata参数在数据部分也可以指定一些标量变量(scalarvariables)。当一个标量变量在数据部分确定时称之为参数。例如假设模型中用利率作为一个参数就可以象下面一样输入一个利率作为参数。例data:interestrate=enddata也可以同时指定多个参数。例data:interestrate,inflationrate=enddata参数也可以在求解时交互输入:例data:interestrate,inflationrate=enddata指定属性为一个值可以在数据声明的右边输入一个值来把所有的成员的该属性指定为一个值。例sets:daysMO,TU,WE,TH,FR,SA,SU:needsendsetsdata:needs=enddataLINGO将用指定days集的所有成员的needs属性。对于多个属性的情形见下例。例sets:daysMO,TU,WE,TH,FR,SA,SU:needs,costendsetsdata:needscost=enddata数据部分的未知数值有时只想为一个集的部分成员的某个属性指定值而让其余成员的该属性保持未知以便让LINGO去求出它们的最优值。例sets:years:capacityendsetsdata:capacity=,,,,enddata属性capacity的第个和第个值分别为和其余的未知。初始段(INITsection)ThevaluesyouinputintheinitsectionareusedasstartingpointsbyLINGO'ssolver格式:INIT赋值语句ENDINIT例init:X,Y=,endinitY=log(X)X^Y^<=好的初始点会减少模型的求解时间。[]目标函数和约束条件()目标函数:MAXMIN=expression()约束条件(基本语句):expression=或>或<或>=或<=expression算术运算符算术运算符是针对数值进行操作的。LINGO提供了种二元运算符:^乘方﹡乘/除﹢加﹣减LINGO唯一的一元算术运算符是取反函数“﹣”。运算的次序可以用圆括号“()”来改变。函数()常用的数学函数ABS(X)SIGN(X)EXP(X)LOG(X)SIN(X)COS(X)TAN(X)SMIN(list)SMAX(list)()集合(循环)函数:格式:function(setname(setindexlist)|condition:expressionlist)其中condition代表逻辑表达式可包含以下一些运算符:#GT#(大于),#GE#(大于等于)#LT#(大于),#LE#(大于等于)#EQ#(等于),#NE#(不等于)逻辑运算符#NOT##AND##OR#FORFOR(setname(setindexlist)|condition:expressionlist)例:SETS:TRUCKSMAC,PETERBILT,FORD,DODGE:HAULENDSETSFOR(TRUCKS(T):HAUL(T)<=)可生成如下四条约束:HAUL(MAC)<=HAUL(PETERBILT)<=HAUL(FORD)<=HAUL(DODGE)<=SETS:NUMBERS:VALUE,RECIPROCALENDSETSDATA:VALUE=ENDDATAFOR(NUMBERS(I):RECIPROCAL(I)=VALUE(I))FOR(NUMBERS(I)|VALUE(I)#NE#:RECIPROCAL(I)=VALUE(I))SUM(setname(setindexlist)|condition:expressionlist)SETS:VENDORSVVVVV:DEMANDENDSETSDATA:DEMAND=ENDDATATOTALDEMAND=SUM(VENDORS(J):DEMAND(J))或TOTALDEMAND=SUM(VENDORS:DEMAND)DEMAND=SUM(VENDORS(J)|J#LE#:DEMAND(J))MIN(setname(setindexlist)|condition:expressionlist)MAX(setname(setindexlist)|condition:expressionlist)()变量定界函数BND(L,x,U)限定x>=Lx<=UBIN(x)限制x为或FREE(x)取消x的非负限制GIN(x)限制x为整数()财务函数()概率函数()集操作函数()文件输入输出函数例:选址问题某公司有个建筑工地位置坐标为(ai,bi)(单位:公里),水泥日用量di(单位:吨)假设:料场和工地之间有直线道路i123456abd)现有料场位于A(,),B(,),记(xj,yj),j=,,日储量ej各有吨。目标:制定每天的供应计划即从A,B两料场分别向各工地运送多少吨水泥使总的吨公里数最小。用例中数据计算最优解为总吨公里数为线性规划模型决策变量:cij(料场j到工地i的运量)~维(料场A)(料场B)选址问题:NLP)改建两个新料场需要确定新料场位置(xj,yj)和运量cij在其它条件不变下使总吨公里数最小。决策变量:cij(xj,yj)~维非线性规划模型LINGO模型的构成:个段集合段(SETSENDSETS)数据段(DATAENDDATA)初始段(INITENDINIT)目标与约束段局部最优:(吨公里)LP:移到数据段边界

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

评分:

/85

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利