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

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