优化模型与LINDOLINGO优化软件教程来自清华大学数学科学系

数学建模讲座（2004年7月~8月江西）优化模型与LINDO/LINGO优化软件谢金星清华大学数学科学系Tel:010-62787812Email:jxie@math.tsinghua.edu.cnhttp://faculty.math.tsinghua.edu.cn/~jxie简要提纲优化模型简介LINDO公司的主要软件产品及功能简介LINDO软件的使用简介LINGO软件的使用简介建模与求解实例（结合软件使用）优化模型实际问中的优化模型x~决策变量f(x)~目标函数gi(x)0~约束条件数学规划线性规划(LP)二次规划(QP)非线性规划(NLP)纯整数规划(PIP)混合整数规划(MIP)整数规划(IP)0-1整数规划一般整数规划连续规划LINDO公司软件产品简要介绍美国芝加哥(Chicago)大学的LinusSchrage教授于1980年前后开发,后来成立LINDO系统公司（LINDOSystemsInc.），网址：http://www.lindo.comLINDO:LinearINteractiveandDiscreteOptimizer(V6.1)LINGO:LinearINteractiveGeneralOptimizer(V8.0)LINDOAPI:LINDOApplicationProgrammingInterface(V2.0)What’sBest!:(SpreadSheete.g.EXCEL)(V7.0)演示(试用)版、学生版、高级版、超级版、工业版、扩展版…（求解问题规模和选件不同）LINDO和LINGO软件能求解的优化模型LINGOLINDO优化模型线性规划(LP)非线性规划(NLP)二次规划(QP)连续优化整数规划(IP)LPQPNLPIP全局优化(选)ILPIQPINLPLINDO/LINGO软件的求解过程LINDO/LINGO预处理程序线性优化求解程序非线性优化求解程序分枝定界管理程序1.确定常数2.识别类型1.单纯形算法2.内点算法(选)1、顺序线性规划法(SLP)2、广义既约梯度法(GRG)(选)3、多点搜索(Multistart)(选)建模时需要注意的几个基本问题1、尽量使用实数优化，减少整数约束和整数变量2、尽量使用光滑优化，减少非光滑约束的个数如：尽量少使用绝对值、符号函数、多个变量求最大/最小值、四舍五入、取整函数等3、尽量使用线性模型，减少非线性约束和非线性变量的个数（如x/y<5改为x<5y）4、合理设定变量上下界，尽可能给出变量初始值5、模型中使用的参数数量级要适当(如小于103)需要掌握的几个重要方面1、LINDO:正确阅读求解（尤其要掌握敏感性分析）2、LINGO：掌握集合(SETS)的应用；正确阅读求解报告；正确理解求解状态窗口；学会设置基本的求解选项(OPTIONS)；掌握与外部文件的基本接口例1加工奶制品的生产计划50桶牛奶时间480小时至多加工100公斤A1制订生产计划，使每天获利最大35元可买到1桶牛奶，买吗？若买，每天最多买多少?可聘用临时工人，付出的工资最多是每小时几元?A1的获利增加到30元/公斤，应否改变生产计划？每天：x1桶牛奶生产A1x2桶牛奶生产A2获利24×3x1获利16×4x2原料供应劳动时间加工能力决策变量目标函数每天获利约束条件非负约束线性规划模型(LP)时间480小时至多加工100公斤A1模型求解max72x1+64x2st2）x1+x2<503）12x1+8x2<4804）3x1<100endOBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2DORANGE(SENSITIVITY)ANALYSIS?No20桶牛奶生产A1,30桶生产A2，利润3360元。模型求解reducedcost值表示当该非基变量增加一个单位时（其他非基变量保持不变）目标函数减少的量(对max型问题)OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2也可理解为：为了使该非基变量变成基变量，目标函数中对应系数应增加的量OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000原料无剩余时间无剩余加工能力剩余40max72x1+64x2st2）x1+x2<503）12x1+8x2<4804）3x1<100end三种资源“资源”剩余为零的约束为紧约束（有效约束）结果解释OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000结果解释最优解下“资源”增加1单位时“效益”的增量原料增1单位,利润增48时间加1单位,利润增2能力增减不影响利润影子价格35元可买到1桶牛奶，要买吗？35<48,应该买！聘用临时工人付出的工资最多每小时几元？2元！RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000最优解不变时目标系数允许变化范围DORANGE(SENSITIVITY)ANALYSIS?Yesx1系数范围(64,96)x2系数范围(48,72)A1获利增加到30元/千克，应否改变生产计划x1系数由243=72增加为303=90，在允许范围内不变！(约束条件不变)结果解释结果解释RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000影子价格有意义时约束右端的允许变化范围原料最多增加10时间最多增加5335元可买到1桶牛奶，每天最多买多少？最多买10桶？(目标函数不变)注意:充分但可能不必要使用LINDO的一些注意事项“>”（或“<”）号与“>=”（或“<=”）功能相同变量与系数间可有空格(甚至回车),但无运算符变量名以字母开头，不能超过8个字符变量名不区分大小写（包括LINDO中的关键字）目标函数所在行是第一行，第二行起为约束条件行号(行名)自动产生或人为定义。行名以“）”结束行中注有“!”符号的后面部分为注释。如:!It’sComment.在模型的任何地方都可以用“TITLE”对模型命名（最多72个字符），如：TITLEThisModelisonlyanExample变量不能出现在一个约束条件的右端表达式中不接受括号“()”和逗号“,”等任何符号,例:400(X1+X2)需写为400X1+400X2表达式应化简，如2X1+3X2-4X1应写成-2X1+3X2缺省假定所有变量非负；可在模型的“END”语句后用“FREEname”将变量name的非负假定取消可在“END”后用“SUB”或“SLB”设定变量上下界例如：“subx110”的作用等价于“x1<=10”但用“SUB”和“SLB”表示的上下界约束不计入模型的约束，也不能给出其松紧判断和敏感性分析。14.“END”后对0-1变量说明：INTn或INTname15.“END”后对整数变量说明：GINn或GINname使用LINDO的一些注意事项二次规划(QP)问题LINDO可求解二次规划(QP)问题，但输入方式较复杂，因为在LINDO中不许出现非线性表达式需要为每一个实际约束增加一个对偶变量（LAGRANGE乘子），在实际约束前增加有关变量的一阶最优条件，转化为互补问题“END”后面使用QCP命令指明实际约束开始的行号，然后才能求解建议总是用LINGO解QP[注意]对QP和IP:敏感性分析意义不大状态窗口（LINDOSolverStatus）当前状态：已达最优解迭代次数：18次约束不满足的“量”(不是“约束个数”)：0当前的目标值：94最好的整数解：94整数规划的界：93.5分枝数：1所用时间：0.00秒（太快了，还不到0.005秒）刷新本界面的间隔:1(秒)选项设置Preprocess：预处理(生成割平面)；PreferredBranch：优先的分枝方式：“Default”（缺省方式）、“Up”（向上取整优先）、“Down”（向下取整优先）；IPOptimalityTol：IP最优值允许的误差上限（一个百分数，如5%即0.05）；IPObjectiveHurdle：IP目标函数的篱笆值，即只寻找比这个值更优最优解（如当知道当前模型的某个整数可行解时，就可以设置这个值）；IPVarFixingTol：固定一个整数变量取值所依据的一个上限（如果一个整数变量的判别数（REDUCEDCOST）的值很大，超过该上限，则以后求解中把该整数变量固定下来）。NonzeroLimit：非零系数的个数上限；IterationLimit：最大迭代步数；InitialContraintTol：约束的初始误差上限；FinalContraintTol：约束的最后误差上限；EnteringVarTol：进基变量的REDUCEDCOST的误差限；PivotSizeTol：旋转元的误差限Report/Statistics第一行：模型有5行（约束4行），4个变量，两个整数变量（没有0-1变量），从第4行开始是二次规划的实际约束。第二行：非零系数19个，约束中非零系数12个(其中6个为1或-1)，模型密度为0.760(密度=非零系数/[行数＊(变量数＋１)])。第三行的意思：按绝对值看，系数最小、最大分别为0.3和277。第四行的意思：模型目标为极小化；小于等于、等于、大于等于约束分别有２、０、２个；广义上界约束（GUBS）不超过１个；变量上界约束（VUBS）不少于０个。所谓GUBS，是指一组不含有相同变量的约束；所谓VUBS，是指一个蕴涵变量上界的约束，如从约束X1+X2-X3=0可以看出，若X3=0，则X1=0，X2=0（因为有非负限制），因此X1+X2-X3=0是一个VUBS约束。第五行的意思：只含１个变量的约束个数=０个；冗余的列数=０个ROWS=5VARS=4INTEGERVARS=2(0=0/1)QCP=4NONZEROS=19CONSTRAINTNONZ=12(6=+-1)DENSITY=0.760SMALLESTANDLARGESTELEMENTSINABSOLUTEVALUE=0.300000277.000OBJ=MIN,NO.<,=,>:202,GUBS<=1VUBS>=0SINGLECOLS=0REDUNDANTCOLS=0LINDO行命令、命令脚本文件批处理：可以采用命令脚本（行命令序列）WINDOWS环境下行命令的意义不大Example演示用FILE/TAKECOMMANDS(F11)命令调入必须是以LINDOPACKED形式（压缩）保存的文件FILE/SAVE命令SAVE行命令LINGO软件简介目标与约束段集合段（SETSENDSETS）数据段（DATAENDDATA）初始段（INITENDINIT）LINGO模型的构成：4个段LINGO模型的优点包含了LINDO的全部功能提供了灵活的编程语言（矩阵生成器）LINGO模型—例：选址问题某公司有6个建筑工地，位置坐标为(ai,bi)(单位：公里),水泥日用量di(单位：吨）假设：料场和工地之间有直线道路用例中数据计算，最优解为总吨公里数为136.2线性规划模型决策变量：cij(料场j到工地i的运量）~12维选址问题：NLP2）改建两个新料场，需要确定新料场位置(xj,yj)和运量cij，在其它条件不变下使总吨公里数最小。决策变量：cij，(xj,yj)~16维非线性规划模型LINGO模型的构成：4个段集合段（SETSENDSETS）数据段（DATAENDDATA）初始段（INITENDINIT）目标与约束段局部最优：89.8835(吨公里)LP：移到数据段边界集合的类型集合派生集合基本集合稀疏集合稠密集合元素列表法元素过滤法直接列举法隐式列举法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运算符的优先级三类运算符：算术运算符逻辑运算符关系运算符优先级运算符最高#NOT#—（负号）^*/+—（减法）#EQ##NE##GT##GE##LT##LE##AND##OR#最低<(=)=>(=)集合循环函数四个集合循环函数：FOR、SUM、MAX、MIN@function(setname[(set_index_list)[|condition]]:expression_list);[objective]MAX=@SUM(PAIRS(I,J):BENEFIT(I,J)*MATCH(I,J));@FOR(STUDENTS(I):[constraints]@SUM(PAIRS(J,K)|J#EQ#I#OR#K#EQ#I:MATCH(J,K))=1);@FOR(PAIRS(I,J):@BIN(MATCH(I,J)));MAXB=@MAX(PAIRS(I,J):BENEFIT(I,J));MINB=@MIN(PAIRS(I,J):BENEFIT(I,J));Example:状态窗口SolverType:B-and-BGlobalMultistartModelClass:LP，QP，ILP，IQP，PILP,PIQP，NLP，INLP，PINLPState:GlobalOptimumLocalOptimumFeasibleInfeasibleUnboundedInterruptedUndetermined7个选项卡(可设置80-90个控制参数)程序与数据分离文本文件使用外部数据文件Cut(orCopy)–Paste方法@FILE输入数据、@TEXT输出数据（文本文件）@OLE函数与电子表格软件（如EXCEL）连接@ODBC函数与数据库连接LINGO命令脚本文件LG4（LONGO模型文件）LNG（LONGO模型文件）LTF（LONGO脚本文件）LDT（LONGO数据文件）LRP（LONGO报告文件）常用文件后缀@FILE和@TEXT：文本文件输入输出MODEL:SETS:MYSET/@FILE(‘myfile.txt’)/:@FILE(‘myfile.txt’);ENDSETSMIN=@SUM(MYSET(I):SHIP(I)*COST(I));@FOR(MYSET(I):[CON1]SHIP(I)>NEED(I);[CON2]SHIP(I)内容

财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容