第二讲最优化模型.ppt

Schoolofmathematics physics 华北电力大学数理学院 爱因斯坦的一句名言 想象力比知识更重要 因为知识是有限的 而想象力包括世界的一切 是知识的源泉 要点 最优优化模型 Schoolofmathematics physics 华北电力大学数理学院 最优化模型概述 最大值或最小值数学规划 线性规划 整数规划 0 1规划 目标规划等 非线性规划动态规划 Schoolofmathematics physics 华北电力大学数理学院 一 简单优化问题 案例1 产销平衡下的某种产品的最优价格 即使工厂利润最大的价格 1 模型假设 Schoolofmathematics physics 华北电力大学数理学院 一 简单优化问题 2 模型建立 总收入 I p px总支出 C p qx利润 U I p C p p q x p q f p 数学模型为 Schoolofmathematics physics 华北电力大学数理学院 3 模型求解及其结果分析 需求函数是售价的减函数 通常是根据实际销售情况定出 现在 假设它是线性函数 即 一 简单优化问题 Schoolofmathematics physics 华北电力大学数理学院 一 简单优化问题 利润U p 达到最大值的最优价格满足 得到 最优价格一部分是成本的一半 另一部分与 绝对需求 成正比 与市场需求对价格的敏感系数成反比 Schoolofmathematics physics 华北电力大学数理学院 边界收入 边界支出 当边界支出等于边界收入时利润最大 经济学著名定理 最大利润 一 简单优化问题 Schoolofmathematics physics 华北电力大学数理学院 二 数学规划模型 案例2 奶制品的生产计划 一奶制品加工厂用牛奶生产A1 A2两种奶制品 参数见表 根据市场需求 生产的A1 A2产品全部能售出 且每千克A1产品获利24元 每千克A2产品获利16元 试为该厂订一个生产计划 使每天获利最大 并进一步讨论以下问题 一 问题的提出 Schoolofmathematics physics 华北电力大学数理学院 1 若用35元可以买到1桶牛奶 是否应作这项投资 若投资 每天最多购买多少桶牛奶 2 若可以聘用临时工人以增加劳动时间 付给临时工人的工资最多是每小时几元 3 由于市场需求变化 每千克A1产品的获利增加到30元 是否应改变生产计划 二 模型分析 生产计划就是每天生产多少A1和多少A2 获利润最大 或者是每天用多少桶牛奶生产A1和用多少桶牛奶生产A2 获利润最大 当技术参数 价值系数为常数时 此为线性规划模型 二 数学规划模型 Schoolofmathematics physics 华北电力大学数理学院 三 模型的假设 1 每天用桶牛奶生产A1 桶牛奶生产A2 可以是任意的实数 2 劳动时间 设备能力 利润均为与产量无关常数 即技术参数 价值系数为常数 二 数学规划模型 3 生产的产品全能售出 Schoolofmathematics physics 华北电力大学数理学院 四 模型的建立 目标 设每天收入z元 则 二 数学规划模型 Schoolofmathematics physics 华北电力大学数理学院 二 数学规划模型 综上可得 Schoolofmathematics physics 华北电力大学数理学院 五 模型求解及结果分析 二 数学规划模型 即按每天用20桶牛奶生产A1 用30桶牛奶生产A2 获最大收益 z 3360元 Schoolofmathematics physics 华北电力大学数理学院 附加问题 1 和 2 是要不要扩大生产 这取决于对第i种资源的估价 影子价格 在完全市场经济的条件下 当某种资源的市场价低于影子价格时 企业应买进该资源用于扩大生产 而当某种资源的市场价高于企业影子价格时 则企业的决策者应把已有资源卖掉 附加问题的讨论 附加问题 3 是考虑当费用系数c变化时对最优解和最优值有没有影响 找出使最优解不变的区间 二 数学规划模型 Schoolofmathematics physics 华北电力大学数理学院 二 数学规划模型 Schoolofmathematics physics 华北电力大学数理学院 二 数学规划模型 解附加问题 1 由于每桶牛奶的市场价35元低于影子价格 所以企业应买进牛奶用于扩大生产 设再增加x桶 其他条件不变 则有相应生产计划 x 0 0000 60 0000 10 0000 z 3 4900e 003收入 3840 即最多每天再多买进10桶 Schoolofmathematics physics 华北电力大学数理学院 解附加问题 2 在每位临时工人的工资不超过每小时2元的条件下 可以聘用临时工人以增加劳动时间 设小时工资为s 0 s 2 元 其他条件不变的条件下 再增加x小时 则有相应生产计划 Schoolofmathematics physics 华北电力大学数理学院 f 72 642 a 110 128 1 300 b 50 480 100 x z linprog f a b 0 0 0 x 21 1790 28 8210 4 7160z 3 3600e 003 收入 s 2时 3369 53 f 72 640 a 110 128 1 300 b 50 480 100 x z linprog f a b 0 0 0 x 33 3333 16 6667 104 3896z 3 4667e 003 收入 s 0时 3466 7 0 s 2时 f 72 64s a 110 128 1 300 b 50 480 100 x z linprog f a b 0 0 0 x 33 3333 16 6667 53 3333z 3 4133e 003 收入 3466 7 Schoolofmathematics physics 华北电力大学数理学院 解附加问题 3 求使最优解不变的c的变化范围 由f 0时的最终表 Schoolofmathematics physics 华北电力大学数理学院 建立此问题的初始单纯性表 现在 所以不用改变生产计划 Schoolofmathematics physics 华北电力大学数理学院 案例3 奶制品的生产销售计划 一 问题的提出 案例2的A1 A2的生产条件 利润 资源都不变条件下 提高奶制品深加工技术 增加工厂获利 用2小时和3元加工费 可将1千克A1加工成0 8千克高级奶制品B1 也可将1千克A2加工成0 75千克高级奶制品B2 每千克B1可获利44元 每千克B2可获利32元 生产的产品全能售出 试着为该厂订制一个生产销售计划 使每天获利最大 并进一步讨论以下问题 1 若投资30元可增加供应1桶牛奶 投资3元可增加1小时劳动时间 是否应作这项投资 若每天投资150元 可赚回多少 2 每千克高级奶制品B1 B2的获利经常有10 的波动 对制订的生产销售计划有无影响 若每千克B1的获利下降10 计划是否应作调整 Schoolofmathematics physics 华北电力大学数理学院 二 模型分析 对本案例来讲 决策变量取为A1 A2 B1 B2每天的销售量讨论更方便 当技术参数 价值系数为常数时 此为线性规划模型 三 模型的假设 2 劳动时间 设备能力 利润均为与产量无关常数 即技术参数 价值系数为常数 3 生产的产品全能售出 1 每天销售产品A1 A2 B1 B2分别为公斤 且用公斤A1加工B1 用公斤A2加工B2 Schoolofmathematics physics 华北电力大学数理学院 四 模型的建立 目标 设每天净利润z元 则 Schoolofmathematics physics 华北电力大学数理学院 综上可得 Schoolofmathematics physics 华北电力大学数理学院 五 模型求解及结果分析 利用LINDO6 1 max24x1 16x2 44x3 32x4 3x5 3x6st2 4x1 3x2 4x5 3x6 6003 4x1 2x2 6x5 4x6 4804 x1 x5 1005 x3 0 8x5 06 x4 0 75x6 0end 得到如下结果 Schoolofmathematics physics 华北电力大学数理学院 LPOPTIMUMFOUNDATSTEP2OBJECTIVEFUNCTIONVALUE 最优值 1 3460 800VARIABLEVALUE 最优解 REDUCEDCOSTX10 0000001 680000X2168 0000000 000000X319 2000010 000000X40 0000000 000000X524 0000000 000000X60 0000001 520000ROWSLACKORSURPLUSDUALPRICES 影子价格 2 0 0000003 1600003 0 0000003 2600004 76 0000000 0000005 0 00000044 0000006 0 00000032 000000 Schoolofmathematics physics 华北电力大学数理学院 NO ITERATIONS 2RANGESINWHICHTHEBASISISUNCHANGED OBJCOEFFICIENTRANGES 使最优解不变的费用系数的取值范围 VARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX124 0000001 680000INFINITYX216 0000008 1500002 100000X344 00000019 7500023 166668X432 0000002 026667INFINITYX5 3 00000015 8000002 533334X6 3 0000001 520000INFINITYRIGHTHANDSIDERANGES 资源系数的取值范围 ROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE2600 000000120 000000280 0000003480 000000253 33332880 0000004100 000000INFINITY76 00000050 000000INFINITY19 20000160 000000INFINITY0 000000 Schoolofmathematics physics 华北电力大学数理学院 现在的生产与销售计划 生产24公斤A1并全部用于深加工B1 生产168公斤A2并全部用于销售 获利最大为3460 8元 附加问题 1 因为增加一桶牛奶可使净利润增长3 16 12 37 92元 增加一小时劳动力使净利润增长3 26元 所以应该投资30元增加供应1桶牛奶或投资3元增加1小时劳动时间 投资150元 5桶奶 可赚回37 92 5 189 6元 附加问题 2 最优解不变的x3 x4的费用系数变化范围分别是 44 3 17 44 19 75 32 inf 32 2 03 因此 B1 B2的获利10 的波动对销售计划有影响 Schoolofmathematics physics 华北电力大学数理学院 若每千克B1的获利下降10 计划应作调整 Schoolofmathematics physics 华北电力大学数理学院 max24x1 16x2 39 6x3 32x4 3x5 3x6st2 4x1 3x2 0 x3 0 x4 4x5 3x6 6003 4x1 2x2 0 x3 0 x4 6x5 4x6 4804 x1 0 x2 0 x3 0 x4 x5 0 x6 1005 0 x1 0 x2 x3 0 x4 0 8x5 0 x6 06 0 x1 0 x2 0 x3 x4 0 x5 0 75x6 0end 执行 得到 Schoolofmathematics physics 华北电力大学数理学院 LPOPTIMUMFOUNDATSTEP3OBJECTIVEFUNCTIONVALUE1 3400 000VARIABLEVALUEREDUCEDCOSTX10 0000000 666667X2160 0000000 000000X30 0000000 000000X430 0000000 000000X50 0000000 986666X640 0000000 000000ROWSLACKORSURPLUSDUALPRICES2 0 0000003 6666673 0 0000002 5000004 100 0000000 0000005 0 00000039 5999986 0 00000032 000000 Schoolofmathematics physics 华北电力大学数理学院 案例4 露天矿生产的车辆安排 2003B 许多现代化铁矿是露天开采的 它的生产主要是由电动铲车 电铲 装车 电动轮自卸卡车 卡车 运输来完成 提高这些大型设备的利用率是增加露天矿经济效益的首要任务 露天矿里有若干个爆破生成的石料堆 铲位 和卸货地点 以下简称卸点 每个铲位已预先根据铁含量分成矿石和岩石 低于25 且矿石 岩石数量以及矿石的平均铁含量 称为品位 都是已知的 卸点有卸矿石的矿石漏 铁路倒装场 简称倒装场 有卸岩石的岩石漏 岩场 每个卸点都有各自的产量要求 一 问题的提出 Schoolofmathematics physics 华北电力大学数理学院 现某露天矿有铲位10个 卸点5个 现有电铲7台 卡车20辆 各卸点一个班次的产量要求 矿石漏1 2万吨 倒装场 1 3万吨 倒装场 1 3万吨 岩石漏1 9万吨 岩场1 3万吨 铲位和卸点位置的二维示意图如下 Schoolofmathematics physics 华北电力大学数理学院 各铲位矿石 岩石数量 万吨 和矿石的平均铁含量如下表 各铲位和各卸点之间的距离 公里 如下表 Schoolofmathematics physics 华北电力大学数理学院 一个班次的生产计划应该包含以下内容 出动几台电铲 分别在哪些铲位上 出动几辆卡车 分别在哪些路线上各运输多少次 注意 因为随机因素影响 装车 卸车时间与运输时间都不精确 所以排时计划无效 只求出各条路线上的卡车数及安排即可 一个合格的生产计划要在卡车不等待条件下满足产量和质量 品位 要求 而一个好的计划还应该考虑下面两条原则之一 1 总运量 吨公里 最小 同时出动最少的卡车 从而运输成本最小 2 利用现有车辆运输 获得最大的产量 岩石产量优先 在产量相同的情况下 取总运量最小的解 请你就两条原则分别建立数学模型 并给出具体的生产计划 相应的总运量及岩石和矿石产量 Schoolofmathematics physics 华北电力大学数理学院 补充条件 1 一般来说 平均铁含量大于等于25 的为矿石 否则为岩石 2 每个铲位至多能安置一台电铲 电铲的平均装车时间为5分钟 3 应该尽量把矿石按矿石卸点需要的铁含量 品位 搭配起来送到卸点 搭配的量在一个班次 8小时 内满足品位限制即可 假设每个矿石卸点品位要求都为29 5 1 卡车的平均卸车时间为3分钟 4 所用卡车载重量为154吨 平均时速28 卡车每次都是满载运输 5 电铲和卸点都不能同时为两辆及两辆以上卡车服务 6 每个铲位到每个卸点的道路都是专用的宽60m的双向车道 不会出现堵车现象 每段道路的里程都是已知的 7 卡车在等待时所耗费的能量也是相当可观的 原则上在安排时不应发生卡车等待的情况 8 发动机点火时需要消耗相当多的电瓶能量 故一个班次中只在开始工作时点火一次 9 卡车的耗油量很大 每个班次每台车消耗近1吨柴油 Schoolofmathematics physics 华北电力大学数理学院 二 模型分析 属于运输问题 但与典型的运输问题 某种物资由m个产地运往n个销地 在满足各产地的供应和各销地的需求的条件下 使总运量 吨公里 最小 制订运输计划 相比 还有以下特点 1 车辆满载运输 154吨 车次 2 运输矿石与岩石两种物资 矿石卸点有品位约束 各铲位的矿石需搭配运输 3 电铲和卸点都不能同时为两辆及两辆以上卡车服务 即各个铲位 卸点还有一个班次内运输车次的限制 4 每条路线上有一个班次内运输车次的限制 5 铲位数10大于电铲数7 要从10个中选择不大于7个铲位 6 用最少的车辆 不超过20 给出各条路线上的车辆安排 几辆车 跑几次 如何处理以上不同之处 Schoolofmathematics physics 华北电力大学数理学院 三模型的假设 Schoolofmathematics physics 华北电力大学数理学院 四模型的建立 1 基本模型 现将m 10 个铲位 产地 上的石料运往n 5 个卸点 销地 在满足各产地的供应和各销地的需求的条件下 使总运量 吨公里 最小 制订运输计划 设cij 产地 铲位 i到销地 卸点 j的距离 公里 xij 产地i到销地j的车次 154xij吨 ai 产地i的供应量 吨