单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,用,Lingo,软件编程求解规划问题,刘甫,北京师范大学,什么是规划问题？,求目标函数在,约束条件,下的最大值或最小值的问题，统称为规划问题。,决策变量、约束条件、目标函数是线性规划的三要素,.,主要解决最优生产计划、最优分配、最优设计、最优决策、最佳管理等最优化问题。,线性规划,非线性规划,实数规划,整数规划,0-1,规划,例,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,，乙车间的加工能力没有限制。试为该厂制订一个生产计划，使每天获利最大,例,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),例,1,加工奶制品的生产计划,求,的最大值？,改变,z,，即移动直线,z=72x1+64x2,并使之与蓝色区域有交叉，即可找到最大值。,见动画,求,的最大值？,用,Lingo,软件求解,Lingo,结果中其它项的意思！,更多信息,例,1,加工奶制品的生产计划,例,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,),例,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,),例,2,军队供给问题,用,Lingo,软件求解,结果,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,是一个可以简洁地阐述、解决和分析复杂问题的简便工具。,其特点是程序执行速度很快，易于输入、修改、求解和分析一个数学规划问题。,Lingo,软件,集合段（,SETS ENDSETS,）,目标与约束段,数据段（,DATA ENDDATA,）,初始段（,INIT ENDINIT,）,LINGO,模型的构成：,4,个段,Lingo,是一个可以简洁地阐述、解决和分析复杂问题的简便工具。,其特点是程序执行速度很快，易于输入、修改、求解和分析一个数学规划问题。,Lingo,软件,集合,集是相联系的对象的集合，比如工厂、消费者群体、交通工具和雇工等等；,集是,LINGO,建模语言的基础，是程序设计最强有力的基本构件目标与约束段；,借助于集，能够用一个单一的、长的、简明的复合公式表示一系列相似的约束，从而可以快速方便地表达规模较大的模型；,集有成员和属性。,集合,派生集合 基本集合,稀疏集合 稠密集合,元素列表法 元素过滤法 直接列举法 隐式列举法,Lingo,软件,集合,setname,/,member_list,/:,attribute_list,;,setname(parent_set_list,)/,member_list,/:,attribute_list,;,Lingo,软件,基本集合元素的列举,setname,/,member_list,/:,attribute_list,;,sets:,students/John Jill,Rose Mike/:sex,age;,endsets,集成员不放在集定义中，而在随后的数据部分来定义。,sets:,students:sex,age,;,endsets,data:,students,sex,age,=John 1 16,Jill 0 14,Rose 0 17,Mike 1 13;,enddata,一个原始集是由一些最基本的对象组成的。,类型,隐式列举格式,示例,示例集合的元素,数字型,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,软件,基本集合元素的隐式列举,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(&1)#,ge,#demand(,Lingo,软件,数据段与初始段,数据段：,输入集成员和数据，提供了模型相对静止部分和数据分离的可能性。,object_list,=,value_list,;,对象列数值列；,初始段：,为决策变量设置初始值。,在初始部分输入的值仅被,LINGO,求解器当作初始点来用，,并且仅仅对非线性模型有用,。和数据部分指定变量的值不同，,LINGO,求解器可以,自由改变,初始部分初始化的变量的值。,以“,init:”,开始，以“,endinit,”,结束。初始部分的初始声明规则和数据部分的数据声明规则相同。,Lingo,软件,目标与约束段,四个集合循环函数：,FOR,、,SUM,、,MAX,、,MIN,function(,setname,(,set_index_list,)|condition:,expression_list,);,例子：,Lingo,软件,目标与约束段,四个集合循环函数：,FOR,、,SUM,、,MAX,、,MIN,function(,setname,(,set_index_list,)|condition:,expression_list,);,objective,MAX=SUM(PAIRS(I,J):BENEFIT(I,J)*MATCH(I,J);,FOR(STUDENTS(I):,constraints,SUM(PAIRS(J,K)|J#EQ#I#OR#K#EQ#I:MATCH(J,K)=1);,FOR(PAIRS(I,J):BIN(MATCH(I,J);,MAXB=MAX(PAIRS(I,J):BENEFIT(I,J);,MINB=MIN(PAIRS(I,J):BENEFIT(I,J);,例子：,优先级,运算符,最高,#NOT#,（负号）,*,/,+,（减法）,#EQ#NE#GT#GE#LT#LE#,#AND#OR#,最低,(=),三类运算符：,算术运算符 逻辑运算符 关系运算符,Lingo,软件,运算符与优先级,主要用于集循环函数的条件表达式中,形成模型的一个约束条件，指定一个表达式的左边是否等于、小于等于、或者大于等于右边。,针对数值进行操作,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,中的最小值,数学函数,Lingo,软件,函数,变量定界函数,bin(x,),限制,x,为,0,或,1,bnd(L,x,U,),限制,LxU,free(x,),取消对变量,x,的默认下界为,0,的限制，即,x,可以取任意实数,gin(x,),限制,x,为整数,例,3,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