离散优化ppt课件.ppt

离散优化的应用 日程安排资本预算广告投放运输问题项目评价等等 9 1用离散优化模型定量描述一个管理问题 我们将通过三个管理问题的实例来介绍离散优化模型的应用 它们分别是 实例9 1一架飞机的制造问题 实例9 2一个资本运算问题 实例9 3一个战略重新布置的问题 实例9 1一架飞机的制造问题 1 CRISP商务飞机制造公司生产四种类型小型商务飞机 分别为 AR1型 具有一个座位 AR2型 具有二个座位 AR4型 具有四个座位 AR6型 具有六个座位 飞机的制造是以月为单位进行的 表9 1说明了CRISP公司的有关飞机制造的重要信息 实例9 1一架飞机的制造问题 2 表9 1 CRISP公司飞机制造的相关信息 实例9 1一架飞机的制造问题 3 表9 1的第一行说明了联邦航空局允许每种飞机在下个月的最大产量 表9 1的第二行说明了建造每种飞机所需要的时间 以天为单位 表9 1的第三行说明了生产每种飞机所需要管理人员数目 表9 1的最后行说明了每种飞机的单位利润 在下个月 CRISP公司可用的管理人员总数为60人 CRISP公司的生产能力为9架 天 按每月30天计算 下一个月可以得到的制造天数为270天 实例9 1一架飞机的制造问题 4 CRISP公司的主管想要确定在下一个月里每种飞机的生产数量 以便使公司的利润最大化 定义下述决策变量 A1 下一个月生产AR1型飞机的数目 A2 下一个月生产AR2型飞机的数目 A4 下一个月生产AR4型飞机的数目 A6 下一个月生产AR6型飞机的数目 在这个问题中 每个决策变量必须是一个非负的整数值 即数的形式是0 1 2 3 所以CRISP公司的生产计划问题的模型必须包括对决策变量的下述约束 A1 A2 A4 A6是整数 实例9 1一架飞机的制造问题 5 CRISP公司的生产计划模型为 最大化 62A1 84A2 103A4 125A6约束条件为 建造时间 4A1 7A2 9A4 11A6 270管理人员 A1 A2 2A4 2A6 60AR1产量 A1 8AR2产量 A2 17AR4产量 A4 11AR6产量 A6 15非负性 A1 A2 A4 A6 0整数要求 A1 A2 A4 A6是整数 实例9 1一架飞机的制造问题 6 把上述问题表示成电子表格形式 并且用EXCEL的规划求解进行求解 将在后面介绍 我们将获得CRISP公司的最优生产计划 参见表9 2 表9 2 实例9 1一架飞机的制造问题 7 注意在表9 2中 决策变量的取值都是整数 这个计划的利润为 利润 62 8 84 17 103 1 125 10 1000 3277000 美元 用于CRISP公司的生产计划模型是一个线性离散 或整数 优化模型的实例 线性离散 或整数 优化模型的定义为 如果所有的决策变量被要求是非负整数 并且所有的约束和目标函数都是线性函数 那么该优化模型被称为一个线性离散 或整数 优化模型 实例9 2一个资本预算问题 1 K A公司是一家中型建筑管理公司 公司正在考虑下一年可能要投资的工程项目 表9 3说明了每个工程所需要的投资 以及每个工程在未来三年中的预期利润 表9 3 实例9 2一个资本预算问题 2 公司准备在下一年投入1 500万美元 希望选择使总预期利润最大化的那些工程 设定决策变量 设Xi表示工程是Xi被选中的决策变量 并且定义Xi如下 如果工程1被选中 则X1 1如果工程1没有被选中 则X1 0如果变量X被要求只取数值0或1 那我们称这个变量X为二态变量 定义X2 X3 X4为 如果工程2被选中 则X2 1如果工程2没有被选中 则X2 0如果工程3被选中 则X3 1如果工程3没有被选中 则X3 0如果工程4被选中 则X4 1如果工程4没有被选中 则X4 0X2 X3 X4都是二态变量 实例9 2一个资本预算问题 3 K A公司的资本预算模型为下列优化模型 最大化 12X1 8X2 7X3 6X4约束条件为 预算 8X1 6X2 5X3 4X4 15二态性 X1 X2 X3 X4是二态变量我们可以把这个问题表示成电子表格的形式 并且计算出结果 将在后面介绍 参见表9 4 我们看到在表9 4中 决策变量的取值都是二态的 即0和1 根据表9 4中的数据 最优工程的选择是工程2 工程3以及工程4 在这种方案之下的利润为 12 0 8 1 7 1 6 1 21 实例9 2一个资本预算问题 4 表9 4 K A公司的资本预算问题的最优解 实例9 2一个资本预算问题 5 K A公司的资本预算问题的优化模型是一个线性二态化模型的实例 线性二态化优化模型的定义为 如果所有的决策变量被要求是二态变量 即0和1 并且并且所有的约束和目标函数都是线性函数 那么该优化模型被称为一个线性二态优化模型 一个线性二态优化模型也被称为线性0 1整数优化模型 二态决策变量可以极大地增强特定类型的约束能力 例如 我们可以考虑以下附加约束 1 公司最多可以投资两个工程 该约束被表示为 X1 X2 X3 X4 2 实例9 2一个资本预算问题 6 2 如果工程4被选中 那么工程3必须被选择 该约束可被表示为 X3 X4 0 3 由于相关法律原因 公司不可以同时投资于工程1和工程3 该约束可被表示为 X1 X3 1如果我们把上述三个条件增加到资本预算模型中 那么新的线性二态优化模型为 实例9 2一个资本预算问题 7 最大化 12X1 8X2 7X3 6X4约束条件为 预算 8X1 6X2 5X3 4X4 15两个工程最大数 X1 X2 X3 X4 2工程3和工程4 X3 X4 2工程1和工程3 X1 X3 1二态性 X1 X2 X3 X4是二态变量 实例9 2一个资本预算问题 8 在次对上述问题利用EXCEL规划求解进行求解 求解结果参见表9 5 表9 5 实例9 3一个战略重新布置的问题 1 TRD公司是一家大型计算机制造企业 目前 TRD公司有三个面向欧洲客户服务的服务中心 分别为 伦敦 马德里以及巴黎 七个主要客户对TRD公司服务及时性提出投诉 这些客户反映它们需要等待两天时间才能获得从某个服务中心运来的计算机配件 同时 TRD公司的运输成本以及维持服务中心的运营成本一直在增加 TRD公司考虑重新布置欧洲服务中心的位置 并希望将中心数目由目前3个减少到2个 公司也考虑将汉堡和罗马作为可能的服务中心 表9 6给出5个可能的服务中心 将从中选出两个 的年运营成本 实例9 3一个战略重新布置的问题 2 表9 6 TRD公司5个可能的服务中心 实例9 3一个战略重新布置的问题 3 TRD公司的主要客户位于5个国家 英国 德国 瑞士 意大利和法国 表9 7说明了TRD公司的主要客户分布在5个国家的百分比 表9 7 实例9 3一个战略重新布置的问题 4 表9 8说明了单位配件从每个潜在的服务中心 共5个 到5个国家的平均运输时间 表9 8 实例9 3一个战略重新布置的问题 5 公司目标是选择服务中心的位置使服务中心年度总经营成本最小化 但是需要满足客户的要求 1 从任何一个服务中心到任何一个国家的平均运输时间不超过1 5天 2 从任何一个服务中心到五个国家的总平均运输时间不超过1 1天 相当于对需求 1 再进行算术平均 共有5个值 设j 1 2 3 4 5分别表示5个潜在的服务中心位置 i 1 2 3 4 5分别表示5个国家 定义二态决策变量 如果位置j被选中 yj 1 如果位置j没有被选中 yj 0 实例9 3一个战略重新布置的问题 6 此外 对于i 1 2 3 4 5和j 1 2 3 4 5 定义xij 来自国家i的服务请求由服务中心j提供服务的比例年运营成本为 成本 20y1 15y2 22y3 21y4 16y5来自英国的服务请求被分解到5个服务中心 所以英国 i 1 的服务请求比例之和必须等于1 比例1 x11 x12 x13 x14 x15 1类似地 对于其他国家 i 2 3 4 5 我们将有类似的约束 实例9 3一个战略重新布置的问题 7 比例2 x21 x22 x23 x24 x25 1比例3 x31 x32 x33 x34 x35 1比例4 x41 x42 x43 x44 x45 1比例5 x51 x52 x53 x54 x55 1定义决策变量wi 分别表示从5个中心到国家i的平均运输时间 天 根据表9 8中的数据 我们可以把w1 w2 w3 w4 和w5表示为 w1 0 5x11 2 5x12 1 5x13 2 0 x14 3 0 x15w2 2 0 x21 3 0 x22 1 0 x23 0 5x24 2 0 x25w3 3 0 x31 2 0 x32 2 0 x33 1 5x34 1 0 x35w4 3 0 x41 1 0 x42 2 0 x43 2 0 x44 0 5x45w5 1 5x51 2 0 x52 0 5x53 1 0 x54 2 0 x55 实例9 3一个战略重新布置的问题 8 由于从5个中心到一个国家的平均运输时间不超过1 5天 我们加入下列约束 时间约束 w1 1 5 w2 1 5 w3 1 5 w4 1 5 w5 1 5此外 还要保证从中心到5个国家的平均运输时间不超过1 1天 利用表9 7中的数据 我们有以下约束 用客户比例加权 总运输时间 0 25w1 0 30w2 0 15w3 0 10w4 0 20w5 1 1如果yj 0 那么对于所有i 1 2 3 4 5来说xij 0 那么有 逻辑 对于所有的i 1 2 3 4 5和j 1 2 3 4 5 xij yj 实例9 3一个战略重新布置的问题 9 最后 由于公司希望服务中心的数目为2个 原来为3个 所以 服务中心的数目应当大于2个或者小于3个 那么我们将加上以下约束条件 数目2个 y1 y2 y3 y4 y5 2数目3个 y1 y2 y3 y4 y5 3注意到 这个优化模型有35个决策变量 即25个变量xij 5个变量wi以及5个二态变量yj 最后 我们把TRD公司的服务中心重新布置问题表示为下述离散优化模型 实例9 3一个战略重新布置的问题 10 最小化20y1 15y2 22y3 21y4 16y5约束条件为 比例1 x11 x12 x13 x14 x15 1比例2 x21 x22 x23 x24 x25 1比例3 x31 x32 x33 x34 x35 1比例4 x41 x42 x43 x44 x45 1比例5 x51 x52 x53 x54 x55 1运输时间1 w1 0 5x11 2 5x12 1 5x13 2 0 x14 3 0 x15运输时间2 w2 2 0 x21 3 0 x22 1 0 x23 0 5x24 2 0 x25运输时间3 w3 3 0 x31 2 0 x32 2 0 x33 1 5x34 1 0 x35运输时间4 w4 3 0 x41 1 0 x42 2 0 x43 2 0 x44 0 5x45运输时间5 w5 1 5x51 2 0 x52 0 5x53 1 0 x54 2 0 x55时间约束 w1 1 5 w2 1 5 w3 1 5 w4 1 5 w5 1 5总运输时间 0 25w1 0 30w2 0 15w3 0 10w4 0 20w5 1 1逻辑 对于所有的i 1 2 3 4 5和j 1 2 3 4 5 xij yj数目2 y1 y2 y3 y4 y5 2数目3 y1 y2 y3 y4 y5 3非负性 xij 0 其中i 1 2 3 4 5和j 1 2 3 4 5整数性 yj是二态变量 其中i 1 2 3 4 5 实例9 3一个战略重新布置的问题 11 我们可以把上述TRD公司的服务中心重新布置的离散优化问题表示成电子表格的形式 并且利用EXCEL的规划求解功能进行计算 我们将在后面介绍如何求解一个离散优化问题 其结果参见表9 9 表9 10和表9 11 实例9 3一个战略重新布置的问题 12 表9 9 实例9 3一个战略重新布置的问题 13 表9 10决策变量xij的最优值 实例9 3一个战略重新布置的问题 14 表9 11运输时间的决策变量wi的最优值 实例9 3一个战略重新布置的问题 15 我们来研究这个最优解 根据表9 9 服务中心的最优选择是巴黎和罗马 总成本为 20 0 15 0 22 1 21 0 16 1 38根据表9 9 我们有 所有来自英国的客户应向巴黎服务中心请求服务 91 7 的德国客户应向巴黎服务中心请求服务 剩下的8 3 的德国客户应向罗马服务中心请求服务 TRD公司所面临的战略重新布置问题的优化模型是一个混合整数优化模型 其定义为 实例9 3一个战略重新布置的问题 16 如果一些决策变量要求要么是非负整数 要么是二态变量 而其余决策变量被允许是普通决策变量 并且所有的约束和目标函数都是线性函数 那么该优化模型被称为一个混合整数优化模型 9 1离散优化问题类型小结 三种类型的离散优化模型 一个整数优化模型是所有的决策变量被要求是非负整数 并且所有的约束和目标函数都是线性函数 一个二态优化模型是所有决策变量被要求是二态变量 并且所有的约束和目标函数都是线性函数 一个混合整数优化模型是一些决策变量要求要么是非负整数 要么是二态变量 而其余决策变量被允许是普通决策变量 并且所有的约束和目标函数都是线性函数 9 2具有两个变量的离散优化模型的图形分析 1 我们以两个变量的离散优化模型为例研究其几何特征 考虑下列整数优化问题 IM 最大化150X 112Y约束条件 7 5X 6Y 908X 12Y 13855X 33Y 600X Y是整数我们构造IM问题的可行域的图形 参见图9 1 9 2具有两个变量的离散优化模型的图形分析 2 Y X 图9 1 9 2具有两个变量的离散优化模型的图形分析 3 设点 X Y 属于上述多边形中的整数点 所有整数点的集合就是整数优化问题IM的可行域 我们可以观测到 IM的可行域可行域是一个离散点的集合 是多边形的子集 该可行域不存在的顶点 可行域的边界并不一定对应着两个约束相遇的地方 9 3离散优化问题的计算机求解 1 电子表格软件EXCEL可以用来求解一个离散优化问题 考虑实例9 1的CRISP公司的生产计划模型为 最大化 62A1 84A2 103A4 125A6约束条件为 建造时间 4A1 7A2 9A4 11A6 270管理人员 A1 A2 2A4 2A6 60AR1产量 A1 8AR2产量 A2 17AR4产量 A4 11AR6产量 A6 15非负性 A1 A2 A4 A6 0整数要求 A1 A2 A4 A6是整数 9 3离散优化问题的计算机求解 2 实例9 1的电子表格的表示形式 9 3离散优化问题的计算机求解 3 作业 5 P491练习9 3P493练习9 5P493练习9 6 9 6案例分析 Dellmar公司的供应链管理 1 Dellmar公司是一家商用空调系统制造商 公司一年前引进的空调系统CAP非常成功 产品的订单一直在上升 但是这款产品的成功却暴露了Dellmar公司物流系统的不足 国内和区域分发中心对CAP进出的耽搁使客户的订单受到不同程度的延误 过高的库存和运输成本也引起Dellmar公司管理层的关注 在2月份 库存和运输成本超过了140万美元 公司管理层希望制定能够将产品迅速交给客户同时降低库存和运输成本的解决方案 9 6案例分析 Dellmar公司的供应链管理 2 CAP空调系统的供应链Dellmar公司在NH制造工厂制造CAP系统 这个工厂每月可以生产5万部CAP系统 公司正在考虑扩大每月10 的生产能力 每月须额外支付财务和运营成本为55 000美元 Dellmar公司将国内销售区域划分为三个区域 东部 西部和中西部 每个区域由一个区域销售分发中心提供服务 Dellmar公司还经营着两个国内分发中心 一个位于Ohio 为中西部和西部提供服务 另一个位于NJ 为中西部和东部提供服务 CAP空调系统首先由NH工厂运输到两个国内分发中心库存 然后 再运输到三个区域销售分发中心 运输的时间为每月一次 9 6案例分析 Dellmar公司的供应链管理 3 运输和库存成本CAP空调系统从工厂运输到一个国内分发中心 或者从一个国内分发中心运输到任何一个区域分发中心 单位运输成本是每系统10美元 安排货运的固定运输成本参见表9 15 在Ohio和NJ国内分发中心的库存成本是每月每件5美元 而在区域销售分发中心的单位库存成本是每月每件10美元 9 6案例分析 Dellmar公司的供应链管理 4 表9