线性、整数规划模型

线性、整数规划模型线性、整数规划模型 优优 化化 建建 模模参考书参考书优化建模与优化建模与LINDO/LINGO软件软件谢金星谢金星,薛毅编著薛毅编著,清华大学出版社清华大学出版社,2005年年7月第月第1版版.http:/ 优优 化化 建建 模模内容提要内容提要1.优化模型的基本概念优化模型的基本概念2.优化问题的建模实例优化问题的建模实例3.LINDO/LINGO软件简介软件简介 优优 化化 建建 模模1.优化模型的基本概念优化模型的基本概念 优优 化化 建建 模模最优化是工程技术、经济管理、科学研究、社最优化是工程技术、经济管理、科学研究、社会生活中经常遇到的问题会生活中经常遇到的问题,如如:优化模型和算法的重要意义优化模型和算法的重要意义结构设计结构设计资源分配资源分配生产计划生产计划运输方案运输方案解决优化问题的手段解决优化问题的手段经验积累，主观判断经验积累，主观判断作试验，比优劣作试验，比优劣建立数学模型，求解最优策略建立数学模型，求解最优策略最优化最优化:在一定条件下，寻求使目标最大在一定条件下，寻求使目标最大(小小)的决策的决策 优优 化化 建建 模模优化问题三要素：优化问题三要素：决策变量决策变量；目标函数目标函数；约束条件约束条件约约束束条条件件决策变量决策变量优化问题的一般形式优化问题的一般形式无约束优化无约束优化(没有约束没有约束)与约束优化与约束优化(有约束有约束)可行解（只满足约束）与最优解可行解（只满足约束）与最优解(取到最优值取到最优值)目标函数目标函数 优优 化化 建建 模模局部最优解与整体最优解局部最优解与整体最优解局部最优解局部最优解(LocalOptimalSolution,如如x1)整体最优解整体最优解(GlobalOptimalSolution,如如x2)x*f(x)x1x2o 优优 化化 建建 模模优化模型的优化模型的简单分类简单分类线性规划线性规划(LP)目标和约束均为线性函数目标和约束均为线性函数非线性规划非线性规划(NLP)目标或约束中存在非线性函数目标或约束中存在非线性函数二次规划二次规划(QP)目标为二次函数、约束为线性目标为二次函数、约束为线性整数规划整数规划(IP)决策变量决策变量(全部或部分全部或部分)为整数为整数整数整数线性线性规划规划(ILP)，整数，整数非线性非线性规划规划(INLP)纯整数规划纯整数规划(PIP),混合整数规划混合整数规划(MIP)一般整数规划，一般整数规划，0-1（整数）规划（整数）规划连连续续优优化化离离散散优优化化数学规划数学规划 优优 化化 建建 模模优化模型的简单分类和求解难度优化模型的简单分类和求解难度 优化线性规划非线性规划二次规划连续优化整数规划 问题求解的难度增加 优优 化化 建建 模模2.优化模型实例优化模型实例目标函数目标函数约束条件约束条件例例2.1线性规划模型线性规划模型(LP)优优 化化 建建 模模模型求解模型求解 图解法图解法 x1x20ABCDl1l2l3l4l5约约束束条条件件目标目标函数函数 Z=0Z=2400Z=3600z=c(常数常数)等值线等值线c在在B(20,30)点得到最优解点得到最优解目标函数和约束条件是线性函数目标函数和约束条件是线性函数可行域为直线段围成的凸多边形可行域为直线段围成的凸多边形目标函数的等值线为直线目标函数的等值线为直线最优解一定在凸多边最优解一定在凸多边形的某个顶点取得。形的某个顶点取得。优优 化化 建建 模模求解求解LP的基本思想的基本思想思路：从可行域的某一顶点开始，只需在有限多个思路：从可行域的某一顶点开始，只需在有限多个顶点中一个一个找下去，一定能得到顶点中一个一个找下去，一定能得到最优解最优解。LP的约束和目标函数均为线性函数的约束和目标函数均为线性函数2维维可行域可行域线段组成的凸多边形线段组成的凸多边形目标函数目标函数等值线为直线等值线为直线最优解最优解凸多边形的某个顶点凸多边形的某个顶点n维维超平面组成的凸多面体超平面组成的凸多面体等值线是超平面等值线是超平面凸多面体的某个顶点凸多面体的某个顶点LPLP的通常解法是单纯形法的通常解法是单纯形法(G.B.Dantzig,1947)(G.B.Dantzig,1947)优优 化化 建建 模模线性规划模型的解的几种情况线性规划模型的解的几种情况 线性规划问题线性规划问题有可行解有可行解(Feasible)无无可可行行解解（Infeasible）有有最最优优解解（Optimal）无无最最优优解解(Unbounded)优优 化化 建建 模模目标目标98 x1+277 x2x120.3 x1 x22x22约束约束x1+x2100 x12 x2x1,x20二次规划模型二次规划模型(QP)若还要求若还要求变量为整数，则是整数二次规划模型变量为整数，则是整数二次规划模型(IQP)二次规划模型二次规划模型(QP)-例例1.21.2 优优 化化 建建 模模决策变量：决策变量：ci j，(xj,yj)16维维非线性规划模型非线性规划模型(NLP)非线性规划模型非线性规划模型(NLP)例例1.3：优优 化化 建建 模模整数规划问题整数规划问题一般形式一般形式整数线性规划整数线性规划(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等）等）优优 化化 建建 模模MATLABMATLAB优化工具箱优化工具箱能求解的优化模型能求解的优化模型优化工具箱优化工具箱3.0(MATLAB7.0R14)连续优化连续优化离散优化离散优化无约束优化无约束优化非线性非线性极小极小fminunc非光滑非光滑(不可不可微微)优化优化fminsearch非线性非线性方方程程(组组)fzerofsolve全局全局优化优化暂缺暂缺非线性非线性最小二乘最小二乘lsqnonlinlsqcurvefit线性规划线性规划linprog纯纯0-1规划规划bintprog一般一般IP(暂缺暂缺)非线性规划非线性规划fminconfminimaxfgoalattainfseminf上下界约束上下界约束fminbndfminconlsqnonlinlsqcurvefit约束线性约束线性最小二乘最小二乘lsqnonneglsqlin约束优化约束优化二次规划二次规划quadprog 优优 化化 建建 模模LINDO LINDO 公司软件产品简要介绍公司软件产品简要介绍美国芝加哥美国芝加哥(Chicago)大学的大学的LinusSchrage教授于教授于1980年前后开发年前后开发,后来成立后来成立LINDO系统公司（系统公司（LINDOSystemsInc.），），网址：网址：http:/LINDO:LinearINteractiveandDiscreteOptimizer(V6.1)LINDOAPI:LINDOApplicationProgrammingInterface(V4.1)LINGO:LinearINteractiveGeneralOptimizer(V10.0)WhatsBest!:(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桶桶牛奶牛奶 3kgA1 12h 8h 4kgA2 或或获利获利24元元/kg获利获利16元元/kg50桶牛奶桶牛奶时间时间480h至多加工至多加工100kgA1制订生产计划，使每天获利最大制订生产计划，使每天获利最大 35元可买到元可买到1桶牛奶，买吗？若买，每天最多买多少桶牛奶，买吗？若买，每天最多买多少?可聘用临时工人，付出的工资最多是每小时几元可聘用临时工人，付出的工资最多是每小时几元?A1的获利增加到的获利增加到30元元/kg，应否改变生产计划？，应否改变生产计划？每天：每天：问问题题 优优 化化 建建 模模1桶桶牛奶牛奶3kgA112h8h4kgA2或或获利获利24元元/kg获利获利16元元/kgx1桶牛奶生产桶牛奶生产A1x2桶牛奶生产桶牛奶生产A2获利获利243x1获利获利164 x2原料供应原料供应 劳动时间劳动时间 加工能力加工能力 决策变量决策变量 目标函数目标函数 每天获利每天获利约束条件约束条件非负约束非负约束 线性线性规划规划模型模型(LP)时间时间480h至多加工至多加工100kgA150桶牛奶桶牛奶每天每天基本基本模型模型 优优 化化 建建 模模模型求解模型求解 软件实现软件实现 LINGOmodel:max=72*x1+64*x2;milkx1+x250;time12*x1+8*x2480;cpct3*x1100;end Globaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2VariableValueReducedCost X120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.000000MILK0.00000048.00000TIME0.0000002.000000CPCT40.000000.000000 20桶牛奶生产桶牛奶生产A1,30桶生产桶生产A2，利润，利润3360元元.优优 化化 建建 模模LINGO的语法规定：的语法规定：（1）求目标函数的最大值或最小值分别用）求目标函数的最大值或最小值分别用MAX=或或MIN=来表示；来表示；（2）每个语句必须以分号）每个语句必须以分号“；”结束，每行结束，每行可以有许多语句，语句可以跨行；可以有许多语句，语句可以跨行；（3）变量名称必须以字母）变量名称必须以字母(AZ)开头，由字母、开头，由字母、数字数字(09)和下划线所组成，长度不超过和下划线所组成，长度不超过32个个字符，不区分大小写；字符，不区分大小写；（4）可以给语句加上标号，例如）可以给语句加上标号，例如OBJMAX=200*X1+300*X2；优优 化化 建建 模模LINGO的语法规定：的语法规定：（5）以惊叹号）以惊叹号“！”开头，以分号开头，以分号“；”结束的语结束的语句是注释语句句是注释语句;（6）如果对变量的取值范围没有作特殊说明，则默）如果对变量的取值范围没有作特殊说明，则默认所有决策变量都非负；认所有决策变量都非负；（7）乘号）乘号“*”必须输入，不能省略。必须输入，不能省略。（8）LINGO模型以语句模型以语句“MODEL：”开头，以开头，以“END”结束，对于比较简单的模型，这两个语句可结束，对于比较简单的模型，这两个语句可以省略。以省略。优优 化化 建建 模模模型求解模型求解 软件实现软件实现 LINGOmodel:max=72*x1+64*x2;milkx1+x250;time12*x1+8*x2480;cpct3*x1100;end Globaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2VariableValueReducedCost X120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.000000MILK0.00000048.00000TIME0.0000002.000000CPCT40.000000.000000 20桶牛奶生产桶牛奶生产A1,30桶生产桶生产A2，利润，利润3360元元.优优 化化 建建 模模结果解释结果解释 Globaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.000000MILK0.00000048.00000TIME0.0000002.000000CPCT40.000000.000000 model:max=72*x1+64*x2;milkx1+x250;time12*x1+8*x2480;cpct3*x1100;end三三种种资资源源“资源资源”剩余为零的约束为紧约束（有效约束）剩余为零的约束为紧约束（有效约束）原料无剩余原料无剩余时间无剩余时间无剩余加工能力剩余加工能力剩余40 优优 化化 建建 模模结果解释结果解释 Globaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.000000MILK0.00000048.00000TIME0.0000002.000000CPCT40.000000.000000最优解下最优解下“资源资源”增加增加1单位时单位时“效益效益”的增的增量量影子价格影子价格35元可买到元可买到1桶牛奶，要买吗桶牛奶，要买吗?3548,应该买！应该买！聘用临时工人付出的工资最多每小时几元聘用临时工人付出的工资最多每小时几元?2元！元！原料增加原料增加1单位单位,利润增长利润增长48时间增加时间增加1单位单位,利润增长利润增长2加工能力增长不影响利润加工能力增长不影响利润 优优 化化 建建 模模该命令产生当前模型的灵敏度分析报告该命令产生当前模型的灵敏度分析报告（需要通过（需要通过Lingo菜单设置激活）菜单设置激活）(1)最优解最优解保持不变的情况下保持不变的情况下,目标函数的系目标函数的系数数变化范围变化范围;(2)在在影子价格影子价格和缩减成本系数都不变的前和缩减成本系数都不变的前提下提下,约束条件右边约束条件右边的常数变化范围的常数变化范围;敏感性分析敏感性分析(“LINGO|Ranges”)注意：灵敏性分析耗费相当多的求解时间，因注意：灵敏性分析耗费相当多的求解时间，因此当速度很关键时此当速度很关键时,就没有必要激活它就没有必要激活它 优优 化化 建建 模模Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX172.0000024.000008.000000X264.000008.00000016.00000RighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecreaseMILK50.0000010.000006.666667TIME480.000053.3333380.00000CPCT100.0000INFINITY40.00000 最优解不变时目标函最优解不变时目标函数系数允许变化范围数系数允许变化范围敏感性分析敏感性分析(“LINGO|Ranges”)x1系数范围系数范围(64,96)x2系数范围系数范围(48,72)A1获利增加到获利增加到30元元/kg，应否改变生产计划，应否改变生产计划?x1系数由系数由24 3=72增加增加为为30 3=90，在在允许范围内允许范围内不变！不变！(约束条件不变约束条件不变)优优 化化 建建 模模结果解释结果解释 Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX172.0000024.000008.000000X264.000008.00000016.00000RighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecreaseMILK50.0000010.000006.666667TIME480.000053.3333380.00000CPCT100.0000INFINITY40.00000影子价格有意义时约束右端的允许变化范围影子价格有意义时约束右端的允许变化范围原料最多增加原料最多增加10时间最多增加时间最多增加5335元可买到元可买到1桶牛奶桶牛奶,每天最多买多少每天最多买多少?最多买最多买10桶桶!(目标函数不变目标函数不变)充分条件充分条件!优优 化化 建建 模模奶制品的生产与销售奶制品的生产与销售 由于产品利润、加工时间等均为常数，可由于产品利润、加工时间等均为常数，可建立建立线性规划线性规划模型模型.线性规划模型的三要素：线性规划模型的三要素：决策变量、目标决策变量、目标函数、约束条件函数、约束条件.用用LINGO求解，输出丰富，利用求解，输出丰富，利用影子价格影子价格和和灵敏性分析灵敏性分析可对结果做进一步研究可对结果做进一步研究.建模时尽可能利用原始的数据信息，把尽量建模时尽可能利用原始的数据信息，把尽量多的计算留给计算机去做多的计算留给计算机去做.优优 化化 建建 模模主要内容整数规划方法432024年5月2日 整数规划的一般模型；整数规划的一般模型；整数规划解的求解方法；整数规划解的求解方法；整数规划的整数规划的软件求解方法；软件求解方法；0-10-1规划的模型与求解方法；规划的模型与求解方法；整数规划的应用案例分析。整数规划的应用案例分析。优优 化化 建建 模模 如果生产某一类型汽车，则至少要生产如果生产某一类型汽车，则至少要生产8080辆，辆，那么最优的生产计划应作何改变？那么最优的生产计划应作何改变？汽车厂生产三种类型的汽车，已知各类型每辆车对汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量钢材、劳动时间的需求，利润及工厂每月的现有量.小型小型中型中型大型大型现有量现有量钢材（钢材（t）1.535600劳动时间（劳动时间（h）28025040060000利润（万元）利润（万元）234制订月生产计划，使工厂的利润最大制订月生产计划，使工厂的利润最大.引例引例 汽车生产计划汽车生产计划 优优 化化 建建 模模设每月生产小、中、大型设每月生产小、中、大型汽车的数量分别为汽车的数量分别为x1,x2,x3汽车厂生产计划汽车厂生产计划 模型建立模型建立 小型小型中型中型大型大型现有量现有量钢材钢材1.535600时间时间28025040060000利润利润234线性规划线性规划模型模型(LP)优优 化化 建建 模模模型求解模型求解 3）模型中）模型中增加条件增加条件：x1,x2,x3均为整数，重新求解均为整数，重新求解.ObjectiveValue:632.2581VariableValueReducedCostX164.5161290.000000X2167.7419280.000000X30.0000000.946237RowSlackorSurplusDualPrice20.0000000.73118330.0000000.003226结果为小数，结果为小数，怎么办？怎么办？1）舍去小数舍去小数：取：取x1=64，x2=167，算出目标函数值，算出目标函数值z=629，与，与LP最优值最优值632.2581相差不大相差不大.2）试试探探：如如取取x1=65，x2=167；x1=64，x2=168等等，计算函数值计算函数值z，通过比较可能得到更优的解，通过比较可能得到更优的解.但但必须检验必须检验它们是否满足约束条件它们是否满足约束条件.为什么？为什么？优优 化化 建建 模模IP可用可用LINGO直接求解直接求解整数规划整数规划(IntegerProgramming,简记简记IP)IP的最优解的最优解x1=64，x2=168，x3=0，最优，最优值值z=632 Globaloptimalsolutionfound.Objectivevalue:632.0000Extendedsolversteps:0Totalsolveriterations:3VariableValueReducedCostX164.00000-2.000000X2168.0000-3.000000X30.000000-4.000000模型求解模型求解 IP结果输出结果输出 优优 化化 建建 模模其中其中3个个子模型应子模型应去掉，然后去掉，然后逐一求解，比较目标函数值，逐一求解，比较目标函数值，再加上整数约束，得最优解：再加上整数约束，得最优解：方法方法1：分解为：分解为8个个LP子模型子模型汽车厂生产计划汽车厂生产计划 若生产某类汽车，则至少生产若生产某类汽车，则至少生产8080辆，求生产计划辆，求生产计划.x1,x2,x3=0或或 80 x1=80，x2=150，x3=0，最优值，最优值z=610 优优 化化 建建 模模LINGO中中对对0-1变变量的限定：量的限定：bin(y1);bin(y2);bin(y3);方法方法2：引入引入0-1变量，化为整数规划变量，化为整数规划M为大的正数为大的正数,本例可取本例可取1000ObjectiveValue:610.0000VariableValueReducedCostX180.000000-2.000000X2150.000000-3.000000X30.000000-4.000000Y11.0000000.000000Y21.0000000.000000Y30.0000000.000000 若生产某类汽车，则至少生产若生产某类汽车，则至少生产8080辆，求生产计划辆，求生产计划.x1=0 或 80 x2=0 或 80 x3=0 或 80最优解同最优解同前前 优优 化化 建建 模模max=2*x1+3*x2+4*x3;1.5*x1+3*x2+5*x3600;280*x1+250*x2+400*x30;x2*(x2-80)0;x3*(x3-80)0;gin(x1);gin(x2);gin(x3);方法方法3：化为非线性规划化为非线性规划非线性规划非线性规划（Non-LinearProgramming，简记简记NLP）若生产某类汽车，则至少生产若生产某类汽车，则至少生产8080辆，求生产计划辆，求生产计划.x1=0或或 80 x2=0或或 80 x3=0或或 80最优解同前最优解同前.一般地，整数规划和非一般地，整数规划和非线性规划的求解比线性线性规划的求解比线性规划困难得多，特别是规划困难得多，特别是问题规模较大或者要求问题规模较大或者要求得到全局最优解时得到全局最优解时.优优 化化 建建 模模532024年5月2日2.整数规划模型的一般形式整数规划模型的一般形式一、整数规划的一般模型一、整数规划的一般模型问题是如何求解整数规划问题呢？问题是如何求解整数规划问题呢？能否设想先略去决策变量整数约束，即变为线性能否设想先略去决策变量整数约束，即变为线性规划问题求解，再对其最优解进行取整处理呢？规划问题求解，再对其最优解进行取整处理呢？实际上，可借鉴这种思想来解决整数规划问题实际上，可借鉴这种思想来解决整数规划问题 优优 化化 建建 模模582024年5月2日1、0-1整数规划的模型整数规划的模型三、三、0-1 整整 数数 规规 划划 优优 化化 建建 模模592024年5月2日2、指派（或分配）问题、指派（或分配）问题三、三、0-1 整整 数数 规规 划划 在生产管理上，总希望把人员最佳分派，在生产管理上，总希望把人员最佳分派，以发挥其最大工作效率，创造最大的价值。以发挥其最大工作效率，创造最大的价值。例如：某部门有例如：某部门有n项任务，正好需要项任务，正好需要n个个人去完成，由于任务的性质和各人的专长不人去完成，由于任务的性质和各人的专长不同，如果分配每个人仅能完成一项任务。同，如果分配每个人仅能完成一项任务。如何分派使完成如何分派使完成n项任务的总效益为最项任务的总效益为最高（效益量化），这是典型的分配问题。高（效益量化），这是典型的分配问题。优优 化化 建建 模模2.2.指派（或分配）问题指派（或分配）问题指派（或分配）问题指派（或分配）问题602024年5月2日 现在不妨设有现在不妨设有4 4个人，各有能力去完成个人，各有能力去完成4 4项科项科研任务中的任一项，由于研任务中的任一项，由于4 4个人的能力和经验不同，个人的能力和经验不同，所需完成各项任务的时间如右表：所需完成各项任务的时间如右表：问如何分配何问如何分配何人去完成何项人去完成何项目使完成目使完成4 4项项任务所需总时任务所需总时间最少？间最少？优优 化化 建建 模模612024年5月2日2.2.指派（或分配）问题指派（或分配）问题指派（或分配）问题指派（或分配）问题 优优 化化 建建 模模622024年5月2日2.2.指派（或分配）问题指派（或分配）问题指派（或分配）问题指派（或分配）问题 优优 化化 建建 模模632024年5月2日2.2.指派（或分配）问题指派（或分配）问题指派（或分配）问题指派（或分配）问题 优优 化化 建建 模模642024年5月2日2.2.指派（或分配）问题指派（或分配）问题指派（或分配）问题指派（或分配）问题指派问题的一般模型：指派问题的一般模型：优优 化化 建建 模模652024年5月2日2.2.指派（或分配）问题指派（或分配）问题指派（或分配）问题指派（或分配）问题指派问题的一般模型：指派问题的一般模型：优优 化化 建建 模模为了选修课程门数最少，应学习哪些课程为了选修课程门数最少，应学习哪些课程？例例选课策略选课策略要求至少选两门数学课、三门运筹学课和两门计算机课要求至少选两门数学课、三门运筹学课和两门计算机课 课号课号课名课名学分学分所属类别所属类别先修课要求先修课要求1微积分微积分5数学数学2线性代数线性代数4数学数学3最优化方法最优化方法4数学；运筹学数学；运筹学微积分；线性代数微积分；线性代数4数据结构数据结构3数学；计算机数学；计算机计算机编程计算机编程5应用统计应用统计4数学；运筹学数学；运筹学微积分；线性代数微积分；线性代数6计算机模拟计算机模拟3计算机；运筹学计算机；运筹学计算机编程计算机编程7计算机编程计算机编程2计算机计算机8预测理论预测理论2运筹学运筹学应用统计应用统计9数学实验数学实验3运筹学；计算机运筹学；计算机微积分；线性代数微积分；线性代数 优优 化化 建建 模模0-1规划模型规划模型 决策变量决策变量 目标函数目标函数 xi=1选修课号选修课号i 的的课程（课程（xi=0不选）不选）选修课程总数最少选修课程总数最少约束条件约束条件最少最少2门数学课，门数学课，3门运筹学课，门运筹学课，2门计算机课门计算机课.课号课号课名课名所属类别所属类别1微积分微积分数学数学2线性代数线性代数数学数学3最优化方法最优化方法数学；运筹学数学；运筹学4数据结构数据结构数学；计算机数学；计算机5应用统计应用统计数学；运筹学数学；运筹学6计算机模拟计算机模拟计算机；运筹学计算机；运筹学7计算机编程计算机编程计算机计算机8预测理论预测理论运筹学运筹学9数学实验数学实验运筹学；计算机运筹学；计算机 优优 化化 建建 模模先修课程要求先修课程要求最优解：最优解：x1=x2=x3=x6=x7=x9=1,其他为其他为0；6门课程，总学分门课程，总学分21.0-1规划模型规划模型 约束条件约束条件x3=1必有必有x1=x2=1模型求解（模型求解（LINGO）课号课号课名课名先修课要求先修课要求1微积分微积分2线性代数线性代数3最优化方法最优化方法微积分；线性代数微积分；线性代数4数据结构数据结构计算机编程计算机编程5应用统计应用统计微积分；线性代数微积分；线性代数6计算机模拟计算机模拟计算机编程计算机编程7计算机编程计算机编程8预测理论预测理论应用统计应用统计9数学实验数学实验微积分；线性代数微积分；线性代数 优优 化化 建建 模模选选课课策策略略用用0-1变量表示策略选择是常用的方法变量表示策略选择是常用的方法“要选甲要选甲(x1)必选乙必选乙(x2)”可用可用x1 x2描述描述.“要选甲要选甲(x1)必不选乙必不选乙(x2)”怎样描述怎样描述?“甲乙二人至多选一人甲乙二人至多选一人”怎样描述怎样描述?“甲乙二人至少选一人甲乙二人至少选一人”怎样描述怎样描述?优优 化化 建建 模模782024年5月2日四、案例分析四、案例分析:兼职值班员问题兼职值班员问题1.问题的提出问题的提出 优优 化化 建建 模模792024年5月2日实验室开放时间为上午实验室开放时间为上午8:008:00至晚上至晚上10:00;10:00;开放时间内须有且仅有一名学生值班开放时间内须有且仅有一名学生值班;规定大学生每周值班不少于规定大学生每周值班不少于8 8小时小时;研究生每周值班不少于研究生每周值班不少于7 7小时小时;每名学生每周值班不超每名学生每周值班不超3 3次次;每次值班不少于每次值班不少于2 2小时小时;每天安排值班的学生不超过每天安排值班的学生不超过3 3人，且其中必须人，且其中必须有一名研究生有一名研究生.试为该实验室安排一张人员的值班表，使试为该实验室安排一张人员的值班表，使总支付的报酬这最少。总支付的报酬这最少。四、案例分析四、案例分析:兼职值班员问题兼职值班员问题1.问题的提出问题的提出 优优 化化 建建 模模802024年5月2日四、案例分析四、案例分析:兼职值班员问题兼职值班员问题问题的分析问题的分析目标目标总报酬总报酬每人报酬每人报酬每人值班时长每人值班时长每人每天值班时长每人每天值班时长值班时刻表值班时刻表 优优 化化 建建 模模812024年5月2日四、案例分析四、案例分析:兼职值班员问题兼职值班员问题2.模型的建立与求解模型的建立与求解 优优 化化 建建 模模822024年5月2日四、案例分析四、案例分析:兼职值班员问题兼职值班员问题目标目标总报酬总报酬每人报酬每人报酬每人值班时长每人值班时长每人每天每人每天值班时长值班时长值班时刻表值班时刻表 优优 化化 建建 模模832024年5月2日四、案例分析四、案例分析:兼职值班员问题兼职值班员问题实验室开放时间为上午实验室开放时间为上午8:008:00至晚上至晚上10:00;10:00;开放时间内须有且仅有一名学生值班开放时间内须有且仅有一名学生值班;优优 化化 建建 模模842024年5月2日四、案例分析四、案例分析:兼职值班员问题兼职值班员问题规定大学生每周值班不少于规定大学生每周值班不少于8小时小时;优优 化化 建建 模模852024年5月2日四、案例分析四、案例分析:兼职值班员问题兼职值班员问题研究生每周值班不少于研究生每周值班不少于7小时小时;优优 化化 建建 模模862024年5月2日四、案例分析四、案例分析:兼职值班员问题兼职值班员问题每名学生每周值班不超每名学生每周值班不超3次次(周末除外周末除外);优优 化化 建建 模模872024年5月2日四、案例分析四、案例分析:兼职值班员问题兼职值班员问题每次值班不少于每次值班不少于2小时小时;不超过每天小时上限不超过每天小时上限;优优 化化 建建 模模882024年5月2日四、案例分析四、案例分析:兼职值班员问题兼职值班员问题每天安排值班的学生不超过每天安排值班的学生不超过3人，人，且必须有一名研究生且必须有一名研究生.优优 化化 建建 模模2 2、模型的建立与求解、模型的建立与求解892024年5月2日问问题题的的数数学学模模型：型：优优 化化 建建 模模902024年5月2日3 3、模型的求解结果、模型的求解结果 优优 化化 建建 模模912024年5月2日3 3、模型的求解结果、模型的求解结果结束语结束语谢谢大家聆听！谢谢大家聆听！92