第6章 分配与网络模型

西北农林科技大学
第六章 分配与网络模型
教 师：朱玉春 教授 单 位：经济管理学院
2011年
本章主要内容


6.1 6.2 6.3 6.4 6.5 6.6
运输问题 指派问题 转运问题 最短路径问题 最大流问题 生产和库存应用
6.1
运输问题
运输问题经常出现在计划货物配送和从某些供给地区到达某些需
量写在每个目的地节点边上。从起始节点到目的地节点之
间运输的货物数量表示了这个网络的流量。注意：直接流 量（从起点到终点）是用带箭头的线条表示的。
6.1
运输问题
对应这个福斯特公司的运输问题的目标是要确定使用哪 些路线以及每条线路上的流量是多少时，使得总的运输成本 最低。每条线路单位产品的运输费用在图6-1中的每条弧上 标明。
6.2 指派问题
比如说，在福尔公司问题中，我们有5个客户（任务）和3个项目
负责人（代理）。在加入两个虚拟的项目负责人后，我们可以建立一 个新的项目负责人与客户数量相等的指派问题。虚拟项目负责人的指 派问题的目标函数系数设为0，这样最优解的值就代表进行指派的实 际所需天数（虚拟负责人的指派是实际上不进行的）。 如果指派的备选方案是根据收入或者利润而不是时间或者成本进 行评价的，那么线性规划模型可以处理成最大化而不是最小化问题。
图6-1中，从克里夫兰到圣路易斯之间的这条弧应当删除。线性规划
模型中的变量x13也应当被删除。解决这个有11个变量和7个约束条件 的线性规划模型得出的最优解的同时，也保证了克里夫兰——圣路易
斯之源自文库的线路不被使用。
6.1
运输问题
6.1.2 运输问题的一般线性规划模型
为了表示这个运输问题的一般线性规划模型，我们将用到下列概念： i——起点下标，i=1，2，...，m；
在本节一开始，我们就指出指派问题有一个明显的特征，一个代理
电机的生产能力以及坐落在波士顿、芝加哥、圣路易斯和莱克星顿的
4个分销中心3个月的需求预测，详见教材162页。
6.1
运输问题
6.1
运输问题
6.1
运输问题
管理者想知道从每个加工厂运输到分销中心的产品运
输量应为多少。图6-1显示了12条福斯特公司可以用的配 送路线。这种图称为网络图；圆圈表示节点，连接节点的 线条表示弧。每个起点和目的地都由节点表示，每个可能 的运输路线都由弧表示。供给量写在起始节点边上，需求
6.1
运输问题
比较线性规划模型与图6-1中的网络，会发现几个观察值。所有
线性规划模型所需的信息都能在网络图中找到，每个节点需要一个约 束条件，每一条弧需要一个变量。对应的每个起点节点出发的每条弧 上的变量值之和必须小于或者等于这个起点节点的供给，对应的去往 每个目的地节点的弧上的变量值之和必须等于这个目的地节点的需求
1.总的代理（供给）数不等于总的任务（需求）数。
2.目标函数最大化。 3.不可接受的分配。 代理数不等于任务数时的情形和运输问题中总供给不等于总需求时 类似。在线性规划模型中，如果代理数多于任务的数量，多余的代理将 不被指派。如果任务数多于代理数，那么线性规划模型就没有可行的解 决方案。在这种情况下，一种简单的修正方法就是加入足够多的虚拟代 理，使代理数等于任务数。
路 从 克利夫兰 克利夫兰 贝德福德 贝德福德 贝德福德 约克 线 到 波士顿 芝加哥 芝加哥 圣路易斯 莱克星顿 波士顿 3500 1500 2500 2000 1500 2500 运输量 单位成本 （美元） 3 2 5 2 3 2 总成本（美元） 10500 3000 12500 4000 4500 5000
j——终点下标，j=1，2，...，n；
xij——起点i到终点j之间的运输量； cij——起点i到终点j之间的单位运输成本；
si——起点i的供应量或者生产能力；
dj——终点j的需求量。 m个起点，n个终点的运输问题的线性规划的一般模型如下：
6.1
min
运输问题
c x
i 1
n
m个起点，n个终点的运输问题的线性规划的一般模型如下：
xij
cij=把代理i指派给任务j所花的成本
6.2 指派问题

该一般线性规划模型如下所示： m n min cij xij
i 1 j 1
s.t.
x
j 1
m i 1
n
ij
1
1
i=1，2，...，m j=1，2，...，n 对所有的i和j
代理 任务
x
ij
xij ≥ 0 ，
6.2 指派问题
≥ 0 ，其中，i=1，2，3；j=1，2，3。
6.2 指派问题
模型的计算机计算结果如下，特瑞被指派给了客户2，卡尔被指 派给了客户3，迈克孟德被指派给了客户1。总的项目完成时间为26 天。
目标函数值 = 26.000
变
量
值
0.000 1.000 0.000
成本的减少量
0.000 0.000 3.000
X11 X12 X13
X21 X22
X23 X31 X32
0.000 0.000
1.000 1.000 0.000
0.000 4.000
0.000 0.000 3.000
X33
0.000
1.000
6.2 指派问题
6.2.1 问题的变化 因为指派问题可以被看做一个运输问题的特例，那么指派问题中可 能出现的变化就和运输问题中出现的变化相似，所以我们能够处理下面 的情形：
为了解决这个指派问题，福尔的管理层必须首先考虑所有可能的 负责人——客户的分配方法，然后预测相对应的完成项目所需的时间。 3个项目负责人和3个客户可以产生9种分配方案。
6.2 指派问题
6.2 指派问题
图6-2是福尔公司指派问题的一个网络图。节点对应着项目负责 人和客户，弧代表项目负责人——客户之间的可能分配。每个起点节 点的供给和终点节点的需求都是1；把一个项目负责人指派给一个客 户的成本是这个负责人完成客户的市场调研任务所需的时间。注意指 派问题的网络图（图6-2）和运输问题的网络图（图6-1）之间的相似 性。这个指派问题其实就是运输问题的一个特殊情形，其中所有的供 给和需求量都是1，每条弧的运输量不是1就是0。 因为这个指派问题就是运输问题的一个特殊实例，那么可以设计 一个线性规划模型。定义福尔公司指派问题的决策变量为： xij 1，如果项目负责人i被分配给客户j 这里，i=1，2，3；j=1，2，3。 0，其他情况
6.1
6.1.1
运输问题
问题的变化
福斯特公司发电机问题阐述了基本的运输模型的应用，基本运输模 型的变化可能有以下几种情况： 1、总供给不等于总需求 通常情况下总供给不等于总需求。 如果总供给超过总需求，线性规划模型不需要修改。多余的供给总量 在线性规划解决方案中表现为松弛。而任何起点的松弛都可以被理解 为未使用的供给或者未从起点运输的货物数量。如果总供给小于总需 求，运输问题的线性规划模型没有可行解，在这种情况下，我们可以 对网络图做如下修改：增加一个虚拟起点，这个起点的供给恰好等于 不被满足的需求。增加从这个虚拟起点到每个终点的弧，线性规划模 型就会有可行的解决办法了。我们规定每条从虚拟起点出发的弧上单 位的运输成本为0。
6.1
Max
运输问题
3x11+2x12+7x13+6x14+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.2 指派问题
根据所给信息，我们可以得到一个具有9个变量和6个约束条件 的福尔公司指派问题的线性规划模型：
min s.t. x11+x12+x13 ≤ 1 x21+x22+x23 ≤ 1 x31+x32+x33 ≤ 1 x11+x21+x31 = 1 x12+x22+x32 = 1 x13+x23+x33 = 1 xij 对特瑞的指派 对卡尔的指派 对迈克孟德的指派 客户1 客户2 客户3 10x11+15x12+9x13+9x21+18x22+5x23+6x31+14x32+3x33
6.2 指派问题
很多决策过程都会产生指派问题。指派问题中一个很明显的特征 是一个代理只分配给一个任务，仅仅一个任务，特别是我们寻找一组 能够最优化所设立的目标的分配，例如成本最小、时间最短或者利润 最大。 为了阐述指派问题，让我们来看看福尔市场调查公司的案例，这 个公司刚刚从3个新客户那里获得市场调查项目。公司面临着给每一 个客户分配一个项目负责人的任务。最近有3个项目负责人手上没有 其他任务，可以被分配。这3个项目具有相似的优先顺序，公司希望 分配的项目负责人完成这3个项目所需总时间最短。如果每个客户只 需要一个项目负责人，那么该怎么分配？
求地区之间的服务中，特别是每个供给地区的货物可获得量是有限的，
每个需求地区的货物需求量是已知的。运输问题中最常用的目标是要
使货物从起点到目的地的运输成本最低。 让我们通过考虑福斯特发电机公司面临的这个运输问题来进行介
绍。这个问题包括从3个加工厂运输一种产品到4个分销中心。福斯特
发电机公司在俄亥俄州的克里夫兰、印第安纳州的贝德福德和宾夕法 尼亚州的约克有3个加工厂，下3个月的计划期内的这个特殊型号的发
6.1
运输问题
这样，经过修改的问题的最优解将会代表实际运输的货物的运输 成本（从虚拟起点出发的线路没有实际运输发生）。当我们执行这个 最优解时，目的地节点处显示的运输量是这个节点需求不被满足的货 物短缺量。 2、最大化目标函数 在某些运输问题中，目标是要找到最大 化利润或者收入的解决方案。这种情况下我们只要把单位利润或者收 入作为一个系数列入目标函数中，简单地把最小改成最大，约束条件 不变，就可求得线性规划的最大值而不是最小值。 3、路线容量和或路线最小量 运输问题的线性规划模型也能 够包含一条或者更多的路线容量或者最小数量问题。例如，假设在福 斯特公司发电机问题中，约克——波士顿路线（起点3到终点1）因为 其常规的运输模式中有限空间的限制，只有1000单位的运输能力。用 x31表示约克——波士顿线路的运输量，那么这条线路的运输能力约束 为：x31 ≤ 1000，类似地，路线的最小量也可以确定下来。
线性规划模型可以用来解决这类运输问题，我们将用双 下标决策变量来描述变量。一般情况下，一个有m个起点和n 个目的地的运输问题的决策变量常被表示成以下形式：
xij——从起点i到目的地j之间的运输量 式中，i=1,2,3,...,m,j=1,2,3,...,n。 根据所给信息，我们可以构建一个有12个变量，7个约束 的线性规划模型
6.1
运输问题
例如，x22 ≥ 2000，这个约束条件保证了最优解中保留先前承诺
的最小2000单位的订单。 4、不可接受的路线 最后一种情况，构建从每一个起点到终
点的路线并不都是可能的。为了处理这种情况，我们只需要简单地去
除网络图中相关的弧和线性规划模型中相关的变量。例如，如果克里 夫兰——圣路易斯之间的路线是不可接受的或者是不可用的，那么在
另外，如果一个或者更多的指派是不可接受的，那么相对应的决策变
量应当从线性规划模型中删除。这种情况可能发生，例如，如果其中 一个代理没有这个任务或者更多任务所需的必要经验。
6.2 指派问题
6.2.2 指派问题的一般线性规划模型 为了展示包括m个代理和n个任务的指派问题的一般线性规划 模型，我们做如下设定： 1，如果项目负责人i被分配给客户j 0，其他情况
m n
s.t.
j 1
ij ij
x
j 1
ij
si
i=1，2，...，m j=1，2，...，n
供给 需求
xij d j
i 1
m
xij ≥ 0，对所有i和j 就如先前我们提到的，如果从起点i到终点j之间的运输容量为Lij， 可以在约束里加一个xij ≤ Lij，一个包含了这种类型的约束条件的运 输问题就称为有容量限制的运输问题。类似地，如果起点i到终点j之 间必须处理的运输容量最小为Mij，那么我们在约束条件里加上最小运 输容量约束xij ≥ Mij。