第六讲-运输、指派与转运问题...ppt

第六讲运输、指派与转运问题,物流管理系薛伟霞,主要内容,运输问题：网络模型与线性规划模型,指派问题：网络模型与线性规划模型,转运问题：网络图与线性规划模型,生产与库存应用,运输问题,运输问题经常出现在计划货物配送和从某些供给地区到达需求地区之间的服务中，特别是每个供给地区（起点）的货物可获得量是有限的，每个需求地区（目的地）的货物需求量是已知的。运输问题中最常用的目标是要使货物从起点到目的地的运输成本最低。,案例福斯特发电机公司的运输问题,从3个加工厂运输一种产品到4个分销中心。福斯特发电机公司在俄亥俄州的克里夫兰、印第安纳州的贝德福德和宾夕法尼亚州的约克有3个工厂，下3个月德计划期内的这个特殊型号的发电机的生产能力如下：,案例福斯特发电机公司的运输问题,公司通过坐落在波士顿、芝加哥、圣路易斯和莱克星顿的4个分销中心来分销这种发电机；每个分销中心3个月的需求预测如下：,案例福斯特发电机公司的运输问题,运输成本如下所示：,管理层想知道从每个加工厂运输到分销中心的产品运输量为多少。,网络图,圆圈表示节点，连接节点的线条表示弧。每个起点和目的地都由节点表示，每个可能的运输路线都由弧表示。供给量写在起始节点边上，需求量写在每个目的地节点边上。从起始节点到目的地节点之间运输的货物数量表示了这个网络的流量。,建立线性规划模型的步骤,1、全面地了解问题；2、描述目标；3、描述约束条件；4、定义决策变量；5、用决策变量写出目标函数；6、用决策变量写出约束条件。,描述目标和约束条件,确定使用哪些路线以及每条线路上的流量是多少时，使得总的运输成本最低。每个起点的供给能力和每个目的地的特定需求量是有限的。,定义决策变量,运用双下标决策变量。x11表示起点1(克利夫兰)运送到终点(波士顿)的货物数量，x12表示从起点1(克利夫兰)运送到终点2(芝加哥)的货物数量等等。一般来说,运输问题的决策变量有m个起点和n个终点，如下:,用决策变量写出目标函数,从克利夫兰运输货物的成本：3x112x127x13+6x14从贝德福德运输货物德成本：7x215x222x23+3x24从约克运输货物德成本：2x315x324x33+5x34这些公式的总和为我们提供了福斯特发电厂运输总成本的目标函数。,用决策变量写出约束条件,每个起点的供给能力和每个目的地的特定需求量是有限的。供给约束条件和需求约束条件,供给约束条件,克利夫兰的供给约束条件则为:x11x12x13+x145000贝德福德的供给约束条件：x21x22x23+x245000约克的供给约束条件：x31x32x33+x342500,需求约束条件,波士顿分销售中心需要量：x11+x21+x31=6000芝加哥分销售中心需要量：x12+x22+x32=4000圣.路易斯分销售中心需要量：x13+x23+x33=2000莱克星顿分销售中心需要量：x14+x24+x34=1500,福斯特公司的线性规划模型,管理科学软件求解,线性规划运输问题,问题的变化,总供给不等于总需求最大化目标函数线路容量或者线路最小量不可接受的路线,总供给不等于总需求,总供给超过总需求线性规划模型不需要进行修改。多余的供给总量在线性规划解决方案中表现为松弛。而任何起点的松弛都可以被理解为未使用的供给或者未从起点运输的货物数量。,总供给小于总需求运输问题的线性规划模型没有可行解。增加一个虚拟起点，等于不被满足的需求。从虚拟起点出发的弧上单位的运输成本为零。最优解中目的地节点处显示的运输量为这个节点需求不被满足的货物短缺量。,最大化目标函数,问题在某些运输问题中，目标是要找到最大化利润或者收入的解决方案。,解决方法把单位利润或者收入作为一个系数列入目标函数中，简单地把最小改成最大，约束条件不变，就可求得线性规划的最大值而不是最小值。,路线容量和/或路线最小量,运输问题的线性规划模型也能够包含一条或者更多的路线容量或者最小数量问题。例如：假设在福斯特公司发电机问题中，约克-波士顿路线（起点3到终点1）因为其常规的运输模式中有限空间的限制，只有1000单位的运输能力。用x31表示从约克运到波士顿的货物数量，那么约克波士顿路线容量的约束条件为：x311000同样,路线的最小量也可以得到说明。例如：x222000，这一条件保证了我们可以在最优解中继续维持先前承诺的至少2000单位的贝德福德芝加哥路线的交货订单。,不可接受的路线,构建从每一个起点到终点的路线并不都是可能的。去除网络图中相关的弧和线性规划模型中相关的变量。,运输问题的一般线性规划模型,i起点下标，i=1，2，m；j终点下标，j=1，2，n；xij从起点i到终点j的运量量；cij从起点i到终点j的单位运输成本；si起点i的供应量或者生产能力；dj终点j的需求量。,运输问题的一般线性规划模型,m个起点，n个终点的运输问题的线性规划的一般模型如下:,有容量限制的运输问题,如果从起点i到终点j之间的运输容量为Lij，增加约束条件：xijLij。如果起点i到终点j之间必须处理的运输容量最小为Mij，增加约束条件：xijMij。,练习,某种产品在3个不同的工厂生产后被运输到3个不同的仓库（下表显示了每件的运输成本），相关信息如下表。,练习,a.设计一个网络模型来求解这个问题。b.设计一个线性规划模型，该模型的目标是最小化总运输成本；求解最低成本方案。c.假设表中的数据表示在工厂i生产出来的运到仓库j的每件产品的利润，你在(b)部分所建的模型该如何变动？d.如果W2总需求变为500，试改变模型。,实践海军陆战队的调遣,美国海军陆战队已经建立了一个网络模型，以备在世界危机或者战争中用来调遣军官。这个问题要解决的就是尽可能快地把每个军官指派到合适的位置（职位指派）。起点节点或者供应节点代表现有的军官，目标节点或者需求节点代表的是职位。实际执行时有40000个军官和25000个职位。如果所有军官-职位的连接弧都是可行的，那么这个运输问题就有1亿条弧。为了减小问题的规模，相似条件的军官可以汇集成一个供应节点，相似的职位可以汇集成一个需求节点。用这个方法将不可行的弧删除，海军陆战队在10秒钟之内就通过一台个人电脑解决了包含27000个军官和10000个工作职位的指派问题。,实践海军陆战队的调遣,结果是令人满意的：合适级别和工作资历的军官都被派遣到了需要的工作岗位上。遇到危机时，如果能够获得并使用这套系统的话，他能够决定我们将对此做出适当的反应还是将去面对一场灾难。先前的系统需要24天来产生这么一个完整的分配计划且这个计划的军官资历和职位需求之间的匹配度比较低。海军陆战队利用现在这个分配模型提高了它在和平时期的运作能力。,指派问题,典型的指派问题有：将工作分配给机器，对代理分配任务，将销售人员分配给销售区域，将合同分配给投标人，等等。特征：一个代理只分配给一个任务，仅仅一个任务。,案例福尔市场调查公司,公司刚刚从3个新客户那里获得市场调查项目。公司面临着给每一个客户分配一个项目负责人的任务。最近，有3个项目负责人手上没有其他的任务，可以被分配。福尔的管理层意识到完成每个市场调研的时间取决于项目负责人的经验和能力。这3个项目具有相似的优先顺序，公司希望分配的项目负责人完成这3个项目所需的总时间最短。如果每个客户只需要一个项目负责人，那么怎么进行分配呢？,案例富尔市场调查公司,为了解决这个指派问题，福尔的管理层必须首先考虑所有可能的负责人-客户的分配方法，然后预测相对应的完成项目所需的时间。,网络模型,指派问题和运输问题的相似性？,线性规划模型,这里i1，2，3；j1，2，3。,决策变量,线性规划模型目标函数,使用表73中的符号和完成时间数据，我们得出了完成时间表达式：特瑞完成配置所用的总天数：10 x11+15x12+9x13卡尔完成配置所用的总天数：9x21+18x22+5x23迈克孟德完成配置所用的总天数：6x31+14x32+3x33,目标函数：MinZ=10 x11+15x12+9x13+9x21+18x22+5x23+6x31+14x32+3x33,线性规划模型约束条件,保证每个负责人能够被至多分配给一个客户且每个客户必须有一个分配过来的负责人。x11+x12+x131对特瑞的指派x21+x22+x231对卡尔的指派x31+x32+x331对迈克孟德的指派x11+x21+x311客户1x12+x22+x321客户2x13+x23+x331客户3,福尔公司指派问题的线性规划模型,管理科学软件求解结果,ObjectiveFunctionValue=26.000VariableValueReducedCostsx110.0000.000 x121.0000.000 x130.0003.000 x210.0000.000 x220.0004.000 x231.0000.000 x311.0000.000 x320.0003.000 x330.0001.000,福尔公司问题的最优项目负责人指派,Assignment模块求解结果,问题的变化,总的代理（供给）数不等于总的任务（需求）数。目标函数最大化。不可接受的分配。,指派问题的一般线性规划模型,一般指派问题包括m个代理和n项任务。令xij=1或者0来表示代理i是否分配给任务j，如果cij表示把代理i分配给任务j所花的成本，一般指派模型如下：,多种指派,假设：福尔公司问题中的特瑞能被指派给两个客户，增加约束条件：x11+x12+x132一般情况下，如果ai表示代表i能够被指派的任务的最高上限，我们可以把代理约束条件写成如下形式：,实践HerryInternational,HerryInternational与田纳西州等多方客户签订了各种建设项目的合同，包括高等教育设施、旅馆和停车场。在任何一个时间点上，Herry都有100多个正在进行的项目。每个项目必须单独指派一个主管。如果7个主管可以指派的话，有多于7007100种可能的指派。在外来顾问的协助下，HerryInternational设计出了一个给项目指派建筑主管的数学模型。,实践HerryInternational,Herry设计出的指派模型对于每个主管和项目组合使用0/1决策变量，就如前边讨论过的指派问题一样。指派主管的目标是为了平衡每个主管之间的工作负担，在同一个时间内最小化从主管家到建筑项目的工作地点之间的交通成本。由此得出了关于每个可能的指派目标函数系数：将项目强度（一个关于项目预算大小的函数）和从主管人员的家到建筑工地的交通距离组合起来。目标函数要求所有的指派变量的系数总和最小。,实践HerryInternational,由于建筑项目多于主管人数，所以必须考虑对包含了多种指派的标准指派问题进行修改。有两组约束条件，一组要求每个项目有一个并只能有一个主管；另一组通过限制所有被指派项目的总的可接受强度来限制每个主管接到的指派的任务量。HerryInternational实行了这个指派模型，产生了很好的效果。据副总裁EmoryF.Redden称：“最优化模型对于我们指派主管到项目很有帮助，我们对于纳什维尔分部的指派就很满意，我们希望将这种模型应用于我们的亚特兰大及Herry集团的每一个分部。”,练习,美国电缆公司利用包括5个分销中心、8个客户区域的分销系统分销产品。配给每个客户区域一个专门的资源供应商，且其所有电缆产品都来自同一分销中心。为了能平衡分销中心的客户需求和雇员的工作量，公司负责物流的副总裁特别指明一个分销中心最多负责3个客户区。下面的表格就是这5个分销中心以及每个客户区的供给成本（单位：1000美元）：1、设计一个表述该问题的网络图。2、构建一个该问题的线性规划模型，并求解得出使总成本最小的最优解。3、如果有，哪一分销中心没有分派任务？4、假设每个分销中心最多只能负责两个客户区，那么这个限制条件将如何改变指派和客户区的供给成本？,练习,转运问题,运输问题的扩展，其中中间节点代表转运节点，加入这个节点的目的是指代地点位置，例如仓库。,案例瑞恩电子公司的转运问题,瑞恩电子是一家电子公司，其生产线分别位于丹佛和亚特兰大，在每条生产线上生产出来的商品都可以被运送到公司在堪萨斯城或者是路易斯维尔地区的仓库中，公司把这些地区的仓库中的商品发给底特律、迈阿密、达拉斯和新奥尔良的零售商。,600,400,200,300,350,150,网络图,线性规划模型,决策变量：令xij代表从节点i到节点j运输的件数。,目标函数：运输线路的总运输成本最小,起点节点约束：输出的总量减去输入的总量必须小于或等于该节点的商品供给量,终点节点约束：输入的总量减去输出的总量必须等于该节点的需求。,转运节点约束：输出的总量必须等于输入的总量。,瑞恩电子问题的线性规划模型,管理科学软件求解结果,ObjectiveFunctionValue=5200.000VariableValueReducedCostsx13550.0000.000 x1450.0000.000 x230.0003.000 x24400.0000.000 x35200.0000.000 x360.0001.000 x37350.0000.000 x380.0000.000 x450.0003.000 x46150.0000.000 x470.0004.000 x48300.0000.000,瑞恩电子转运问题的最优解,更一般的转运问题,假设可以直接从亚特兰大运输商品到新奥尔良，单位运输费用为4美元，且从达拉斯运到新奥尔良的单位运费为1美元。,1,2,4,3,8,7,6,5,工厂开始节点,仓库转载节点,丹佛600,亚特兰大400,底特律200,迈阿密150,达拉斯350,新奥尔良300,堪萨斯城,路易斯维尔,2,3,3,1,2,6,3,6,5,6,4,4,4,1,线性规划模型,软件求解结果,问题的变化,总供给不等于总需求最大化目标函数路线容量或者路线最小量（有容量限制的转运问题）不可接受的路线,转运问题的一般线性规划模型,这里，xij表示从节点i到节点j的运量；cij表示从节点i到节点j的单位运价；si表示起点节点i的供给量；dj表示终点节点j的需求量。,实践宝洁公司在产品供应上的启发式探索,几年前，宝洁公司开始了一个重大战略计划，称为北美产品供应研究。宝洁公司想综合运用它的资源供应，最优化其北美的产品