线性、整数规划模型

优化建模优化建模与计算许顺维优化建模参考书《优化建模与LINDO/LINGO软件》谢金星,薛毅编著,清华大学出版社,2005年7月第1版.~jxie/lindo优化建模内容提要1.优化模型的基本概念2.优化问题的建模实例3.LINDO/LINGO软件简介优化建模1.优化模型的基本概念优化建模最优化是工程技术、经济管理、科学研究、社会生活中经常遇到的问题,如:优化模型和算法的重要意义结构设计资源分配生产计划运输方案解决优化问题的手段•经验积累，主观判断•作试验，比优劣•建立数学模型，求解最优策略最优化:在一定条件下，寻求使目标最大(小)的决策优化建模优化问题三要素：决策变量；目标函数；约束条件约束条件决策变量优化问题的一般形式njiDxljxgmixhtsxf,...,1,0)(,...,1,0)(..)(min•无约束优化(没有约束)与约束优化(有约束)•可行解（只满足约束）与最优解(取到最优值)目标函数优化建模局部最优解与整体最优解•局部最优解(LocalOptimalSolution,如x1)•整体最优解(GlobalOptimalSolution,如x2)x*f(x)x1x2o优化建模优化模型的简单分类•线性规划(LP)目标和约束均为线性函数•非线性规划(NLP)目标或约束中存在非线性函数二次规划(QP)目标为二次函数、约束为线性•整数规划(IP)决策变量(全部或部分)为整数整数线性规划(ILP)，整数非线性规划(INLP)纯整数规划(PIP),混合整数规划(MIP)一般整数规划，0-1（整数）规划njiDxljxgmixhtsxf,...,1,0)(,...,1,0)(..)(min连续优化离散优化数学规划优化建模优化模型的简单分类和求解难度优化线性规划非线性规划二次规划连续优化整数规划问题求解的难度增加优化建模2.优化模型实例5021xx48081221xx10031x216472xxzMax目标函数约束条件0,21xx例2.1线性规划模型(LP)优化建模模型求解图解法x1x20ABCDl1l2l3l4l55021xx48081221xx10031x0,21xx约束条件50:211xxl480812:212xxl1003:13xl0:,0:2514xlxl216472xxzMax目标函数Z=0Z=2400Z=3600z=c(常数)~等值线c在B(20,30)点得到最优解目标函数和约束条件是线性函数可行域为直线段围成的凸多边形目标函数的等值线为直线最优解一定在凸多边形的某个顶点取得。优化建模求解LP的基本思想思路：从可行域的某一顶点开始，只需在有限多个顶点中一个一个找下去，一定能得到最优解。LP的约束和目标函数均为线性函数2维可行域线段组成的凸多边形目标函数等值线为直线最优解凸多边形的某个顶点n维超平面组成的凸多面体等值线是超平面凸多面体的某个顶点LP的通常解法是单纯形法(G.B.Dantzig,1947)优化建模线性规划模型的解的几种情况线性规划问题有可行解(Feasible)无可行解（Infeasible）有最优解（Optimal）无最优解(Unbounded)优化建模),(max21,21xxzxx目标98x1+277x2－x12－0.3x1x2－2x22约束x1+x2≤100x1≤2x2x1,x2≥0二次规划模型(QP)若还要求变量为整数，则是整数二次规划模型(IQP)二次规划模型(QP)-例1.2优化建模2,1,6,...,1,..])()[(min612121612/122jecidctsbyaxcjijiiijjjiijijij决策变量：cij，(xj,yj)~16维非线性规划模型(NLP)非线性规划模型(NLP)－例1.3：优化建模整数规划问题一般形式ljxgmixhtsxfjiZxn,...,1,0)(,...,1,0)(..)(min•整数线性规划(ILP)目标和约束均为线性函数•整数非线性规划(NLP)目标或约束中存在非线性函数整数规划问题的分类•纯(全)整数规划(PIP)决策变量均为整数•混合整数规划(MIP)决策变量有整数，也有实数•0-1规划决策变量只取0或1优化建模取消整数规划中决策变量为整数的限制（松弛），对应的连续优化问题称为原问题的松弛问题整数规划问题对应的松弛问题松弛问题松弛整数规划问题最优解最优解整数非整数整数舍入非最优解优化建模基本思想：隐式地枚举一切可行解（“分而治之”）所谓分枝，就是逐次对解空间（可行域）进行划分；而所谓定界，是指对于每个分枝（或称子域），要计算原问题的最优解的下界（对极小化问题）.这些下界用来在求解过程中判定是否需要对目前的分枝进一步划分，也就是尽可能去掉一些明显的非最优点，避免完全枚举.分枝定界法（B&B:BranchandBound）整数线性规划的分枝定界算法优化建模无约束优化更多的优化问题线性规划非线性规划网络优化组合优化整数规划不确定规划多目标规划目标规划动态规划连续优化离散优化从其他角度分类•应用广泛：生产和运作管理、经济与金融、图论和网络优化、目标规划问题、对策论、排队论、存储论，以及更加综合、更加复杂的决策问题等•实际问题规模往往较大，用软件求解比较方便优化建模3.LINDO/LINGO软件简介优化建模常用优化软件1.LINDO/LINGO软件2.MATLAB优化工具箱/Mathematic的优化功能3.SAS(统计分析)软件的优化功能4.EXCEL软件的优化功能5.其他（如CPLEX等）优化建模MATLAB优化工具箱能求解的优化模型优化工具箱3.0(MATLAB7.0R14)连续优化离散优化无约束优化非线性极小fminunc非光滑(不可微)优化fminsearch非线性方程(组)fzerofsolve全局优化暂缺非线性最小二乘lsqnonlinlsqcurvefit线性规划linprog纯0-1规划bintprog一般IP(暂缺)非线性规划fminconfminimaxfgoalattainfseminf上下界约束fminbndfminconlsqnonlinlsqcurvefit约束线性最小二乘lsqnonneglsqlin约束优化二次规划quadprog优化建模LINDO公司软件产品简要介绍美国芝加哥(Chicago)大学的LinusSchrage教授于1980年前后开发,后来成立LINDO系统公司（LINDOSystemsInc.），网址：(V6.1)LINDOAPI:LINDOApplicationProgrammingInterface(V4.1)LINGO:LinearINteractiveGeneralOptimizer(V10.0)What’sBest!:(SpreadSheete.g.EXCEL)(V8.0)演示(试用)版、高级版、超级版、工业版、扩展版…（求解问题规模和选件不同）优化建模•LINGO除了能用于求解线性规划和二次规划外，还可以用于非线性规划求解以及一些线性和非线性方程（组）的求解等。LINGO软件的最大特色在于它允许优化模型中的决策变量为整数，而且执行速度快。LINGO内置了一种建立最优化模型的语言，可以简便地表达大规模问题，利用LINGO高效的求解器可快速求解并分析结果。•LINGO可以求解:线性规划、二次规划、非线性规划、整数规划、图论及网络优化和排队论模型中的最优化问题等。优化建模LINDO/LINGO软件能求解的模型优化线性规划非线性规划二次规划连续优化整数规划LINDOLINGO优化建模建模时需要注意的几个基本问题1、尽量使用实数优化，减少整数约束和整数变量2、尽量使用光滑优化，减少非光滑约束的个数如：尽量少使用绝对值、符号函数、多个变量求最大/最小值、四舍五入、取整函数等3、尽量使用线性模型，减少非线性约束和非线性变量的个数（如x/y5改为x5y）4、合理设定变量上下界，尽可能给出变量初始值5、模型中使用的参数数量级要适当(如小于103)优化建模需要掌握的几个重要方面LINGO：正确阅读求解报告；掌握集合(SETS)的应用；正确理解求解状态窗口；学会设置基本的求解选项(OPTIONS)；掌握与外部文件的基本接口方法优化建模§1.2了解LINGO的菜单新建打开保存打印剪切复制粘贴取消重做查找定位匹配括号求解显示答案模型图示选项设置窗口后置关闭所有窗口平铺窗口在线帮助上下文相关帮助文件菜单编辑菜单LINGO菜单窗口菜单帮助菜单优化建模[变量][约束][非零系数][内存使用量][已运行时间][求解器状态][扩展求解器状态]优化建模例1加工奶制品的生产计划1桶牛奶3kgA112h8h4kgA2或获利24元/kg获利16元/kg50桶牛奶时间480h至多加工100kgA1制订生产计划，使每天获利最大•35元可买到1桶牛奶，买吗？若买，每天最多买多少?•可聘用临时工人，付出的工资最多是每小时几元?•A1的获利增加到30元/kg，应否改变生产计划？每天：问题优化建模1桶牛奶3kgA112h8h4kgA2或获利24元/kg获利16元/kgx1桶牛奶生产A1x2桶牛奶生产A2获利24×3x1获利16×4x2原料供应5021xx劳动时间48081221xx加工能力10031x决策变量目标函数216472maxxxz每天获利约束条件非负约束0,21xx线性规划模型(LP)时间480h至多加工100kgA150桶牛奶每天基本模型优化建模模型求解软件实现LINGOmodel:max=72*x1+64*x2;[milk]x1+x250;[time]12*x1+8*x2480;[cpct]3*x1100;endGlobaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.000000MILK0.00000048.00000TIME0.0000002.000000CPCT40.000000.00000020桶牛奶生产A1,30桶生产A2，利润3360元.优化建模LINGO的语法规定：•（1）求目标函数的最大值或最小值分别用MAX=…或MIN=…来表示；•（2）每个语句必须以分号“；”结束，每行可以有许多语句，语句可以跨行；•（3）变量名称必须以字母(A~Z)开头，由字母、数字(0~9)和下划线所组成，长度不超过32个字符，不区分大小写；•（4）可以给语句加上标号，例如[OBJ]MAX=200*X1+300*X2；优化建模LINGO的语法规定：•（5）以惊叹号“！”开头，以分号“；”结束的语句是注释语句;•（6）如果对变量的取值范围没有作特殊说明，则默认所有决策变量都非负；•（7）乘号“*”必须输入，不能省略。•（8）LINGO模型以语句“MODEL：”开头，以“END”结束，对于比较简单的模型，这两个语句可以省略。优化建模模型求解软件实现LINGOmodel:max=72*x1+64*x2;[milk]x1+x250;[time]12*x1+8*x2480;[cpct]3*x1100;endGlobaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDu