数学规划与软件

2020年4月16日6时41分2020年4月16日星期四6时41分21秒王文祥2013.7数学规划模型、案例与软件求解2020年4月16日6时41分2020年4月16日星期四6时41分21秒一.数学规划模型与优化软件简介二.LINDO/LINGO软件Outline四.LINGO建模语言三.建模实例2020年4月16日6时41分2020年4月16日星期四6时41分21秒•数学规划是优化问题的一个分支，起始于20世纪30年代末，50年代与60年代发展成为一个完整的分支并受到数学界和社会各界的重视。七八十年代是数学规划飞速发展时期，无论是从理论上还是算法方面都得到了进一步完善。时至今日数学规划仍然是运筹学领域中热点研究问题。从国内外的数学建模竞赛的试题中看，有一半以上的问题可用数学规划进行求解。一.数学规划模型与优化软件简介2020年4月16日6时41分2020年4月16日星期四6时41分21秒约束条件数学规划模型的一般形式1012013min(max)()()..(),,...,()(),,...,()ijnorzfxsthximgxjlxDR可行域三要素：决策变量；目标函数；约束条件•可行解（只满足约束）与最优解(取到最优值))(..tosubjectts“受约束于”之意．2020年4月16日6时41分2020年4月16日星期四6时41分21秒数学规划类型•连续规划:全部决策变量取值均为连续数值(实数)•离散规划:部分或全部决策变量只取离散数值2020年4月16日6时41分2020年4月16日星期四6时41分21秒•线性规划(LP)目标和约束均为线性函数•非线性规划(NLP)目标或约束中存在非线性函数二次规划(QP)目标为二次函数、约束为线性•整数规划(IP)决策变量(全部或部分)为整数整数线性规划(ILP)，整数非线性规划(INLP)纯整数规划(PIP),混合整数规划(MIP)一般整数规划，0-1（整数）规划连续规划离散规划数学规划(MathematicalProgramming)2020年4月16日6时41分2020年4月16日星期四6时41分21秒常用优化软件1.LINDO/LINGO软件2.MATLAB优化工具箱/mathematica优化程序包3.EXCEL软件的优化功能4.SAS(统计分析)软件的优化功能2020年4月16日6时41分2020年4月16日星期四6时41分21秒LINDO公司软件产品简要介绍美国芝加哥(Chicago)大学的LinusSchrage教授于1980年前后开发,后来成立LINDO系统公司（LINDOSystemsInc.），网址：:LinearInteractionGeneralOptimizer2020年4月16日6时41分2020年4月16日星期四6时41分21秒LINDO和LINGO能求解的数学规划模型LINGOLINDO数学规划模型线性规划(LP)非线性规划(NLP)二次规划(QP)连续规划整数规划(IP)2020年4月16日6时41分2020年4月16日星期四6时41分21秒•LINDO是专门用于求解数学规划的软件包。LINDO执行速度很快、易于方便输入，因此在数学、科研和工业界得到广泛应用。•LINDO主要用于解线性规划、二次规划。也可以用于线性方程组的求解以及代数方程求根等。•LINDO中包含了建模语言和许多常用的数学函数（包括大量概论函数），可供使用者建立规划问题时调用。•一般用LINDO（LinearInteractiveandDiscreteOptimizer）解决线性规划二.LINDO/LINGO软件简介2020年4月16日6时41分2020年4月16日星期四6时41分21秒•最大规模的模型的非零系数可以达到1,000,000个•最大变量个数可以达到100,000个，最大目标函数和约束条件个数可以达到32000个•最大整数变量个数可以达到100,000个•LINDO6.1学生版至多可求解多达300个变量和150个约束的规划问题2020年4月16日6时41分2020年4月16日星期四6时41分21秒1.求解线性规划和非线性规划问题2.模型输入简练直观3.运行速度快计算能力强4.内置建模语言提供内部函数较少语句直观描述大规模优化模型5.引入集合容易建模6.数据交换方便(与EXCEL和数据库)LINGO软件的主要功能和特点2020年4月16日6时41分2020年4月16日星期四6时41分21秒例1简单的线性规划（LP）问题：0,12531034..32yxyxyxtsyxzMax在空白的模型窗口中输入这个LP模型：max2x+3yst4x+3y=103x+5y12end2020年4月16日6时41分2020年4月16日星期四6时41分21秒如图：2020年4月16日6时41分2020年4月16日星期四6时41分21秒LINDO程序有以下特点：★程序以“MAX”（或“MIN”）开始，表示目标最大化（或最小化）问题，后面直接写目标函数表达式和约束表达式；★目标函数和约束之间用“ST”分开；（或用“s.t.”）★程序以“END”结束（“END”也可以省略）。★系数与变量之间的乘号必须省略。★系统对目标函数所在行自动生成行名“1）”,对约束默认的行名分别是“2)”“3)”…，用户也可以自己输入行名；行名放在对应的约束之前。★书写相当灵活，不必对齐，不区分字符的大小写。★默认所有的变量都是非负的,所以不必输入非负约束。★约束条件中的“=”及“=”可分别用“”及“”代替。★一行中感叹号“！”后面的文字为是注释语句，可增强程序的可读性，不参与模型的建立。2020年4月16日6时41分2020年4月16日星期四6时41分21秒模型求解：用鼠标点击工具栏中的图标，或从菜单中选择Solve|Solve（Ctrl+S）命令LINDO首先开始编译这个模型，编译没有错误则开始求解；求解时会首先显示如右图所示的LINDO“求解器运行状态窗口”。2020年4月16日6时41分2020年4月16日星期四6时41分21秒求解器运行状态窗口显示的相应信息及含义：名称含义Status当前状态显示当前求解状态：“Optimal”表示已达到最优解；其他可能的显示还有三个：Feasible(可行解),Infeasible(不可行),Unbounded(最优值无界)。Iterations迭代次数显示迭代次数：“2”表示经过了2次迭代。Infeasibility不可行性约束不满足的量(即各个约束条件不满足的“数量”的和)：“0”表示解是可行的。Objective当前目标值显示目标函数当前的值：7.45455。BestIP整数规划当前最佳目标值显示整数规划当前的最佳目标值：“N/A”（NoAnswer）表示无答案或无意义，因为这个模型中没有整数变量，不是整数规划（IP）。2020年4月16日6时41分2020年4月16日星期四6时41分21秒名称含义IPBound整数规划的界显示整数规划的界（对最大化问题显示上界；对最小化问题，显示下界）Branches分枝数显示分枝定界算法已经计算的分枝数：ElapsedTime所用时间显示计算所用时间（秒）：“0.00”说明计算太快了，用时还不到0.005秒。UpdateInterval刷新本界面时间间隔显示和控制刷新本界面的时间间隔：“1”表示1秒；用户可以直接在界面上修改这个时间间隔。InterruptSolver中断求解程序当模型规模比较大时，求解时间会很长，可以在程序运行过程中用鼠标点击该按钮终止计算。Close关闭该按钮是关闭状态窗口，并不终止计算2020年4月16日6时41分2020年4月16日星期四6时41分21秒紧接着弹出一对话框，询问你是否需要做灵敏性分析（DORANGE(SENSITIVITY)ANALYSIS?）先选择“否（N）”按钮，这个窗口就会关闭。然后，再把状态窗口也关闭。2020年4月16日6时41分2020年4月16日星期四6时41分21秒报告窗口用鼠标选择“Window|ReportsWindow”（报告窗口），就可以查看该窗口的内容2020年4月16日6时41分2020年4月16日星期四6时41分21秒输出结果表示的意思是：“LPOPTIMUMFOUNDATSTEP2”表示单纯形法在两次迭代（旋转）后得到最优解。“OBJECTIVEFUNCTIONVALUE1)7.454545”表示最优目标值为7.454545.（注意：在LINDO中目标函数所在的行总是被认为是第1行，这就是这里“1）”的含义）。2020年4月16日6时41分2020年4月16日星期四6时41分21秒“VALUE”给出最优解中各变量(VARIABLE)的值:X=1.272727,Y=1.636364.“REDUCEDCOST”给出最优的单纯形表中目标函数行（第1行）中变量对应的系数.“SLACKORSURPLUS（松驰或剩余）”给出约束对应的松驰变量的值:第2、3行松驰变量均为0,说明对于最优解来讲，两个约束（第2、3行）均取等号，即都是紧约束。2020年4月16日6时41分2020年4月16日星期四6时41分21秒“DUALPRICES”给出对偶价格（或影子价格）的值:表示最优解下“资源”增加1单位时“效益”的增量。第2、3行对偶价格分别为.090909，.545455。“NO.ITERATIONS=2”表示用单纯形法进行了两次迭代。2020年4月16日6时41分2020年4月16日星期四6时41分21秒使用LINDO的一些注意事项1.“”（或“”）号与“=”（或“=”）功能相同2.变量与系数间可有空格(甚至回车),但无运算符3.变量名以字母开头，不能超过8个字符4.变量名不区分大小写（包括LINDO中的关键字）5.目标函数所在行是第一行，第二行起为约束条件6.行号(行名)自动产生或人为定义。行名以“）”结束7.行中注有“!”符号的后面部分为注释。如:!It’sComment.8.在模型的任何地方都可以用“TITLE”对模型命名（最多72个字符），如：TITLEThisModelisonlyanExample2020年4月16日6时41分2020年4月16日星期四6时41分21秒9.变量不能出现在一个约束条件的右端10.表达式中不接受括号“()”和逗号“,”等任何符号,例:400(X1+X2)需写为400X1+400X211.表达式应化简，如2X1+3X2-4X1应写成-2X1+3X212.缺省假定所有变量非负；可在模型的“END”语句后用“FREEname”将变量name的非负假定取消13.可在“END”后用“SUB”或“SLB”设定变量上下界例如：“subx110”的作用等价于“x1=10”但用“SUB”和“SLB”表示的上下界约束不计入模型的约束，也不能给出其松紧判断和敏感性分析。使用LINDO的一些注意事项2020年4月16日6时41分2020年4月16日星期四6时41分21秒14.“END”后对0-1变量说明：INTn或INTname15.“END”后对整数变量说明：GINn或GINname使用LINDO的一些注意事项16.简单错误的检查和避免：输入模型时可能会有某些输入错误.当问题规模较大时,要查找错误是比较困难的。在LINDO中有一些可帮助寻找错误的功能，其中之一就是菜单命令“Report|Picture（Alt+5）”,它的功能是可以将目标函数和约束表达式中的非零系数通过列表（或图形）显示出来。2020年4月16日6时41分2020年4月16日星期四6时41分21秒三个变量范围限定命令(FREE、SUB、SLB)的作用求解如下的LP问题：MAX2x–3y+4zS.T.4x+3y+2z≤10-3x+5y-z≤12x+y+5z≥8-5x-y-z≥20≤y≤20,z