Lingo软件编程求解规划问题--数学建模PPT.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,用,Lingo,软件编程求解规划问题,1,什么是规划问题？,求目标函数在,约束条件,下的最大值或最小值的问题，统称为规划问题。,决策变量、约束条件、目标函数是线性规划的三要素,.,主要解决最优生产计划、最优分配、最优设计、最优决策、最佳管理等最优化问题。,线性规划,非线性规划,实数规划,整数规划,0-1,规划,2,例,1,加工奶制品的生产计划,获利,24,元,/,公斤,获利,16,元,/,公斤,1,桶牛奶,3,公斤,A,1,12,小时,8,小时,4,公斤,A,2,或,50,桶牛奶,时间,480,小时,至多加工,100,公斤,A,1,每天：,一奶制品加工厂用牛奶生产,A1,A2,两种奶制品，,1,桶牛奶可以在甲车间用,12,小时加工成,3,公斤,A1,，或者在乙车间用,8,小时加工成,4,公斤,A2,。根据市场需求，生产的,A1,A2,全部能售出，且每公斤,A1,获利,24,元，每公斤,A2,获利,16,元。现在加工厂每天能得到,50,桶牛奶的供应，每天正式工人总的劳动时间,480,小时，并且甲车间每天至多能加工,100,公斤,A1,，乙车间的加工能力没有限制。试为该厂制订一个生产计划，使每天获利最大,.,并进一步讨论以下,3,个附加问题：,1,）若用,35,元可以买到,1,桶牛奶，应否作这项投资？若投资，每天最多购买多少桶牛奶？,2,）若可以聘用临时工人以增加劳动时间，付给临时工人的工资最多是每小时几元？,3,）由于市场需求变化，每公斤,A1,的获利增加到,30,元，应否改变生产计划？,3,例,1,加工奶制品的生产计划,获利,24,元,/,公斤,获利,16,元,/,公斤,1,桶牛奶,3,公斤,A,1,12,小时,8,小时,4,公斤,A,2,或,50,桶牛奶,时间,480,小时,至多加工,100,公斤,A,1,每天：,x,1,桶牛奶生产,A,1,x,2,桶牛奶生产,A,2,获利,243,x,1,获利,164,x,2,原料供应,劳动时间,加工能力,决策变量,目标函数,每天获利,约束条件,非负约束,线性规划模型,(LP),4,例,1,加工奶制品的生产计划,求 的最大值？,5,求 的最大值？,用,Lingo,软件求解,Lingo,结果中其它项的意思！,更多信息,例,1,加工奶制品的生产计划,6,max=sin(x)*2*exp(-x);,x0;,7,Lingo,软件,LINGO Help:,LINGO is a simple tool for utilizing the power of linear and nonlinear optimization to formulate large problems concisely,solve them,and analyze the solution.,Optimization helps you find the answer that yields the best result;attains the highest profit,output,or happiness;or the one that achieves the lowest cost,waste,or discomfort.,Often these problems involve making the most efficient use of your resources,including money,time,machinery,staff,inventory,and more.,Lingo,是一个可以简洁地阐述、解决和分析复杂问题的简便工具。,其特点是程序执行速度很快，易于输入、修改、求解和分析一个数学规划问题。,8,lingo,软件擅长于解决运筹问题，即最有问题，常见的是线性规划。,而,matlab,则功能比较多，主要是以矩阵为基础的运算，也能解决运筹问题。,matlab,的功能更强大一些，也比较难学，东西多,lingo,主要用于优化问题，,matlab,功能强大，几乎什么都能做，但是碰到循环时速度较慢，而且对机器要求较高，,lingo,主要用以解线性规划，方程之类，使用比,matlab,简单，解决线性问题速度也不错，有些东西不能做。不过现在国外有将,2,者结合的。,matlab,都能解，就是麻烦点,LINGO,是使建立和求解线性、非线性和整数最佳化模型更快更简单更有效率的综合工具。,LINGO,提供强大的语言和快速的求解引擎来阐述和求解最佳化模型。,9,原则上还是,lingo,要快，特别是变量较多的时候，但是这里面不能比较非线性规划，因为非线性规划的求解速度不仅取决于问题的规模，还要看非线性程度以及初始,.,简单的模型表示,LINGO,可以将线性、非线性和整数问题迅速得予以公式表示，并且容易阅读、了解和修改。,方便的数据输入和输出选择,LINGO,建立的模型可以直接从数据库或工作表获取资料。同样地，,LINGO,可以将求解结果直接输出到数据库或工作表。,强大的求解引擎,LINGO,内建的求解引擎有线性、非线性,(convex and nonconvex),、二次、二次限制和整数最佳化。,Model Interactively or Create Turn-key Applications,LINGO,提供完全互动的环境供您建立、求解和分析模型。,LINGO,也提供,DLL,和,OLE,界面可供使用者由撰写的程序中呼叫。,10,11,12,13,0 Global Optimum,（全局最优）,1 Infeasible,（不可行）,2 Unbounded,（无界）,3 Undetermined,（不确定）,4 Feasible,（可行）,5 Infeasible or Unbounded,（通常需要关闭“预处理”选项后重新求解模型，以确定模型究竟是不可行还是无界）,6 Local Optimum,（局部最优）,7 Locally Infeasible,（局部不可行，尽管可行解可能存在，但是,LINGO,并没有找到一个）,8 Cutoff,（目标函数的截断值被达到）,9 Numeric Error,（求解器因在某约束中遇到无定义的算术运算而停止）,14,15,LP:,线性规划,linear programming,QP,二次规划,NLPNONLINEAR PROGRAMMING,ILP,线性整数,IQP,二次整数,PILP,线性纯整数,PIQP,二次纯整数,NLP,非线性,NLPNONLINEAR PROGRAMMING,INLP,整数非线性,PINLP,纯整数非线性,16,例,2,军队供给问题,corps,需求量,35,37,22,32,41,32,43,38,拥有量,B1,B2,B3,B4,B5,B6,B7,B8,depot,60,A1,6,2,6,7,4,2,5,9,55,A2,4,9,5,3,8,5,8,2,51,A3,5,2,1,9,7,4,3,3,43,A4,7,6,7,3,9,2,7,1,41,A5,2,3,9,5,7,2,6,5,52,A6,5,5,2,2,8,1,4,3,军队有某种先进武器,302,台分别放在,6,个补给站,(depot),中，现由于战争需要，,8,个军团,(corps),分别需要此种武器数目如表中所示，并且给出了从各补给站送一台武器到任一军团的费用，问如何运输可使成本最小？,capacity(i),V(i),demand(j),d(j),cost(i,j),c(i,j),number(i,j),n(i,j),17,例,2,军队供给问题,corps,需求量,35,37,22,32,41,32,43,38,拥有量,B1,B2,B3,B4,B5,B6,B7,B8,depot,60,A1,6,2,6,7,4,2,5,9,55,A2,4,9,5,3,8,5,8,2,51,A3,5,2,1,9,7,4,3,3,43,A4,7,6,7,3,9,2,7,1,41,A5,2,3,9,5,7,2,6,5,52,A6,5,5,2,2,8,1,4,3,capacity(i),V(i),demand(j),d(j),cost(i,j),c(i,j),number(i,j),n(i,j),18,例,2,军队供给问题,用,Lingo,软件求解,结果,19,Lingo,软件,集合段（,SETS ENDSETS,）,目标与约束段,数据段（,DATA ENDDATA,）,初始段（,INIT ENDINIT,）,LINGO,模型的构成：,4,个段,Lingo,是一个可以简洁地阐述、解决和分析复杂问题的简便工具。,其特点是程序执行速度很快，易于输入、修改、求解和分析一个数学规划问题。,20,21,Lingo,软件,集合,概念,集是相联系的对象的集合，比如工厂、消费者群体、交通工具和雇工等等；,集是,LINGO,建模语言的基础，是程序设计最强有力的基本构件目标与约束段；,借助于集，能够用一个单一的、长的、简明的复合公式表示一系列相似的约束，从而可以快速方便地表达规模较大的模型；,集有成员和属性。,22,集部分,是,LINGO,模型的一个可选部分。在,LINGO,模型中使用集之前，必须在集部分事先定义。集部分以关键字“,sets:”,开始，以“,endsets”,结束。,一个模型可以没有集部分，或有一个简单的集部分，或有多个集部分。一个集部分可以放置于模型的任何地方，但是一个集及其属性在模型约束中被引用之前必须定义了它们。,23,Lingo,软件,基本集合元素的列举,setname/member_list/:attribute_list;,sets:,students/John Jill,Rose Mike/:sex,age;,endsets,一个原始集是由一些最基本的对象组成的。,集、集成员和集属性,24,集成员无论用何种字符标记,它的索引都是从,1,开始连续计数。,在,attribute_ list,可以指定一个或多个集成员的属性，属性之间必须用逗号隔开。,25,定义一个原始集,，用下面的语法：,setname/member_list/:attribute_list;,注意：用“,”,表示该部分内容可选。下同，不再赘述。,Setname,是你选择的来标记集的名字，最好具有较强的可读性。集名字必须严格符合标准命名规则：以拉丁字母或下划线（,_,）为首字符，其后由拉丁字母（,AZ,）、下划线、阿拉伯数字（,0,，,1,，,，,9,）组成的总长度不超过,32,个字符的字符串，且不区分大小写。,注意：该命名规则同样适用于集成员名和属性名等的命名。,Member_list,是集成员列表。采取显式罗列和隐式罗列两种方式。,26,类型,隐式列举格式,示例,示例集合的元素,数字型,1.n,1.5,1,2,3,4,5,字符,-,数字型,stringM.stringN,Car101.car208,Car101,car102,car208,星期型,dayM.dayN,MON.FRI,MON,TUE,WED,THU,FRI,月份型,monthM.monthN,OCT.JAN,OCT,NOV,DEC,JAN,年份,-,月份型,monthYearM.monthYearN,OCT2001.JAN2002,OCT2001,NOV2001,DEC2001,JAN2002,Lingo,软件,基本集合元素的隐式列举,27,集成员不放在集定义中，而在随后的数据部分来定义。,sets:,students:sex,age;,endsets,data:,students,sex,age=John 1 16,Jill 0 14,Rose 0 17,Mike 1 13;,enddata,28,注意：开头用感叹号（,!,），末尾用分号（,;,）表示注释，可跨多行。,29,Lingo,软件,派生集,setname(parent_set_list)/member_list/:attribute_list;,一个派生集是用一个或多个其它集来定义的。也就是说，它的成员来自于其它已存在的集。,稠密集：,派生集成员由父集成员所有组合构成；,稀疏集：,其成员为父集成员所有组合构成的集合的一个子集。,显式：,links(depot,corps)/d1 c2,d2 c3,d3 c6,d4 c3,d5 c1,d6 c8/:cost,number;,过滤：,links(depot,corps)|capacity(,派生集的成员列表有两种方式生成：显式罗列；设置成员资格过滤器。,30,sets:,product/A B/;,machine/M N/;,week/1.2/;,allowed(product,machine,week):x;,endsets,LINGO,生成了三个父集的所有组合共八组作为,allowed,集的成员。列表如下：,编号 成员,1 (A,M,1),2(A,M,2),3(A,N,1),4(A,N,2),5(B,M,1),6(B,M,2),7(B,N,1),8(B,N,2),31,例,sets:,!,学生集：性别属性,sex,，,1,表示男性，,0,表示女性；年龄属性,age.;,students/John,Jill,Rose,Mike/:sex,age;,!,男学生和女学生的联系集：友好程度属性,friend,，,0,，,1,之间的数。,;,linkmf(students,students)|sex(,!,男学生和女学生的友好程度大于,0.5,的集,;,linkmf2(linkmf)|friend(,endsets,data:,sex,age=1 16,0 14,0 17,0 13;,friend=0.3 0.5 0.6;,enddata,用竖线（,|,）来标记一个成员资格过滤器的开始。,#eq#,是逻辑运算符，用来判断是否“相等”，可参考,4.&1,可看作派生集的第,1,个原始父集的索引，它取遍该原始父集的所有成员；,&2,可看作派生集的第,2,个原始父集的索引，它取遍该原始父集的所有成员；,&3,，,&4,，,，以此类推。,32,集合,派生集合 基本集合,稀疏集合 稠密集合,元素列表法 元素过滤法 直接列举法 隐式列举法,Lingo,软件,集合,setname/member_list/:attribute_list;,setname(parent_set_list)/member_list/:attribute_list;,33,Lingo,软件,数据段与初始段,数据段：,输入集成员和数据，提供了模型相对静止部分和数据分离的可能性。,object_list=value_list;,对象列数值列；,初始段：,为决策变量设置初始值。,在初始部分输入的值仅被,LINGO,求解器当作初始点来用，,并且仅仅对非线性模型有用,。和数据部分指定变量的值不同，,LINGO,求解器可以,自由改变,初始部分初始化的变量的值。,以“,init:”,开始，以“,endinit”,结束。初始部分的初始声明规则和数据部分的数据声明规则相同。,34,sets:,set1/A,B,C/:X,Y;,endsets,data:,X,Y=1 4,2 5,3 6;,enddata,data:,X=1,2,3;,Y=4,5,6;,enddata,35,和数据部分指定变量的值不同，,LINGO,求解器可以自由改变初始部分初始化的变量的值。,例,init:,X,Y=0,.1;,endinit,Y=log(X);,X2+Y2=1;,36,优先级,运算符,最高,#NOT#,（负号）,*/,+,（减法）,#EQ#NE#GT#GE#LT#LE#,#AND#OR#,最低,(=),三类运算符：,算术运算符 逻辑运算符 关系运算符,Lingo,软件,运算符与优先级,主要用于集循环函数的条件表达式中,形成模型的一个约束条件，指定一个表达式的左边是否等于、小于等于、或者大于等于右边。,针对数值进行操作,37,#not#,否定该操作数的逻辑值，,not,是一个一元运算符,#eq#,若两个运算数相等，则为,true,；否则为,flase,#ne#,若两个运算符不相等，则为,true,；否则为,flase,#gt#,若左边的运算符严格大于右边的运算符，则为,true,；否则为,flase,#ge#,若左边的运算符大于或等于右边的运算符，则为,true,；否则为,flase,#lt#,若左边的运算符严格小于右边的运算符，则为,true,；否则为,flase,#le#,若左边的运算符小于或等于右边的运算符，则为,true,；否则为,flase,#and#,仅当两个参数都为,true,时，结果为,true,；否则为,flase,#or#,仅当两个参数都为,false,时，结果为,false,；否则为,true,38,Lingo,软件,函数,abs(x),返回,x,的绝对值,sin(x),返回,x,的正弦值，,x,采用弧度制,cos(x),返回,x,的余弦值,tan(x),返回,x,的正切值,exp(x),返回常数,e,的,x,次方,log(x),返回,x,的自然对数,lgm(x),返回,x,的,gamma,函数的自然对数,sign(x),如果,x=0,时，返回不超过,x,的最大整数；当,x0,时，返回不低于,x,的最大整数。,smax(x1,x2,xn),返回,x1,，,x2,，,，,xn,中的最大值,smin(x1,x2,xn),返回,x1,，,x2,，,，,xn,中的最小值,数学函数,39,Lingo,软件,函数,变量定界函数,bin(x),限制,x,为,0,或,1,bnd(L,x,U),限制,LxU,free(x),取消对变量,x,的默认下界为,0,的限制，即,x,可以取任意实数,gin(x),限制,x,为整数,min,和,max,返回指定的集成员的一个表达式的最小值或最大值。,40,41,qrand(seed),产生服从,(0,1),区间的拟随机数。,qrand,只允许在模型的数据部分使用，它将用拟随机数填满集属性。通常，声明一个,mn,的二维表，,m,表示运行实验的次数，,n,表示每次实验所需的随机数的个数。在行内，随机数是独立分布的；在行间，随机数是非常均匀的。这些随机数是用“分层取样”的方法产生的。,例,4.5,model:,data:,M=4;N=2;seed=1234567;,enddata,sets:,rows/1.M/;,cols/1.N/;,table(rows,cols):x;,endsets,data:,X=qrand(seed);,enddata,end,如果没有为函数指定种子，那么,LINGO,将用系统时间构造种子。,42,43,data:,N=6;,enddata,sets:,number/1.N/:x;,endsets,data:,x=5 1 3 4 6 10;,enddata,minv=min(number(I)|I#le#5:x);,end,44,45,输入和输出函数,1,file,函数,该函数用从外部文件中输入数据，可以放在模型中任何地方。该函数的语法格式为,file(filename),。这里,filename,是文件名，可以采用相对路径和绝对路径两种表示方式。,46,例,以例,1.2,来讲解,file,函数的用法。,注意到在例,1.2,的编码中有两处涉及到数据。第一个地方是集部分的,6,个,warehouses,集成员和,8,个,vendors,集成员；第二个地方是数据部分的,capacity,，,demand,和,cost,数据。,为了使数据和我们的模型完全分开，我们把它们移到外部的文本文件中。修改模型代码以便于用,file,函数把数据从文本文件中拖到模型中来。修改后（修改处代码黑体加粗）的模型代码如下：,model:,!6,发点,8,收点运输问题,;,sets:,warehouses/,file(1_2.txt),/:capacity;,vendors/,file(1_2.txt),/:demand;,links(warehouses,vendors):cost,volume;,endsets,!,目标函数,;,min=sum(links:cost*volume);,!,需求约束,;,for(vendors(J):,sum(warehouses(I):volume(I,J)=demand(J);,!,产量约束,;,for(warehouses(I):,sum(vendors(J):volume(I,J)=required(J);,end,50,例,Lingo,与,Excel,的连接,corps,需求量,35,37,22,32,41,32,43,38,拥有量,B1,B2,B3,B4,B5,B6,B7,B8,depot,60,A1,6,2,6,7,4,2,5,9,55,A2,4,9,5,3,8,5,8,2,51,A3,5,2,1,9,7,4,3,3,43,A4,7,6,7,3,9,2,7,1,41,A5,2,3,9,5,7,2,6,5,52,A6,5,5,2,2,8,1,4,3,capacity(i),V(i),demand(j),d(j),cost(i,j),c(i,j),number(i,j),n(i,j),51,3,、,ole,函数,是从,EXCEL,中引入或输出数据的接口函数，它是基于传输的,OLE,技术。,OLE,传输直接在内存中传输数据，并不借助于中间文件。,例,3,Lingo,与,Excel,的连接,OLE,可以同时读集成员和集属性（读写）,OLE,只能读一维或二维的,Ranges,绝对路径,ole(data.xls);,相对路径,ole(D:data.xls);,例题,52,求 的最大值？,用,Lingo,软件求解,Lingo,结果中其它项的意思！,更多信息,例,1,加工奶制品的生产计划,53,54,55,56,Global optimal solution found at iteration:3,Objective value:280.0000,Variable Value,Reduced Cost,DESKS 2.000000 0.000000,TABLES 0.000000 5.000000,CHAIRS 8.000000 0.000000,Row Slack or Surplus Dual Price,1 280.0000 1.000000,2 24.00000 0.000000,3 0.000000 10.00000,4 0.000000 10.00000,5 5.000000 0.000000,“,Reduced Cost,”,列出最优单纯形表中判别数所在行的变量的系数，表示当变量有微小变动时,目标函数的变化率。,其中基变量的,reduced cost,值应为,0,，对于非基变量,Xj,相应的,reduced cost,值表示当某个变量,Xj,增加一个单位时目标函数减少的量,(max,型问题,),。本例中：变量,tables,对应的,reduced cost,值为,5,，表示当非基变量,tables,的值从,0,变为,1,时（此时假定其他非基变量保持不变,但为了满足约束条件，基变量显然会发生变化），最优的目标函数值,=280-5=275,。,“Value”,给出最优解中各变量的值：造,2,个书桌（,desks,）,0,个餐桌（,tables,）,8,个椅子（,chairs,）。所以,desks,、,chairs,是基变量（非,0,），,tables,是非基变量（,0,）。,57,58,灵敏度的分析,59,60,灵敏度分析的结果是,Ranges in which the basis is unchanged:,Objective Coefficient Ranges,Current Allowable Allowable,Variable Coefficient Increase Decrease,DESKS 60.00000 20.00000 4.000000,TABLES 30.00000 5.000000 INFINITY,CHAIRS 20.00000 2.500000 5.000000,Righthand Side Ranges,Row Current Allowable Allowable,RHS Increase Decrease,2 48.00000 INFINITY 24.00000,3 20.00000 4.000000 4.000000,4 8.000000 2.000000 1.333333,5 5.000000 INFINITY 5.000000,（,56,80,）,（,35,）,48-24,，,48+=24,，,61,文件菜单（,File Menu,）,1,新建（,New,）,从文件菜单中选用“新建”命令、单击“新建”按钮或直接按,F2,键可以创建一个新的“,Model”,窗口。,在这个新的“,Model”,窗口中能够输入所要求解的模型。,2,打开（,Open,）,从文件菜单中选用“打开”命令、单击“打开”按钮或直接按,F3,键可以打开一个已经存在的文本文件。,这个文件可能是一个,Model,文件。,3,保存,(Save),从文件菜单中选用“保存”命令、单击“保存”按钮或直接按,F4,键用来保存当前活动窗口（最前台的窗口）,中的模型结果、命令序列等保存为文件。,4,另存为,(Save As,),从文件菜单中选用“另存为”命令或按,F5,键可以将当前活动窗口中的内容保存为文本文件，其文件名为你在,“另存为”对话框中输入的文件名。利用这种方法你可以将任何窗口的内容如模型、求解结果或命令保存为文件。,5,关闭（,Close,）,在文件菜单中选用“关闭”,(Close),命令或按,F6,键将关闭当前活动窗口。如果这个窗口是新建窗口或已经改变了当前,文件的内容，,LINGO,系统将会提示是否想要保存改变后的内容。,6,打印,(Print),在文件菜单中选用“打印”,(Print),命令、单击“打印”按钮或直接按,F7,键可以将当前活动窗口中的内容发送到打印机。,7,打印设置,(Print Setup,),在文件菜单中选用“打印设置”命令或直接按,F8,键可以将文件输出到指定的打印机。,8,打印预览,(Print Preview),在文件菜单中选用“打印预览”命令或直接按,Shift+F8,键可以进行打印预览。,12,退出（,Exit,）,从文件菜单中选用“,Exit”,命令或直接按,F10,键可以退出,LINGO,系统。,62,63,64,65,