lingo软件的使用具体例子

数模中的,LINGO,软件使用,优化问题三要素：,决策变量,；,目标函数,；,约束条件,约束条件,决策变量,优化问题的一般形式,当最优解在可行域边界上取得时,不能用无约束优化方法求解,目标函数,约束优化的分类,线性规划,(LP),目标和约束均为线性函数,非线性规划,(NLP),目标或约束中存在非线性函数,二次规划,(QP),目标为二次函数、约束为线性,整数规划,(IP),决策变量,(,部分,),为整数,整数,线性,规划,(ILP),整数,非线性,规划,(INLP),0-1,规划,整数决策变量只取或,连续优化,离散优化,基本内容,2.,基本原理与解法,3. LINDO / LINGO,软件的使用,1.,实例及其数学模型,分枝定界法,动态规划法,实例,1,：选课问题,略,问题,1.,如何下料最节省,?,实例,2,：钢管下料,问题,2.,客户增加需求：,原料钢管,:,每根,19,米,4,米,50,根,6,米,20,根,8,米,15,根,客户需求,节省的标准是什么？,由于采用不同切割模式太多，会增加生产和管理成本，规定切割模式不能超过,3,种。如何下料最节省？,5,米,10,根,按照客户需要在一根原料钢管上安排切割的一种组合。,切割模式,余料,1,米,4,米,1,根,6,米,1,根,8,米,1,根,余料,3,米,4,米,1,根,6,米,1,根,6,米,1,根,合理切割模式,的余料应小于客户需要钢管的最小尺寸,余料,3,米,8,米,1,根,8,米,1,根,钢管下料,为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节省？,合理切割模式,2.,所用原料钢管总根数最少,模式,4,米钢管根数,6,米钢管根数,8,米钢管根数,余料,(,米,),1,4,0,0,3,2,3,1,0,1,3,2,0,1,3,4,1,2,0,3,5,1,1,1,1,6,0,3,0,1,7,0,0,2,3,钢管下料问题,1,两种标准,1.,原料钢管剩余总余量最小,x,i,按第,i,种模式切割的原料钢管根数,(,i,=,1,2,7,),约束,满足需求,决策变量,目标,1,（总余量）,模式,4,米根数,6,米根数,8,米根数,余料,1,4,0,0,3,2,3,1,0,1,3,2,0,1,3,4,1,2,0,3,5,1,1,1,1,6,0,3,0,1,7,0,0,2,3,需求,50,20,15,整数约束：,x,i,为整数,以上两个模型均是一般,整数线性规划,目标,2,（总根数）,钢管下料问题,1,约束条件不变,x,i,为整数,当余料没有用处时，,通常以总根数最少为目标,钢管下料问题,2,对大规模问题，用模型的约束条件界定合理模式,增加一种需求：,5,米,10,根；切割,模式不超过,3,种。,现有,4,种,需求：,4,米,50,根，,5,米,10,根，,6,米,20,根，,8,米,15,根，用枚举法确定合理切割模式，过于复杂。,决策变量,x,i,按第,i,种模式切割的原料钢管根数,(,i,=,1,2,3,),r,1,i,r,2,i,r,3,i,r,4,i,第,i,种切割模式下，每根原料钢管生产,4,米、,5,米、,6,米和,8,米长的钢管的数量,满足需求,模式合理：每根余料不超过,3,米,整数非线性规划,钢管下料问题,2,目标函数,（,总根数）,约束条件,整数约束：,x,i,r,1,i,r,2,i,r,3,i,r,4,i,(,i,=,1,2,3,),为整数,实例,3,： 饮料的生产批量问题,安排生产计划,满足每周的需求,使,4,周总费用最小。,生产成本,（可变成本）,:,50,元,/,箱,(50,千元,/,千箱,),存 贮 费,:,每周每千箱饮料,1,千元,饮料厂使用同一条生产线轮流生产,多种,饮料。,若某周开工生产,某种,饮料,需支出,生产准备费,3,千元。,某种饮料,4,周的需求量,周次,需求量,(,千箱,),1,2,2,3,3,2,4,4,合计,11,生产批量问题的一般提法,c,t,时段,t,生产费用,(,元,/,件,),；,h,t,时段,t,(,末,),库存费,(,元,/,件,),；,s,t,时段,t,生产准备费,(,元,),；,d,t,时段,t,市场需求,(,件,),；,假设初始库存为,0,制订生产计划,满足需求,并使,T,个时段的总费用最小。,决策变量,x,t,时段,t,生产量；,I,t,时段,t,(,末,),库存量；,y,t,=1 ,时段,t,开工,生产,(,y,t,=0 ,不开工,),。,目标,约束,混合线性,0-1,规划,生产批量问题的一般提法,M,是一个充分大的正数（这里可取,M,= 11,）,混合非线性,0-1,规划？,整数规划问题一般形式,整数线性规划,(ILP),目标和约束均为线性函数,整数非线性规划,(INLP),目标或约束中存在非线性函数,纯,(,全,),整数规划,(PIP),决策变量均为整数,混合整数规划,(MIP),决策变量有整数，也有实数,0-1,规划,决策变量只取,0,或,1,分 类,取消整数规划中决策变量为整数的限制（,松弛,），对应的连续优化问题称为原问题的,松弛问题,整数规划问题对应的松弛问题,松弛问题,松 弛,整数规划问题,最优解,最优解,整数,非整数,整数,舍入,下界（对,Min,问题）,上界（对,Max,问题）,非最优解,原问题,松弛,对松弛问题的最优解（分量）舍入为整数，得到的往往不是原整数规划问题的最优解（甚至不是可行解）,IP,可行解对应于整点,A(2,2),和,B(1,1),而最优解为,A,点,.,但,LP,松弛的最优解为,C(3.5,2.5),目标函数下降方向,x,1,x,2,C,A,B,O,整数规划问题对应的松弛问题,x,1,x,2,0,P,o,6,9,Z,max,5,6,去掉整数限制后，可行域为点（,0,0), (6,0), (0,5),P (2.25,3.75),围成的,4,边形,从,LP,最优解经过简单的 “移动”不一定得到,IP,最优解,基本思想：,隐式地枚举一切可行解（,“,分而治之,”）,所谓分枝，就是逐次对解空间（可行域）进行划分；而所谓定界，是指对于每个分枝（或称子域），要计算原问题的最优解的下界（对极小化问题）,.,这些下界用来在求解过程中判定是否需要对目前的分枝进一步划分，也就是尽可能去掉一些明显的非最优点，避免完全枚举,.,整数规划的分枝定界法,（,BB: Branch and Bound,）,对于,极小化,问题，在子域上解,LP,，其最优值是,IP,限定在该子域时的下界；,IP,任意可行点的函数值是,IP,的上界,线性规划松弛定界,若在某一时刻，得到一个全整数解的费用为,z,m,，则,z,m,为原问题的一个上界,;,否则得该分枝的一个下界，继续分枝,（,P1,）,（,P2,）,线性,IP,分枝定界,算法,例,（,P0,）,该问题的,LP,松弛解为,不是整数解,最优值为,z,0,=-4.,(P1): (P0),加上,;,(P2): (P0),加上,.,问题,(P1),的,LP,松弛解为,不是整数解,最优值为,z,1,=-3.5,(P3): (P1),加上,;,(P4): (P1),加上,.,P0,P1,P2,P3,P4,P5,P6,无可行解,P0,P1,P2,P3,P4, z,0,=-4, z,1,=-7/2,z,0,=-13/4,z,0,=-3,无可行解,z,2,=,-2.5,z,6,整数规划的动态规划法,例：最短路问题,求各点到,T,的最短路,5,6,7,7,4,9,6,8,6,5,8,3,3,6,C,1,B,1,C,2,B,2,A,1,A,2,A,3,T,S,6,节点,i,到节点,T,的最短路长,递推计算,“,全过程的最优策略具有这样的性质：不管该最优策略上某状态以前的状态和决策如何，对该状态而言，余下的诸决策必定构成最优子策略,.,”,即：最优策略的任一,后部子策略,都是最优的,.,这只是最优性定理的一个推论，即最优策略的必要条件,.,最优化原理,最优子结构,（,Optimal Substructure,）,:,An optimal solution to the problem contains within it optimal solutions to subproblems.,（,1,）,正确划分阶段，选择阶段变量,k,.,（,2,）,对每个阶段，正确选择状态变量,x,k,.,选择状态变量时应当注意两点：一是要能够正确描述受控过程的演变特性，二是要满足,无后效性,.,（,3,）,对每个阶段，正确选择决策变量,u,k,.,（,4,）,列出相邻阶段的状态转移方程：,x,k+,1,=,T,k,(,x,k,u,k,).,（,5,） 列出按阶段,可分的准则函数,V,1,n,.,假设问题的目标是极小化,建立动态规划模型的基本过程,逆序递推,k=,1,k=n,k,k=,2,f,k,(,x,k,),表示第,k,阶段初始状态为,x,k,时，,k,后部子过程,(,阶段,k,k,+1,n,),的最优准则函数,动态规划基本方程,资源分配问题,：,某公司现有,M,台设备准备分配给该公司所属的,N,家工厂,.,当分配台,u,k,设备给工厂,k,时，工厂,k,利用这些设备为公司创造的利润（假设非负）为,g,k,(,u,k,).,如何分配设备资源，使得公司总利润最大？,可能是非线性整数规划,甚至,g,k,(,u,k,),没有显式表达式,应用动态规划方法的几个例子,工厂,k,设备数,1,2,3,0,1,2,3,4,0,4,6,7,7,0,2,5,6,8,0,3,5,7,8,状态变量,x,k,-,第,k,阶段初分配者手中拥有的设备台数,.,由题意可知,x,0,=,M,，,x,N+1,= 0,阶段的,准则函数,为,共有,N,个工厂，可以把问题分解为,N,个,阶段,：,当阶段,k,=,N,时，把手中设备分配给工厂,N,；,当阶段,k,=,N,-1,时，把手中设备分配给工厂,N,-1,；,依次类推；,当阶段,k,=1,时，把手中设备分配给工厂,1.,决策变量,u,k,：第,k,阶段分配给工厂,k,的设备台数,状态转移方程,资源分配问题,用,f,k,(,x,k,),表示将手中资源,x,k,分配给工厂,k,k,+1,N,时的最大利润，原问题即为计算,f,1,(,M,),M,=4,，,N,=3,，边界条件,f,4,(,x,4,) =,f,4,(,0,) =0,k,=3,时： （增函数）,具体计算（例）,k,=2,时：,资源分配问题,k,=1,时：,最优解,最大利润为,.,推广：非线性整数规划问题，如：,M=4, N=3,资源分配问题,应用动态规划方法解整数规划,实例,3,：单产品、无能力限制的批量问题,可以只考虑,可以证明：一定存在满足条件 的最优解,.,用,f,t,表示当,t,时段初始库存为,0,时，从,t,时段到,T,时段的子问题的最优费用值,最优值（费用）为,f,1,.,假设费用均非负，则在最优解中 ，即,X=(2,5,0,4),最优值为,561,（千元）,T,=4,， （千元）， （千元）， （千元,/,千件）,(,千件,),具体计算过程如下：,f,5,= 0;,f,4,= 3+50*4+0+0=203;,f,3,= min3+50(2+4)+1*4+0,3+50*2+0+11=306;,f,2,= min3+50(3+2+4)+1(2+4)+1*4+0,3+50(3+2)+1*2+11,3+50*3+0+18=458;,f,1,= min3+50(2+3+2+4)+1(3+2+4)+1(2+4)+1*4+0,3+50(2+3+2)+1(3+2)+1*2+11,3+50(2+3)+1*3+18, 3+50*2+0+26 = 561,LINDO,公司软件产品简要介绍,美国芝加哥(Chicago)大学的Linus Schrage教授于1980年前后开发, 后来成立 LINDO系统公司（LINDO Systems Inc.），,LINDO: Linear INteractive and Discrete Optimizer (V6.1),LINGO: Linear INteractive General Optimizer (V10.0),LINDO API: LINDO Application Programming Interface (V4.1),Whats Best!: (SpreadSheet e.g. EXCEL) (V8.0),演,示,(,试用,),版、高级版、超级版、工业版、扩展版,（求解,问题规模,和,选件,不同）,LINDO,和,LINGO,软件能求解的优化模型,LINGO,LINDO,优化模型,线性规划,(LP),非线性规划,(NLP),二次规划,(QP),连续优化,整数规划,(IP),目标,1,（总余量）,按模式,2,切割,12,根,按模式,5,切割,15,根，余料,27,米,最优解：,x,2,=12,x,5,=15,其余为,0,；,最优值：,27,x,i,为整数,实例,2,：钢,管下料,(,问题,1),当余料没有用处时，,通常以总根数最少为目标,目标,2,（总根数）,最优解：,x,2,=15,x,5,=5,x,7,=5,其余为,0,；,最优值：,25,。,x,i,为整数,按模式,2,切割,15,根，按模式,5,切割,5,根，按模式,7,切割,5,根，共,25,根，余料,35,米,虽余料增加,8,米，但减少了,2,根,与,目标,1,的结果“共切割,27,根，余料,27,米” 相比,:,实例,2,：钢,管下料,(,问题,1),LINGO,软件简介,LINGO,模型的优点,集成了线性,(,非线性,) /,连续,(,整数,),优化功能,运行速度较快,具有多点搜索,/,全局优化功能,提供了灵活的编程语言,(,矩阵生成器,),，可方便地输入模型,提供与其他数据文件的接口,(,如,TEXT, EXCEL, ODBC,数据库接口,),提供与其他编程语言的接口,LINDO API,可用于自主开发,LP QP NLP IP,全局优化,(,选,),ILP IQP INLP,LINGO,软件的求解过程,LINGO,预处理程序,线性优化求解程序,非线性优化求解程序,分枝定界管理程序,1.,确定常数,2.,识别类型,1.,单纯形算法,2.,内点算法,(,选,),1,、顺序线性规划法,(SLP),2,、广义既约梯度法,(GRG),(,选,),3,、多点搜索,(Multistart),(,选,),目标与约束段,集合段（,SETS ENDSETS,）,数据段（,DATA ENDDATA,）,初始段（,INIT ENDINIT,）,计算段（,CALC ENDCALC,）,- 9.0+,子模型（,SUBMODEL ENDSUBMODEL,）,- 10.0+,LINGO,模型的构成：,6,个段,集合的类型,集合,派生集合 基本集合,稀疏集合 稠密集合,元素列表法 元素过滤法 直接列举法 隐式列举法,setname /member_list/ : attribute_list;,setname(parent_set_list) /member_list/,: attribute_list;,SETS:,CITIES /A1,A2,A3,B1,B2/;,ROADS(CITIES, CITIES)/ A1,B1 A1,B2 A2,B1 A3,B2/:D;,ENDSETS,SETS:,STUDENTS /,S1.S8,/;,PAIRS( STUDENTS, STUDENTS) |,&2 #GT# &1,: BENEFIT, MATCH;,ENDSETS,集合循环函数,四个集合循环函数：,FOR,、,SUM,、,MAX,、,MIN,function( setname ( set_index_list) | condition : expression_list);,FOR(STUDENTS( I):,constraints,SUM( PAIRS( J, K) | J #EQ# I #OR# K #EQ# I: MATCH( J, K) =1);,Example:,objective,MAX = SUM( PAIRS( I, J): BENEFIT( I, J) * MATCH( I, J);,目标函数（,总根数）,x,i,r,1,i,r,2,i,r,3,i,r,4,i,(,i,=,1,2,3,),为整数,实例,2,：钢管下料,(,问题,2),增加约束，缩小可行域，便于求解,原料钢管总根数下界：,特殊生产计划：对每根原料钢管,模式,1,：切割成,4,根,4,米钢管，需,13,根；,模式,2,：切割成,1,根,5,米和,2,根,6,米钢管，需,10,根；,模式,3,：切割成,2,根,8,米钢管，需,8,根。,原料钢管总根数上界：,31,模式排列顺序可任定,需求：,4,米,50,根，,5,米,10,根，,6,米,20,根，,8,米,15,根,每根原料钢管长,19,米,实例,2,：钢管下料,(,问题,2),Local optimal solution found at iteration: 12211,Variable Value Reduced Cost,X1,X2,R11,R12,R21,R22 0.000000 R23 0.000000 0.000000 R31 0.000000 R32 0.000000 R33 0.000000 0.000000 R41 0.000000 R42 0.000000 R43 2.000000 0.000000,模式,1,：每根原料钢管切割成,3,根,4,米和,1,根,6,米钢管，共,10,根；,模式,2,：每根原料钢管切割成,2,根,4,米、,1,根,5,米和,1,根,6,米钢管，共,10,根；,模式,3,：每根原料钢管切割成,2,根,8,米钢管，共,8,根。,原料钢管总根数为,28,根。,演示；,实例,2,：钢管下料,(,问题,2),例：最短路；生产批量,建模时需要注意的几个基本问题,1,、,尽量使用实数优化，减少整数约束和整数变量,2,、,尽量使用光滑优化，减少非光滑约束的个数,如：尽量少使用绝对值、符号函数、多个变量求最大,/,最小值、四舍五入、取整函数等,3,、,尽量使用线性模型，减少非线性约束和非线性变量的个数 （如,x/y,5,改为,x,5,y,）,4,、,合理设定变量上下界，尽可能给出变量初始值,5,、,模型中使用的参数数量级要适当,(,如小于,10,3,),总结与实验,目的,1),掌握用,LINDO/LINGO,软件,求解整数规划,，并对结果作初步分析；,2),通过实例练习用,整数规划求解实际问题。,