《数学规划及》PPT课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数学规划模型,实际问题中,的优化模型,x,决策变量,f,(,x,),目标函数,g,i,(,x,),0,h,j,(,x,),=0,约束条件,数学规划,线性规划,:,目标函数和约束条件均为线性。,非线性规划：目标函数和约束条件至少一个非线性的。,整数规划：决策变量取值为整数。,多元函数条件极值,决策变量个数,n,和约束条件个数,m,1,+m,2,较大；,最优解在可行域的边界上取得。,数学规划模型,重点在模型的建立、软件求解及结果的分析。,数学软件求解优化模型包括：,Lingo,、,Matlab,等。为了结合结果分析，这里我们主要介绍,Lingo 11,软件。,LINGO,简介,LINGO,软件有多种版本，如,LINDO,，,GINO,和,LINGO(,包括,LINGO NL),软件。,LINGO,是一种专门用于求解数学规划问题的优化计算软件包，版权现在由美国,LINDO,系统公司所拥有。,LINGO,软件包的特点是程序执行速度快，易于方便地输入、修改、求解和分析一个数学规划（优化问题），因此,LINGO,在教学，科研和工业界得到广泛应用。,LINGO,11,有两种命令模式,Windows 模式,通过下拉式菜单命令驱动LINGO 运行,。,命令行(Command-Line)模式,仅在命令窗口下操作,。,LINGO,软件主要具有两大优点,1,、可用于求解非线性规划问题，包括非线性整数规划问题。还可以进行灵敏性分析。,2,、,LINGO,包含了内置的建模语言，允许以简练、直观的方式描述较大规模的优化问题，模型中所需的数据可以以一定格式保存在独立的文件中,说明：,LP,问题的数学模型及,LINGO,程序,s.t.,min=2*x1+3*x2;,x1+x2350;,x1100;,2*x1+x2600;,（,1,）,.,将目标函数的表示方式从“,min”,变成了“,min=”,。,（,2,）,.“ST”,在,LINGO,模型中不再需要，所以被删除了。,（3）每个系数与变量间增加了运算符“*”（即乘号不能省略）,（4）每行（目标、约束和说明语句）后面均增加了一个分号“;”,（,7,）模型结束标志“END”也被删除了（LINGO 中只有当模型以“MODEL：”开始时才能以“END”结束）。,（,5,）,LINGO,中变量不区分大小写；,（,6,）,由于,LINGO,中已假设所以变量都是非负的，所以非负约束不必再输到计算机中；,状态窗口的参数解释,变量数量（其中包括变量总数、,非线性变量数、整数变量数）,非零系数数量（总数、非线,性项的个数）,内存使用量、求解花费的时间,约束数量（约束总数、非线性约束个数）,状态窗口的参数解释,用,LINGO,来解二次规划问题,s.t.,max=98*x1+277*x2-x12-0.3*x1*x2-2*x22;,x1+x2100;,x12*x2;,gin(x1);gin(x2);,1),变量和行名可以超过,8,个字符，但不能超过,32,个字符，且必须以字母开头,;,2)LINGO,已假定各变量非负（除非用函数,free,或,sub,或,slb,另行说明）,;,3),变量可以放在约束条件的右端（同时数字也可放在约束条件的左端）。但为了提高效率，应尽可能采用线性表达式定义目标和约束（如果可能,).,说明：,求解结果：,s.t.,LINGO,的编程,对于复杂的优化模型的求解时要涉及到,LINGO,编程，即，,定义集合、使用循环语句和文件输入输出操作等。如,LINGO,程序为,：,model:,!6,发点,8,收点运输问题,;,sets:!,集合段,;,warehouses/wh1.wh6/:capacity;,vendors/v1.v8/: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)=capacity(I);,!,下面是数据,;!,数据段,;,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 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;,!text(r.txt)=volume;,!cost=file(c.txt);,Enddata,!,初始段,Init:endinit;,end,集部分是,LINGO,模型的一个可选部分。在,LINGO,模型中使用集之前，必须在集部分事先定义。集部分以关键字“,sets:”,开始，以“,endsets”,结束。,模型的集部分,为了定义一个原始集，必须详细声明：,集的名字,可选，集的成员,可选，集成员的属性,定义一个原始集，用下面的语法：,setname/member_list/:attribute_list;,原始集,集可以分为两类，即：原始集和派生集,为了定义一个派生集，必须详细声明：,集的名字,父集的名字,可选，集成员,可选，集成员的属性,可用下面的语法定义一个派生集：,setname(parent_set_list)/member_list/:attribute_list;,例如：,sets:,product/A B/;,machine/M N/;,week/1.2/;,allowed(product,machine,week):x;,endsets,派生集,优先级,运算符,最高,#NOT#，（负号）,*,，,/,+,，（减号）,#EQ#，#NE#，#GE#，#GT#，#LE#，#LT#,#AND#，#OR#,最低,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,函数的自然对数。,mod(x,y),：返回,x,除以,y,的余数。,sign(x),：如果,x=0,时，返回不超过,x,的最大整数；当,x0,时，返回不低于,x,的最大整数。,smax(x1,x2,xn),：返回,x1,，,x2,，,，,xn,中的最大值。,smin(x1,x2,xn),：返回,x1,，,x2,，,，,xn,中的最小值。,LINGO,提供了大量的标准数学函数：,变量界定函数实现对变量取值范围的附加限制，共,4,种：,bin(x),：限制,x,为,0,或,1,；,bnd(L,x,U),：限制,LxU,；,free(x),：取消对变量,x,的默认下界为,0,的限制，即,x,可以取任意实数；,gin(x),：限制,x,为整数。,在默认情况下，,LINGO,规定变量是非负的，也就是说下界为,0,，上界为,+,。,free,取消了默认的下界为,0,的限制，使变量也可以取负值。,bnd,用于设定一个变量的上下界,它也可以取消默认下界为,0,的约束。,变量界定函数,集循环函数,集循环函数遍历整个集进行操作。其语法为,function(setname(set_index_list)|conditional_qualifier:expression_list);,1,for,该函数用来产生对集成员的约束。基于建模语言的标量需要显式输入每个约束，不过,for,函数允许只输入一个约束，然后,LINGO,自动产生每个集成员的约,model:,sets:,number/1.5/:x;,endsets,for(number(I):x(I)=I2);,end,例：产生序列,1,4,9,16,25,2,sum,该函数返回遍历指定的集成员的一个表达式的和。,例：求向量,5,，,1,，,3,，,4,，,6,，,10,前,5,个数的和。,model:,data:,N=6;,enddata,sets:,number/1.N/:x;,endsets,data:,x=5 1 3 4 6 10;,enddata,s=sum(number(I)|I#le#5:x);,end,3,min,和,max,例：求向量,5,，,1,，,3,，,4,，,6,，,10,前,5,个数的最小值，后,3,个数的最大值。,model:,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);,maxv=max(number(I)|I#ge#N-2:x);,end,输入和输出函数可以把模型和外部数据比如文本文件、数据库和电子表格等连接起来。,输入和输出函数,1,file,函数,该函数用从外部文件中输入数据，可以放在模型中任何地方。该函数的语法格式为,file(,filename,),。这里,filename,是文件名，可以采用相对路径和绝对路径两种表示方式。,2,text,函数,该函数被用在数据部分用来把解输出至文本文件中。它可以输出集成员和集属性值。其语法为,text(,filename,),。,用该命令产生当前模型的灵敏性分析报告：研究当目标函数的费用系数和约束右端项在什么范围（此时假定其它系数不变）时，最优基保持不变。灵敏性分析是在求解模型时作出的，因此在求解模型时灵敏性分析是激活状态，但是默认是不激活的。为了激活灵敏性分析，运行,LINGO|Options,，选择,General Solver Tab,，在,Dual Computations,列表框中，选择,Prices and Ranges,选项。灵敏性分析耗费相当多的求解时间，因此当速度很关键时，就没有必要激活它。,灵敏性分析（,Range,，,Ctrl+R,）,加工奶制品的生产计划,1,桶牛奶,3,公斤,A,1,12,小时,8,小时,4,公斤,A,2,或,获利,24,元,/,公斤,获利,16,元,/,公斤,50,桶牛奶,时间,480,小时,至多加工,100,公斤,A,1,制订生产计划，使每天获利最大,35,元可买到,1,桶牛奶，买吗？若买，每天最多买多少,?,可聘用临时工人，付出的工资最多是每小时几元,?,A,1,的获利增加到,30,元,/,公斤，应否改变生产计划？,每天：,1,桶牛奶,3,公斤,A,1,12,小时,8,小时,4,公斤,A,2,或,获利,24,元,/,公斤,获利,16,元,/,公斤,x,1,桶牛奶生产,A,1,x,2,桶牛奶生产,A,2,获利,243,x,1,获利,164,x,2,原料供应,劳动时间,加工能力,决策变量,目标函数,每天获利,约束条件,非负约束,线性规划模型,(LP),时间,480,小时,至多加工,100,公斤,A,1,50,桶牛奶,每天,模型求解,软件实现,LINGO 11,max=72,*,x1+64,*,x2,；,x1+x250,；,12,*,x1+8,*,x2480,；,3,*,x1100,；,Global optimal solution found.,Objective value:,3360.000,Infeasibilities:0.000000,Total solver iterations:2,Variable Value Reduced Cost,X1 2