数据、模型与决策（原书第16版）课件 第6章、分配与网络模型

AnIntroductiontoManagementScience,16e第六章、分配与网络模型章节内容6-1 供应链模型6-2 指派问题6-3 最短路径问题6-4 最大流问题6-5 生产和库存应用章节目标完成本章后，你将能够:LO6.1

建立并求解运输问题的网络和线性规划模型LO6.2 建立并求解指派问题的网络和线性规划模型LO6.3 建立并求解转运问题的网络和线性规划模型LO6.4 建立并求解最短路径问题的网络和线性规划模型LO6.5 建立并求解最大流问题的网络和线性规划模型介绍本章讨论的模型属于一类特殊的线性规划问题，通常被称为网络流问题。网络流问题包括供应链管理中常见的运输问题和转运问题，和其他三种类型：指派问题

、最短路径问题和最大流问题。在每一个问题中，我们将以网络的形式建立问题的图解模型，然后说明每个问题是怎样被构建成线性规划模型并进行求解的。6-1供应链模型：运输问题供应链供应链是一个产品从生产到分销涉及的所有相互联系的资源集合。一般来说，供应链的设计目标是以最小的成本满足顾客对某种产品的需求。控制供应链的主体必须做出很多决策，比如在哪里生产产品、生产多少产品、在哪里销售产品。我们将会介绍两种在供应链模型中普遍存在，并且可以使用线性规划解决的问题：运输问题转运问题运输问题运输问题经常出现在规划货物从某些供应地区到达某些需求地区之间的配送服务中。通常，每个供应地区（起点）可提供的货物量是有限的，并且每个需求地区（终点）的货物需求的已知的。运输问题中常见的目标是要使货物从起点到终点的运输总成本最低。现在我们考虑福斯特发电机公司面临的运输问题——将产品从3个工厂运输到4个配送中心。6-1福斯特发电机公司：运输问题供给福斯特发电机公司希望确定应该从每个加工厂运输多少产品量到每个配送中心。福斯特发电机公司在俄亥俄州的克利夫兰、印第安纳州的贝德福德和宾夕法尼亚州的约克有3个加工厂。某一特殊型号的发电机在今后3个月的计划期内的生产能力如下：需求公司通过位于波士顿、芝加哥、圣路易斯和莱克星顿的4个配送中心来配送这种发电机。每个配送中心这3个月的需求预测如下：6-1福斯特发电机公司：网络表示（网络图）右图显示了福斯特可以用的12条配送路线。供给量写在每个起始节点的左侧，需求量写在每个目的节点的右侧。每个起点和终点都由节点表示；每个可能的运输路线都由弧表示，每条弧都表示出了每条路线上每件货物的运输成本。从起始节点到目的节点之间运输的货物量表示了这个网络中的流量。（流向用箭头表示）福斯特发电机公司的这个运输问题的目标是决定要使用哪些线路以及通过每条线路的流量，使总运输成本最小。6-1福斯特发电机公司：问题表达方法决策变量

目标函数

6-1福斯特发电机公司：约束条件供给

需求

6-1福斯特发电机公司：完整的LP模型联合目标函数和这些约束条件构成了一个线性规划模型，这个福斯特发电机公司运输问题是一个含有12个变量和7个约束的线性规划模型：s.t.6-1福斯特发电机公司：结果与解释福斯特发电机公司问题的最优目标函数值和最优决策变量如右图所示，其中，最小的总运输成本为39500美元。该图表总结了网络图的最优解，决策变量的值显示了每条线路运输的最优运输量。例如，应当将3500个单位的发电机从克利夫兰运输到波士顿，应当将1500个单位的发电机从克利夫兰运输到芝加哥。6-1运输问题：一般化的LP模型

6-1供应链模型：转运问题转运问题转运问题是运输问题的一种扩展，其中中间节点代表转运节点，加入这个节点是为了考虑诸如仓库等的位置。在这种更加普遍的分销问题中，运输可能发生在3个一般类型的节点的任意两个之间。这3中节点为：起始节点、转运节点和目的节点。就如在运输问题中一样，每个起始节点的可得供应量是有限的，每个目的节点的需求也是确定的。在转运问题中，目标是在满足目的节点需求的基础上，确定网络图中每条弧线上应该运输多少单位的货物，才能使得总运输成本最低。让我们看看瑞恩电子所面临的转运问题。瑞恩电子是一家电子公司，其加工厂分别位于丹佛和亚特兰大。从每个工厂生产出来的零件可能被运送到公司在堪萨斯城或路易斯维尔的地区仓库中。公司把这些地区仓库中的商品供应给底特律、迈阿密、达拉斯和新奥尔良的零售商。瑞恩电子6-1瑞恩电子：网络表示（网络图）

6-1瑞恩电子：约束条件

6-1瑞恩电子：完整的LP模型联合目标函数和这些约束条件构成了一个线性规划模型，瑞恩电子公司的转运问题是一个含有12个变量和8个约束的线性规划模型：s.t.6-1瑞恩电子：结果与解释瑞恩电子转运问题的最优目标函数值和最优决策变量表明其最小的总运输成本为52000美元。下表显示了7个节点的产品运输量。注意，亚特兰大-堪萨斯城、堪萨斯城-迈阿密、堪萨斯城-新奥尔良、路易斯维尔-底特律和路易斯维尔-达拉斯这5个节点不是活动节点。6-1转运问题：一般化的LP模型

6-1供应链问题的变化基本的运输问题或者转运问题的变化可能涉及以下的情况:1、总供应不等于总需求：若总供给大于总需求，不需要修改LP模型，在LP的求解中，用松弛变量来表达过剩供给。若总供给小于总需求，则LP模型没有可行的解。在这种情况下，需要添加一个虚拟的起始节点，其供给等于总需求与总供给之差。2、最大化目标函数：当使用最大化目标函数来找到一个使利润或收入最大化的解决方案时，不会对约束条件产生影响。3、路线容量或者路线最小量：运输问题或者转运问题的LP模型可以容纳对一条或多条线路的容量或最小数量的约束。4、不可接受的线路：建立从每个起点到每个终点的线路有时是不可能的。为了处理这种情况，我们需要从网络图中删除相应的弧，并从线性规划模型中删除相对应的变量。6-2指派问题介绍指派问题出现在多种决策过程中，典型的指派问题包括:将工作指派给机器，将任务指派给代理商，将销售人员指派到销售区域，将合同指派给投标人等。指派问题的一个显著特征是只能给一个代理商指派一个任务。特别是我们在寻找一组能够最优化设定的目标的指派，例如成本最小、时间最短或者利润最大。福尔市场研究公司让我们来考虑福尔市场研究公司的案例。这个公司刚刚从3个新客户那里拿到市场研究项目。公司面临着将项目负责人(代理)指派给每一个客户(任务)的任务每个市场调研的时间将取决于指派的项目负责人的经验和能力。这3个项目具有相似的优先顺序，公司希望指派过去的项目负责人全部完成这3个项目所需的时间最短。每个项目负责人只能指派给一个客户6-2福尔公司：网络表示（网络图）福尔管理层必须首先考虑所有可能的项目负责人一客户的指派方法，然后预测相对应的项目完成时间。3个项目负责人和3个客户可以产生9种可能的指派方案。下表总结了各种可能的指派方案和预计项目完成时间。（注意指派问题的网络图和运输问题的网络图之间的相似性。）6-2福尔公司:问题表达方法决策变量

目标函数和约束条件

6-2福尔公司：完整的LP模型把目标函数和约束条件组合在一起形成一个模型，下面就是具有9个变量和6个约束条件的福尔公司指派问题的线性规划模型：s.t.6-2福尔公司:结果与解释

6-2指派问题的变化指派问题的变化可能涉及以下一种或多种情况:1.总的代理(供应)数不等于总的任务(需求)数：如果代理数多于任务数，则不需要修改LP模型，并且多余的代理将不被指派出去。如果代理数少于任务数，那么线性规划模型就没有可行解了。在这种情况下,一种简单的修正方法就是加人足够多的虚拟代理，使代理数等于任务数。目标函数的最大化:如果指派的备选方案是根据收益或者利润而不是时间或者成本进行评价的，那么线性规划模型可以被当作最大化而不是最小化问题来处理。不可接受的指派:如果一个或者更多的指派是不可接受的，那么相对应的决策变量应当从线性规划模型中删除。例如，如果其中一个代理没有这个任务或者更多任务所需的必要经验，这种情况可能发生。6-2指派问题：一般化的LP模型

6-3最短路径问题介绍最短路径问题的目标是确定一个网络内它的两个节点间的最短路径或线路。如果网络中所有的弧线都是非负值，则可以使用标号法来寻找从特定节点到网络中所有其他节点的最短路径。在最短路径问题中，尽管使用了“最短”一词来描述过程，但最小化的准则并不局限于距离。其他标准包括时间和成本。(时间和成本都不一定与距离成线性关系)Gorman建筑公司Gomman建筑公司想要确定一条能够最小化Gomman建筑公司的办事处(坐落在节点1)和坐落在节点6的建筑工地间的总行程距离的路径。6-3Gorman公司:网络表示（网络图）为最短路径问题建立模型的关键是要理解该问题是转运问题的一个特例。起始节点：节点1；转运节点：节点2-5；目的节点：节点6增加到弧线上的箭头显示了货流的方向，它们总是从起始节点出来，并进人目的节点。注意到在成对转运节点之间也存在两个方向的孤线。在任何一个方向上，两个转运节点间的距离是相同的。为了找到节点1到节点6的最短路径，我们认为节点1有1单位的供应量，并且节点6有1单位的需求。6-3Gorman公司:问题表达方法决策变量和目标函数

约束条件

6-3Gorman公司:完整的LP模型把目标函数和约束条件组合在一起形成一个模型，下面就是具有13个变量和6个约束条件的Gorman公司最短路径问题的线性规划模型：s.t.6-3Gorman公司:结果与解释

6-3最短路径问题:一般化的LP模型

6-4最大流问题介绍最大流问题的目标是确定最大数量的流量(交通工具、信息、液体等)，它们能够在一个给定时期内流入和流出一个网络系统。由于网络不同弧线上的能力限制，流量的数量也被限制了。例如，在交通系统中，高速公路的类型限制交通工具的流量。而在石油分配系统中，管道的大小限制石油流量。弧线上流量的最大或最高限制被称作弧线的流通能力。即使不明确说明各节点的能力，我们也要假定流出一个节点的流量等于流人该节点的流量。辛辛那提高速公路系统每条弧的流向被指明了，而且弧的通过能力标注在每条弧的旁边。注意，大部分的街道是单向的。然而,在节点2和节点3之间，以及节点5和节点6之间存在双向的街道。6-4高速公路系统:网络表示（网络图）

6-4高速公路系统:约束条件对于每一个节点，流量守恒约束条件表示需要流出必须等于流入。或者用另一种方式陈述是，流出减去流人必须等于0。节点流出流入1234567

6-4高速公路系统:结果和解释这个拥有15个变量、21个约束条件的线性规划问题的最优解表明穿过高速公路系统的最大流量是每小时14000辆车。下图显示了车流量（以千辆车为单位）是怎样穿过起始的高速公路网的。6-5生产和库存应用运输和转运模型涉及从几个供应地或产地到几个需求地或目的地之间的货物运输的应用。转运模型能够被用来求解生产调度和库存问题。康托斯毛毯厂是一家生产家用和办公室毛毯的小型生产商。其生产能力、需求和生产成本随着季度的不同而变化，然而库存成本从一个季度到下一个季度一直是0.25美元/码。康托斯毛毯厂要决定每个季度生产多少平方码的毛毯，才能使这4个季度的总生产和库存成本最低。6-5康托斯毛毯厂:网络表示（网络图）我们先建立这个问题的网络图。创建对应于每个季度生产的4个节点，和对应于每个季度需求的4个节点。每个生产节点由一条流出的弧线连接到同一时期的需求节点，弧线上的流量表示这个季度生产的毛毯的平方码数。对于每个需求节点，流出的弧线代表了库存中持有到下一个季度需求节点的数量(毛毯的平方码数)。节点1到节点4表示每个季度的生产量，节点5到节点8表示每个季度的需求量。每个季度的生产能力显示在左边缘，每个季度的需求显示在右边缘。6-5康托斯毛毯厂:问题表达方法决策变量和目标函数

约束条件

6-5康托斯毛毯厂:完整的LP模型把目标函数和约束条件组合在一起形成一个模