管 理 运 筹 学 1
第七章 运 输 问 题
§ 1 运 输 模 型
§ 2 运输问题的计算机求解
§ 3 运输问题的应用
§ 4* 运输问题的表上作业法管 理 运 筹 学 2
例 1,某公司从两个产地 A1,A2将物品运往三个销地 B1,B2,B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？
B 1 B 2 B 3 产量
A 1 6 4 6 200
A 2 6 5 5 300
销量 150 150 200
解,产销平衡问题,总产量 = 总销量设 xij 为从产地 Ai运往销地 Bj的运输量，得到下列运输量表,B 1 B 2 B 3 产量
A 1 x 1 1 x 1 2 x 1 3 200
A 2 x 2 1 x 2 2 x 2 3 300
销量 150 150 200
Min f = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23
s.t,x11+ x12 + x13 = 200
x21 + x22+ x23 = 300
x11 + x21 = 150
x12 + x22 = 150
x13 + x23 = 200x
ij ≥ 0 ( i = 1,2； j = 1,2,3）
§ 1 运 输 模 型管 理 运 筹 学 3
§ 1 运 输 模 型
一般运输模型,产销平衡
A1,A2,…,Am 表示某物资的 m个产地； B1,B2,…,Bn 表示某物质的
n个销地； si 表示产地 Ai的产量； dj 表示销地 Bj 的销量； cij 表示把物资从产地
Ai运往销地 Bj的单位运价。
设 xij 为从产地 Ai运往销地 Bj的运输量，得到下列一般运输量问题的模型：
m n
Min f = cij xij
i = 1 j = 1
n
s.t,? xij = si i = 1,2,…,m
j = 1
m
xij = dj j = 1,2,…,n
i = 1
xij ≥ 0 (i = 1,2,…,m ; j = 1,2,…,n)
变化：
1）有时目标函数求最大。如求利润最大或营业额最大等；
2）当某些运输线路上的能力有限制时，在模型中直接加入约束条件
（等式或不等式约束 )；
3）产销不平衡时，可加入假想的产地（销大于产时）或销地（产大于销时）。
管 理 运 筹 学 4
§ 2 运输问题的计算机求解例 2,某公司从两个产地 A1,A2将物品运往三个销地 B1,B2、
B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？
解,增加一个虚设的销地运输费用为 0
B 1 B 2 B 3 产量
A 1 6 4 6 3 00
A 2 6 5 5 300
销量 150 150 200 6 0 0
500
B 1 B 2 B 3 B 4 产量
A 1 6 4 6 0 3 00
A 2 6 5 5 0 300
销量 150 150 200 100 60 0
600
管 理 运 筹 学 5
§ 2 运输问题的计算机求解例 3,某公司从两个产地 A1,A2将物品运往三个销地 B1,B2、
B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？
解,增加一个虚设的产地运输费用为 0
B 1 B 2 B 3 产量
A 1 6 4 6 200
A 2 6 5 5 300
销量 250 200 200 50 0
650
B 1 B 2 B 3 产量
A 1 6 4 6 2 00
A 2 6 5 5 300
A 3 0 0 0 150
销量 250 200 200 65 0
650
管 理 运 筹 学 6
§ 3 运输问题的应用一、产销不平衡的运输问题例 4,石家庄北方研究院有一、二、三三个区。每年分别需要用煤 3000,1000、
2000吨，由河北临城、山西盂县两处煤矿负责供应，价格、质量相同。供应能力分别为 1500,4000吨，运价为：
由于需大于供，经院研究决定一区供应量可减少 0--300吨，二区必须满足需求量，三区供应量不少于 1500吨，试求总费用为最低的调运方案。
解,根据题意，作出产销平衡与运价表：
这里 M 代表一个很大的正数，其作用是强迫相应的 x31,x33,x34取值为 0。
一区 二区 三区 产量山西盂县 1,8 0 1,70 1,5 5 4000
河北临城 1,6 0 1,5 0 1,7 5 1500
需要量 3000 1000 2000
一区 一区 二区 三区 三区 产量山西盂县 1,8 0 1,8 0 1,70 1,5 5 1,5 5 4000
河北临城 1,6 0 1,6 0 1,5 0 1,7 5 1,7 5 1500
假想生产点 M 0 M M 0 500
需要量 2 7 00 3 00 1000 1 5 00 5 00 6000
6000
管 理 运 筹 学 7
§ 3 运输问题的应用一、产销不平衡的运输问题例 5,设有 A,B,C三个化肥厂供应 1,2,3,4四个地区的农用化肥。假设效果相同，有关数据如下表：
试求总费用为最低的化肥调拨方案。
解,根据题意，作出产销平衡与运价表：
最低要求必须满足，因此把相应的虚设产地运费取为 M,而最高要求与最低要求的差允许按需要安排，因此把相应的虚设产地运费取为 0 。对应 4”的销量
50 是考虑问题本身适当取的数据，根据产销平衡要求确定 D的产量为 50。
1 2 3 4 产量
A 1 6 1 3 22 17 50
B 14 1 3 19 15 60
C 19 20 23 --- 50
最低需要量 30 70 0 10
最高需要量 50 70 30 不限
1 ’
1,2 3 4 ’ 4,产量
A 1 6 1 6 1 3 22 17 17 50
B 14 14 1 3 19 15 15 60
C 19 19 20 23 M M 50
D M 0 M 0 M 0 50
销量 30 20 70 30 10 50 2 1 0
2 1 0
管 理 运 筹 学 8
§ 3 运输问题的应用二、生产与储存问题例 6,某厂按合同规定须于当年每个季度末分别提供 10,15、
25,20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如右表。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用 0.15
万元。试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。
生产能力 （台） 单位成本 （万元）
一季度 25 1 0,8
二季度 35 1 1,1
三季度 30 1 1,0
四季度 10 1 1,3
管 理 运 筹 学 9
§ 3 运输问题的应用解,设 xij为第 i 季度生产的第 j 季度交货的柴油机数目，那么应满足：
交货,x11 = 10 生产,x11 + x12 + x13 + x14 ≤ 25
x12 + x22 = 15 x22 + x23 + x24 ≤ 35
x13 + x23 + x33 = 25 x33 + x34 ≤ 30
x14 + x24 + x34 + x44 = 20 x44 ≤ 10
把第 i 季度生产的柴油机数目看作第 i 个生产厂的产量；把第 j 季度交货的柴油机数目看作第 j 个销售点的销量；成本加储存、维护等费用看作运费。可构造下列产销平衡问题：
目标函数,Min f = 10.8 x11 +10.95 x12 +11.1 x13 +11.25 x14 +11.1 x22 +11.25
x23 +11.4 x24 +11.0 x33 +11.15 x34 +11.3 x44
第一季度第二季度 第三季度 第四季度 D 产量第一季度 1 0,8 0 1 0,9 5 1 1,1 0 1 1,2 5 0 25
第二季度 M 1 1,1 0 1 1,2 5 1 1,4 0 0 35
第三季度 M M 1 1,0 0 1 1,1 5 0 30
第四季度 M M M 1 1,3 0 0 10
销量 10 15 25 20 30 1 0 0
1 0 0
管 理 运 筹 学 10
§ 3 运输问题的应用二、生产与储存问题例 7,光明仪器厂生产电脑绣花机是以产定销的。已知 1至 6月份各月的生产能力、合同销量和单台电脑绣花机平均生产费用见下表：
已知上年末库存 103台绣花机，如果当月生产出来的机器当月不交货，
则需要运到分厂库房，每台增加运输成本 0.1万元,每台机器每月的平均仓储费、维护费为 0.2万元。在 7--8月份销售淡季，全厂停产 1个月，因此在 6
月份完成销售合同后还要留出库存 80台。加班生产机器每台增加成本 1万元。问应如何安排 1--6月份的生产，可使总的生产费用（包括运输、仓储、维护）最少？
正常生产能力 （台） 加班生产能力 （台） 销量 （台） 单台费用 （万元）
1 月份 60 10 104 15
2 月份 50 10 75 14
3 月份 90 20 1 1 5 1 3,5
4 月份 100 40 160 13
5 月份 100 40 103 13
6 月份 80 40 70 1 3,5
管 理 运 筹 学 11
§ 3 运输问题的应用解,这个生产存储问题可化为运输问题来做。考虑,各月生产与交货分别视为产地和销地
1） 1--6月份合计生产能力（包括上年末储存量）为 743台，销量为 707台。设一假想销地销量为 36；
2）上年末库存 103台，只有仓储费和运输费，把它列为第 0行；
3） 6月份的需求除 70台销量外，还要 80台库存，其需求应为 70+80=150台；
4） 1--6表示 1--6月份正常生产情况,1’--6’表示 1--6月份加班生产情况。
产销平衡与运价表：
1 月 2 月 3 月 4 月 5 月 6 月 虚销地 正常产量 加班产量
0 0,3 0,5 0,7 0,9 1,1 1,3 0 103
1 15 1 5,3 1 5,5 1 5,7 1 5,9 1 6,1 0 60
1 ’ 16 1 6,3 1 6,5 1 6,7 6,9 1 7,1 0 10
2 M 14 1 4,3 1 4,5 1 4,7 1 4,9 0 50
2 ’ M 15 1 5,3 1 5,5 1 5,7 1 5,9 0 10
3 M M 1 3,5 1 3,8 1 4,0 1 4,2 0 90
3 ’ M M 1 4,5 1 4,8 1 5,0 1 5,2 0 20
4 M M M 1 3,0 1 3,3 1 3,5 0 100
4 ’ M M M 1 4,0 1 4,3 1 4,5 0 40
5 M M M M 1 3,0 1 3,3 0 100
5 ’ M M M M 1 4,0 1 4,3 0 40
6 M M M M M 1 3,5 0 80
6 ’ M M M M M 1 4,5 0 40
销量 104 75 1 1 5 160 103 150 36 7 4 3
743
管 理 运 筹 学 12
§ 3 运输问题的应用
1 月 2 月 3 月 4 月 5 月 6 月 假想销量
0 63 15 5 20
1 41 19
1 ’
2 50
2 ’ 10
3 90
3 ’ 20
4 100
4 ’ 40
5 63 37
5 ’ 40
6 80
6 ’ 33 7
用“管理运筹学”软件解得的结果是,1-6月最低生产费用为 8307.5
万元，每月的销售安排如下表所示管 理 运 筹 学 13
§ 3 运输问题的应用三、转运问题：
在原运输问题上增加若干转运站。运输方式有：产地?转运站、转运站?销地、产地?产地、产地?销地、销地?转运站、销地?产地等 。
例 8,腾飞电子仪器公司在大连和广州有两个分厂生产同一种仪器，大连分厂每月生产 400台，广州分厂每月生产 600
台。该公司在上海和天津有两个销售公司负责对南京、济南、南昌、青岛四个城市的仪器供应。另外因为大连距离青岛较近，公司同意大连分厂向青岛直接供货，运输费用如图，单位是百元。问应该如何调运仪器，
可使总运输费用最低？ 图中 1-广州,2 - 大连、
3 - 上海,4 - 天津,5 - 南京,6 - 济南,7 - 南昌,8 - 青岛管 理 运 筹 学 14
§ 3 运输问题的应用解,设 xij 为从 i 到 j 的运输量，可得到有下列特点的线性规划模型：
目标函数,Min f = 所有可能的运输费用（运输单价与运输量乘积之和）
约束条件：
对产地（发点） i,输出量 - 输入量 = 产量对转运站（中转点）：输入量 - 输出量 = 0
对销地（收点） j,输入量 - 输出量 = 销量例 8．（续）
目标函数,Min f = 2x13+ 3x14+ 3x23+ x24+ 4x28 + 2x35+ 6x36+ 3x37+ 6x38+
4x45+ 4x46+ 6x47+ 5x48
约束条件：
s.t,x13+ x14 ≤ 600 ( 广州分厂供应量限制）
x23+ x24+ x28 ≤ 400 ( 大连分厂供应量限制）
-x13- x23 + x35 + x36+ x37 + x38 = 0 （上海销售公司，转运站）
-x14- x24 + x45 + x46+ x47 + x48 = 0 （天津销售公司，转运站）
x35+ x45 = 200 （南京的销量）
x36+ x46 = 150 （济南的销量）
x37+ x47 = 350 （南昌的销量）
x38+ x48 + x28 = 300 （青岛的销量）
xij ≥ 0,i,j = 1,2,3,4,5,6,7,8
管 理 运 筹 学 15
§ 3 运输问题的应用用“管理运筹学”软件求得结果：
x13 = 550 x14 =50 ；
x23 = 0 x24 = 100 x28 = 300 ；
x35 = 200 x36 = 0 x37 = 350 x38 = 0 ；
x45 = 0 x46 = 150 x47 = 0 x48 = 0 。
最小运输费用为,4600百元例 9,某公司有 A1,A2,A3三个分厂生产某种物资，分别供应 B1,B2,B3,B4
四个地区的销售公司销售。假设质量相同，有关数据如下表：
试求总费用为最少的调运方案。
假设：
1.每个分厂的物资不一定直接发运到销地，可以从其中几个产地集中一起运；
2.运往各销地的物资可以先运给其中几个销地，再转运给其他销地；
3.除产销地之外，还有几个中转站，在产地之间、销地之间或在产地与销地之间转运。
B 1 B 2 B 3 B 4 产量
A 1 3 1 1 3 10 7
A 2 1 9 2 8 4
A 3 7 4 10 5 9
销量 3 6 5 6 和 = 20
管 理 运 筹 学 16
§ 3 运输问题的应用运价如下表：
解,把此转运问题转化为一般运输问题：
1、把所有产地、销地、转运站都同时看作产地和销地；
2、运输表中不可能方案的运费取作 M，自身对自身的运费为 0；
3,Ai,产量为 20+原产量,销量为 20； Ti,产量、销量均为 20； Bi,产量为 20,销量为 20 +原销量，其中 20为各点可能变化的最大流量；
4、对于最优方案，其中 xi i 为自身对自身的运量，实际上不进行运作。
A
1
A
2
A
3
T
1
T
2
T
3
T
4
B
1
B
2
B
3
B
4
A
1
1 3 2 1 4 3 3 1 1 3 10
A
2
1 --- 3 5 --- 2 1 9 2 8
A
3
3 --- 1 --- 2 3 7 4 10 5
T
1
2 3 1 1 3 2 2 8 4 6
T
2
1 5 --- 1 1 1 4 5 2 7
T
3
4 --- 2 3 1 2 1 8 2 4
T
4
3 2 3 2 1 2 1 --- 2 6
B
1
3 1 7 2 4 1 1 1 4 2
B
2
11 9 4 8 5 8 --- 1 2 1
B
3
3 2 10 4 2 2 2 4 2 3
B
4
10 8 5 6 7 4 6 2 1 3
管 理 运 筹 学 17
§ 3 运输问题的应用扩大的运输问题产销平衡与运价表：
A
1
A
2
A
3
T
1
T
2
T
3
T
4
B
1
B
2
B
3
B
4
产量
A
1
0 1 3 2 1 4 3 3 1 1 3 10 27
A
2
1 0 M 3 5 M 2 1 9 2 8 24
A
3
3 M 0 1 M 2 3 7 4 10 5 29
T
1
2 3 1 0 1 3 2 2 8 4 6 20
T
2
1 5 M 1 0 1 1 4 5 2 7 20
T
3
4 M 2 3 1 0 2 1 8 2 4 20
T
4
3 2 3 2 1 2 0 1 M 2 6 20
B
1
3 1 7 2 4 1 1 0 1 4 2 20
B
2
11 9 4 8 5 8 M 1 0 2 1 20
B
3
3 2 10 4 2 2 2 4 2 0 3 20
B
4
10 8 5 6 7 4 6 2 1 3 0 20
销量 20 20 20 20 20 20 20 23 26 25 26 240
管 理 运 筹 学 18
§ 4* 运输问题的表上作业法
表上作业法是一种求解运输问题的特殊方法，其 实质是单纯形法。
运输问题都存在最优解。
计算过程（假设产销平衡）：
– 1.找出初始基本可行解。对于有 m个产地 n个销地的产销平衡问题，
则有 m个关于产量的约束方程和 n个关于销量的约束方程。由于产销平衡，其模型最多只有 m+n-1个独立的约束方程，即运输问题有
m+n-1个基变量。在 m× n的产销平衡表上给出 m+n-1个数字格，其相对应的调运量的值即为基变量的值。
– 2.求各非基变量的检验数，即检验除了上述 m+n-1个基变量以外的空格的检验数判别是否达到最优解，如果已是最优，停止计算，否则转到下一步。
– 3.确定入基变量和出基变量，找出新的基本可行解。在表上用闭回路法调整。
– 4.重复 2,3直到得到最优解。
管 理 运 筹 学 19
§ 4* 运输问题的表上作业法运输问题的一般数学模型设有 m个产地（记作 A1,A2,A3,…,Am），生产某种物资，其产量分别为 a1,a2,…,am；有 n个销地（记作 B1,B2,…,Bn），
其需要量分别为 b1,b2,…,bn；且产销平衡，即 。
从第 i个产地到 j 个销地的单位运价为 cij,在满足各地需要的前提下，求总运输费用最小的调运方案。 设 xij(i=1,2,…,m；
j=1,2,…,n)为第 i个产地到第 j个销地的运量，则数学模型为：
n
j
j
m
i
i ba
11
n
j
ijij
m
i
xcz
11
m in
njmix
njbx
miax
ij
j
m
i
ij
n
j
iij
,,1;,,1,0
,,1
,,1
1
1
管 理 运 筹 学 20
§ 4* 运输问题的表上作业法
n
i
ijij
m
i
xcz
11
m in
njmix
njbx
miax
ij
j
m
i
ij
n
j
iij
,,1;,,1,0
,,1
,,1
1
1
设平衡运输问题的数学模型为：
模型特征
1.运输问题存在可行解，也一定存在最优解
2.当供应量和需求量都是整数时，则一定存在整数最优解
3.有 m+n个约束,mn个变量
4.有 m+n－ 1个基变量管 理 运 筹 学 21
§ 4* 运输问题的表上作业法
【 证 】 因为产销平衡,即,将前 m个约束方程两边相加得
m
i
n
j
ii ba
1 1
m
i
n
j
m
i
iij ax
1 1 1
再将后 n个约束相加得
n
j
m
i
n
j
jij bx
1 1 1
显然前 m个约束方程之和等于后 n个约束方程之和,m+n个约束方程是相关的,系数矩阵
【 定理 1】 设有 m个产地 n个销地且产销平衡的运输问题，则基变量数为 m+n-1。
管 理 运 筹 学 22
§ 4* 运输问题的表上作业法中任意 m+n阶子式等于零，取第一行到 m+n－ 1行与对应的列（共 m+n-1列）组成的 m+n－ 1阶子式
1,1121121,,,,?nmnnn xxxxxx,，，
11 12 1 21 22 2 1 2
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
n n m m m n
x x x x x x x x x
A
＝
管 理 运 筹 学 23
§ 4* 运输问题的表上作业法 0
1
1
1
1
1
1111
故 r(A)=m+n－ 1所以运输问题有 m+n－ 1个基变量 。
为了在 mn个变量中找出 m+n－ 1个变量作为一组基变量,就是要在 A中找出 m+n-1个线性无关的列向量,下面引用闭回路的概念寻找这些基变量 。
管 理 运 筹 学 24
§ 4* 运输问题的表上作业法
),,,,,,(,,,,,,2121132222111 互不相同；称集合 ssjijijijijiji jjjiiixxxxxx sss
为一个闭回路,集合中的变量称为回路的顶点,相邻两个变量的连线为闭回路的边 。
x25x23
B1 B2 B3 B4 B5
A1
A2
A3 x35
A4 x43
x11 x12
x31
x42
表中闭回路的变量集合是
{x11,x12,x42,x 43,x 23,x 25,x
35,x 31}共有 8个顶点,这 8
个顶点间用水平或垂直线段连接起来，组成一条封闭的回路。
管 理 运 筹 学 25
§ 4* 运输问题的表上作业法
x11 x12
x32 x33
x41
B1 B2 B3
A1
A2
A3
A4 x
43
一条回路中的顶点数一定是偶数，回路遇到顶点必须转 90度与另一顶点连接，上表中的变量
x 32及 x33不是回闭路的顶点，只是连线的交点。
表中闭回路是
123233434111,,,,,xxxxxx
;,,,,,121131352521 xxxxxxA?
;,,,,2111123233 xxxxxB?
例如变量组
A不能组成一条闭回路，但 A中包含有闭回路
B的变量数是奇数，显然不是闭回路，也不含有闭回路；
管 理 运 筹 学 26
§ 4* 运输问题的表上作业法
333211122321,,,,,xxxxxxC?
C是一条闭回路，若把 C重新写成就不难看出 C仍是一条闭回路。?111232332321,,,,,xxxxxxC?
【 定理 2】 若变量组 B 包含有闭回路,则 B
中的变量对应的例向量线性相关 。
【 证 】 由线性代数知,向量组中部分向量组线性相关则该向量组线性相关,显然,将 C中列向量分别乘以正负号线性组合后等于零,即
1 1 1 2 2 2 1 0si j i j i j i jP P P P－
因而 C中的列向量线性相关,所以 B中列向量线性相关 。
12111,,,jijiji sxxxC
管 理 运 筹 学 27
§ 4* 运输问题的表上作业法由定理 2可知,当一个变量组中不包含有闭回路,则这些变量对应的系数向量线性无关 。
求运输问题的一组基变量,就是要找到 m+n－ 1个变量,使得它们对应的系数列向量线性无关,由定理 2,找这样的一组变量是很容易的,只要 m+n－ 1个变量中不包含闭回路,就可得到一组基变量 。
因而有：
【 定理 3】 m+n－ 1个变量组构成基变量的充要条件是它不包含任何闭回路 。
定理 3告诉了一个求基变量的简单方法,同时也可以判断一组变量是否可以作为某个运输问题的基变量 。 这种方法是直接在运价表中进行的,不需要在系数矩阵 A中去寻找,从而给运输问题求初始基可行解带来极大的方便 。
管 理 运 筹 学 28
§ 4* 运输问题的表上作业法
Bj
Ai
B1 B2 B3 B4 ai
A1 c11 c12 c13 c14 a1
x11 x12 x13 x14
A2 c21 c22 c23 c24 a2
x21 x22 x23 x24
A3 c31 c32 c2 c34 a3
x31 x32 x33 x34
bj b1 b2 b3 b4
例如,m=3,n=4,将 xij与运价 Cij放在同一张表中,如表 5-5所示 。
管 理 运 筹 学 29
§ 4* 运输问题的表上作业法这个运输问题的基变量数目是 3+4－ 1=6。 变量组中有 7个变量,显然不能构成一组基变量,又如中有 6个变量,但包含有一条闭回路故不能构成一组基变量 。 变量组有 6个变量且不含有任何闭回路,故可以构成此问题的一组基变量 。
22121324323111,,,,,,xxxxxxx
,,,,,,342413322221 xxxxxx
24343222,,,xxxx
343332222111,,,,,xxxxxx
管 理 运 筹 学 30
§ 4* 运输问题的表上作业法
例 10.喜庆食品公司有三个生产面包的分厂 A1,A2,A3，有四个销售公司 B1,B2,B3,B4，其各分厂每日的产量、各销售公司每日的销量以及各分厂到各销售公司的单位运价如表所示，在表中产量与销量的单位为吨，运价的单位为百元 /吨。问该公司应如何调运产品在满足各销点的需求量的前提下总运费最少？
这是一个产销平衡的运输问题，因此不需要再设假想产地和销地了。
销地产地 B1 B2 B3 B4
产量
A1 3 11 3 10 7
A2 1 9 2 8 4
A3 7 4 10 5 9
销量 3 6 5 6 20
20
管 理 运 筹 学 31
§ 4* 运输问题的表上作业法一、确定初始基本可行解为了把初始基本可行解与运价区分开，我们把 运价 放在每一栏的 右上角,每一栏的中间写上初始基本可行解（调运量）。
1.西北角法,先从表的左上角（即西北角）的变量 x11开始分配运输量，并使
x11取尽可能大的值，即 x11=min(7,3)=3,则 x21与 x31必为零。同时把 B1的销量与 A1的产量都减去 3填入销量和产量处，划去原来的销量和产量。同理可得余下的初始基本可行解。
销地产地 B1 B2 B3 B4 产量
A1 3 4 7 4 0
A2 2 2 4 2 0
A3 3 6 9 6 0
销量
3
0
6
2
0
5
3
0
6
0
20
20
3 11 3 10
8
510
29
47
1
管 理 运 筹 学 32
§ 4* 运输问题的表上作业法
2.最小元素法西北角法是对西北角的变量分配运输量，而最小元素法是就近供应，即对单位运价最小的变量分配运输量。在表上找到单位运价最小的 x21，并使 x21取尽可能大的值，即 x21=min(4,3)=3,把 A1的产量改为 1,B1的销量改为 0，并把 B1列划去。在剩下的 3× 3矩阵中再找最小运价，同理可得其他的基本可行解。
一般来说用最小元素法求得的初始基本可行解比西北角法求得的总运价要少。这样从用最小元素法求得的初始基本可行解出发求最优解的迭代次数可能少一些。
销地产地 B1 B2 B3 B4 产量
A1 4 3 7 3 0
A2 3 1 4 1 0
A3 6 3 9 3 0
销量
3
0
6
0
5
4
0
6
3
0
20
20
3 11 3 10
8
510
29
47
1
管 理 运 筹 学 33
§ 4* 运输问题的表上作业法
在求初始基本可行解时要注意的两个问题：
– 1.当我们取定 xij的值之后，会出现 Ai的产量与 Bj的销量都改为零的情况，这时只能划去 Ai行或 Bj列，但不能同时划去 Ai行与 Bj列。
– 2.用最小元素法时，可能会出现只剩下一行或一列的所有格均未填数或未被划掉的情况，此时在这一行或者一列中除去已填上的数外均填上零，不能按空格划掉。这样可以保证填过数或零的格为 m+n-1个，即保证基变量的个数为 m+n-1个。
管 理 运 筹 学 34
§ 4* 运输问题的表上作业法二、最优解的判别
1.闭回路法所谓 闭回路 是在已给出的调运方案的运输表上从一个代表非基变量的空格出发，沿水平或垂直方向前进，只有遇到代表基变量的填入数字的格才能向左或右转 90度（当然也可以不改变方向）继续前进，这样继续下去，直至回到出发的那个空格，由此形成的封闭折线叫做闭回路。一个空格存在唯一的闭回路。
所谓 闭回路法,就是对于代表非基变量的空格（其调运量为零），把它的调运量调整为 1，由于产销平衡的要求,
我们必须对这个空格的闭回路的顶点的调运量加上或减少 1。
最后我们计算出由这些变化给整个运输方案的总运输费带来的变化。如果所有代表非基变量的空格的检验数也即非基变量的检验数都大于等于零，则已求得最优解，否则继续迭代找出最优解。
管 理 运 筹 学 35
§ 4* 运输问题的表上作业法
从非基变量 x11出发，找到一个闭回路如上表所示。回路有四个顶点，
除 x11外，其余都为基变量。现在把 x11的调运量从零增加为 1吨，运费也增加了 3元，为了使 A1产量平衡,x13必须减少 1吨，运费减少 3元。为了
B3的销量平衡,x23必须增加 1吨，运费增加 2元。同理把 x21减少 1吨，运费减少 1元。调整后，总运费增加了 3-3+2-1=1元。说明如果让 x11为基变量，运费就会增加，其增加值 1作为 x11的 检验数,为了区别调整量，
我们把 1加圈。
用同样的方法可以找出所有空格（即非基变量）的检验数。
销地产地 B1 B2 B3 B4 产量
A1 1 4 7
A2 3 1 4
A3 9
销量 3 6 5 6 2020
3 11 3 10
8
510
29
47
1
管 理 运 筹 学 36
Bj
Ai
B1 B2 B3 B4 ai
A1
9 3 8 4
70× 60 10 ×
A2
7 6 5 1
50× × 20 30
A3
2 10 9 2
2010 × 10 ×
bj 10 60 40 30
8
31331311,,,xxxx31331311,,,CCCC
829893133131111 CCCC?
0
9 6
6 -3
39512
698310
63856
92957
08514
3323243434
3313123232
1213232222
3133232121
1323244114
CCCC
CCCC
CCCC
CCCC
CCCC
管 理 运 筹 学 37
2,位势法求检验 位势法求检验数是根据对偶理论推导出来的一种方法 。
m
i
n
j
jiij xcZ
1 1
m in
njmix
njbx
miax
ij
m
i
jij
n
j
iij
,,2,1,,2,1,0
,,2,1
,2,1
1
1
；
，
，
设前 m个约束对应的对偶变量为 ui,i=1,2,…,m,后 n个约束对应的对偶变量为 vj,j=1,2,…,n则运输问题的对偶问题是
§ 4* 运输问题的表上作业法管 理 运 筹 学 38
§ 4* 运输问题的表上作业法
m
i
n
j
jjii vbuaw
1 1
m a x
njmivu
njmiCvu
ji
ijji
,2,1;,,2,1,
,,2,1;,,2,1,
无约束又因为：
记原问题基变量 XB的下标集合为 I,有如下式子成立：
IjivuC
IjiCvu
jiijji
ijji
).()
),(
（?
解上面第一个方程，将 ui,vj代入第二个方程求出 λij
ijijijBijij YPcPBcc 1?
管 理 运 筹 学 39
§ 4* 运输问题的表上作业法
2.位势法所谓位势法，我们对运输表上的每一行赋予一个数值 ui，对每一列赋予一个数值 vj，它们的数值是由基变量 xij的检验数 所决定的，则非基变量 xij的检验数就可以用公式 求出。
我们先给 u1赋个任意数值，不妨设 u1=0，则从基变量 x13的检验数求得 v3=c13-u1=3-0=3。同理可以求得 v4=10,u2=-1等等见上表。检验值的求法即用公式,如 。
销地产地 B1 B2 B3 B4 ui
A1 1 2 4 3 0
A2 3 1 1 -1 -1
A3 10 6 12 3 -5
vj 2 9 3 10 2020
3 11 3 10
8
510
29
47
1
0 jiijij vuc?
jiijij vuc
jiijij vuc 1203111111 vuc?
管 理 运 筹 学 40
§ 4* 运输问题的表上作业法三、改进运输方案的办法 ——闭回路调整法当表中的某个检验数小于零时，方案不为最优，需要调整。方法是：选取所有负检验数最小的非基变量作为入基变量，以求尽快实现最优。本例中取,
表明增加一个单位的 x24运输量，可使得总运费减少 1。在以 x24为出发点的闭回路中，找出所有偶数的顶点的调运量,x14=3,x23=1,x24=min(3,1)=1。把所有闭回路上为偶数顶点的运输量都减少这个值，奇数顶点的运输量都增加这个值 (见下表 )。
124
销地产地 B1 B2 B3 B4 ui
A1 4(+1) 3(-1) 0
A2 3 1 (-1) +1 -1
A3 6 3 -5
vj 2 9 3 10 2020
3 11 3 10
8
510
29
47
1
管 理 运 筹 学 41
§ 4* 运输问题的表上作业法
对上表用位势法进行检验如下表销地产地 B1 B2 B3 B4 产量
A1 5 2 7
A2 3 1 4
A3 6 3 9
销量 3 6 5 6 2020
销地产地 B1 B2 B3 B4 ui
A1 0 2 5 2 0
A2 3 2 1 1 -1
A3 9 6 12 3 -5
vj 2 9 3 10 2020
3 11 3 10
8
510
29
47
1
管 理 运 筹 学 42
§ 4* 运输问题的表上作业法四、如何找多个最优方案识别是否有多个最优解的方法和单纯形表法一样，只需看最优方案中是否存在非基变量的检验数为零。如在本题中给出的最优运输方案中 x11的检验数为
0，可知此运输问题有多个最优解。只要把 x11作为入基变量，调整运输方案，
就可得到另一个最优方案。
销地产地 B1 B2 B3 B4
A1 (+2) 5 2(-2)
A2 3(-2) 1(+2)
A3 6 3
销地产地 B1 B2 B3 B4
A1 2 5
A2 1 3
A3 6 3
管 理 运 筹 学 43
§ 4* 运输问题的表上作业法
【 例 5.4】 求表 5-10给出的运输问题的初始基本可行解．
B1 B2 B3 B4 si
A1 4 10 4 4 20
A2 7 7 3 8 15
A3 1 2 10 6 15
dj 5 10 25 10 50
表 5-10
管 理 运 筹 学 44
§ 4* 运输问题的表上作业法表 5-11
Bj
Ai
B1 B2 B3 B4 ai
A1
4 10 4 4
20
A2
7 7 3 8
15
A3
1 2 10 6
15
bj 5 10 25 10 50
【 解 】
5
×
×
10 × ×
×
0
15 ×
10 10
第七章 运 输 问 题
§ 1 运 输 模 型
§ 2 运输问题的计算机求解
§ 3 运输问题的应用
§ 4* 运输问题的表上作业法管 理 运 筹 学 2
例 1,某公司从两个产地 A1,A2将物品运往三个销地 B1,B2,B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？
B 1 B 2 B 3 产量
A 1 6 4 6 200
A 2 6 5 5 300
销量 150 150 200
解,产销平衡问题,总产量 = 总销量设 xij 为从产地 Ai运往销地 Bj的运输量，得到下列运输量表,B 1 B 2 B 3 产量
A 1 x 1 1 x 1 2 x 1 3 200
A 2 x 2 1 x 2 2 x 2 3 300
销量 150 150 200
Min f = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23
s.t,x11+ x12 + x13 = 200
x21 + x22+ x23 = 300
x11 + x21 = 150
x12 + x22 = 150
x13 + x23 = 200x
ij ≥ 0 ( i = 1,2； j = 1,2,3）
§ 1 运 输 模 型管 理 运 筹 学 3
§ 1 运 输 模 型
一般运输模型,产销平衡
A1,A2,…,Am 表示某物资的 m个产地； B1,B2,…,Bn 表示某物质的
n个销地； si 表示产地 Ai的产量； dj 表示销地 Bj 的销量； cij 表示把物资从产地
Ai运往销地 Bj的单位运价。
设 xij 为从产地 Ai运往销地 Bj的运输量，得到下列一般运输量问题的模型：
m n
Min f = cij xij
i = 1 j = 1
n
s.t,? xij = si i = 1,2,…,m
j = 1
m
xij = dj j = 1,2,…,n
i = 1
xij ≥ 0 (i = 1,2,…,m ; j = 1,2,…,n)
变化：
1）有时目标函数求最大。如求利润最大或营业额最大等；
2）当某些运输线路上的能力有限制时，在模型中直接加入约束条件
（等式或不等式约束 )；
3）产销不平衡时，可加入假想的产地（销大于产时）或销地（产大于销时）。
管 理 运 筹 学 4
§ 2 运输问题的计算机求解例 2,某公司从两个产地 A1,A2将物品运往三个销地 B1,B2、
B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？
解,增加一个虚设的销地运输费用为 0
B 1 B 2 B 3 产量
A 1 6 4 6 3 00
A 2 6 5 5 300
销量 150 150 200 6 0 0
500
B 1 B 2 B 3 B 4 产量
A 1 6 4 6 0 3 00
A 2 6 5 5 0 300
销量 150 150 200 100 60 0
600
管 理 运 筹 学 5
§ 2 运输问题的计算机求解例 3,某公司从两个产地 A1,A2将物品运往三个销地 B1,B2、
B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？
解,增加一个虚设的产地运输费用为 0
B 1 B 2 B 3 产量
A 1 6 4 6 200
A 2 6 5 5 300
销量 250 200 200 50 0
650
B 1 B 2 B 3 产量
A 1 6 4 6 2 00
A 2 6 5 5 300
A 3 0 0 0 150
销量 250 200 200 65 0
650
管 理 运 筹 学 6
§ 3 运输问题的应用一、产销不平衡的运输问题例 4,石家庄北方研究院有一、二、三三个区。每年分别需要用煤 3000,1000、
2000吨，由河北临城、山西盂县两处煤矿负责供应，价格、质量相同。供应能力分别为 1500,4000吨，运价为：
由于需大于供，经院研究决定一区供应量可减少 0--300吨，二区必须满足需求量，三区供应量不少于 1500吨，试求总费用为最低的调运方案。
解,根据题意，作出产销平衡与运价表：
这里 M 代表一个很大的正数，其作用是强迫相应的 x31,x33,x34取值为 0。
一区 二区 三区 产量山西盂县 1,8 0 1,70 1,5 5 4000
河北临城 1,6 0 1,5 0 1,7 5 1500
需要量 3000 1000 2000
一区 一区 二区 三区 三区 产量山西盂县 1,8 0 1,8 0 1,70 1,5 5 1,5 5 4000
河北临城 1,6 0 1,6 0 1,5 0 1,7 5 1,7 5 1500
假想生产点 M 0 M M 0 500
需要量 2 7 00 3 00 1000 1 5 00 5 00 6000
6000
管 理 运 筹 学 7
§ 3 运输问题的应用一、产销不平衡的运输问题例 5,设有 A,B,C三个化肥厂供应 1,2,3,4四个地区的农用化肥。假设效果相同，有关数据如下表：
试求总费用为最低的化肥调拨方案。
解,根据题意，作出产销平衡与运价表：
最低要求必须满足，因此把相应的虚设产地运费取为 M,而最高要求与最低要求的差允许按需要安排，因此把相应的虚设产地运费取为 0 。对应 4”的销量
50 是考虑问题本身适当取的数据，根据产销平衡要求确定 D的产量为 50。
1 2 3 4 产量
A 1 6 1 3 22 17 50
B 14 1 3 19 15 60
C 19 20 23 --- 50
最低需要量 30 70 0 10
最高需要量 50 70 30 不限
1 ’
1,2 3 4 ’ 4,产量
A 1 6 1 6 1 3 22 17 17 50
B 14 14 1 3 19 15 15 60
C 19 19 20 23 M M 50
D M 0 M 0 M 0 50
销量 30 20 70 30 10 50 2 1 0
2 1 0
管 理 运 筹 学 8
§ 3 运输问题的应用二、生产与储存问题例 6,某厂按合同规定须于当年每个季度末分别提供 10,15、
25,20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如右表。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用 0.15
万元。试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。
生产能力 （台） 单位成本 （万元）
一季度 25 1 0,8
二季度 35 1 1,1
三季度 30 1 1,0
四季度 10 1 1,3
管 理 运 筹 学 9
§ 3 运输问题的应用解,设 xij为第 i 季度生产的第 j 季度交货的柴油机数目，那么应满足：
交货,x11 = 10 生产,x11 + x12 + x13 + x14 ≤ 25
x12 + x22 = 15 x22 + x23 + x24 ≤ 35
x13 + x23 + x33 = 25 x33 + x34 ≤ 30
x14 + x24 + x34 + x44 = 20 x44 ≤ 10
把第 i 季度生产的柴油机数目看作第 i 个生产厂的产量；把第 j 季度交货的柴油机数目看作第 j 个销售点的销量；成本加储存、维护等费用看作运费。可构造下列产销平衡问题：
目标函数,Min f = 10.8 x11 +10.95 x12 +11.1 x13 +11.25 x14 +11.1 x22 +11.25
x23 +11.4 x24 +11.0 x33 +11.15 x34 +11.3 x44
第一季度第二季度 第三季度 第四季度 D 产量第一季度 1 0,8 0 1 0,9 5 1 1,1 0 1 1,2 5 0 25
第二季度 M 1 1,1 0 1 1,2 5 1 1,4 0 0 35
第三季度 M M 1 1,0 0 1 1,1 5 0 30
第四季度 M M M 1 1,3 0 0 10
销量 10 15 25 20 30 1 0 0
1 0 0
管 理 运 筹 学 10
§ 3 运输问题的应用二、生产与储存问题例 7,光明仪器厂生产电脑绣花机是以产定销的。已知 1至 6月份各月的生产能力、合同销量和单台电脑绣花机平均生产费用见下表：
已知上年末库存 103台绣花机，如果当月生产出来的机器当月不交货，
则需要运到分厂库房，每台增加运输成本 0.1万元,每台机器每月的平均仓储费、维护费为 0.2万元。在 7--8月份销售淡季，全厂停产 1个月，因此在 6
月份完成销售合同后还要留出库存 80台。加班生产机器每台增加成本 1万元。问应如何安排 1--6月份的生产，可使总的生产费用（包括运输、仓储、维护）最少？
正常生产能力 （台） 加班生产能力 （台） 销量 （台） 单台费用 （万元）
1 月份 60 10 104 15
2 月份 50 10 75 14
3 月份 90 20 1 1 5 1 3,5
4 月份 100 40 160 13
5 月份 100 40 103 13
6 月份 80 40 70 1 3,5
管 理 运 筹 学 11
§ 3 运输问题的应用解,这个生产存储问题可化为运输问题来做。考虑,各月生产与交货分别视为产地和销地
1） 1--6月份合计生产能力（包括上年末储存量）为 743台，销量为 707台。设一假想销地销量为 36；
2）上年末库存 103台，只有仓储费和运输费，把它列为第 0行；
3） 6月份的需求除 70台销量外，还要 80台库存，其需求应为 70+80=150台；
4） 1--6表示 1--6月份正常生产情况,1’--6’表示 1--6月份加班生产情况。
产销平衡与运价表：
1 月 2 月 3 月 4 月 5 月 6 月 虚销地 正常产量 加班产量
0 0,3 0,5 0,7 0,9 1,1 1,3 0 103
1 15 1 5,3 1 5,5 1 5,7 1 5,9 1 6,1 0 60
1 ’ 16 1 6,3 1 6,5 1 6,7 6,9 1 7,1 0 10
2 M 14 1 4,3 1 4,5 1 4,7 1 4,9 0 50
2 ’ M 15 1 5,3 1 5,5 1 5,7 1 5,9 0 10
3 M M 1 3,5 1 3,8 1 4,0 1 4,2 0 90
3 ’ M M 1 4,5 1 4,8 1 5,0 1 5,2 0 20
4 M M M 1 3,0 1 3,3 1 3,5 0 100
4 ’ M M M 1 4,0 1 4,3 1 4,5 0 40
5 M M M M 1 3,0 1 3,3 0 100
5 ’ M M M M 1 4,0 1 4,3 0 40
6 M M M M M 1 3,5 0 80
6 ’ M M M M M 1 4,5 0 40
销量 104 75 1 1 5 160 103 150 36 7 4 3
743
管 理 运 筹 学 12
§ 3 运输问题的应用
1 月 2 月 3 月 4 月 5 月 6 月 假想销量
0 63 15 5 20
1 41 19
1 ’
2 50
2 ’ 10
3 90
3 ’ 20
4 100
4 ’ 40
5 63 37
5 ’ 40
6 80
6 ’ 33 7
用“管理运筹学”软件解得的结果是,1-6月最低生产费用为 8307.5
万元，每月的销售安排如下表所示管 理 运 筹 学 13
§ 3 运输问题的应用三、转运问题：
在原运输问题上增加若干转运站。运输方式有：产地?转运站、转运站?销地、产地?产地、产地?销地、销地?转运站、销地?产地等 。
例 8,腾飞电子仪器公司在大连和广州有两个分厂生产同一种仪器，大连分厂每月生产 400台，广州分厂每月生产 600
台。该公司在上海和天津有两个销售公司负责对南京、济南、南昌、青岛四个城市的仪器供应。另外因为大连距离青岛较近，公司同意大连分厂向青岛直接供货，运输费用如图，单位是百元。问应该如何调运仪器，
可使总运输费用最低？ 图中 1-广州,2 - 大连、
3 - 上海,4 - 天津,5 - 南京,6 - 济南,7 - 南昌,8 - 青岛管 理 运 筹 学 14
§ 3 运输问题的应用解,设 xij 为从 i 到 j 的运输量，可得到有下列特点的线性规划模型：
目标函数,Min f = 所有可能的运输费用（运输单价与运输量乘积之和）
约束条件：
对产地（发点） i,输出量 - 输入量 = 产量对转运站（中转点）：输入量 - 输出量 = 0
对销地（收点） j,输入量 - 输出量 = 销量例 8．（续）
目标函数,Min f = 2x13+ 3x14+ 3x23+ x24+ 4x28 + 2x35+ 6x36+ 3x37+ 6x38+
4x45+ 4x46+ 6x47+ 5x48
约束条件：
s.t,x13+ x14 ≤ 600 ( 广州分厂供应量限制）
x23+ x24+ x28 ≤ 400 ( 大连分厂供应量限制）
-x13- x23 + x35 + x36+ x37 + x38 = 0 （上海销售公司，转运站）
-x14- x24 + x45 + x46+ x47 + x48 = 0 （天津销售公司，转运站）
x35+ x45 = 200 （南京的销量）
x36+ x46 = 150 （济南的销量）
x37+ x47 = 350 （南昌的销量）
x38+ x48 + x28 = 300 （青岛的销量）
xij ≥ 0,i,j = 1,2,3,4,5,6,7,8
管 理 运 筹 学 15
§ 3 运输问题的应用用“管理运筹学”软件求得结果：
x13 = 550 x14 =50 ；
x23 = 0 x24 = 100 x28 = 300 ；
x35 = 200 x36 = 0 x37 = 350 x38 = 0 ；
x45 = 0 x46 = 150 x47 = 0 x48 = 0 。
最小运输费用为,4600百元例 9,某公司有 A1,A2,A3三个分厂生产某种物资，分别供应 B1,B2,B3,B4
四个地区的销售公司销售。假设质量相同，有关数据如下表：
试求总费用为最少的调运方案。
假设：
1.每个分厂的物资不一定直接发运到销地，可以从其中几个产地集中一起运；
2.运往各销地的物资可以先运给其中几个销地，再转运给其他销地；
3.除产销地之外，还有几个中转站，在产地之间、销地之间或在产地与销地之间转运。
B 1 B 2 B 3 B 4 产量
A 1 3 1 1 3 10 7
A 2 1 9 2 8 4
A 3 7 4 10 5 9
销量 3 6 5 6 和 = 20
管 理 运 筹 学 16
§ 3 运输问题的应用运价如下表：
解,把此转运问题转化为一般运输问题：
1、把所有产地、销地、转运站都同时看作产地和销地；
2、运输表中不可能方案的运费取作 M，自身对自身的运费为 0；
3,Ai,产量为 20+原产量,销量为 20； Ti,产量、销量均为 20； Bi,产量为 20,销量为 20 +原销量，其中 20为各点可能变化的最大流量；
4、对于最优方案，其中 xi i 为自身对自身的运量，实际上不进行运作。
A
1
A
2
A
3
T
1
T
2
T
3
T
4
B
1
B
2
B
3
B
4
A
1
1 3 2 1 4 3 3 1 1 3 10
A
2
1 --- 3 5 --- 2 1 9 2 8
A
3
3 --- 1 --- 2 3 7 4 10 5
T
1
2 3 1 1 3 2 2 8 4 6
T
2
1 5 --- 1 1 1 4 5 2 7
T
3
4 --- 2 3 1 2 1 8 2 4
T
4
3 2 3 2 1 2 1 --- 2 6
B
1
3 1 7 2 4 1 1 1 4 2
B
2
11 9 4 8 5 8 --- 1 2 1
B
3
3 2 10 4 2 2 2 4 2 3
B
4
10 8 5 6 7 4 6 2 1 3
管 理 运 筹 学 17
§ 3 运输问题的应用扩大的运输问题产销平衡与运价表：
A
1
A
2
A
3
T
1
T
2
T
3
T
4
B
1
B
2
B
3
B
4
产量
A
1
0 1 3 2 1 4 3 3 1 1 3 10 27
A
2
1 0 M 3 5 M 2 1 9 2 8 24
A
3
3 M 0 1 M 2 3 7 4 10 5 29
T
1
2 3 1 0 1 3 2 2 8 4 6 20
T
2
1 5 M 1 0 1 1 4 5 2 7 20
T
3
4 M 2 3 1 0 2 1 8 2 4 20
T
4
3 2 3 2 1 2 0 1 M 2 6 20
B
1
3 1 7 2 4 1 1 0 1 4 2 20
B
2
11 9 4 8 5 8 M 1 0 2 1 20
B
3
3 2 10 4 2 2 2 4 2 0 3 20
B
4
10 8 5 6 7 4 6 2 1 3 0 20
销量 20 20 20 20 20 20 20 23 26 25 26 240
管 理 运 筹 学 18
§ 4* 运输问题的表上作业法
表上作业法是一种求解运输问题的特殊方法，其 实质是单纯形法。
运输问题都存在最优解。
计算过程（假设产销平衡）：
– 1.找出初始基本可行解。对于有 m个产地 n个销地的产销平衡问题，
则有 m个关于产量的约束方程和 n个关于销量的约束方程。由于产销平衡，其模型最多只有 m+n-1个独立的约束方程，即运输问题有
m+n-1个基变量。在 m× n的产销平衡表上给出 m+n-1个数字格，其相对应的调运量的值即为基变量的值。
– 2.求各非基变量的检验数，即检验除了上述 m+n-1个基变量以外的空格的检验数判别是否达到最优解，如果已是最优，停止计算，否则转到下一步。
– 3.确定入基变量和出基变量，找出新的基本可行解。在表上用闭回路法调整。
– 4.重复 2,3直到得到最优解。
管 理 运 筹 学 19
§ 4* 运输问题的表上作业法运输问题的一般数学模型设有 m个产地（记作 A1,A2,A3,…,Am），生产某种物资，其产量分别为 a1,a2,…,am；有 n个销地（记作 B1,B2,…,Bn），
其需要量分别为 b1,b2,…,bn；且产销平衡，即 。
从第 i个产地到 j 个销地的单位运价为 cij,在满足各地需要的前提下，求总运输费用最小的调运方案。 设 xij(i=1,2,…,m；
j=1,2,…,n)为第 i个产地到第 j个销地的运量，则数学模型为：
n
j
j
m
i
i ba
11
n
j
ijij
m
i
xcz
11
m in
njmix
njbx
miax
ij
j
m
i
ij
n
j
iij
,,1;,,1,0
,,1
,,1
1
1
管 理 运 筹 学 20
§ 4* 运输问题的表上作业法
n
i
ijij
m
i
xcz
11
m in
njmix
njbx
miax
ij
j
m
i
ij
n
j
iij
,,1;,,1,0
,,1
,,1
1
1
设平衡运输问题的数学模型为：
模型特征
1.运输问题存在可行解，也一定存在最优解
2.当供应量和需求量都是整数时，则一定存在整数最优解
3.有 m+n个约束,mn个变量
4.有 m+n－ 1个基变量管 理 运 筹 学 21
§ 4* 运输问题的表上作业法
【 证 】 因为产销平衡,即,将前 m个约束方程两边相加得
m
i
n
j
ii ba
1 1
m
i
n
j
m
i
iij ax
1 1 1
再将后 n个约束相加得
n
j
m
i
n
j
jij bx
1 1 1
显然前 m个约束方程之和等于后 n个约束方程之和,m+n个约束方程是相关的,系数矩阵
【 定理 1】 设有 m个产地 n个销地且产销平衡的运输问题，则基变量数为 m+n-1。
管 理 运 筹 学 22
§ 4* 运输问题的表上作业法中任意 m+n阶子式等于零，取第一行到 m+n－ 1行与对应的列（共 m+n-1列）组成的 m+n－ 1阶子式
1,1121121,,,,?nmnnn xxxxxx,，，
11 12 1 21 22 2 1 2
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
n n m m m n
x x x x x x x x x
A
＝
管 理 运 筹 学 23
§ 4* 运输问题的表上作业法 0
1
1
1
1
1
1111
故 r(A)=m+n－ 1所以运输问题有 m+n－ 1个基变量 。
为了在 mn个变量中找出 m+n－ 1个变量作为一组基变量,就是要在 A中找出 m+n-1个线性无关的列向量,下面引用闭回路的概念寻找这些基变量 。
管 理 运 筹 学 24
§ 4* 运输问题的表上作业法
),,,,,,(,,,,,,2121132222111 互不相同；称集合 ssjijijijijiji jjjiiixxxxxx sss
为一个闭回路,集合中的变量称为回路的顶点,相邻两个变量的连线为闭回路的边 。
x25x23
B1 B2 B3 B4 B5
A1
A2
A3 x35
A4 x43
x11 x12
x31
x42
表中闭回路的变量集合是
{x11,x12,x42,x 43,x 23,x 25,x
35,x 31}共有 8个顶点,这 8
个顶点间用水平或垂直线段连接起来，组成一条封闭的回路。
管 理 运 筹 学 25
§ 4* 运输问题的表上作业法
x11 x12
x32 x33
x41
B1 B2 B3
A1
A2
A3
A4 x
43
一条回路中的顶点数一定是偶数，回路遇到顶点必须转 90度与另一顶点连接，上表中的变量
x 32及 x33不是回闭路的顶点，只是连线的交点。
表中闭回路是
123233434111,,,,,xxxxxx
;,,,,,121131352521 xxxxxxA?
;,,,,2111123233 xxxxxB?
例如变量组
A不能组成一条闭回路，但 A中包含有闭回路
B的变量数是奇数，显然不是闭回路，也不含有闭回路；
管 理 运 筹 学 26
§ 4* 运输问题的表上作业法
333211122321,,,,,xxxxxxC?
C是一条闭回路，若把 C重新写成就不难看出 C仍是一条闭回路。?111232332321,,,,,xxxxxxC?
【 定理 2】 若变量组 B 包含有闭回路,则 B
中的变量对应的例向量线性相关 。
【 证 】 由线性代数知,向量组中部分向量组线性相关则该向量组线性相关,显然,将 C中列向量分别乘以正负号线性组合后等于零,即
1 1 1 2 2 2 1 0si j i j i j i jP P P P－
因而 C中的列向量线性相关,所以 B中列向量线性相关 。
12111,,,jijiji sxxxC
管 理 运 筹 学 27
§ 4* 运输问题的表上作业法由定理 2可知,当一个变量组中不包含有闭回路,则这些变量对应的系数向量线性无关 。
求运输问题的一组基变量,就是要找到 m+n－ 1个变量,使得它们对应的系数列向量线性无关,由定理 2,找这样的一组变量是很容易的,只要 m+n－ 1个变量中不包含闭回路,就可得到一组基变量 。
因而有：
【 定理 3】 m+n－ 1个变量组构成基变量的充要条件是它不包含任何闭回路 。
定理 3告诉了一个求基变量的简单方法,同时也可以判断一组变量是否可以作为某个运输问题的基变量 。 这种方法是直接在运价表中进行的,不需要在系数矩阵 A中去寻找,从而给运输问题求初始基可行解带来极大的方便 。
管 理 运 筹 学 28
§ 4* 运输问题的表上作业法
Bj
Ai
B1 B2 B3 B4 ai
A1 c11 c12 c13 c14 a1
x11 x12 x13 x14
A2 c21 c22 c23 c24 a2
x21 x22 x23 x24
A3 c31 c32 c2 c34 a3
x31 x32 x33 x34
bj b1 b2 b3 b4
例如,m=3,n=4,将 xij与运价 Cij放在同一张表中,如表 5-5所示 。
管 理 运 筹 学 29
§ 4* 运输问题的表上作业法这个运输问题的基变量数目是 3+4－ 1=6。 变量组中有 7个变量,显然不能构成一组基变量,又如中有 6个变量,但包含有一条闭回路故不能构成一组基变量 。 变量组有 6个变量且不含有任何闭回路,故可以构成此问题的一组基变量 。
22121324323111,,,,,,xxxxxxx
,,,,,,342413322221 xxxxxx
24343222,,,xxxx
343332222111,,,,,xxxxxx
管 理 运 筹 学 30
§ 4* 运输问题的表上作业法
例 10.喜庆食品公司有三个生产面包的分厂 A1,A2,A3，有四个销售公司 B1,B2,B3,B4，其各分厂每日的产量、各销售公司每日的销量以及各分厂到各销售公司的单位运价如表所示，在表中产量与销量的单位为吨，运价的单位为百元 /吨。问该公司应如何调运产品在满足各销点的需求量的前提下总运费最少？
这是一个产销平衡的运输问题，因此不需要再设假想产地和销地了。
销地产地 B1 B2 B3 B4
产量
A1 3 11 3 10 7
A2 1 9 2 8 4
A3 7 4 10 5 9
销量 3 6 5 6 20
20
管 理 运 筹 学 31
§ 4* 运输问题的表上作业法一、确定初始基本可行解为了把初始基本可行解与运价区分开，我们把 运价 放在每一栏的 右上角,每一栏的中间写上初始基本可行解（调运量）。
1.西北角法,先从表的左上角（即西北角）的变量 x11开始分配运输量，并使
x11取尽可能大的值，即 x11=min(7,3)=3,则 x21与 x31必为零。同时把 B1的销量与 A1的产量都减去 3填入销量和产量处，划去原来的销量和产量。同理可得余下的初始基本可行解。
销地产地 B1 B2 B3 B4 产量
A1 3 4 7 4 0
A2 2 2 4 2 0
A3 3 6 9 6 0
销量
3
0
6
2
0
5
3
0
6
0
20
20
3 11 3 10
8
510
29
47
1
管 理 运 筹 学 32
§ 4* 运输问题的表上作业法
2.最小元素法西北角法是对西北角的变量分配运输量，而最小元素法是就近供应，即对单位运价最小的变量分配运输量。在表上找到单位运价最小的 x21，并使 x21取尽可能大的值，即 x21=min(4,3)=3,把 A1的产量改为 1,B1的销量改为 0，并把 B1列划去。在剩下的 3× 3矩阵中再找最小运价，同理可得其他的基本可行解。
一般来说用最小元素法求得的初始基本可行解比西北角法求得的总运价要少。这样从用最小元素法求得的初始基本可行解出发求最优解的迭代次数可能少一些。
销地产地 B1 B2 B3 B4 产量
A1 4 3 7 3 0
A2 3 1 4 1 0
A3 6 3 9 3 0
销量
3
0
6
0
5
4
0
6
3
0
20
20
3 11 3 10
8
510
29
47
1
管 理 运 筹 学 33
§ 4* 运输问题的表上作业法
在求初始基本可行解时要注意的两个问题：
– 1.当我们取定 xij的值之后，会出现 Ai的产量与 Bj的销量都改为零的情况，这时只能划去 Ai行或 Bj列，但不能同时划去 Ai行与 Bj列。
– 2.用最小元素法时，可能会出现只剩下一行或一列的所有格均未填数或未被划掉的情况，此时在这一行或者一列中除去已填上的数外均填上零，不能按空格划掉。这样可以保证填过数或零的格为 m+n-1个，即保证基变量的个数为 m+n-1个。
管 理 运 筹 学 34
§ 4* 运输问题的表上作业法二、最优解的判别
1.闭回路法所谓 闭回路 是在已给出的调运方案的运输表上从一个代表非基变量的空格出发，沿水平或垂直方向前进，只有遇到代表基变量的填入数字的格才能向左或右转 90度（当然也可以不改变方向）继续前进，这样继续下去，直至回到出发的那个空格，由此形成的封闭折线叫做闭回路。一个空格存在唯一的闭回路。
所谓 闭回路法,就是对于代表非基变量的空格（其调运量为零），把它的调运量调整为 1，由于产销平衡的要求,
我们必须对这个空格的闭回路的顶点的调运量加上或减少 1。
最后我们计算出由这些变化给整个运输方案的总运输费带来的变化。如果所有代表非基变量的空格的检验数也即非基变量的检验数都大于等于零，则已求得最优解，否则继续迭代找出最优解。
管 理 运 筹 学 35
§ 4* 运输问题的表上作业法
从非基变量 x11出发，找到一个闭回路如上表所示。回路有四个顶点，
除 x11外，其余都为基变量。现在把 x11的调运量从零增加为 1吨，运费也增加了 3元，为了使 A1产量平衡,x13必须减少 1吨，运费减少 3元。为了
B3的销量平衡,x23必须增加 1吨，运费增加 2元。同理把 x21减少 1吨，运费减少 1元。调整后，总运费增加了 3-3+2-1=1元。说明如果让 x11为基变量，运费就会增加，其增加值 1作为 x11的 检验数,为了区别调整量，
我们把 1加圈。
用同样的方法可以找出所有空格（即非基变量）的检验数。
销地产地 B1 B2 B3 B4 产量
A1 1 4 7
A2 3 1 4
A3 9
销量 3 6 5 6 2020
3 11 3 10
8
510
29
47
1
管 理 运 筹 学 36
Bj
Ai
B1 B2 B3 B4 ai
A1
9 3 8 4
70× 60 10 ×
A2
7 6 5 1
50× × 20 30
A3
2 10 9 2
2010 × 10 ×
bj 10 60 40 30
8
31331311,,,xxxx31331311,,,CCCC
829893133131111 CCCC?
0
9 6
6 -3
39512
698310
63856
92957
08514
3323243434
3313123232
1213232222
3133232121
1323244114
CCCC
CCCC
CCCC
CCCC
CCCC
管 理 运 筹 学 37
2,位势法求检验 位势法求检验数是根据对偶理论推导出来的一种方法 。
m
i
n
j
jiij xcZ
1 1
m in
njmix
njbx
miax
ij
m
i
jij
n
j
iij
,,2,1,,2,1,0
,,2,1
,2,1
1
1
；
，
，
设前 m个约束对应的对偶变量为 ui,i=1,2,…,m,后 n个约束对应的对偶变量为 vj,j=1,2,…,n则运输问题的对偶问题是
§ 4* 运输问题的表上作业法管 理 运 筹 学 38
§ 4* 运输问题的表上作业法
m
i
n
j
jjii vbuaw
1 1
m a x
njmivu
njmiCvu
ji
ijji
,2,1;,,2,1,
,,2,1;,,2,1,
无约束又因为：
记原问题基变量 XB的下标集合为 I,有如下式子成立：
IjivuC
IjiCvu
jiijji
ijji
).()
),(
（?
解上面第一个方程，将 ui,vj代入第二个方程求出 λij
ijijijBijij YPcPBcc 1?
管 理 运 筹 学 39
§ 4* 运输问题的表上作业法
2.位势法所谓位势法，我们对运输表上的每一行赋予一个数值 ui，对每一列赋予一个数值 vj，它们的数值是由基变量 xij的检验数 所决定的，则非基变量 xij的检验数就可以用公式 求出。
我们先给 u1赋个任意数值，不妨设 u1=0，则从基变量 x13的检验数求得 v3=c13-u1=3-0=3。同理可以求得 v4=10,u2=-1等等见上表。检验值的求法即用公式,如 。
销地产地 B1 B2 B3 B4 ui
A1 1 2 4 3 0
A2 3 1 1 -1 -1
A3 10 6 12 3 -5
vj 2 9 3 10 2020
3 11 3 10
8
510
29
47
1
0 jiijij vuc?
jiijij vuc
jiijij vuc 1203111111 vuc?
管 理 运 筹 学 40
§ 4* 运输问题的表上作业法三、改进运输方案的办法 ——闭回路调整法当表中的某个检验数小于零时，方案不为最优，需要调整。方法是：选取所有负检验数最小的非基变量作为入基变量，以求尽快实现最优。本例中取,
表明增加一个单位的 x24运输量，可使得总运费减少 1。在以 x24为出发点的闭回路中，找出所有偶数的顶点的调运量,x14=3,x23=1,x24=min(3,1)=1。把所有闭回路上为偶数顶点的运输量都减少这个值，奇数顶点的运输量都增加这个值 (见下表 )。
124
销地产地 B1 B2 B3 B4 ui
A1 4(+1) 3(-1) 0
A2 3 1 (-1) +1 -1
A3 6 3 -5
vj 2 9 3 10 2020
3 11 3 10
8
510
29
47
1
管 理 运 筹 学 41
§ 4* 运输问题的表上作业法
对上表用位势法进行检验如下表销地产地 B1 B2 B3 B4 产量
A1 5 2 7
A2 3 1 4
A3 6 3 9
销量 3 6 5 6 2020
销地产地 B1 B2 B3 B4 ui
A1 0 2 5 2 0
A2 3 2 1 1 -1
A3 9 6 12 3 -5
vj 2 9 3 10 2020
3 11 3 10
8
510
29
47
1
管 理 运 筹 学 42
§ 4* 运输问题的表上作业法四、如何找多个最优方案识别是否有多个最优解的方法和单纯形表法一样，只需看最优方案中是否存在非基变量的检验数为零。如在本题中给出的最优运输方案中 x11的检验数为
0，可知此运输问题有多个最优解。只要把 x11作为入基变量，调整运输方案，
就可得到另一个最优方案。
销地产地 B1 B2 B3 B4
A1 (+2) 5 2(-2)
A2 3(-2) 1(+2)
A3 6 3
销地产地 B1 B2 B3 B4
A1 2 5
A2 1 3
A3 6 3
管 理 运 筹 学 43
§ 4* 运输问题的表上作业法
【 例 5.4】 求表 5-10给出的运输问题的初始基本可行解．
B1 B2 B3 B4 si
A1 4 10 4 4 20
A2 7 7 3 8 15
A3 1 2 10 6 15
dj 5 10 25 10 50
表 5-10
管 理 运 筹 学 44
§ 4* 运输问题的表上作业法表 5-11
Bj
Ai
B1 B2 B3 B4 ai
A1
4 10 4 4
20
A2
7 7 3 8
15
A3
1 2 10 6
15
bj 5 10 25 10 50
【 解 】
5
×
×
10 × ×
×
0
15 ×
10 10
