第6章-分配与网络模型

第六章分配与网络模型教师：朱玉春教授单位：经济管理学院2011年西北农林科技大学本章主要内容6.1运输问题6.2指派问题6.3转运问题6.4最短路径问题6.5最大流问题6.6生产和库存应用运输问题经常出现在计划货物配送和从某些供给地区到达某些需求地区之间的服务中，特别是每个供给地区的货物可获得量是有限的，每个需求地区的货物需求量是已知的。运输问题中最常用的目标是要使货物从起点到目的地的运输成本最低。让我们通过考虑福斯特发电机公司面临的这个运输问题来进行介绍。这个问题包括从3个加工厂运输一种产品到4个分销中心。福斯特发电机公司在俄亥俄州的克里夫兰、印第安纳州的贝德福德和宾夕法尼亚州的约克有3个加工厂，下3个月的计划期内的这个特殊型号的发电机的生产能力以及坐落在波士顿、芝加哥、圣路易斯和莱克星顿的4个分销中心3个月的需求预测，详见教材162页。6.1运输问题6.1运输问题6.1运输问题管理者想知道从每个加工厂运输到分销中心的产品运输量应为多少。图6-1显示了12条福斯特公司可以用的配送路线。这种图称为网络图；圆圈表示节点，连接节点的线条表示弧。每个起点和目的地都由节点表示，每个可能的运输路线都由弧表示。供给量写在起始节点边上，需求量写在每个目的地节点边上。从起始节点到目的地节点之间运输的货物数量表示了这个网络的流量。注意：直接流量（从起点到终点）是用带箭头的线条表示的。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运输问题Max3x11+2x12+7x13+6x14+7x21+5x22+2x23+3x24+2x31+5x32+4x33+5x34s.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中的网络，会发现几个观察值。所有线性规划模型所需的信息都能在网络图中找到，每个节点需要一个约束条件，每一条弧需要一个变量。对应的每个起点节点出发的每条弧上的变量值之和必须小于或者等于这个起点节点的供给，对应的去往每个目的地节点的弧上的变量值之和必须等于这个目的地节点的需求6.1运输问题路线运输量单位成本（美元）总成本（美元）从到克利夫兰波士顿3500310500克利夫兰芝加哥150023000贝德福德芝加哥2500512500贝德福德圣路易斯200024000贝德福德莱克星顿150034500约克波士顿2500250006.1.1问题的变化福斯特公司发电机问题阐述了基本的运输模型的应用，基本运输模型的变化可能有以下几种情况：1、总供给不等于总需求通常情况下总供给不等于总需求。如果总供给超过总需求，线性规划模型不需要修改。多余的供给总量在线性规划解决方案中表现为松弛。而任何起点的松弛都可以被理解为未使用的供给或者未从起点运输的货物数量。如果总供给小于总需求，运输问题的线性规划模型没有可行解，在这种情况下，我们可以对网络图做如下修改：增加一个虚拟起点，这个起点的供给恰好等于不被满足的需求。增加从这个虚拟起点到每个终点的弧，线性规划模型就会有可行的解决办法了。我们规定每条从虚拟起点出发的弧上单位的运输成本为0。6.1运输问题这样，经过修改的问题的最优解将会代表实际运输的货物的运输成本（从虚拟起点出发的线路没有实际运输发生）。当我们执行这个最优解时，目的地节点处显示的运输量是这个节点需求不被满足的货物短缺量。2、最大化目标函数在某些运输问题中，目标是要找到最大化利润或者收入的解决方案。这种情况下我们只要把单位利润或者收入作为一个系数列入目标函数中，简单地把最小改成最大，约束条件不变，就可求得线性规划的最大值而不是最小值。3、路线容量和或路线最小量运输问题的线性规划模型也能够包含一条或者更多的路线容量或者最小数量问题。例如，假设在福斯特公司发电机问题中，约克——波士顿路线（起点3到终点1）因为其常规的运输模式中有限空间的限制，只有1000单位的运输能力。用x31表示约克——波士顿线路的运输量，那么这条线路的运输能力约束为：x31≤1000，类似地，路线的最小量也可以确定下来。6.1运输问题例如，x22≥2000，这个约束条件保证了最优解中保留先前承诺的最小2000单位的订单。4、不可接受的路线最后一种情况，构建从每一个起点到终点的路线并不都是可能的。为了处理这种情况，我们只需要简单地去除网络图中相关的弧和线性规划模型中相关的变量。例如，如果克里夫兰——圣路易斯之间的路线是不可接受的或者是不可用的，那么在图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之间的单位运输成本；si——起点i的供应量或者生产能力；dj——终点j的需求量。m个起点，n个终点的运输问题的线性规划的一般模型如下：6.1运输问题6.1运输问题m个起点，n个终点的运输问题的线性规划的一般模型如下：mins.t.i=1，2，...，m供给j=1，2，...，n需求xij≥0，对所有i和j就如先前我们提到的，如果从起点i到终点j之间的运输容量为Lij，可以在约束里加一个xij≤Lij，一个包含了这种类型的约束条件的运输问题就称为有容量限制的运输问题。类似地，如果起点i到终点j之间必须处理的运输容量最小为Mij，那么我们在约束条件里加上最小运输容量约束xij≥Mij。injijsx1jmiijdx1njijijmixc11很多决策过程都会产生指派问题。指派问题中一个很明显的特征是一个代理只分配给一个任务，仅仅一个任务，特别是我们寻找一组能够最优化所设立的目标的分配，例如成本最小、时间最短或者利润最大。为了阐述指派问题，让我们来看看福尔市场调查公司的案例，这个公司刚刚从3个新客户那里获得市场调查项目。公司面临着给每一个客户分配一个项目负责人的任务。最近有3个项目负责人手上没有其他任务，可以被分配。这3个项目具有相似的优先顺序，公司希望分配的项目负责人完成这3个项目所需总时间最短。如果每个客户只需要一个项目负责人，那么该怎么分配？为了解决这个指派问题，福尔的管理层必须首先考虑所有可能的负责人——客户的分配方法，然后预测相对应的完成项目所需的时间。3个项目负责人和3个客户可以产生9种分配方案。6.2指派问题6.2指派问题6.2指派问题图6-2是福尔公司指派问题的一个网络图。节点对应着项目负责人和客户，弧代表项目负责人——客户之间的可能分配。每个起点节点的供给和终点节点的需求都是1；把一个项目负责人指派给一个客户的成本是这个负责人完成客户的市场调研任务所需的时间。注意指派问题的网络图（图6-2）和运输问题的网络图（图6-1）之间的相似性。这个指派问题其实就是运输问题的一个特殊情形，其中所有的供给和需求量都是1，每条弧的运输量不是1就是0。因为这个指派问题就是运输问题的一个特殊实例，那么可以设计一个线性规划模型。定义福尔公司指派问题的决策变量为：1，如果项目负责人i被分配给客户j0，其他情况xij这里，i=1，2，3；j=1，2，3。根据所给信息，我们可以得到一个具有9个变量和6个约束条件的福尔公司指派问题的线性规划模型：min10x11+15x12+9x13+9x21+18x22+5x23+6x31+14x32+3x33s.t.x11+x12+x13≤1对特瑞的指派x21+x22+x23≤1对卡尔的指派x31+x32+x33≤1对迈克孟德的指派x11+x21+x31=1客户1x12+x22+x32=1客户2x13+x23+x33=1客户3xij≥0，其中，i=1，2，3；j=1，2，3。6.2指派问题模型的计算机计算结果如下，特瑞被指派给了客户2，卡尔被指派给了客户3，迈克孟德被指派给了客户1。总的项目完成时间为26天。6.2指派问题目标函数值=26.000变量值成本的减少量X110.0000.000X121.0000.000X130.0003.000X210.0000.000X220.0004.000X231.0000.000X311.0000.000X320.0003.000X330.0001.0006.2.1问题的变化因为指派问题可以被看做一个运输问题的特例，那么指派问题中可能出现的变化就和运输问题中出现的变化相似，所以我们能够处理下面的情形：1.总的代理（供给）数不等于总的任务（需求）数。2.目标函数最大化。3.不可接受的分配。代理数不等于任务数时的情形和运输问题中总供给不等于总需求时类似。在线性规划模型中，如果代理数多于任务的数量，多余的代理将不被指派。如果任务数多于代理数，那么线性规划模型就没有可行的解决方案。在这种情况下，一种简单的修正方法就是加入足够多的虚拟代理，使代理数等于任务数。6.2指派问题比如说，在福尔公司问题中，我们有5个客户（任务）和3个项目负责人（代理）。在加入两个虚拟的项目负责人后，我们可以建立一个新的项目负责人与客户数量相等的指派问题。虚拟项目负责人的指派问题的目标函数系数设为0，这样最优解的值就代表进行指派的实际所需天数（虚拟负责人的指派是实际上不进行的）。如果指派的备选方案是根据收入或者利润而不是时间或者成本进行评价的，那么线性规划模型可以处理成最大化而不是最小化问题。另外，如果一个或者更多的指派是不可接受的，那么相对应的决策变量应当从线性规划模型中删除。这种情况可能发生，例如，如果其中一个代理没有这个任务或者更多任务所需的必要经验。6.2指派问题6.2指派问题6.2.2指派问题的一般线性规划模型为了展示包括m个代理和n个任务的指派问题的一般线性规划模型，我们做如下设定：cij=把代理i指派给任务j所花的成本1，如果项目负责人i被分配给客户j0，其他情况xij6.2指派问题该一般线性规划模型如下所示：mins.t.i=1，2，...，m代理j=1，2，...，n任务xij≥0，对所有的i和jnjijijmixc1111njijx11miijx在本节一开始，我们就指出指派问题有一个明显的特征，一个代理只能被指派给一个任务。对于一个代理可以被分配给两个或者更多个任务的广义指派问题，我们可以对线性规划模型进行简单修正。例如，假设福尔公司问题中特瑞能够被指派给两个客户；在这种情况下，代表特瑞指派的约束条件就为x11+x12+x13≤2。一般情况下，如果ai表示代理i能够被指派的任务的最高上限，那么我们把代理约束写成如下形式：i=1，2，...，m因此，我们发现把指派问题像线性规划模型一样构建和求解的一个好处就是，特殊情形，例如涉及多种指派的情况，比较容易处理。injijax16.2指派问题6.3转运问题转运问题是运输问题的扩展，其中中间节点代表转运节点，加入这个节点的目的是指代地