数学建模中的优化模型ppt课件.ppt

简要提纲 1 优化模型简介2 简单的优化模型3 数学规划模型4 图论 动态规划 选讲 5 建模与求解实例 1 1 优化模型简介 2 优化问题的一般形式 3 无约束优化 最优解的分类和条件 4 约束优化的简单分类 5 优化建模如何创新 方法1 大胆创新 别出心裁 采用有特色的目标函数 约束条件等 你用非线性规划 我用线性规划 你用整数 离散规划 我用连续规划 网络优化 方法2 细致入微 滴水不漏 对目标函数 约束条件处理特别细致 有算法设计和分析 不仅仅是简单套用软件 敏感性分析详细 全面 6 建模时需要注意的几个基本问题 1 尽量使用实数优化 减少整数约束和整数变量2 尽量使用光滑优化 减少非光滑约束的个数如 尽量少使用绝对值 符号函数 多个变量求最大 最小值 四舍五入 取整函数等3 尽量使用线性模型 减少非线性约束和非线性变量的个数 如x y 5改为x 5y 4 合理设定变量上下界 尽可能给出变量初始值5 模型中使用的参数数量级要适当 如小于103 7 常用优化软件 1 LINGO软件2 MATLAB优化工具箱3 EXCEL软件的优化功能4 SAS 统计分析 软件的优化功能5 其他 8 2 简单的优化模型 生猪的出售时机 饲养场每天投入4元资金 用于饲料 人力 设备 估计可使80千克重的生猪体重增加2公斤 问题 市场价格目前为每千克8元 但是预测每天会降低0 1元 问生猪应何时出售 如果估计和预测有误差 对结果有何影响 分析 投入资金使生猪体重随时间增加 出售单价随时间减少 故存在最佳出售时机 使利润最大 9 求t使Q t 最大 10天后出售 可多得利润20元 建模及求解 生猪体重w 80 rt 出售价格p 8 gt 销售收入R pw 资金投入C 4t 利润Q R C pw C 估计r 2 若当前出售 利润为80 8 640 元 t天出售 10 Q 10 660 640 g 0 1 10 敏感性分析 研究r g变化时对模型结果的影响 设g 0 1不变 t对r的 相对 敏感度 生猪每天体重增加量r增加1 出售时间推迟3 11 敏感性分析 研究r g变化时对模型结果的影响 设r 2不变 t对g的 相对 敏感度 生猪价格每天的降低量g增加1 出售时间提前3 12 强健性分析 保留生猪直到利润的增值等于每天的费用时出售 由S t r 3 建议过一周后 t 7 重新估计 再作计算 研究r g不是常数时对模型结果的影响 w 80 rt w w t p 8 gt p p t 若 10 则 30 13 3 数学规划模型 例1汽车厂生产计划例2加工奶制品的生产计划例3运输问题 14 如果生产某一类型汽车 则至少要生产80辆 那么最优的生产计划应作何改变 例1汽车厂生产计划 汽车厂生产三种类型的汽车 已知各类型每辆车对钢材 劳动时间的需求 利润及工厂每月的现有量 制订月生产计划 使工厂的利润最大 15 设每月生产小 中 大型汽车的数量分别为x1 x2 x3 汽车厂生产计划 模型建立 线性规划模型 LP 16 模型求解 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 通过比较可能得到更优的解 但必须检验它们是否满足约束条件 为什么 17 IP可用LINGO直接求解 整数规划 IntegerProgramming 简记IP IP的最优解x1 64 x2 168 x3 0 最优值z 632 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 Globaloptimalsolutionfound Objectivevalue 632 0000Extendedsolversteps 0Totalsolveriterations 3VariableValueReducedCostX164 00000 2 000000X2168 0000 3 000000X30 000000 4 000000 模型求解 IP结果输出 18 其中3个子模型应去掉 然后逐一求解 比较目标函数值 再加上整数约束 得最优解 方法1 分解为8个LP子模型 汽车厂生产计划 若生产某类汽车 则至少生产80辆 求生产计划 x1 x2 x3 0或 80 x1 80 x2 150 x3 0 最优值z 610 19 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 最优解同前 20 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 最优解同前 一般地 整数规划和非线性规划的求解比线性规划困难得多 特别是问题规模较大或者要求得到全局最优解时 21 例2加工奶制品的生产计划 50桶牛奶 时间480小时 至多加工100公斤A1 制订生产计划 使每天获利最大 35元可买到1桶牛奶 买吗 若买 每天最多买多少 可聘用临时工人 付出的工资最多是每小时几元 A1的获利增加到30元 公斤 应否改变生产计划 每天 问题 22 x1桶牛奶生产A1 x2桶牛奶生产A2 获利24 3x1 获利16 4x2 原料供应 劳动时间 加工能力 决策变量 目标函数 每天获利 约束条件 非负约束 线性规划模型 LP 时间480小时 至多加工100公斤A1 基本模型 23 模型分析与假设 比例性 可加性 连续性 xi对目标函数的 贡献 与xi取值成正比 xi对约束条件的 贡献 与xi取值成正比 xi对目标函数的 贡献 与xj取值无关 xi对约束条件的 贡献 与xj取值无关 xi取值连续 A1 A2每公斤的获利是与各自产量无关的常数 每桶牛奶加工A1 A2的数量 时间是与各自产量无关的常数 A1 A2每公斤的获利是与相互产量无关的常数 每桶牛奶加工A1 A2的数量 时间是与相互产量无关的常数 加工A1 A2的牛奶桶数是实数 线性规划模型 24 模型求解 图解法 约束条件 目标函数 z c 常数 等值线 在B 20 30 点得到最优解 目标函数和约束条件是线性函数 可行域为直线段围成的凸多边形 目标函数的等值线为直线 最优解一定在凸多边形的某个顶点取得 25 模型求解 软件实现 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元 26 结果解释 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 三种资源 资源 剩余为零的约束为紧约束 有效约束 27 结果解释 Globaloptimalsolutionfound Objectivevalue 3360 000Totalsolveriterations 2VariableValueReducedCostX120 000000 000000X230 000000 000000RowSlackorSurplusDualPrice13360 0001 000000MILK0 00000048 00000TIME0 0000002 000000CPCT40 000000 000000 最优解下 资源 增加1单位时 效益 的增量 影子价格 35元可买到1桶牛奶 要买吗 35 48 应该买 聘用临时工人付出的工资最多每小时几元 2元 28 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元 公斤 应否改变生产计划 x1系数由24 3 72增加为30 3 90 在允许范围内 不变 约束条件不变 29 结果解释 Rangesinwhichthebasisisunchanged ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX172 0000024 000008 000000X264 000008 00000016 00000RighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecreaseMILK50 0000010 000006 666667TIME480 000053 3333380 00000CPCT100 0000INFINITY40 00000 影子价格有意义时约束右端的允许变化范围 原料最多增加10 时间最多增加53 35元可买到1桶牛奶 每天最多买多少 最多买10桶 目标函数不变 充分条件 30 生产 生活物资从若干供应点运送到一些需求点 怎样安排输送方案使运费最小 或利润最大 例3运输问题 31 其他费用 450元 千吨 应如何分配水库供水量 公司才能获利最多 若水库供水量都提高一倍 公司利润可增加到多少 例3运输问题 自来水输送 收入 900元 千吨 支出 32 总供水量 160 确定送水方案使利润最大 问题分析 总需求量 120 180 300 总收入900 160 144 000 元 收入 900元 千吨 其他费用 450元 千吨 支出 引水管理费 其他支出450 160 72 000 元 33 供应限制 约束条件 需求限制 线性规划模型 LP 目标函数 水库i向j区的日供水量为xij x34 0 决策变量 模型建立 确定3个水库向4个小区的供水量 34 模型求解 部分结果 ObjectiveValue 24400 00VariableValueReducedCostX110 00000030 000000X1250 0000000 000000X130 00000050 000000X140 00000020 000000X210 00000010 000000X2250 0000000 000000X230 00000020 000000X2410 0000000 0