《6.16.2单纯形表与Lingo.ppt》由会员分享，可在线阅读，更多相关《6.16.2单纯形表与Lingo.ppt（19页珍藏版）》请在三一文库上搜索。
1、6 单纯形法,6.1 ，6.2单纯形表和Lingo,在第五章介绍了单纯形表及其变化形式,把典式的系数记为,称T(B)是LP问题(L)对基B的单纯形表. 大家读懂单纯形表后转化为Lingo程序求解,单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解，再鉴别；若仍不是，则再转换，按此重复进行。 因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。 如果问题无最优解也可用此法判别。,对单纯形表形式的说明,课本中计算采用的形式:,基变量，对应A中的列向量为基,基变量的值,这个基解下目标函数的值,目标函数,共有五个变量,顺序
2、排列,变换后的目标函数的系数,变换后的系数矩阵,单纯形法的解题步骤：,否,得最优解，结束,无最优解，结束,重复流程,否,再论单纯形表,单纯形法迭代计算的基本方法：,2. 最小比值法是保证可行解的前提条件.,1. 保持原问题为可行解的基础上，通过换基迭代， 当其检验数都为非正数时，就达到了目标函数的 最优值.,Lingo运行过程,LP QP NLP IP 全局优化(选) ILP IQP INLP,LINDO/LINGO预处理程序,线性优化求解程序,非线性优化求解程序,分枝定界管理程序,1. 确定常数 2. 识别类型,1. 单纯形算法 2. 内点算法barrier(选),1.顺序线性规划法(SLP
3、) 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.
4、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
5、”（不可行）“Unbounded”（无界）“Interrupted”（中断）“Undetermined”（未确定）,约束不满足的总量,目前为止的迭代次数,目标函数值的界,分枝数(对B-and-B程序)； 子问题数(对Global程序)； 初始点数(对Multistart程序),可直接求 解的变量 不作为决 策变量。,更新时间间隔,求解报告窗口,Lingo注意事项,“”（或“=”（或“=”）功能相同； LINGO模型以“MODEL：”开始，“END”结束； 变量与系数间有乘号运算符“ * ”如：2*x； 变量名以字母开头且不区分大小写，不能超过64个字符； 模型的开头可以用“TITLE” 对模型
6、命名且语句的顺序不重要； 行中注有“!”符号的后面部分为注释，例如: ! 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: STUD
7、ENTS /S1S8/; PAIRS( STUDENTS, STUDENTS) | ENDSETS,集合元素的隐式列举,调用函数,开头都是函数调用，例如： gin（x）：表示变量x取整； bin（x）：表示变量x=0或1； bnd（L，x，U）：表示Lx U； free（x）：表示变量x无非负限制， 即xR,集合循环函数 for，sum，max，min,生成约束for：对集合中的所有元素进行约束 一般格式为 for(setname(set-index-list) condition :expression-list);,求和sum：用于计算集合中所有元素的表达式的总和 一般格式为 sum(se
8、tname(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/13/:B; LIE/15/: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 OBJMIN=SUM(LIE:C*X); FOR(HANG(I):YUESHU SUM(LIE(J):A(I,J)*X(J)=B(I); END,