运输、指派问题与网络最优化

Data, Model and Decisions 数据、模型与决策,第四讲 运输、指派问题与网络最优化,主要内容,P&T公司配送问题 运输问题 运输问题的特征 运输问题的一个获奖应用 各种运输问题变体 特赛格公司的选地址问题,指派问题 指派问题模型 指派问题的变形 指派问题的应用,主要内容,主要内容,飞利浦石油公司运输工具替换计划 网络最优化模型的应用 网络最优化问题类型 最小费用流问题 最短路问题 最小支撑树问题,配送问题,P&T公司是一家由家族经营的小公司。它收购生菜并在食品罐头厂中把它们家工成罐头，然后在把这些罐头食品分销到各地。公司的一个主要产品是豌豆罐头，在三个食品罐头厂生产（靠近华盛顿的贝林翰；俄勒冈州的尤基尼；明尼苏达州的艾尔贝李）然后用卡车把它们运送到美国西部的四个分销仓库（加利福尼亚州的萨克拉门托；犹他州的盐湖城；南达科他州的赖皮特城；新墨西哥州的澳尔巴古）。,实际问题,配送问题,实际问题,配送问题,当前的当前的运输策略： 1因为在贝林翰的罐头厂距离仓库最远，所以把它的产品运送到最近的一个仓库。也就是萨克拉门托的那个仓库。如果还有剩余的话，就把它们运送到盐湖城的仓库中去。 2因为在澳尔巴古的仓库距离食品罐头厂最远，所以就要从最近的一个罐头厂（艾尔贝·李的罐头厂）中运送产品到澳尔巴古。如果还有剩余的话，就要运送到赖皮特城的仓库中。 3用尤基尼的罐头厂满足其他仓库的剩余需求。,实际问题,配送问题,现在所要做的是要检查当前的运输计划，看看是否能够制定出一个新的运输计划，使总运输成本下降到一个绝对最小值。,实际问题,运输问题是物流中的一个普遍问题，如何以尽可能小的成本把货物从一系列起始地（sources）（如工厂、仓库）运输到一系列终点地（destinations）（如仓库、顾客）,运输问题,运输问题,运输问题,运输问题,P&T公司运输问题,运输问题,P&T公司运输问题,运输问题,P&T公司运输问题,运输问题,P&T公司运输问题,运输问题,P&T公司运输问题,Excel建模,运输问题,每一个出发地都有一定的供应量（supply）配送到目的地，每一个目的地都有需要从一定的需求量（demand），接收从出发地发出的产品 需求假设（The Requirements Assumption） 可行解特性（The Feasible Solutions Property） 成本假设（The Cost Assumption） 整数解性质（Integer Solutions Property）,运输问题的特征,运输问题特征,需求假设（The Requirements Assumption）： 每一个出发地都有一个固定的供应量，所有的供应量都必须配送到目的地。与之相类似，每一个目的地都有一个固定的需求量，整个需求量都必须由出发地满足,需求假设,运输问题特征,可行解特性（The Feasible Solutions Property）：当且仅当供应量的总和等于需求量的总和时，运输问题才有可行解,可行解特性,运输问题特征,成本假设（The Cost Assumption）： 从任何一个出发地到任何一个目的地的货物配送成本和所配送的数量成线性比例关系，因此这个成本就等于配送的单位成本乘以所配送的数量,成本假设,运输问题特征,整数解性质（Integer Solutions Property）： 只要它的供应量和需求量都是整数，任何有可行解的运输问题必然有所有决策变量都是整数的最优解。因此，没有必要加上所有变量都是整数的约束条件,整数解性质,运输问题特征,P&G重新设计制造和配送体系 ：90S 成百上千个供应商 50多个产品类别 超过60个的工厂 15个配送中心 超过1000个的顾客群体,运输问题的一个获奖应用,获奖应用,为每个单独的产品种类设计并求解运输问题 对于针对还在运行的工厂的每一个选择，为每 一个产品种类解决相应的运输问题体现了从这 些工厂运送产品到配送中心或顾客区所需要的 配送成本是多少。 在找出最好的新生产和配送系统的过程之中解 决了许多这样的运输问题 北美工厂数减少了20%，并且公司每年节省了2 亿美元的税前费用,运输问题的一个获奖应用,获奖应用,供应总量超出了需求总量 供应总量小于需求总量 一个目的地同时存在着最小需求和最大需求 在配送中不能使用特定的出发地目的地组合 目标是与配送量有关的总利润最大不是成本最小,各种运输问题变形,运输问题变形,求佳产品公司决定使用三个有生产余力的工厂进行四种新产品的生产制造。每单位产品需要等量的工作，所以工厂的有效生产能力以每天生产的任意种产品的数量来衡量。,求佳公司指定工厂生产产品,运输问题变形,求佳公司指定工厂生产产品,运输问题变形,耐芙迪公司选择顾客,耐芙迪公司在三个工厂中专门生产一种产品。这种产品有着优良的品质，所以现在公司接到了许多的订单，产品供不应求。公司也正在努力扩大生产，甚至计划要建立一个新的工厂，但是这个新的工厂要到明年才能投人运营。 在未来的四个月中，有四个处于国内不同区域的潜在顾客（批发商）很有可能大量订购。顾客1是公司最好的顾客，所以它的全部订购量都应该满足；顾客2和3也是公司很重要的顾客，所以营销经理认为作为最低限度至少要满足他们订单的1/3；对于顾客4，她认为并不需要进行特殊考虑，所以不想向这位顾客供应货物。这样就有足够的货物满足最少数量。,运输问题变形,耐芙迪公司选择顾客,运输问题变形,德罗水管站分配自然资源,米德罗水管站是一个主管着广阔地域的水资源分配的机构。由于这个地域十分干燥，所以这个机构需要从外地引水。这些引人的水来自于科伦坡、塞克隆以及卡路里河这三条河流。引人这些水之后，这个机构把水转卖给这个地区的用户。它的主要客户是布都、劳斯戴维斯、圣哥以及豪利格拉斯等城市的供水部门。,运输问题变形,德罗水管站分配自然资源,运输问题变形,德罗水管站分配自然资源,Excel,运输问题变形,北方飞机制造公司生产进度安排,北方飞机制造公司为全世界的航空公司生产各种商务飞机。制造过程的最后的一步是生产喷气发动机并把它们安装到已经完成的飞机框架之中去（非常快的一个操作）按照公司的一些订单合同，不久公司要交付使用相当多数量的飞机。所以有必要现在为未来四个月这些飞机喷气发动机的生产制定计划。,运输问题变形,北方飞机制造公司生产进度安排,运输问题变形,Excel,排米德尔城学区划分学生入学区域,米德尔城学区开办了第三所中学，需要为每一所学校重新划定这个城市内的服务区域。 在初步的计划中，这个城市被分成了拥有大致相同数量人口的九个区域（在进一步细化的计划之中，就把城市分成了超过100个更小的区域）表5-12 给出了每一所学校与每一个区域之间的近似距离。最右一列给出了明年每一个区域的高中学生数量（这些数字在未来几年之内估计会有缓慢的增长）。最下面的两行表示了每一所学校所能够安排的最少和最多的学生数量。,运输问题变形,排米德尔城学区划分学生入学区域,运输问题变形,源丰公司满足能源需求,源丰公司需要为新的建筑物建立起能源系统。 建筑物的能源需求主要来自于下面三个方面：1）电，2）热水，3）建筑物内取暖。每天这三类用途的能源需求（以相同的单位衡量）分别是20个单位、10个单位和30个单位。 满足这些需求的三个可能的能源来源是：电、天然气和安装在屋顶上的太阳能加热装置。房屋屋顶的大小决定了太阳能加热装置每天所能够提供的能源量30单位。但是对于电和天然气来说没有这种限制。,运输问题变形,源丰公司满足能源需求,运输问题变形,特塞格公司的选址问题,特塞格公司,特塞格公司的选址问题,特塞格公司,特塞格公司的选址问题,特塞格公司,特塞格炼油厂每一个备选厂址所带来的年变动成本,特塞格公司的选址问题,特塞格公司,一种特殊的线性规划问题，我们也经常遇到指派人员做某项工作的情况。指派问题的许多应用都用来帮助管理人员解决如何为一项将要开展进行的工作指派人员的问题。其他的一些应用如为一项任务指派机器、设备或者是工厂 。,指派问题,指派问题的形式表述: 给定了一系列所要完成的任务（tasks）以及一系列完成任务的被指派者（assignees），所需要解决的问题就是要确定出哪一个人被指派进行哪一项任务。,指派问题模型,指派问题的假设: 被指派者的数量和任务的数量是相同的 每一个被指派者只完成一项任务 每一项任务只能由一个被指派者来完成 每个被指派者和每项任务的组合有一个相关成本 目标是要确定怎样进行指派才能使得总成本最小,指派问题模型,塞尔默公司的营销经理将要主持召开一年一度的由营销区域经理以及销售人员参加的销售协商会议。为了更好地安排这次会议，他雇用了四个临时工（安、伊安、琼、肖恩）每一个人负责完成下面的一项任务： 1书面陈述的文字处理。 2制作口头和书面陈述的电脑图。 3会议材料的准备，包括书面材料的抄写和组织。 4处理与会者的提前和当场注册报名。,塞尔默公司,塞尔默公司,塞尔默公司,指派问题的变形,指派问题的变形: 有一些被指派者并不能进行某一些的任务 任务比被指派者多 被指派者比要完成的任务多 每个被指派者可以同时被指派给多于一个的任务 每一项任务都可以由多个被指派者共同完成,指派问题的应用,在各个地点分派设备 指派工厂生产产品 设计学生入学区域,指派问题应用,各个地点分派设备,指派问题应用,求佳产品公司指派工厂生产产品,指派问题应用,米德尔城学区设计学生入学区域,指派问题应用,飞利浦石油（Phillips Petroleum）应用最短路问题模型对各种高速公路运输车、卡车和货车运输路线的优化来降低成本提高竞争力,飞利浦石油的运输工具替换计划,Waddell (1983) Jul-Aug Interfaces article, “A Model for Equipment Replacement Decisions and Policies”,飞利浦石油,有1500辆卡车和3800辆货车 用最短路模型建立替换战略(20年时间跨度) 每次为每一类运输工具求解模型 考虑成本有维护和运营成本、租赁成本、购买成本、 政府授权费用路税和其他税收（投资税、折旧） 开始做lease-or-buy决策，然后做替换战略，目前扩展到了其他的设备（非运输工具）,飞利浦石油的运输工具替换计划,飞利浦石油,网络最优化模型的应用,网络在交通、电子和通讯网络遍及我们日常生活的 各个方面，网络规划也广泛用于解决不同领域中的 各种问题，如生产、分配、项目计划、厂址选择、 资源管理和财务策划等等。 网络规划为描述系统各组成部分之间的关系提供了 非常有效直观和概念上的帮助，广泛应用于科学、 社会和经济活动的每个领域中。,网络表述,网络最优化问题类型,最小费用流问题 最大流问题 最短路问题 最小支撑树问题,基本术语,节点、供应点 、需求点 、转运点 流量、流量守恒、弧、容量,最小费用流问题,最小费用流问题的构成： 节点(nodes)（供应点 、需求点 、转运点） 弧（arcs） 目标: 通过网络满足需求提供供应， 最小化流的总成本,最小费用流,最小费用流问题的假设,1至少有一个节点是供应点。 2至少有一个节点是需求点。 3所有剩下的节点都是转运点。 4通过弧的流只允许沿着箭头的方向流动，通过弧的最大流量取决于该弧的容量。（如果流是双向的话，则需要用一对箭头指向相反的弧来表示。）,最小费用流,最小费用流问题的假设,5网络中有足够的弧提供足够的容量，使得所有在供应点中产生的流都能够到这需求点。 6在流的单位成本已知的前提下，通过每一条弧的流的成本和流量成正比。 7最小费用流问题的目标是在满足给定需求的条件下，使得通过网络供应的总成本最小。（换一种说法是通过这样做使得总利润最大化。）,最小费用流,解的特征,具有可行解的特征：在以上的假设下，当且仅当供应点所提供的流量总和等于需求点所需要的流量总和时，最小费用流问题有可行解 具有整数解的特征：只要其所有的供应、需求和弧的容量都是整数值，那么任何