6.1,6.2单纯形表与Lingo

6单纯形法6.1，6.2单纯形表和Lingo在第五章介绍了单纯形表及其变化形式,把典式的系数记为bBABbBccABcBT111B1B称T(B)是LP问题(L)对基B的单纯形表.大家读懂单纯形表后转化为Lingo程序求解单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解，再鉴别；若仍不是，则再转换，按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。对单纯形表形式的说明课本中计算采用的形式:基变量，对应A中的列向量为基基变量的值这个基解下目标函数的值目标函数共有五个变量,顺序排列变换后的目标函数的系数变换后的系数矩阵单纯形法的解题步骤：已知可行基开始BT单纯形表系数矩阵?0s是否有检验数rsb元最小比值法则确定枢轴表枢轴换基得新的单纯形否得最优解，结束?0isb是否有无最优解，结束重复流程否再论单纯形表NBIcNBcObBbBcBTNBB1111单纯形法迭代计算的基本方法：2.最小比值法是保证可行解的前提条件.1.保持原问题为可行解的基础上，通过换基迭代，当其检验数都为非正数时，就达到了目标函数的最优值.Lingo运行过程LPQPNLPIP全局优化(选)ILPIQPINLPLINDO/LINGO预处理程序线性优化求解程序非线性优化求解程序分枝定界管理程序1.确定常数2.识别类型1.单纯形算法2.内点算法barrier(选)1.顺序线性规划法(SLP)2.广义既约梯度法(GRG)(选)3.多点搜索(Multistart)(选)LINGO模型的构成：4个段目标与约束段集合段（SETSENDSETS）数据段（DATAENDDATA）初始段（INITENDINIT）Lingo相对于Lindo的优点：1.包含了LINDO的全部功能2.提供了灵活的编程语言（矩阵生成器）状态窗口（LINDOSolverStatus）当前状态：已达最优解迭代次数：18次约束不满足的“量”(不是“约束个数”)：0当前的目标值：94最好的整数解：94整数规划的界：93.5分枝数：1所用时间：0.00秒（太快了，还不到0.005秒）刷新本界面的间隔:1(秒)－求解器状态窗口－变量数量TNInTNTNClassObInfeIteTypeObj求解花费时间非零系数数量内存使用数量约束数量模型类型当前解状态当前目标函数值扩展求解器使用的特殊求解程序到目前的最佳目标值特殊求解程序当前运行步数有效步数B-and-BGlobalMultistartLP，QP，ILP，IQP，PILP，PIQP，NLP，INLP，PINLP“GlobalOptimum”（全局最优）“LocalOptimum”（局部最优）“Feasible”（可行）“Infeasible”（不可行）“Unbounded”（无界）“Interrupted”（中断）“Undetermined”（未确定）约束不满足的总量目前为止的迭代次数目标函数值的界分枝数(对B-and-B程序)；子问题数(对Global程序)；初始点数(对Multistart程序)可直接求解的变量不作为决策变量。更新时间间隔－求解报告窗口－Lingo注意事项“”（或“”）号与“=”（或“=”）功能相同；LINGO模型以“MODEL：”开始，“END”结束；变量与系数间有乘号运算符“*”如：2*x；变量名以字母开头且不区分大小写，不能超过64个字符；模型的开头可以用“TITLE”对模型命名且语句的顺序不重要；行中注有“!”符号的后面部分为注释，例如:!It’sComment.集合段表示集合派生集合基本集合稀疏集合稠密集合元素列表法元素过滤法直接列举法隐式列举法setname[/member_list/][:attribute_list];setname(parent_set_list)[/member_list/][:attribute_list];SETS:CITIES/A1,A2,A3,B1,B2/;ROADS(CITIES,CITIES)/A1,B1A1,B2A2,B1A3,B2/:D;ENDSETSSETS:STUDENTS/S1..S8/;PAIRS(STUDENTS,STUDENTS)|&2#GT#&1:BENEFIT,MATCH;ENDSETS集合元素的隐式列举类型隐式列举格式示例示例集合的元素数字型1..n1..51,2,3,4,5字符-数字型stringM..stringNCar101..car208Car101,car102,…,car208星期型dayM..dayNMON..FRIMON,TUE,WED,THU,FRI月份型monthM..monthNOCT..JANOCT,NOV,DEC,JAN年份-月份型monthYearM..monthYearNOCT2001..JAN2002OCT2001,NOV2001,DEC2001,JAN2002@—调用函数@开头都是函数调用，例如：@gin（x）：表示变量x取整；@bin（x）：表示变量x=0或1；@bnd（L，x，U）：表示L≦x≦U；@free（x）：表示变量x无非负限制，即x∈R集合循环函数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）=@sumLINGO模型的构成：4个段集合段（SETSENDSETS）数据段（DATAENDDATA）初始段（INITENDINIT）——以后再讲目标与约束段局部最优：89.8835(吨公里)LP：移到数据段例151,04382..2-5-min524132121ixxxxxxxxtsxxfLPLingoi求解用Lingo程序（集合段）MODEL:TITLEEX060201;!简单的线性规划只需要修改一下已有模型的集合段和数据段;!直接输入为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=211001001001001;C=-5-2000;B=834;ENDDATA［OBJ］MIN=@SUM(LIE:C*X);@FOR(HANG(I):［YUESHU］@SUM(LIE(J):A(I,J)*X(J))=B(I));END