资源描述
第四讲 运输、指派问题与网络最优化,数据,模型与决策,运输、指派问题和网络最优化,主要内容,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单位。但是对于电和天然气来说没有这种限制。,运输问题变形,源丰公司满足能源需求,运输问题变形,特塞格公司的选址问题,特塞格公司,特塞格公司的选址问题,特塞格公司,特塞格公司的选址问题,特塞格公司,特塞格炼油厂每一个备选厂址所带来的年变动成本,地点,运输原油的总成本(百万美元),运输石油制品,的总成本,(十亿美元),新炼油厂,的运营成本,(,百万美元,),总变动成本,(,十亿美元,),洛杉机,820,1.26,620,2.7,加尔维斯敦,860,1.24,570,2.67,圣路易斯,1040,1.08,530,2.65,特塞格公司的选址问题,特塞格公司,一种特殊的线性规划问题,我们也经常遇到指派人员做某项工作的情况。指派问题的许多应用都用来帮助管理人员解决如何为一项将要开展进行的工作指派人员的问题。其他的一些应用如为一项任务指派机器、设备或者是工厂,。,指派问题,指派问题的形式表述,:,给定了一系列所要完成的任务(,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最小费用流问题的目标是在满足给定需求的条件下,使得通过网络供应的总成本最小。(换一种说法是通过这样做使得总利润最大化。),最小费用流,解的特征,具有,可行解,的特征:在以上的假设下,当且仅当供应点所提供的流量总和等于需求点所需要的流量总和时,最小费用流问题有可行解,具有,整数解,的特征:只要其所有的供应、需求和弧的容量都是整数值,那么任何最小费用流问题的可行解就一定有所有流量都是整数的最优解,最小费用流,无限配送公司,无限配送公司的最小成本流问题的,电子表格模型,最小费用流,网络单纯形法,实际运用中解决比较大型问题时需要用不同的方法,网络单纯形法可以用来解决那些对于单纯形法来说,太大而无法解决的大型问题,Excel Solver,软件中没有网络单纯形法,但是其他的,线性规划的商业软件包通常都有这种方法,最小费用流,一些实际应用,国际纸业公司(,International Paper Company,),配送网络(,Interfaces,1988,年,3/4,),世界上最大的纸浆、纸和纸类产品的制造商以及木材和夹板的主要生产者。拥有两千万英亩的林区或其权益。分布在不同地方的林区是它配送网络的供应点,供应流必须经过一系列很长的转运点,:,林区木材堆积场锯木厂造纸厂,纸制品加工厂仓库客户,最小费用流,一些实际应用,马尔萨斯公司(,Marshalls,Inc.,),配送网络(,Interfaces,1987,年,7/8,),一家折扣连锁零售店,现在和以前是如何使用微型计算机去处理一个最小费用流问题。应用中公司力图,使得从供应商到加工中心,再从加工中心到零售店的商流最优,。其中的一些网络有超过,20,000,条弧。,最小费用流,最大流问题,最大流问题也与网络中的流有关,但目标不是使得流的成本最小化,而是寻找一个流的方案,使得通过网络的流量最大。,最大流问题,最大流问题的假设,1网络中所有流起源于一个节点,这个节点叫做源,所有的流终止于另一个节点,这个节点叫做收点。(在BMZ问题中源和收点分别代表工厂和配送中心),2其余所有的节点叫做转运点。(在BMZ问题中,节点RO、BO、LI、NY和NO都是转运点),3通过每一个弧的流只允许沿着弧的箭头所指方向流动。由源发出的所有的弧背向源,而所有终结于收点的弧都指向收点。,4最大流问题的目标是使得从源到收点的总流量最大。这个流量的大小可以用两种等价的方法来衡量,分别叫做从源点出发的流量和进入收点的流量。,最大流问题,最大流问题,最小费用流问题的这些节点和最大流问题中与其对应的节点有两点区别:,第一个区别是,供应点的供应量和需求点的需求量都是固定的,而源和收点则不同。这是因为后者的目标是使得从源点出发的或进人收点的流量最大,它们的数量不是固定的。,第二个区别是,在最小费用流问题中,不管是供应点的数量还是需求点的数量都可能多于一个。而在最大流问题中只能有一个源和一个收点。但是,有多个源和收点的最大流问题的变形也能用 Excel Solver软件解决。,最大流问题,BMZ,案例研究,BMZ公司是欧洲一家生产豪华汽车的制造商。虽然它生产的汽车在所有发达国家的销量都不错,但是对于这家公司来说,出口到美国显得尤其重要。,BMZ公司因为提供优质的服务而获得很好的声誉,保持这个声誉一个很重要的秘诀是它有着充裕的汽车配件供应,从而能够随时供货给公司众多的经销商和授权维修店。这些供应件主要存放在公司的配送中心里,这样一有需求就可以立即送货。,因为总厂生产的配件量远远要大于能够运送到配送中心的量,所以,可以运送多少配件的限制条件就是该公司配送网络的容量。,最大流问题,BMZ,案例研究,BMZ,从德国斯图加特工厂到洛杉矶配送中心的配送网络,最大流问题,BMZ,案例研究,BMZ,案例的网络描述,最大流问题,BMZ,案例研究,Excel求解,最大流问题,扩展后的BMZ,问题,Excel求解,最大流问题,最短路问题,最短路问题的最普遍的应用在两个点之间寻找最短路,最短路问题,里特城消防站,里特城的消防站和某一农场社区间的道路系统,最短路问题,里特城消防站,里特城的消防站道路系统,的网络表述,最短路问题,里特城消防站,最短路问题,最短路问题的假设,网络中选择一条路,始于某源点终于目标地,连接两个节点的连线叫做边(允许任一个方向行,进),弧(只允许沿着一个方向行进),和每条边相关的一个非负数,叫做该边的长度,目标是为了寻找从源到目标地的最短路,最短路问题,最短路问题三种类型,1行进的总距离最小(上一例),2一序列活动的总成本最小,3一序列活动的总时间最小,最短路问题,使总成本最小的例子,莎拉刚刚高中毕业。在毕业典礼上,她的父母给了她21000美元的汽车基金帮助她购买并保养一辆使用了三年的二手车,以供她上大学。由于开车费用和维修费用随着汽车的老化而飞速上涨,所以莎拉的父母告诉她在接下来的三个夏天里,她也可以一次或几次折价将她的汽车置换为其他使用了三年的二手车。如果她觉得这样做可以使她的总净成本最小的话,他们会同意她这样做的。他们也告诉莎拉,在四年后,他们会送给她一辆新车作为大学毕业的礼物。所以,莎拉到那时肯定要计划把旧车折价卖出。,最短路问题,使总成本最小的例子,在接下来的三个夏天里,什么时候莎拉应该折价卖掉她的汽车仅果有必要的话)可以使得她在大学四年里买车、开车、保养汽车的总费用最小?,最短路问题,使总成本最小的例子,当把莎拉什么时候应该折价购车看成是一个最短路问题时问题的描述。节点的标号代表从现在开始计算的年份,每一条弧代表了购车然后又折价卖出。,Excel求解,最短路问题,使总时间最小的例子,奎克公司获悉它的一个竞争对手计划将把一种很有销售潜力的新产品投放市场。奎克公司也一直在研制一种类似的产品,并计划在20个月后投放市场。但是,研究临近结束,奎克公司的管理者希望迅速推出产品去参与竞争。,现在还有四个没有时间重叠的阶段没有完成,包括正以正常速度进行剩下的研究工作。然而,每个阶段的实施水平可以从正常水平提高为优先水平或应急水平,使之能够加速完成;而且最后三个阶段中都可以考虑提高实施水平。,最短路问题,使总时间最小的例子,最短路问题,使总时间最小的例子,当网络中实际行进在多于一个节点结束时,在每个这样的节点和虚拟目标地之间插入一条长度为0的弧,从而使得网络中仍然只有一个目标地。,最短路问题,最小支撑树问题,最小支撑树问题的假设,1.给你网络中的节点,但没有给你边。或者,给你,可供选择的边和如果把它插入到网络中后的每条边的正的成本(或者相似的度量),2.,在设计网络时你希望通过插入足够的边,以满足每两个节点之间都存在一条路的需要,3.,目标是寻找一种方法,使得在满足要求的同时总成本最小,最小支撑树,简单的算法,1选择第一条边:选择成本最低的备选边;,2选择下一条边:在一个已经有一条边连接的节点和另一个还没有边连接的节点之间选择成本最低的备选边;,3重复第二个步骤,直到所有的节点都有一条边(可能会有多于一条边)与其相连。此时就得到了最优解(最小支撑树)。,处理成本相同的边:当有几条边同时是成本最低的边时,任意选择一条边不会影响最后的最优解。但是,在步骤2中出现这种情况,则表明通过任意选择其他的边也可能出现其他的最优解(这也不是必然的)。,最小支撑树,默登公司铺设光缆,默登(Modem)公司的管理层已经决定铺设最先进的光导纤维网络,为它的主要中心之间提供高速通信(数据、声音和图像)下图中的节点显示了该公司主要中心(包括了公司的总部、巨型计算机、研究区、生产和配送中心)的分布图。虚线是铺设纤维光缆可能的位置。,最小支撑树,默登公司铺设光缆,最小支撑树,默登公司铺设光缆,最小支撑树,默登公司铺设光缆,最小支撑树,默登公司铺设光缆,最小支撑树,一些实际应用,电信网络(计算机网络、电话专用线网络、有线电视网络等等)的设计,低负荷运输网络的设计,使得网络中提供链接的部分(如铁路、公路等,等)的总成本最小,高压输电线路网络的设计,电器设备线路网络(如数字计算机系统)的设计,使得线路总长度最短,连接多个场所的管道网络设计,最小支撑树,本讲小结,运输问题考虑(确实的或是比喻的)从出发地运送货物到目的地。每一个出发地都有一个固定的供应量,每一个目的地都有一个固定的需求量。,指派问就要处理应当将哪一项任务指派给哪一个被指派者,才能使完成这些任务的总达到最小,。,把可能会面临的问题描述为一个运输问题或者指派问题或者它们的变形并进行分析,。,本讲小结,网络表示在描绘网络系统中各部分之间关联上非常有用,最小费用流问题的特殊类型包括运输问题和指派问题,最大流问题的目标是使得从一个特定的起点(,源,)到一个特定的终点(,收点,)的总流量最大,最短路问题也有始点(,源,)和终点(,目标地,),但是,它的目标是从源点到目标地寻找一条总,长度,最短的路,最小支撑树问题的目标是使得为任意两个节点之间提供路时总成本最小,第四讲 结束,下一讲:,项目管理及线性规划的扩展,
展开阅读全文