第四章 运输问题和指派问题
运输问题
提到运输问题，想到什么？
实际生活中有哪些方面涉及运输问题
快递业的运输问题
服装专卖店的转运问题等
运输问题的提出
某公司经销甲产品，它下设三个工厂和四个销售点。各工厂每日的产 量和各销售点每日的销量，以及从各工厂到销售点的单位产品运价如下表。 问该公司应如何调运产品，在满足各销售点的需求量的前提下，使总运费 为最小。
寻找初始可行解的方法
（1）西北角方法； （2）最小元素法。
求平衡运输问题初始解方法—西北角方法
西 北 角 方 法
B1 A1 A2 A3 需求量 3 B2 B3
3
1 7 6
11
9 4 5
3
2
10
B4 10 8 5 6
产量 7 4 9 20
首先满足西北角上空格的需求
B1
B2 3
4
B3 11 3
2
3
求 初 始 解
A1
B4 10 8
产量 7
A2
A3 需求量
4
9 20
5
6
首先满足运费最小的空格
求 初 始 解
B1 A1 A2 A3 需求量 3
3
B2
B3
B4
产量 10 8 7 4 9 20
3
1 7
6
11
9 4 6
4 1
3
2
10
3
3
5
5
6
求平衡运输问题初始解方法—最小元素法
最 小 元 素 法
B1 A1 A2 3 3 1 7 3 B2 11 9 B3 4 1 3 2
45 45
问题分析

供大于求的问题 决策变量 目标函数 约束条件
单位成本 产品1 工厂1 x11 产品2 x12 产品3 x13 产品4 x14 生产能力 75
工厂2
工厂3 需求量
运输问题的一般模式
min cij xij s.t.
目标函数
n表示物资的n个销地 m表示物资的m个产地
x
j 1 m i 1
n
ij
si
供给约束
xij d j
xij 0
需求约束
非负约束
问题分析

决策变量 目标函数 约束条件：产量约束、销量约束、非负 B1 A1 A2 x11 x21 B2 x12 x22 B3 x13 x23
总运费 =3*3+4*11+2*9+2*2+3*10+6*5=135（元）
最小元素法得到初始方案：
x13 4, x14 3, x21 3, x23 1, x32 6, x34 3
总运费 =4*3+3*10+ 3*1+1*2+6*4+3*5=86（元）
最优解的检验——闭回路法
总产量大于总销量（供大于求）
min z cij xij
i 1 j 1 m n
n (i 1, 2..., m) (产量约束) xij ai j 1 m s.t. xij b j ( j 1, 2..., n) (销量约束) i 1 xij 0 (i 1, 2..., m; j 1, 2..., n)
例4.3
某公司决定使用三个有生产余力的工厂进行四种新产品的生 产。每单位产品需要等量的工作，所以工厂的有效生产能力 以每天生产的任意种产品的数量来衡量（见表格最右列）。 而每种产品每天有一定的需求量（见表格最后一行）。除了 3之外，每个工厂都可以生产这些产品。 之外，每个工厂都可以生产这些产品。 工厂2不能生产产品3 然而，每种产品在不同工厂中的单位成本是有差异的（见 表）。现在需要决定的是在哪个工厂生产那种产品，可以使 总成本最小？
min z cij xij
i 1 j 1 m n
n (i 1, 2..., m) (产量约束) xij ai j 1 m s.t. xij b j ( j 1, 2..., n) (销量约束) i 1 xij 0 (i 1, 2..., m; j 1, 2..., n)
供给约束
需求约束
非负约束
注意：由于供应量和需求量都是整数，任何有可行解的 运输问题就必然有所有决策变量都是整数的最优解， 所以无需设置有关整数解的约束条件
产销不平衡的运输问题

实际中，产销往往是不平衡的。可有两种情况： 总产量小于总销量（供不应求） 总产量大于总销量（供大于求）
总产量小于总销量（供不应求）
闭回路法——以最小元素法得到的解为初始可行解
检验第一 个空格
B1
1 -1
B2
3
B3
11-1 4 3 9 1
B4 3 10
8
产量 7
4 9 20
A1
A2 A3 销量
3 1
7
1 2
10
6 4 6 5
3 5 6
3
此时，引起的运费变化为：3-1+2-3=1>0 说明：该空格可以保持不变，即该运输路线不用安排运输
3
6
9
20
接下来，继续用闭回路法对新求得的解进行检验，如果还不是最 总费用为 85 优解，进行改进，如此循环往复 …… 直至得到最优解
运输问题的建模和Excel规划求解
某公司经销甲产品，它下设三个工厂和三个销售点。各工厂每 日的产量和各销售点每日的销量，以及从各工厂到销售点的单 位产品运价如表。问该公司应如何调运产品，在满足各销售点 的需求量的前提下，使总运费为最小。
产销平衡和单位运价表
单 产 位
销
运
地
B1 3
1 7 3
B2 11
9 4 6
B3 3
2 10 5
B4 10
8 5 6
产量 7
4 9 20
供需平衡
地
费
运输的单位成本
A1
A2 A3 销量
运输问题的求解方法
计算过程： 1．寻找初始可行解； 2．检查是否已达到最优。若已是最优或无可行解， 则结束； 3．进一步改善目前 xij 为换入变量，找出它在运输表中的闭回路； （2）以空格 ( Ai , B j ) 为第一个奇数顶点，沿闭回路的顺 （或逆）时针方向前进，对闭回路上的顶点一次编号； xij （3）在闭回路上的所有偶数顶点中，找出运输量最小 min L(e) 的顶点（格子），以该格中的变量为换出变量； xij 为调整量，将该闭回路上所有奇数顶点处 （4）以 min L(e) 的运输量都增加这一数值，所有偶数顶点处的运输量都减 去这一数值，从而得出一新的运输方案； （5）然后，再对得到的新解进行最优性检验，如不是最 优解，就重复以上步骤，直到有最优解。
供不应求的问题
使用Excel求解送水问题2
最大供水量增倍
供大于求的问题
4.3 运输问题的变形



总供应量大于总需求 总供应量小于总需求 一个目的地同时存在着最小需求量和最大需求量，于是所 有在这两个数值之间的数量都是可以接受的 在运输中不能使用特定的出发地——目的地组合 目标是使与运输量有关的总利润最大而不是使总成本最小
存在检验数<0的空格，该解不是 最优解
B1 A1
A2 A3 销量
1
B2
3
2 3
B3
11 9
B4 3 10
-1
产量 7
4 9 20
4 3
1 2
12 10
3 1
4
8
7
6 4 6
3 5 6
3
5
检验数<0表示：例如（A2,B4）如果增加A2到B4的1单 位产品，将会降低1单位的运费，所以，该解不是最优解。
10
B4 3 10 8
产量 7 4
A3
需求量
6
6
4 5
3
6
5
9
20
初 始 解
x13 4, x14 3, x21 3, x23 1, x32 6, x34 3
其余为0。
总运费=4*3+3*10+ 3*1+1*2+6*4+3*5=86 （元）
两种方法结果比较
B1 B2 B3 B4 产量 7 4 9 20 8 5 6
问： （1）该公司应如何分配供水量，才能获利最多？ （2）为了增加供水量，自来水公司正在考虑进行水库 改造，使三个水库每天的最大供水量都提高一倍，问 那时供水方案应如何改变？公司利润可增加多少
甲
A B 160 140
乙
130 130
丙
220 190
丁
170 150
C
190
200
230
问题分析

6
x11 3, x12 4, x22 2, x23 2, x33 3, x34 6
其余为0。
总运费=3*3+4*11+2*9+2*2+3*10+6*5=135（元）
求平衡运输问题初始解方法—最小元素法
B1 B2 3 1 7 3 6 11 9 4 5 B3 3 2
10
最 小 元 素 法
决策变量 目标函数 约束条件
甲 A B C xA1 xB1 xC1 30 50 乙 xA2 xB2 xC2 70 70 丙 xA3 xB3 xC3 10 20 丁 xA4 xB4
----
最大供水量 100 120 100
基本用水量 额外用水量
10 40
最大用水量
80
140
30
50
使用Excel求解送水问题1

要判定运输问题的某个解是否为最优解，可仿照一般单纯 形法，检验这个解的各非基变量（对应于运输表格中的空 格）的检验数，若有某空格 ( Ai , B的检验数为负，则说明将 j) xi j 变为基变量将使运费减少，故当前这个解不是最优解；若 所有空格的检验数全非负，则不管怎样变换解均不能使运 输费用减少，即为最优解。