第6章分配与网络模型ppt课件.ppt

《第6章分配与网络模型ppt课件.ppt》由会员分享，可在线阅读，更多相关《第6章分配与网络模型ppt课件.ppt（44页珍藏版）》请在三一办公上搜索。

1、第六章 分配与网络模型,教 师：朱玉春 教授单 位：经济管理学院 2011年,西北农林科技大学,本章主要内容,6.1 运输问题6.2 指派问题6.3 转运问题6.4 最短路径问题6.5 最大流问题6.6 生产和库存应用,运输问题经常出现在计划货物配送和从某些供给地区到达某些需求地区之间的服务中，特别是每个供给地区的货物可获得量是有限的，每个需求地区的货物需求量是已知的。运输问题中最常用的目标是要使货物从起点到目的地的运输成本最低。让我们通过考虑福斯特发电机公司面临的这个运输问题来进行介绍。这个问题包括从3个加工厂运输一种产品到4个分销中心。福斯特发电机公司在俄亥俄州的克里夫兰、印第安纳州的贝德

2、福德和宾夕法尼亚州的约克有3个加工厂，下3个月的计划期内的这个特殊型号的发电机的生产能力以及坐落在波士顿、芝加哥、圣路易斯和莱克星顿的4个分销中心3个月的需求预测，详见教材162页。,6.1 运输问题,6.1 运输问题,6.1 运输问题,管理者想知道从每个加工厂运输到分销中心的产品运输量应为多少。图6-1显示了12条福斯特公司可以用的配送路线。这种图称为网络图；圆圈表示节点，连接节点的线条表示弧。每个起点和目的地都由节点表示，每个可能的运输路线都由弧表示。供给量写在起始节点边上，需求量写在每个目的地节点边上。从起始节点到目的地节点之间运输的货物数量表示了这个网络的流量。注意：直接流量（从起点到

3、终点）是用带箭头的线条表示的。,6.1 运输问题,6.1 运输问题,对应这个福斯特公司的运输问题的目标是要确定使用哪些路线以及每条线路上的流量是多少时，使得总的运输成本最低。每条线路单位产品的运输费用在图6-1中的每条弧上标明。线性规划模型可以用来解决这类运输问题，我们将用双下标决策变量来描述变量。一般情况下，一个有m个起点和n个目的地的运输问题的决策变量常被表示成以下形式：xij从起点i到目的地j之间的运输量 式中，i=1,2,3,.,m,j=1,2,3,.,n。根据所给信息，我们可以构建一个有12个变量，7个约束的线性规划模型,6.1 运输问题,Max 3x11+2x12+7x13+6x1

4、4+7x21+5x22+2x23+3x24+2x31+5x32+4x33+5x34 s.t.x11+x12+x13+x14 5000 克里夫兰供给 x21+x22+x23+x24 6000 贝德福德供给 x31+x32+x33+x34 2500 约克供给 x11+x21+x31=6000 波士顿需求 x12+x22+x32=4000 芝加哥需求 x13+x23+x33=2000 圣路易斯需求 x14+x24+x34=1500 莱克星顿需求 xij 0，其中，i=1,2,3；j=1,2,3,4,比较线性规划模型与图6-1中的网络，会发现几个观察值。所有线性规划模型所需的信息都能在网络图中找到，每

5、个节点需要一个约束条件，每一条弧需要一个变量。对应的每个起点节点出发的每条弧上的变量值之和必须小于或者等于这个起点节点的供给，对应的去往每个目的地节点的弧上的变量值之和必须等于这个目的地节点的需求,6.1 运输问题,6.1.1 问题的变化 福斯特公司发电机问题阐述了基本的运输模型的应用，基本运输模型的变化可能有以下几种情况：1、总供给不等于总需求 通常情况下总供给不等于总需求。如果总供给超过总需求，线性规划模型不需要修改。多余的供给总量在线性规划解决方案中表现为松弛。而任何起点的松弛都可以被理解为未使用的供给或者未从起点运输的货物数量。如果总供给小于总需求，运输问题的线性规划模型没有可行解，在

6、这种情况下，我们可以对网络图做如下修改：增加一个虚拟起点，这个起点的供给恰好等于不被满足的需求。增加从这个虚拟起点到每个终点的弧，线性规划模型就会有可行的解决办法了。我们规定每条从虚拟起点出发的弧上单位的运输成本为0。,6.1 运输问题,这样，经过修改的问题的最优解将会代表实际运输的货物的运输成本（从虚拟起点出发的线路没有实际运输发生）。当我们执行这个最优解时，目的地节点处显示的运输量是这个节点需求不被满足的货物短缺量。2、最大化目标函数 在某些运输问题中，目标是要找到最大化利润或者收入的解决方案。这种情况下我们只要把单位利润或者收入作为一个系数列入目标函数中，简单地把最小改成最大，约束条件不

7、变，就可求得线性规划的最大值而不是最小值。3、路线容量和或路线最小量 运输问题的线性规划模型也能够包含一条或者更多的路线容量或者最小数量问题。例如，假设在福斯特公司发电机问题中，约克波士顿路线（起点3到终点1）因为其常规的运输模式中有限空间的限制，只有1000单位的运输能力。用x31表示约克波士顿线路的运输量，那么这条线路的运输能力约束为：x31 1000，类似地，路线的最小量也可以确定下来。,6.1 运输问题,例如，x22 2000，这个约束条件保证了最优解中保留先前承诺的最小2000单位的订单。4、不可接受的路线 最后一种情况，构建从每一个起点到终点的路线并不都是可能的。为了处理这种情况，

8、我们只需要简单地去除网络图中相关的弧和线性规划模型中相关的变量。例如，如果克里夫兰圣路易斯之间的路线是不可接受的或者是不可用的，那么在图6-1中，从克里夫兰到圣路易斯之间的这条弧应当删除。线性规划模型中的变量x13也应当被删除。解决这个有11个变量和7个约束条件的线性规划模型得出的最优解的同时，也保证了克里夫兰圣路易斯之间的线路不被使用。,6.1 运输问题,6.1.2 运输问题的一般线性规划模型 为了表示这个运输问题的一般线性规划模型，我们将用到下列概念：i起点下标，i=1，2，.，m；j终点下标，j=1，2，.，n；xij起点i到终点j之间的运输量；cij起点i到终点j之间的单位运输成本；s

9、i起点i的供应量或者生产能力；dj终点j的需求量。m个起点，n个终点的运输问题的线性规划的一般模型如下：,6.1 运输问题,6.1 运输问题,m个起点，n个终点的运输问题的线性规划的一般模型如下：min s.t.i=1，2，.，m 供给 j=1，2，.，n 需求 xij 0，对所有i和j 就如先前我们提到的，如果从起点i到终点j之间的运输容量为Lij，可以在约束里加一个xij Lij，一个包含了这种类型的约束条件的运输问题就称为有容量限制的运输问题。类似地，如果起点i到终点j之间必须处理的运输容量最小为Mij，那么我们在约束条件里加上最小运输容量约束xij Mij。,很多决策过程都会产生指派问

10、题。指派问题中一个很明显的特征是一个代理只分配给一个任务，仅仅一个任务，特别是我们寻找一组能够最优化所设立的目标的分配，例如成本最小、时间最短或者利润最大。为了阐述指派问题，让我们来看看福尔市场调查公司的案例，这个公司刚刚从3个新客户那里获得市场调查项目。公司面临着给每一个客户分配一个项目负责人的任务。最近有3个项目负责人手上没有其他任务，可以被分配。这3个项目具有相似的优先顺序，公司希望分配的项目负责人完成这3个项目所需总时间最短。如果每个客户只需要一个项目负责人，那么该怎么分配？为了解决这个指派问题，福尔的管理层必须首先考虑所有可能的负责人客户的分配方法，然后预测相对应的完成项目所需的时间

11、。3个项目负责人和3个客户可以产生9种分配方案。,6.2 指派问题,6.2 指派问题,6.2 指派问题,图6-2是福尔公司指派问题的一个网络图。节点对应着项目负责人和客户，弧代表项目负责人客户之间的可能分配。每个起点节点的供给和终点节点的需求都是1；把一个项目负责人指派给一个客户的成本是这个负责人完成客户的市场调研任务所需的时间。注意指派问题的网络图（图6-2）和运输问题的网络图（图6-1）之间的相似性。这个指派问题其实就是运输问题的一个特殊情形，其中所有的供给和需求量都是1，每条弧的运输量不是1就是0。因为这个指派问题就是运输问题的一个特殊实例，那么可以设计一个线性规划模型。定义福尔公司指派

12、问题的决策变量为：,这里，i=1，2，3；j=1，2，3。,根据所给信息，我们可以得到一个具有9个变量和6个约束条件的福尔公司指派问题的线性规划模型：min 10 x11+15x12+9x13+9x21+18x22+5x23+6x31+14x32+3x33 s.t.x11+x12+x13 1 对特瑞的指派 x21+x22+x23 1 对卡尔的指派 x31+x32+x33 1 对迈克孟德的指派 x11+x21+x31=1 客户1 x12+x22+x32=1 客户2 x13+x23+x33=1 客户3 xij 0，其中，i=1，2，3；j=1，2，3。,6.2 指派问题,模型的计算机计算结果如下，

13、特瑞被指派给了客户2，卡尔被指派给了客户3，迈克孟德被指派给了客户1。总的项目完成时间为26天。,6.2 指派问题,6.2.1 问题的变化 因为指派问题可以被看做一个运输问题的特例，那么指派问题中可能出现的变化就和运输问题中出现的变化相似，所以我们能够处理下面的情形：1.总的代理（供给）数不等于总的任务（需求）数。2.目标函数最大化。3.不可接受的分配。代理数不等于任务数时的情形和运输问题中总供给不等于总需求时类似。在线性规划模型中，如果代理数多于任务的数量，多余的代理将不被指派。如果任务数多于代理数，那么线性规划模型就没有可行的解决方案。在这种情况下，一种简单的修正方法就是加入足够多的虚拟代

14、理，使代理数等于任务数。,6.2 指派问题,比如说，在福尔公司问题中，我们有5个客户（任务）和3个项目负责人（代理）。在加入两个虚拟的项目负责人后，我们可以建立一个新的项目负责人与客户数量相等的指派问题。虚拟项目负责人的指派问题的目标函数系数设为0，这样最优解的值就代表进行指派的实际所需天数（虚拟负责人的指派是实际上不进行的）。如果指派的备选方案是根据收入或者利润而不是时间或者成本进行评价的，那么线性规划模型可以处理成最大化而不是最小化问题。另外，如果一个或者更多的指派是不可接受的，那么相对应的决策变量应当从线性规划模型中删除。这种情况可能发生，例如，如果其中一个代理没有这个任务或者更多任务所

15、需的必要经验。,6.2 指派问题,6.2 指派问题,6.2.2 指派问题的一般线性规划模型 为了展示包括m个代理和n个任务的指派问题的一般线性规划模型，我们做如下设定：cij=把代理i指派给任务j所花的成本,6.2 指派问题,该一般线性规划模型如下所示：min s.t.i=1，2，.，m 代理 j=1，2，.，n 任务 xij 0，对所有的i和j,在本节一开始，我们就指出指派问题有一个明显的特征，一个代理只能被指派给一个任务。对于一个代理可以被分配给两个或者更多个任务的广义指派问题，我们可以对线性规划模型进行简单修正。例如，假设福尔公司问题中特瑞能够被指派给两个客户；在这种情况下，代表特瑞指派

16、的约束条件就为x11+x12+x13 2。一般情况下，如果ai表示代理i能够被指派的任务的最高上限，那么我们把代理约束写成如下形式：i=1，2，.，m 因此，我们发现把指派问题像线性规划模型一样构建和求解的一个好处就是，特殊情形，例如涉及多种指派的情况，比较容易处理。,6.2 指派问题,6.3 转运问题,转运问题是运输问题的扩展，其中中间节点代表转运节点，加入这个节点的目的是指代地点位置。在更为普遍的指派问题类型中，出货发生在3个一般类型节点的任意两个之间。这3种节点为：起点节点、转运节点和终点节点。就如在运输问题中一样，每个起点节点的可得的供给是有限的，每个终点节点的需求也是确定的。在转运问

17、题中，目标是在满足终点节点需求的基础上，确定网络图中每条弧上运输多少单位，才能使总的运输成本最低。瑞恩电子是一家电子公司，其生产线分别位于丹佛和亚特兰大，在每条生产线上生产出来的商品都可以被运送到公司在堪萨斯或者是路易斯维尔地区的仓库中，公司把这些地区的仓库中的商品发给底特律、迈阿密、达拉斯和新奥尔良的零售商。图6-3显示了网络模型中的每条弧以及这个问题的关键特征。注：每个起点节点的供给量和每个终点节点的需求量都在其旁边标明。,6.3 转运问题,对于运输和指派问题，我们可以构建一个线性规划模型；对于网络图表示的转运问题，我们也可以构建一个线性规划模型。同样，我们也需要给每一个节点和每条弧上的变

18、量一个约束。令xij表示从节点i运输到节点j的运输数量。根据所给信息，我们可得到一个具有12个变量、8个约束条件的线性规划模型：min 2x13+3x14+3x23+x24+2x35+6x36+3x37+6x38+4x45+4x46+6x47+5x48 s.t.x13+x14 600 x23+x24 400-x13-x23+x35+x36+x37+x38=0-x14-x24+4x45+4x46+6x47+5x48=0,6.3 转运问题,6.3 转运问题,6.3 转运问题,6.3.2 转运问题的一般线性规划模型 转运问题的一般线性规划模型如下：min s.t.起点节点i 转运节点 终点节点j 其

19、中，xij 0，对所有的i，j xij节点i到节点j之间的运输量；cij节点i到节点j之间的单位运输成本；Si起点节点i的供给量；dj终点节点的需求量。,6.3 转运问题,6.4 最短路径问题,本节我们将探讨这样一个问题，它的目标是确定一个网络内两个节点间的最短路径或路线。我们将通过分析Gorman建筑公司所面临的情况来讲解最短路径问题。Gorman的办事处和每一个建筑地点之间的行程选择可以用公路网络来描述，如图6-4所示。节点之间的道路距离显示在相应弧线的上面。Gorman想要确定一条能够最小化Gorman的办事处（坐落在节点1）和坐落在节点6的建筑地点间的总行程距离的路径。,Gorman办

20、事处,图6-4,路程的英里数,25,5,20,1,2,3,3,7,4,6,6,4,5,14,4,6.4 最短路径问题,注意：1.每一条弧的长度不是必然和它代表的行驶路程成正比例 2.所有的道路都是双向的；因此流向可能在任一方向中。,为最短路径问题建立模型的关键是要理解该问题是转运问题的一个特殊事例。具体来说，Gorman最短路径问题可以被看成是一个带有一个起始节点（节点1）、一个目标节点（节点6）以及4个转运节点（节点2，3，4和5）的转运问题。为了找到节点1到节点6的最短路径，我们认为节点1有一单位的供给量，并且节点6有一个单位的需求。令xij为从节点i到节点j流动或被传送的单元数。如果xi

21、j=1，则从节点i至节点j的弧线在从节点1至节点6的最短路径上；如果xij=0，则从节点i至节点j的弧线不在该最短路径上。因为我们正在寻找节点1到节点6的最短路径，得出Gorman问题的目标函数是：min 25x12+20 x13+3x23+3x32+5x24+5x42+14x26+6x35+6x53+4x45+4x54+4x46+7x56 再加上一些约束条件，我们可以得到Gorman问题的线性规划模型如下：,6.4 最短路径问题,min 25x12+20 x13+3x23+3x32+5x24+5x42+14x26+6x35+6x53+4x45+4x54+4x46+7x56 s.t.x12+x

22、13=1 起始节点-x12+x23-x32+x24-x42+x26=0 转运节点-x13-x23+x32+x35-x53=0 转运节点-x24+x42+x45-x54+x46=0 转运节点-x35+x53-x45+x54+x56=0 转运节点 x26+x46+x56=1 目标节点 对于所有的i和j，xij 0,6.4 最短路径问题,为了表示最短路径问题的一般线性规划模型，我们使用下面的定义：cij=与从节点i到节点j的弧线相关的距离，时间或费用。最短路径问题的一般线性规划模型如下所示：,xij=,0 反之,1 如果从节点i到节点j的弧线在最短路径上,6.4 最短路径问题,Min s.t.起始节

23、点i 转运节点 目标节点j,6.4 最短路径问题,最大流问题的目标是确定最大数量的流量，它们能够在一个给定时期内进入和退出一个网络系统。在这个问题中，我们尝试着通过网络的所有弧线尽可能有效地传递流量。由于网络不通弧线上的能力限制，流量的数量也被限制了。弧线上流量的最大或最高限制被称为弧线的流通能力。在我们不明确说明各节点的能力时，我们都假定流出一个节点的流量等于进入该节点的流量。作为最大流问题的一个例子，我们考虑穿过辛辛那提和俄亥俄的南北向洲际高速公路系统。我们将出示怎样为这个最大流问题建立一个限制容量的转运模型。首先，我们添加一条从节点7回到节点1的弧线，来表示穿过高速公路系统的总流量。图6

24、-5是标有弧流通能力的网络图，每条弧的流向被指明了，而且弧能力标注在每条弧的旁边,6.5 最大流问题,6.5 最大流问题,6.5 最大流问题,新增的弧线没有通过能力限制，事实上，我们希望最大化通过那条弧线的流量。最大化从节点7到节点1弧线的流量等于穿过途径辛辛那提的南北向高速公路系统的汽车数量。决策变量为：xij=从节点i到节点j的交通流量数。能最大化高速公路系统流量的目标函数是：max x71。对于所有转运问题，每个弧产生一个变量，并且每个节点产生一个约束。对于每一个节点，流量守恒约束表示需要流出必须等于流入。对于节点1，其流出是x12+x13+x14，流入是x71。故而，节点1的约束是：x

25、12+x13+x14-x71=0。其他六个节点同理可得相应约束。,6.5 最大流问题,对于弧的通过能力，我们需要另外一些约束条件加以限制。下面给出了14个简单的上界约束。x12 5;x13 6;x14 5;x23 2;x25 3;x32 2;x34 3;x35 3;x36 7;x46 5;x56 1;x57 8;x65 1;x67 7.注意，没有能力限制的仅有弧线，就是我们从节点7到节点1添加的那一条。,6.5 最大流问题,6.6 生产与库存应用,在6.1节和6.3节中介绍的运输和转运问题主要涉及从几个供应地或产地到几个需求地或目的地之间的货物运输的应用。虽然货物的运输是许多运输和转运问题的主

26、题，但是运输或转运模型可以被应用于起点和终点之间没有任何实物运输的情况。在本节，我们来介绍如何运用转运模型来求解生产调度和库存问题。康托斯毛毯厂是一家生产家用和办公室毛毯的小型生产商，其要决定每个季度生产多少平方码的毛毯，才能使这4个季度的总生产和库存成本最小。我们先建立这个问题的网络示意图，第一步，创建对应于每个季度生产的4个节点，和对应于每个季度需求的4个节点。每个生产节点由一条流出的弧线连接到同一时期的需求节点上，弧线上的流量表示这个季度生产的毛毯的平方码数。对于每个需求节点，流出的弧线代表了库存中持有到下一个季度需求节点的数量（毛毯的平方码数）,6.6 生产与库存应用,上图中。节点1到

27、节点4表示每个季度的产量，节点5到节点8表示每个季度的需求。每个季度的生产能力显示在左边，每个季度的需求显示在右边。决策目标是确定使4个季度的生产和库存总成本最小的生产调度和库存策略。约束条件包括每个季度的生产能力和需求。一般来讲，通过建立每个节点的约束条件和每条弧的变量可将网络图构建成线性规划模型。min 2x15+5x26+3x37+3x48+0.25x56+0.25x67+0.25x78 s.t.x15 600 x26 300 x37 500 x48 400 x15-x56=400 x26+x56-x67=500 x37+x67-x78=400 x48+x78=400,6.6 生产与库存应用,