单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,6,单纯形法,6.1,，,6.2,单纯形表和,Lingo,在第五章介绍了单纯形表及其变化形式,把典式的系数记为,称,T(B),是,LP,问题,(L),对基,B,的单纯形表,.,大家读懂单纯形表后,转化,为,Lingo,程序求解,单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解，再鉴别；若仍不是，则再转换，按此重复进行。,因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。,如果问题无最优解也可用此法判别。,对单纯形表形式的说明,课本中计算采用的形式,:,基变量，对应,A,中的列向量为基,基变量的值,这个基解下目标函数的值,目标函数,共有五个变量,顺序排列,变换后的目标函数的系数,变换后的系数矩阵,单纯形法的解题步骤,：,否,得最优解，结束,无最优解，结束,重复流程,否,再论单纯形表,单纯形法迭代计算的基本方法：,2.,最小比值法是保证可行解的前提条件,.,1.,保持原问题为可行解的基础上，通过换基迭代，,当其检验数都为非正数,时，就达到了目标函数的,最优值,.,Lingo,运行过程,LP QP NLP IP,全局优化,(,选,),ILP IQP INLP,LINDO/LINGO,预处理程序,线性优化求解程序,非线性优化求解程序,分枝定界管理程序,1.,确定常数,2.,识别类型,1.,单纯形算法,2.,内点算法,barrier,(,选,),1.,顺序线性规划法,(SLP),2.,广义既约梯度法,(GRG),(,选,),3.,多点搜索,(Multistart),(,选,),LINGO模型的构成：4个段,目标与约束段,集合段（,SETS ENDSETS,）,数据段（,DATA ENDDATA,）,初始段（,INIT ENDINIT,）,Lingo,相对于,Lindo,的优点：,1.,包含了,LINDO,的全部功能,2.,提供了灵活的编程语言（矩阵生成器）,状态窗口,（,LINDO Solver Status,）,当前状态：已达最优解,迭代次数：,18,次,约束不满足的“量”,(,不是“约束个数”,),：,0,当前的目标值：,94,最好的整数解：,94,整数规划的界：,93.5,分枝数：,1,所用时间：,0.00,秒（太快了，还不到,0.005,秒）,刷新本界面的间隔,:1(,秒,),求解器状态窗口,变量数量,T,N,In,T,N,T,N,Class,Ob,Infe,Ite,Type,Obj,求解花费时间,非零系数数量,内存使用数量,约束数量,模型类型,当前解状态,当前目标函数值,扩展求解器,使用的特殊求解程序,到目前的最佳目标值,特殊求解程序当前运行步数,有效步数,B-and-B,Global,Multistart,LP,，,QP,，,ILP,，,IQP,，,PILP,，,PIQP,，,NLP,，,INLP,，,PINLP,“Global Optimum”,（全局最优）,“Local Optimum”,（局部最优）“,Feasible”,（可行）,“Infeasible”,（不可行）“,Unbounded”,（无界）“,Interrupted”,（中断）“,Undetermined”,（未确定）,约束不满足的总量,目前为止的迭代次数,目标函数值的界,分枝数,(,对,B-and-B,程序,),；,子问题数,(,对,Global,程序,),；,初始点数,(,对,Multistart,程序,),可直接求,解的变量,不作为决,策变量。,更新时间间隔,求解报告窗口,Lingo,注意事项,“,”,（或“,=”,（或“,=”,）功能相同；,LINGO,模型以“,MODEL,：”开始，“,END”,结束；,变量与系数间有乘号运算符“*”如：,2*x,；,变量名以,字母,开头且不区分大小写，不能超过,64,个字符；,模型的开头可以用“,TITLE”,对模型命名且语句的顺序不重要；,行中注有“,!”,符号的后面部分为注释，例如,:,!Its Comment.,集合段表示,集合,派生集合 基本集合,稀疏集合 稠密集合,元素列表法 元素过滤法 直接列举法 隐式列举法,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,集合元素的,隐式列举,类型,隐式列举格式,示例,示例集合的元素,数字型,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,调用函数,开头都是函数调用，例如：,gin,（,x,）：表示变量,x,取整；,bin,（,x,）：表示变量,x=0,或,1,；,bnd,（,L,，,x,，,U,）：表示,L,x,U,；,free,（,x,）：表示变量,x,无非负限制，,即,xR,集合循环函数,for,，,sum,，,max,，,min,生成约束,for,：对集合中的所有元素进行约束,一般格式为,for(setname(set,-index-list),condition ,:expression-list);,求和,sum,：用于计算集合中所有元素的表达式的总和,一般格式为,sum(setname(set,-index-list),condition ,:expression-list);,最大值,max=,最小值,min=,一般格式为,max,（或者,min,）,=sum,LINGO,模型的构成：,4,个段,集合段（,SETS ENDSETS,）,数据段（,DATA ENDDATA,）,初始段（,INIT ENDINIT,）,以后再讲,目标与,约束段,局部最优：,89.8835(,吨公里,),LP,：移到数据段,例,1,Lingo程序（集合段）,MODEL:,TITLE EX060201;,!,简单的线性规划只需要修改一下已有模型的集合段和数据段,;,!,直接输入为,min=-5*x1-2*x2,；,2*x1+x2+x3=8,；,x1+x4=3,；（为了避免中止说明语句，这里用的是文本格式的分号，在模型中是作为文本的）,x2+x5=4;,SETS:,HANG/1.3/:B;,LIE/1.5/:C,X;,XISHU(HANG,LIE):A;,ENDSETS,DATA:,A=2 1 1 0 0,1 0 0 1 0,0 1 0 0 1;,C=-5-2 0 0 0;,B=8 3 4;,ENDDATA,OBJ,MIN=SUM(LIE:C*X);,FOR(HANG(I):,YUESHU,SUM(LIE(J):A(I,J)*X(J)=B(I);,END,