6.16.2单纯形表与Lingo.pptVIP

6 单纯形法 6.1 ，6.2单纯形表和Lingo 单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解，再鉴别；若仍不是，则再转换，按此重复进行。 因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。 如果问题无最优解也可用此法判别。 对单纯形表形式的说明 Lingo运行过程 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(秒) －求解器状态窗口－ Lingo注意事项 @—调用函数 @开头都是函数调用，例如： @gin（x）：表示变量x取整； @bin（x）：表示变量x=0或1； @bnd（L，x，U）：表示L≦x ≦ U； @free（x）：表示变量x无非负限制， 即x∈R 集合循环函数for，sum，max，min 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 * * 在第五章介绍了单纯形表及其变化形式, 把典式的系数记为 称T(B)是LP问题(L)对基B的单纯形表. 大家读懂单纯形表后转化为Lingo程序求解 课本中计算采用的形式: 基变量，对应A中的列向量为基 基变量的值 这个基解下目标函数的值 目标函数 共有五个变量,顺序排列 变换后的目标函数的系数 变换后的系数矩阵 单纯形法的解题步骤： 否 得最优解，结束 无最优解，结束 重复流程 否 再论单纯形表 单纯形法迭代计算的基本方法： 2. 最小比值法是保证可行解的前提条件. 1. 保持原问题为可行解的基础上，通过换基迭代， 当其检验数都为非正数时，就达到了目标函数的 最优值. LP QP NLP IP 全局优化(选) ILP IQP INLP LINDO/LINGO预处理程序 线性优化求解程序 非线性优化求解程序 分枝定界管理程序 1. 确定常数 2. 识别类型 1. 单纯形算法 2. 内点算法barrier(选) 1.顺序线性规划法(SLP) 2.广义既约梯度法(GRG) (选) 3.多点有哪些信誉好的足球投注网站(Multistart) (选) 变量数量 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”（未确定） 约束不满足的总量 目前为止的迭代