数学建模讲义-谢金星

数学建模讲座（2004年7月~8月江西）优化模型与LINDO/LINGO优化软件谢金星清华大学数学科学系Tel:010-62787812Email:[e-mail]~jxie简要提纲•优化模型简介•LINDO公司的主要软件产品及功能简介•LINDO软件的使用简介•LINGO软件的使用简介•建模与求解实例（结合软件使用）优化模型实际问题中的优化模型mixgtsxxxxfzMaxMiniTn,2,1,0)(..),(),()(1或x~决策变量f(x)~目标函数gi(x)0~约束条件数学规划线性规划(LP)二次规划(QP)非线性规划(NLP)纯整数规划(PIP)混合整数规划(MIP)整数规划(IP)0-1整数规划一般整数规划连续规划LINDO公司软件产品简要介绍美国芝加哥(Chicago)大学的LinusSchrage教授于1980年前后开发,后来成立LINDO系统公司（LINDOSystemsInc.），网址：(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/y5改为x5y）4、合理设定变量上下界，尽可能给出变量初始值5、模型中使用的参数数量级要适当(如小于103)需要掌握的几个重要方面1、LINDO:正确阅读求解报告（尤其要掌握敏感性分析）2、LINGO：掌握集合(SETS)的应用；正确阅读求解报告；正确理解求解状态窗口；学会设置基本的求解选项(OPTIONS)；掌握与外部文件的基本接口方法例1加工奶制品的生产计划1桶牛奶3公斤A112小时8小时4公斤A2或获利24元/公斤获利16元/公斤50桶牛奶时间480小时至多加工100公斤A1制订生产计划，使每天获利最大•35元可买到1桶牛奶，买吗？若买，每天最多买多少?•可聘用临时工人，付出的工资最多是每小时几元?•A1的获利增加到30元/公斤，应否改变生产计划？每天：1桶牛奶3公斤A112小时8小时4公斤A2或获利24元/公斤获利16元/公斤x1桶牛奶生产A1x2桶牛奶生产A2获利24×3x1获利16×4x2原料供应5021xx劳动时间48081221xx加工能力10031x决策变量目标函数216472xxzMax每天获利约束条件非负约束0,21xx线性规划模型(LP)时间480小时至多加工100公斤A150桶牛奶每天模型求解max72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100endOBJECTIVEFUNCTIONVALUE1)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+x2503）12x1+8x24804）3x1100end三种资源“资源”剩余为零的约束为紧约束（有效约束）结果解释OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000结果解释最优解下“资源”增加1单位时“效益”的增量原料增1单位,利润增48时间加1单位,利润增2能力增减不影响利润影子价格•35元可买到1桶牛奶，要买吗？3548,应该买！•聘用临时工人付出的工资最多每小时几元？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时间最多增加53•35元可买到1桶牛奶，每天最多买多少？最多买10桶？(目标函数不变)注意:充分但可能不必要使用LINDO的一些注意事项1.“”（或“”）号与“=”（或“=”）功能相同2.变量与系数间可有空格(甚至回车),但无运算符3.变量名以字母开头，不能超过8个字符4.变量名不区分大小写（包括LINDO中的关键字）5.目标函数所在行是第一行，第二行起为约束条件6.行号(行名)自动产生或人为定义。行名以“）”结束7.行中注有“!”符号的后面部分为注释。如:!It’sComment.8.在模型的任何地方都可以用“TITLE”对模型命名（最多72个字符），如：TITLEThisModelisonlyanExample9.变量不能出现在一个约束条件的右端10.表达式中不接受括号“()”和逗号“,”等任何符号,例:400(X1+X2)需写为400X1+400X211.表达式应化简，如2X1+3X2-4X1应写成-2X1+3X212.缺省假定所有变量非负；可在模型的“END”语句后用“FREEname”将变量name的非负假定取消13.可在“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/Statist