线性、整数规划模型

优化建模与计算 许顺维 参考书 优化建模与LINDO LINGO软件 谢金星 薛毅编著 清华大学出版社 2005年7月第1版 内容提要 1 优化模型的基本概念2 优化问题的建模实例3 LINDO LINGO软件简介 1 优化模型的基本概念 最优化是工程技术 经济管理 科学研究 社会生活中经常遇到的问题 如 优化模型和算法的重要意义 结构设计 资源分配 生产计划 运输方案 解决优化问题的手段 经验积累 主观判断 作试验 比优劣 建立数学模型 求解最优策略 最优化 在一定条件下 寻求使目标最大 小 的决策 优化问题三要素 决策变量 目标函数 约束条件 优化问题的一般形式 无约束优化 没有约束 与约束优化 有约束 可行解 只满足约束 与最优解 取到最优值 局部最优解与整体最优解 局部最优解 LocalOptimalSolution 如x1 整体最优解 GlobalOptimalSolution 如x2 优化模型的简单分类 线性规划 LP 目标和约束均为线性函数非线性规划 NLP 目标或约束中存在非线性函数二次规划 QP 目标为二次函数 约束为线性整数规划 IP 决策变量 全部或部分 为整数整数线性规划 ILP 整数非线性规划 INLP 纯整数规划 PIP 混合整数规划 MIP 一般整数规划 0 1 整数 规划 连续优化 离散优化 数学规划 优化模型的简单分类和求解难度 优化 线性规划 非线性规划 二次规划 连续优化 整数规划 问题求解的难度增加 2 优化模型实例 目标函数 约束条件 例2 1线性规划模型 LP 模型求解 图解法 约束条件 目标函数 z c 常数 等值线 在B 20 30 点得到最优解 目标函数和约束条件是线性函数 可行域为直线段围成的凸多边形 目标函数的等值线为直线 最优解一定在凸多边形的某个顶点取得 求解LP的基本思想 思路 从可行域的某一顶点开始 只需在有限多个顶点中一个一个找下去 一定能得到最优解 LP的约束和目标函数均为线性函数 2维 可行域线段组成的凸多边形 目标函数等值线为直线 最优解凸多边形的某个顶点 n维 超平面组成的凸多面体 等值线是超平面 凸多面体的某个顶点 LP的通常解法是单纯形法 G B Dantzig 1947 线性规划模型的解的几种情况 目标 98x1 277x2 x12 0 3x1x2 2x22 约束 x1 x2 100 x1 2x2x1 x2 0 二次规划模型 QP 若还要求变量为整数 则是整数二次规划模型 IQP 二次规划模型 QP 例1 2 决策变量 cij 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等 MATLAB优化工具箱能求解的优化模型 优化工具箱3 0 MATLAB7 0R14 连续优化 离散优化 无约束优化 非线性极小fminunc 非光滑 不可微 优化fminsearch 非线性方程 组 fzerofsolve 全局优化暂缺 非线性最小二乘lsqnonlinlsqcurvefit 线性规划linprog 纯0 1规划bintprog一般IP 暂缺 非线性规划fminconfminimaxfgoalattainfseminf 上下界约束fminbndfminconlsqnonlinlsqcurvefit 约束线性最小二乘lsqnonneglsqlin 约束优化 二次规划quadprog LINDO公司软件产品简要介绍 美国芝加哥 Chicago 大学的LinusSchrage教授于1980年前后开发 后来成立LINDO系统公司 LINDOSystemsInc 网址 LINDO LinearINteractiveandDiscreteOptimizer V6 1 LINDOAPI LINDOApplicationProgrammingInterface V4 1 LINGO LinearINteractiveGeneralOptimizer V10 0 What sBest SpreadSheete g EXCEL V8 0 演示 试用 版 高级版 超级版 工业版 扩展版 求解问题规模和选件不同 LINGO除了能用于求解线性规划和二次规划外 还可以用于非线性规划求解以及一些线性和非线性方程 组 的求解等 LINGO软件的最大特色在于它允许优化模型中的决策变量为整数 而且执行速度快 LINGO内置了一种建立最优化模型的语言 可以简便地表达大规模问题 利用LINGO高效的求解器可快速求解并分析结果 LINGO可以求解 线性规划 二次规划 非线性规划 整数规划 图论及网络优化和排队论模型中的最优化问题等 LINDO LINGO软件能求解的模型 优化 线性规划 非线性规划 二次规划 连续优化 整数规划 LINDO LINGO 建模时需要注意的几个基本问题 1 尽量使用实数优化 减少整数约束和整数变量2 尽量使用光滑优化 减少非光滑约束的个数如 尽量少使用绝对值 符号函数 多个变量求最大 最小值 四舍五入 取整函数等3 尽量使用线性模型 减少非线性约束和非线性变量的个数 如x y 5改为x 5y 4 合理设定变量上下界 尽可能给出变量初始值5 模型中使用的参数数量级要适当 如小于103 需要掌握的几个重要方面 LINGO 正确阅读求解报告 掌握集合 SETS 的应用 正确理解求解状态窗口 学会设置基本的求解选项 OPTIONS 掌握与外部文件的基本接口方法 1 2了解LINGO的菜单 新建 打开 保存 打印 剪切 复制 粘贴 取消 重做 查找 定位 匹配括号 求解 显示答案 模型图示 选项设置 窗口后置 关闭所有窗口 平铺窗口 在线帮助 上下文相关帮助 文件菜单 编辑菜单 LINGO菜单 窗口菜单 帮助菜单 变量 约束 非零系数 内存使用量 已运行时间 求解器状态 扩展求解器状态 例1加工奶制品的生产计划 50桶牛奶 时间480h 至多加工100kgA1 制订生产计划 使每天获利最大 35元可买到1桶牛奶 买吗 若买 每天最多买多少 可聘用临时工人 付出的工资最多是每小时几元 A1的获利增加到30元 kg 应否改变生产计划 每天 问题 x1桶牛奶生产A1 x2桶牛奶生产A2 获利24 3x1 获利16 4x2 原料供应 劳动时间 加工能力 决策变量 目标函数 每天获利 约束条件 非负约束 线性规划模型 LP 时间480h 至多加工100kgA1 基本模型 模型求解 软件实现 LINGO model max 72 x1 64 x2 milk x1 x2 50 time 12 x1 8 x2 480 cpct 3 x1 100 end Globaloptimalsolutionfound Objectivevalue 3360 000Totalsolveriterations 2VariableValueReducedCostX120 000000 000000X230 000000 000000RowSlackorSurplusDualPrice13360 0001 000000MILK0 00000048 00000TIME0 0000002 000000CPCT40 000000 000000 20桶牛奶生产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 结束 对于比较简单的模型 这两个语句可以省略 模型求解 软件实现 LINGO model max 72 x1 64 x2 milk x1 x2 50 time 12 x1 8 x2 480 cpct 3 x1 100 end Globaloptimalsolutionfound Objectivevalue 3360 000Totalsolveriterations 2VariableValueReducedCostX120 000000 000000X230 000000 000000RowSlackorSurplusDualPrice13360 0001 000000MILK0 00000048 00000TIME0 0000002 000000CPCT40 000000 000000 20桶牛奶生产A1 30桶生产A2 利润3360元 模型求解 reducedcost值表示当该非基变量增加一个单位时 其他非基变量保持不变 目标函数减少的量 对max型问题 OBJECTIVEFUNCTIONVALUE1 3360 000VARIABLEVALUEREDUCEDCOSTX120 0000000 000000X230 0000000 000000ROWSLACKORSURPLUSDUALPRICES2 0 00000048 0000003 0 0000002 0000004 40 0000000 000000NO ITERATIONS 2 也可理解为 为了使该非基变量变成基变量 目标函数中对应系数应增加的量 结果解释 Globaloptimalsolutionfound Objectivevalue 3360 000Totalsolveriterations 2VariableValueReducedCostX120 000000 000000X230 000000 000000RowSlackorSurplusDualPrice13360 0001 000000MILK0 00000048 00000TIME0 0000002 000000CPCT40 000000 000000 model max 72 x1 64 x2 milk x1 x2 50 time 12 x1 8 x2 480 cpct 3 x1 100 end 三种资源 资源 剩余为零的约束为紧约束 有效约束 结果解释 Globaloptimalsolutionfound Objectivevalue 3360 000Totalsolveriterations 2VariableValueReducedCostX120 000000 000000X230 000000 000000RowSlackorSurplusDualPrice13360 0001 000000MILK0 00000048 00000TIME0 0000002 000000CPCT40 000000 000000 最优解下 资源 增加1单位时 效益 的增量 影子价格 35元可买到1桶牛奶 要买吗 35 48 应该买 聘用临时工人付出的工资最多每小时几元 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 时间最多增加53 35元可买到1桶牛奶 每天最多买多少 最多买10桶 目标函数不变 充分条件 奶制品的生产与销售 由于产品利润 加工时间等均为常数 可建立线性规划模型 线性规划模型的三要素 决策变量 目标函数 约束条件 用LINGO求解 输出丰富 利用影子价格和灵敏性分析可对结果做进一步研究 建模时尽可能利用原始的数据信息 把尽量多的计算留给计算机去做 主要内容 整数规划方法 43 2020年4月5日 整数规划的一般模型 整数规划解的求解方法 整数规划的软件求解方法 0 1规划的模型与求解方法 整数规划的应用案例分析 如果生产某一类型汽车 则至少要生产80辆 那么最优的生产计划应作何改变 汽车厂生产三种类型的汽车 已知各类型每辆车对钢材 劳动时间的需求 利润及工厂每月的现有量 制订月生产计划 使工厂的利润最大 引例汽车生产计划 设每月生产小 中 大型汽车的数量分别为x1 x2 x3 汽车厂生产计划 模型建立 线性规划模型 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结果输出 IP模型LINGO求解 Model max 2 x1 3 x2 4 x3 1 5 x1 3 x2 5 x3 600 280 x1 250 x2 400 x3 60000 gin x1 gin x2 gin x3 end 其中3个子模型应去掉 然后逐一求解 比较目标函数值 再加上整数约束 得最优解 方法1 分解为8个LP子模型 汽车厂生产计划 若生产某类汽车 则至少生产80辆 求生产计划 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为大的正数 本例可取1000 ObjectiveValue 610 0000VariableValueReducedCostX180 000000 2 000000X2150 000000 3 000000X30 000000 4 000000Y11 0000000 000000Y21 0000000 000000Y30 0000000 000000 若生产某类汽车 则至少生产80辆 求生产计划 x1 0或 80 最优解同前 IP模型LINGO求解 Model max 2 x1 3 x2 4 x3 1 5 x1 3 x2 5 x380 y1 取M 1000 x280 y2 x280 y2 gin x1 gin x2 gin x3 整数约束 bin y1 bin y2 bin y3 0 1变量end max 2 x1 3 x2 4 x3 1 5 x1 3 x2 5 x30 x2 x2 80 0 x3 x3 80 0 gin x1 gin x2 gin x3 方法3 化为非线性规划 非线性规划 Non LinearProgramming 简记NLP 若生产某类汽车 则至少生产80辆 求生产计划 x1 0或 80 最优解同前 一般地 整数规划和非线性规划的求解比线性规划困难得多 特别是问题规模较大或者要求得到全局最优解时 53 2020年4月5日 2 整数规划模型的一般形式 一 整数规划的一般模型 问题是如何求解整数规划问题呢 能否设想先略去决策变量整数约束 即变为线性规划问题求解 再对其最优解进行取整处理呢 实际上 可借鉴这种思想来解决整数规划问题 整数规划模型示例 54 2020年4月5日 固定资源分配问题 问题分析与准备 固定资源分配问题 目标 总利润 各车间 各资源利润 资源分配量 决策变量 56 2020年4月5日 固定资源分配问题 3 整数规划的LINGO解法 二 整数规划的求解方法 57 2020年4月5日 58 2020年4月5日 1 0 1整数规划的模型 三 0 1整数规划 59 2020年4月5日 2 指派 或分配 问题 三 0 1整数规划 在生产管理上 总希望把人员最佳分派 以发挥其最大工作效率 创造最大的价值 例如 某部门有n项任务 正好需要n个人去完成 由于任务的性质和各人的专长不同 如果分配每个人仅能完成一项任务 如何分派使完成n项任务的总效益为最高 效益量化 这是典型的分配问题 2 指派 或分配 问题 60 2020年4月5日 现在不妨设有4个人 各有能力去完成4项科研任务中的任一项 由于4个人的能力和经验不同 所需完成各项任务的时间如右表 问如何分配何人去完成何项目使完成4项任务所需总时间最少 61 2020年4月5日 2 指派 或分配 问题 62 2020年4月5日 2 指派 或分配 问题 63 2020年4月5日 2 指派 或分配 问题 64 2020年4月5日 2 指派 或分配 问题 指派问题的一般模型 65 2020年4月5日 2 指派 或分配 问题 指派问题的一般模型 66 2020年4月5日 匈牙利算法的基本思想 因为每个指派问题都有一个相应的效益矩阵 通过初等变换修改效益矩阵的行或列 使得在每一行或列中至少有一个零元素 直到在不同行不同列中都至少有一个零元素为止 从而得到与这些零元素相对应的一个完全分配方案 这个方案对原问题而言是一个最优的分配方案 3 指派问题的匈牙利算法 67 2020年4月5日 用LINGO求解0 1规划模型 4 0 1规划的LINGO解法 如何选拔队员组成4 100m混合泳接力队 例1混合泳接力队的选拔 5名候选人的百米成绩 穷举法 组成接力队的方案共有5 120种 讨论 丁的蛙泳成绩退步到 戊的自由泳成绩进步到 组成接力队的方案是否应该调整 目标函数 若选择队员i参加泳姿j的比赛 记xij 1 否则记xij 0 0 1规划模型 cij s 队员i第j种泳姿的百米成绩 约束条件 每人最多入选泳姿之一 每种泳姿有且只有1人 模型求解 MODEL sets person 1 5 position 1 4 link person position c x endsetsdata c 66 8 75 6 87 58 6 57 2 66 66 4 53 78 67 8 84 6 59 4 70 74 2 69 6 57 2 67 4 71 83 8 62 4 enddata 输入LINGO求解 min sum link c x for person i sum position j x i j 1 for position i sum person j x j i 1 for link bin x END 模型求解 最优解 x14 x21 x32 x43 1 其他变量为0 输入LINGO求解 甲 自由泳 乙 蝶泳 丙 仰泳 丁 蛙泳 成绩为253 2 s 丁蛙泳c43 69 6 75 2 s 戊自由泳c54 62 4 57 5 s 方案是否调整 敏感性分析 新方案 乙 蝶泳 丙 仰泳 丁 蛙泳 戊 自由泳 IP一般没有与LP相类似的理论 LINGO输出的敏感性分析结果通常是没有意义的 c43 c54的新数据重新输入模型 用LINGO求解 原分配方案 甲 自由泳 乙 蝶泳 丙 仰泳 丁 蛙泳 讨论 最优解 x21 x32 x43 x51 1 成绩为 混合泳接力队的选拔 指派 Assignment 问题 有若干项任务 每项任务必有且只能有一人承担 每人只能承担一项 不同人员承担不同任务的效益 或成本 不同 怎样分派各项任务使总效益最大 或总成本最小 人员数量与任务数量相等 人员数量大于任务数量 本例 人员数量小于任务数量 建立0 1规划模型是常用方法 为了选修课程门数最少 应学习哪些