运筹学课件第四章运输问题制作：北京理工大学 吴祈宗等
2
第四章 运输问题
运输问题与有关概念
运输问题的求解 —表上作业法
运输问题应用 —建模本章内容重点
3
1.运输问题模型及有关概念问题的提出一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地,在每个产地的供应量与每个销地的需求量已知,并知道各地之间的运输单价的前提下,如何确定一个使得总的运输费用最小的方案 。
4
1.运输问题模型及有关概念例 4.1:某公司从两个产地 A1、
A2将物品运往三个销地 B1,B2,B3，
各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？
5
解,产销平衡问题：
总产量 = 总销量设 xij 为从产地 Ai运往销地 Bj
的运输量，得到下列运输量表：
1.运输问题模型及有关概念
6
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 = 200
xij≥0(i=1,2； j=1,2,3）
1.运输问题模型及有关概念
7
1 1 1 0 0 0
0 0 0 1 1 1
1 0 0 1 0 0
0 1 0 0 1 0
0 0 1 0 0 1
系数矩阵
1.运输问题模型及有关概念
8
模型系数矩阵特征
1.共有 m+n行，分别表示各产地和销地； m?n列，分别表示各决策变量；
2.每列只有两个 1，其余为 0，分别表示只有一个产地和一个销地被使用。
1.运输问题模型及有关概念
9
一般运输问题的线性规划模型及求解思路一般运输问题的提法：
假设 A1,A2,…,Am 表示某物资的 m个产地； B1,B2,…,Bn 表示某物资的 n个销地；
si表示产地 Ai 的产量； dj 表示销地 Bj 的销量； cij 表示把物资从产地 Ai 运往销地
Bj 的单位运价 （ 表 4-3） 。 如果
s1 + s2 + … + sm = d1 + d2 + … + dn
则称该运输问题为产销平衡问题；否则,称产销不平衡 。 首先讨论产销平衡问题 。
1.运输问题模型及有关概念
10
表 4-3 运输问题数据表
1.运输问题模型及有关概念销地产地
B1 B2 … Bn 产量
A1
A2
┇
Am
c11 c12 … c1n
c21 c22 … c2n
┇ ┇ ┇ ┇
cm1 cm2 … cmn
s1
s2
┇
sm
销量 d1 d2 … dn
设 xij 为从产地 Ai 运往销地 Bj 的运输量,根据这个运输问题的要求,可以建立运输变量表 （ 表 4-4） 。
11
表 4-4 运输问题变量表
1.运输问题模型及有关概念销地产地
B1 B2 … Bn 产量
A1
A2
┇
Am
x11 x12 … x1n
x21 x22 … x2n
┇ ┇ ┇
xm1 xm2 … xmn
s1
s2
┇
sm
销量 d1 d2 … dn
12
m n
Min f = cij xij （ 4-1）
i=1 j=1
n
s.t.? xij ≤si i = 1,2,…,m （ 4-2）
j=1m
xij ≤(=,≥)dj j = 1,2,…,n （ 4-3）
i=1
xij ≥ 0 (i=1,2,…,m;j=1,2,…,n)（ 4-4）
1.运输问题模型及有关概念于是得到下列 一般运输问题 的模型：
在模型 （ 4-1） —（ 4-4） 中,式 （ 4-2） 为 m 个产地的产量约束；式 （ 4-3） 为 n 个销地的销量约束 。
m n
Min f = cij xij
i=1 j=1
n
s.t,? xij = si i = 1,2,…,m (4-5)
j =1
m? x
ij = dj j = 1,2,…,n (4-6)i =1
xij ≥ 0 (i=1,2,…,m;j=1,2,…,n)
1.运输问题模型及有关概念对于 产销平衡 问题，可得到下列运输问题的模型：
14
在产销平衡问题 中,式 （ 4-2）,（ 4-3）
分别变为 （ 4-5）,（ 4-6）,约束条件成为等式 。
在实际问题建模时,还会出现如下一些变化：
（ 1） 有时目标函数求最大,如求利润最大或营业额最大等；
（ 2） 当某些运输线路上的能力有限制时,
模 型 中可 直 接加 入 （ 等 式或 不等 式 ）
约束；
1.运输问题模型及有关概念
(3)产销不平衡的情况 。 当销量大于产量时可加入一个虚设的产地去生产不足的物资,这相当于在式 （ 4-2）
每一式中加上 1 个松弛变量,共 m
个；当产量大于销量时可加入一个虚设的销地去消化多余的物资,这相当于在式 （ 4-3） 每一式中加上 1 个松弛变量,共 n 个 。
1.运输问题模型及有关概念
16
运输问题是一种特殊的线性规划问题,
在求解时依然可以采用单纯形法的思路,
如图 4-1所示 。
由于运输规划系数矩阵的特殊性,如果直接使用线性规划单纯形法求解计算,
则无法利用这些有利条件 。 人们在分析运输规划系数矩阵特征的基础上建立了针对运输问题的 表上作业法 。
下面主要讨论 基本可行解,检验数 以及基的转换 等问题 。
续下页
1.运输问题模型及有关概念
17
1.运输问题模型及有关概念基本可行解 是否最优解 结束换基是否图 4-1 运输问题的求解思路 返回
18
运输问题求解的有关概念考虑产销平衡问题,由于我们关心的量均在表 4-3与表 4-4中,因此考虑把表 4-3
与表 4-4合成一个表,如下表 4-5
表 4-5 运输问题求解作业数据表
(下页）
1.运输问题模型及有关概念
19
1.运输问题模型及有关概念销地产地
B1 B2 … Bn 产量
A1 c11
x11
c12
x12
… c1n
x1n
a1
A2 c21
x21
c22
x22
… c2n
x2n
a2
┇ ┇ ┇ ┇ ┇
Am cm1
xm1
cm2
xm2
… cmn
xmn
am
销量 b1 b2 … bn
20
运输问题的基变量共有 m + n -1
个,A的秩为 m + n -1。
运输问题的 m + n -1 个变量构成基变量的充分必要条件是不含闭回路。
重要概念,闭回路、闭回路的顶点特点运输问题基变量的
1.运输问题模型及有关概念
21
定义 4.1 在表 4-5的决策变量格中，凡是能够排列成下列形式的
xab,xac,xdc,xde,…,xst,xsb (4-7)
或 xab,xcb,xcd,xed,…,xst,xat (4-8)
其中,a,d,…,s 各不相同； b,c,…,t 各不相同,
我们称之为变量集合的一个 闭回路,并将式
（ 4-7）,式 （ 4-8） 中的变量称为这个 闭回路的顶点 。
为了说明这个特征,我们不加证明的给出一些概念和结论 。 下面的讨论建立在表 4-5
中决策变量格的基础上 。
1.运输问题模型及有关概念
22
例如,x13,x16,x36,x34,x24,x23 ；
x23,x53,x55,x45,x41,x21 ；
x11,x14,x34,x31等都是闭回路 。
若把闭回路的各变量格看作节点,
在表中可以画出如下形式的闭回路：
1.运输问题模型及有关概念闭回路示意图
23
根据定义可以看出闭回路的一些明显特点：
(1)闭回路均为一封闭折线,它的每一条边,或为水平的,或为垂直的；
(2)闭回路的每一条边 （ 水平的或垂直的 ） 均有且仅有两个闭回路的顶点 （ 变量格 ） 。
1.运输问题模型及有关概念
24
关于闭回路有如下的一些重要结论：
(1) 设 xab,xac,xdc,xde,…,xst,
xsb 是一个闭回路,那么该闭回路中变量所对应的系数列向量 pab,pac,pdc,
pde,…,pst,psb 线性相关；
(2) 若变量组 xab,xcd,xef,…,xst
中包含一个部分组构成闭回路,那么该变量组所对应的系数列向量 pab,pcd,
pef,…,pst 线性相关 。
根据上述结论以及线性规划基变量的特点,可以得到下面重要定理及其推论 。
1.运输问题模型及有关概念定理 4.1 变量组 xab,xcd,xef,…,xst 所对应的系数列向量 pab,pcd,pef,…,pst 线性无关的充分必要条件是这个变量组中 不包含闭回路 。
推论 产销平衡运输问题的 m + n -1 个变量构成基变量的充分必要条件是它不含闭回路 。
这个推论给出了运输问题基本解的重要性质,也为寻求基本可行解提供了依据 。
1.运输问题模型及有关概念
2.运输问题求解 — 表上作业法
表上作业法,建立在运输费用矩阵的求解运输问题的方法 。
表上作业法求解运输问题的思想和单纯形法完全类似：
确定一个 初始基本可行解 —— 根据 最优性判别准则 来检查这个基本可行解是不是最优的？
如果是,则计算结束；
如果不是,则进行 换基 。
—— 直至求出最优解为止 。
27
2.运输问题求解
— 表上作业法一,初始基本可行解的确定根据上面的讨论,要求得运输问题的初始基本可行解,必须保证找到 m + n – 1 个不构成闭回路的基变量 。
一般的方法步骤如下：
28
2.运输问题求解
— 表上作业法
(1)在运输问题求解作业数据表中 任选一个单元格 xij ( Ai 行 Bj 列交叉位置上的格 ),令
xij = min { ai,bj }
即从 Ai 向 Bj 运最大量 (使行或列在允许的范围内尽量饱和,即使一个约束方程得以满足 ),填入 xij 的相应位置；
29
2.运输问题求解
— 表上作业法
(2)从 ai 和 bj 中分别减去 xij 的值,修正为新的 ai 和 bj 即调整 Ai 的拥有量及 Bj 的需求量；
(3)若 ai = 0,则划去对应的行 （ 已经把拥有的量全部运走 ）,若 bj = 0 则划去对应的列 （ 已经把需要的量全部运来 ）,且每次只划去一行或一列 （ 即每次要去掉且只去掉一个约束 ） ；
30
2.运输问题求解
— 表上作业法
(4)当最终的运输量选定时,其所在行,
列同时满足,此时要同时划去一行和一列 。 这样,运输平衡表中所有的行与列均被划去,则得到了一个初始基本可行解 。
否则在剩下的运输平衡表中选下一个变量,返回 (1)。
31
上述计算过程可用流程图描述如下（图 4-2）
取未划去的单元格 xij,令
xij = min { ai,bj }
ai’ = ai - xij
bj’ = bj - xij
ai’ = 0? 划去第 i行划去第 j列是否
bj’ = 0
否所有行列是否均被划去是找到初始基本可行解图 4-2 求运输问题的初始基本可行解过程注：为了方便，这里总记剩余的产量和销量为 ai,bj
32
2.运输问题求解
— 表上作业法按照上述方法所产生的一组变量的取值将满足下面条件：
(1)所得的变量均为非负,且变量总数恰好为 m + n – 1 个；
(2)所有的约束条件均得到满足；
(3)所得的变量 不构成闭回路 。
33
2.运输问题求解
— 表上作业法因此,根据定理 4.1及其推论,
所得的解一定是运输问题的基本可行解 。
在上面的方法中,xij 的选取方法并没有给予限制,若采取不同的规则来选取 xij,则得到不同的方法,较常用的方法有 西北角法 和 最小元素法 。 下面分别举例予以说明 。
34
2.运输问题求解
— 表上作业法
1、初始基本可行解的确定
（ 1） 西北角法,从西北角（左上角）格开始，在格内的右下角标上允许取得的最大数。然后按行（列）标下一格的数。若某行（列）的产量
（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解 。
35
（ 2） 最小元素法,从运价最小的格开始，在格内的右下角标上允许取得的最大数。然后按运价从小到大顺序填数。若某行（列）的产量（销量）
已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。
2.运输问题求解
— 表上作业法
36
注,应用西北角法和最小元素法，
每次填完数，都只划去一行或一列，
只有最后一个元例外（同时划去一行和一列）。当填上一个数后行、列同时饱和时，也应任意划去一行（列），
在保留的列（行）中没被划去的格内标一个 0。
2.运输问题求解
— 表上作业法
2.运输问题求解
— 表上作业法表 1
38
2.运输问题求解
— 表上作业法
39
2.运输问题求解
— 表上作业法
40
最优性检验就是检查所得到的方案是不是最优方案 。 检查的方法与单纯形方法中的原理相同,即计算检验数 。 由于目标要求极小,因此,当所有的检验数都大于或等于零时该调运方案就是最优方案；否则就不是最优,
需要进行调整 。 下面介绍两种求检验数的方法,闭回路法 和 位势法二、基本可行解的最优性检验
2.运输问题求解
— 表上作业法
41
1、闭回路法为了方便,我们以表 1给出的初始基本可行解方案为例,考察初始方案的任意一个非基变量,比如 x24。 根据初始方案,
产地 A2 的产品是不运往销地 B4 的 。 如果现在改变初始方案,把 A2 的产品运送 1
个单位给 B4,那么为了保持产销平衡,
就必须使 x14 或 x34 减少 1 个单位；而如果 x14 减少 1 个单位,第 1 行的运输量就必须增加 1 个单位,例如 x13 增加
1 个单位,那么为了保持产销平衡,就必须使 x23 减少 1 个单位 。
2.运输问题求解
— 表上作业法
42
这个过程就是寻找一个以非基变量
x24 为起始顶点的闭回路 —— {x24,
x14,x13,x23 },这个闭回路的其他顶点均为基变量 (对应着填上数字的格 )。
容易计算出上述调整使总的运输费用发生的变化为 8 – 10 + 3 – 2 ＝ -1,
即总的运费减少 1 个单位,这就说明原始方案不是最优方案,可以进行调整以得到更好的方案 。
2.运输问题求解
— 表上作业法
43
可以证明，如果对闭回路的方向不加区别（即只要起点及其他所有顶点完全相同，而不区别行进方向），那么以每一个非基量为起始顶点的闭回路就存在而且唯一。因此，对每一个非基变量可以找到而且只能找到唯一的一个闭回路。
表 4-10中用虚线画出以非基变量
x22 为起始顶点的闭回路 。
2.运输问题求解
— 表上作业法
44
表 4-10 以非基变量 x22 为起始顶点的闭回路销地产地
B1 B2 B3 B4 产量
3
[ ]
11
[ ]
3
4
10
3
7
1
3
9
[ ]
2
1
8
[ ]
4
7
[ ]
4
6
10
[ ]
5
3
9
销量 3 6 5 6 20(产销平衡 )
A1
A2
A3
45
可以计算出以非基变量 x22 为起始顶点的闭回路调整使总的运输费用发生的变化为
9 – 2 + 3 – 10 + 5 – 4 ＝ 1
即总的运费增加 1 个单位,这就说明这个调整不能改善目标值 。
从上面的讨论可以看出,当某个非基变量增加一个单位时,有若干个基变量的取值受其影响 。
2.运输问题求解
— 表上作业法
46
这样,利用单位产品变化 （ 运输的单位费用 ） 可计算出它们对目标函数的综合影响,其作用与线性规划单纯形方法中的检验数完全相同 。 故也称这个综合影响为该非基变量对应的 检验数 。 上面计算的两个非基变量的检验数为?24 =
-1,?22 = 1。 闭回路方法原理就是通过寻找闭回路来找到非基变量的检验数 。
2.运输问题求解
— 表上作业法
47
如果规定作为起始顶点的非基变量为第 1 个顶点,闭回路的其他顶点依次为第 2 个顶点,第 3 个顶点 …… 那么就有
ij = (闭回路上的奇数次顶点单位运费之和 ) - (闭回路上的偶数次顶点单位运费之和 )
其中 ij 为非基变量的下角指标 。
2.运输问题求解
— 表上作业法
48
按上述作法,可计算出表 1的所有非基变量的检验数,把它们填入相应位置的方括号内,如图 4-11所示 。
销地产地
B1 B2 B3 B4 产量
A1 3
[1]
11
[2]
3
4
10
3
7
A2 1
3
9
[1]
2
1
8
[-1]
4
A3 7
[10]
4
6
10
[12]
5
3
9
销量 3 6 5 6 20(产销平衡 )
表 4-11 初始基本可行解及检验数
49
显然,当所有非基变量的检验数均大于或等于零时,现行的调运方案就是最优方案,因为此时对现行方案作任何调整都将导致总的运输费用增加 。
闭回路法的主要缺点是：当变量个数较多时,寻找闭回路以及计算两方面都会产生困难 。
2.运输问题求解
— 表上作业法
2.位势法位势,设对应基变量 xij 的 m +n -1
个 ij,存在 ui,vj 满足
ui+vj=cij,i=1,2 …,m ; j=1,2 …,n,
称这些 ui,vj 为该基本可行解对应的 位势 。
2.运输问题求解
— 表上作业法
51
由于有 m + n 个变量（ ui,vj ），
m + n - 1 个方程（基变量个数），
故有一个自由变量，位势不唯一。
利用位势求检验数：
ij = cij - ui - vj
i = 1,…,m ; j = 1,…,n
2.运输问题求解
— 表上作业法
52
前例，位势法求检验数：
step 1 从任意基变量对应的 cij 开始,任取 ui 或 vj,然后利用公式
cij = ui + vj 依次找出 m + n 个 ui,
vj 从 c14 = 10 开始
step 2 计算非基变量的检验数
ij = cij - ui - vj ；填入圆圈内
2.运输问题求解
— 表上作业法
53
2.运输问题求解
— 表上作业法
54
当非基变量的检验数出现负值时,则表明当前的基本可行解不是最优解 。 在这种情况下,应该对基本可行解进行调整,即找到一个新的基本可行解使目标函数值下降,
这一过程通常称为换基 (或主元变换 )
过程 。
2.运输问题求解
— 表上作业法三,求新的基本可行解
55
（ 1） 选负检验数中最小者?rk，那么 xrk 为主元，作为进基变量（上页图中 x24 ） ;
（ 2） 以 xrk 为起点找一条闭回路，
除 xrk 外其余 顶点必须为基变量格（上页图中的回路） ;
2.运输问题求解
— 表上作业法在运输问题的表上作业法中，换基的过程是如下进行：
56
（ 3） 为闭回路的每一个顶点标号，
xrk 为 1，沿一个方向（顺时针或逆时针）依次给各顶点标号；
（ 4） 求? =Min{xij?xij对应闭回路上的偶数标号格 }= xpq 那么确定 xpq为出基变量,?为调整量；
2.运输问题求解
— 表上作业法
57
（ 5） 对闭回路的各奇标号顶点调整为,xij +?，对各偶标号顶点 调整为,xij -?，特别 xpq -? = 0,xpq变为非 基变量。
重复 (2),(3)步，直到所有检验数均非负，得到最优解。
2.运输问题求解
— 表上作业法
58
2.表上作业法
ij ≥ 0，得到 最优解 x13 = 5,x14 = 2,x21 = 3,x24 = 1,
x32 = 6,x34 = 3,其余 xij = 0 ;
最优值,
f* = 3× 5+10× 2+1× 3+8× 1+4× 6+5× 3 = 85
例：
60
初始基本可行解
61
迭代
62
迭代 2
63
作业：
习题 —1,2(2)
64
四,产销不平衡问题的处理在实际中遇到的运输问题常常不是产销平衡的,而是下列的一般运输问题模型
m n
Min f = cij xij （ 4-1）i=1 j=1
n
s.t.? xij ≤si i = 1,2,…,m （ 4-2）
j=1m
xij ≤(=,≥)dj j = 1,2,…,n (4-3）
i=1
xij ≥ 0 (i=1,2,…,m;j=1,2,…,n)（ 4-4）
2.运输问题求解
— 表上作业法
65
我们已经介绍过，可以通过增加虚设产地或销地（加、减松弛变量）把问题转换成产销平衡问题，下面分别来讨论。
1.产量大于销量的情况
m n考虑?s
i >?dj 的运输问题，得到的数学模i=1 j=1
型为
2.运输问题求解
— 表上作业法
66
2.运输问题求解
— 表上作业法
m n
Min f = cij xij
i=1 j=1
ns.t,? x
ij ≤si i = 1,2,…,mj=1
m?x
ij =dj j = 1,2,…,n
i=1
xij≥0( i=1,2,…,m;j=1,2,…,n)
67
只要在模型中的产量限制约束 （ 前 m
个不等式约束 ） 中引入 m个松弛变量
xin+1 i= 1,2,…,m 即可,变为：
n?x
ij+xin+1=si i=1,2,…,mj=1
然后,需设一个销地 B n+1,它的销量为：
m n
bn+1=?si-?dj
i=1 j=1
2.运输问题求解
— 表上作业法
68
这里,松弛变量 x i n+1 可以视为从产地 A i 运往销地 B n+1 的运输量,
由于实际并不运送,它们的运费为
c i n+1 = 0 i = 1,2,…,m。 于是,
这个运输问题就转化成了一个产销平衡的问题 。
2.运输问题求解
— 表上作业法
69
例 4.2:某公司从两个产地 A1,A2
将物品运往三个销地 B1,B2,B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，
问：应如何调运可使总运输费用最小？
2.运输问题求解
— 表上作业法
70
解：增加一个虚设的销地运输费用为 0
2.运输问题求解
— 表上作业法
71
2.销量大于产量的情况
m n考虑?s
i<?dj的运输问题，得到的数学模型为i=1 j=1
2.运输问题求解
— 表上作业法
m nMin f = c
ij xiji=1 j=1
ns.t.? x
ij =si i = 1,2,…,mj=1
m?x
ij ≤ dj j = 1,2,…,n
i=1
xij≥0( i=1,2,…,m;j=1,2,…,n)
72
只要在模型中的产量限制约束 （ 后
n个不等式约束 ） 中引入 n个松弛变量
xm+1j j = 1,2,…,n即可,变为：
m
xij+xm+1j=dj j=1,2,…,m
i=1
然后,需设一个产地 A m+1,它的销量为：
n m
am+1=?dj-?si
j=1 i=1
2.运输问题求解
— 表上作业法
73
这里,松弛变量 x m+1j 可以视为从产地 A m+1 运往销地 B j 的运输量,由于实际并不运送,它们的运费为 c m+1j = 0 j = 1,2,…,n。 于是,这个运输问题就转化成了一个产销平衡的问题 。
2.运输问题求解
— 表上作业法
74
例 4.3:某公司从两个产地 A1,A2将物品运往三个销地 B1,B2,B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：
应如何调运可使总运输费用最小？
2.运输问题求解
— 表上作业法
75
解：增加一个虚设的产地运输费用为 0
2.运输问题求解
— 表上作业法例 4.4:石家庄北方研究院有一、二、三，三个区。每年分别需要用煤 3000,1000,2000t，
由河北临城、山西盂县两处煤矿负责供应，价格、
质量相同。供应能力分别为 1500,4000t，运价如下表。由于需大于供，经院研究决定一区供应量可减少 0— 300t，二区必须满足需求量，三区供应量不少于 1700t，试求总费用为最低的调运方案。
3.运输问题的应用
77
解,根据题意，作出产销平衡与运价表,取 M 代表一个很大的正数，其作用是强迫相应的 x31,x33,x34取值为 0。
3.运输问题的应用
78
例 4.5:设有 A,B,C三个化肥厂供应 1,2,3,4四个地区的农用化肥。
假设效果相同，有关数据如下表。试求总费用为 最低 的化肥调拨方案。
3.运输问题的应用
79
解,根据题意，作出产销平衡与运价表,
最低要求必须满足，因此把相应的虚设产地运费取为 M,而最高要求与最低要求的差允许按需要安排，因此把相应的虚设产地运费取为 0 。对应 4”的销量 50 是考虑问题本身适当取的数据，根据产销平衡要求确定 D
的产量为 50。
3.运输问题的应用生产与储存问题例 4.6:某厂按合同规定须于当年每个季度末分别提供 10,15,25,20台同一规格的柴油机。
已知该厂各季度的生产能力及生产每台柴油机的成本如右表。如果生产出来的柴油机当季不交货，
每台每积压一个季度需储存、维护等费用 0.15万元。试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。
生产能力 / 台 单位成本 / 万元一季度 25 1 0,8
二季度 35 1 1,1
三季度 30 1 1,0
四季度 10 1 1,3
3.运输问题的应用交货,生产：
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
解,设 xij 为第 i 季度生产的第 j 季度交货的柴油机数目，那么应满足：
3.运输问题的应用把第 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 产量第一季度 10.80 1 0.95 1 1,1 0 1 1.2 0 25
第二季度 M 1 1.10 1 1.25 1 1.40 0 35
第三季度 M M 1 1.00 1 1.15 0 30
第四季度 M M M 1 1.30 0 10
销量 10 15 25 20 30
3.运输问题的应用生产与储存问题例 4.7:光明仪器厂生产电脑绣花机是以销定产的。已知 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
3.运输问题的应用
84
已知上年末库存 103台绣花机，如果当月生产出来的机器当月不交货，则需要运到分厂库房，每台增加运输成本 0.1万元,每台机器每月的平均仓储费、维护费为 0.2万元。在 7--8月份销售淡季，全厂停产 1个月，因此在 6月份完成销售合同后还要留出库存 80台。加班生产机器每台增加成本 1万元。问应如何安排 1--6月份的生产，可使总的生产费用（包括运输、仓储、维护）最少？
运输问题（ 7） § 3 运输问题的应用
85
解,这个生产存储问题可化为运输问题来做。 考虑：各月生产与交货分别视为产地和销地。
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月份加班生产情况。
3.运输问题的应用
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
产销平衡与运价表：
87
例 4.8:腾飞电子仪器公司在大连和广州有两个分厂生产同一种仪器，大连分厂每月生产
450台,广州分厂每月生产 600台。该公司在上海和天津有两个销售公司负责对南京、济南、
南昌、青岛四个城市的仪器供应。另外因为大连距离青岛较近，公司同意大连分厂向青岛直接供货，运输费用如下图，单位是百元。问应该如何调运仪器，可使总运输费用最低？
三、转运问题,原运输问题上增加若干转运站。运输方式有：产地? 转运站、转运站
销地、产地? 产地、产地? 销地、销地? 转运站、销地? 产地等 。
3.运输问题的应用
88
图中 1—广州,2—大连,3—上海,4—天津
5—南京,6—济南,7—南昌,8—青岛
3.运输问题的应用
450
89
解,设 xij 为从 i 到 j 的运输量，可得到有下列特点的线性规划模型：
目标函数,Min f = 所有可能的运输费用 （运输单价与运输量乘积之和）
约束条件,对产地（发点） i,
输出量 - 输入量 = 产量对转运站（中转点）：
输入量 - 输出量 = 0
对销地（收点） j,
输入量 - 输出量 = 销量
3.运输问题的应用
90
约束条件：
s.t,x13+x14 ≤ 600
(广州分厂供应量限制）
x23+x24+x28 ≤ 450
(大连分厂供应量限制）
-x13-x23+x35+x36+x37+x38 = 0
（上海销售公司，转运站）
目标函数：
Min f = 2x13+3x14+3x23+x24+4x28+2x35
+6x36+3x37+6x38+4x45+4x46+6x47+ 5x48
3.运输问题的应用
91
-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
可求得结果：
x13 = 550,x14 = 0
x23 = 0,x24 = 150,x28 = 300
x35 = 200,x36 = 0,x37 = 350,x38 = 0
x45 = 0,x46 = 150,x47 = 0,x48 = 0
3.运输问题的应用例 4.9:某公司有 A1,A2,A3三个分厂生产某种物质，分别供应 B1,B2,B3、
B4四个地区的销售公司销售。假设质量相同，有关数据如下表：
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
3.运输问题的应用
93
试求总费用为最少的调运方案。
假设：
1,每个分厂的物资不一定直接发运到销地,可以从其中几个产地集中一起运；
2,运往各销地的物资可以先运给其中几个销地，再转运给其他销地；
3,除产销地之外，还有几个中转站，在产地之间、销地之间或在产地与销地之间转运。
运价如下表：
3.运输问题的应用
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
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
1 1 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
95
解：把此转运问题转化为一般运输问题：
1.把所有产地、销地、转运站都同时看作产地和销地；
2.运输表中不可能方案的运费取作 M，自身对自身的运费为 0；
3.产量及销量可定为：产地 产量 +20，
销地 销量 +20,中转站及其它点均为 20。 20
为各点可能变化的最大流量；
4.对于最优方案，其中 xi i 为自身对自身的运量，实际上不进行运作。
扩大的运输问题产销平衡表：
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
3.运输问题的应用
97
作业：
习题 — 3,4,5
2
第四章 运输问题
运输问题与有关概念
运输问题的求解 —表上作业法
运输问题应用 —建模本章内容重点
3
1.运输问题模型及有关概念问题的提出一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地,在每个产地的供应量与每个销地的需求量已知,并知道各地之间的运输单价的前提下,如何确定一个使得总的运输费用最小的方案 。
4
1.运输问题模型及有关概念例 4.1:某公司从两个产地 A1、
A2将物品运往三个销地 B1,B2,B3，
各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？
5
解,产销平衡问题：
总产量 = 总销量设 xij 为从产地 Ai运往销地 Bj
的运输量，得到下列运输量表：
1.运输问题模型及有关概念
6
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 = 200
xij≥0(i=1,2； j=1,2,3）
1.运输问题模型及有关概念
7
1 1 1 0 0 0
0 0 0 1 1 1
1 0 0 1 0 0
0 1 0 0 1 0
0 0 1 0 0 1
系数矩阵
1.运输问题模型及有关概念
8
模型系数矩阵特征
1.共有 m+n行，分别表示各产地和销地； m?n列，分别表示各决策变量；
2.每列只有两个 1，其余为 0，分别表示只有一个产地和一个销地被使用。
1.运输问题模型及有关概念
9
一般运输问题的线性规划模型及求解思路一般运输问题的提法：
假设 A1,A2,…,Am 表示某物资的 m个产地； B1,B2,…,Bn 表示某物资的 n个销地；
si表示产地 Ai 的产量； dj 表示销地 Bj 的销量； cij 表示把物资从产地 Ai 运往销地
Bj 的单位运价 （ 表 4-3） 。 如果
s1 + s2 + … + sm = d1 + d2 + … + dn
则称该运输问题为产销平衡问题；否则,称产销不平衡 。 首先讨论产销平衡问题 。
1.运输问题模型及有关概念
10
表 4-3 运输问题数据表
1.运输问题模型及有关概念销地产地
B1 B2 … Bn 产量
A1
A2
┇
Am
c11 c12 … c1n
c21 c22 … c2n
┇ ┇ ┇ ┇
cm1 cm2 … cmn
s1
s2
┇
sm
销量 d1 d2 … dn
设 xij 为从产地 Ai 运往销地 Bj 的运输量,根据这个运输问题的要求,可以建立运输变量表 （ 表 4-4） 。
11
表 4-4 运输问题变量表
1.运输问题模型及有关概念销地产地
B1 B2 … Bn 产量
A1
A2
┇
Am
x11 x12 … x1n
x21 x22 … x2n
┇ ┇ ┇
xm1 xm2 … xmn
s1
s2
┇
sm
销量 d1 d2 … dn
12
m n
Min f = cij xij （ 4-1）
i=1 j=1
n
s.t.? xij ≤si i = 1,2,…,m （ 4-2）
j=1m
xij ≤(=,≥)dj j = 1,2,…,n （ 4-3）
i=1
xij ≥ 0 (i=1,2,…,m;j=1,2,…,n)（ 4-4）
1.运输问题模型及有关概念于是得到下列 一般运输问题 的模型：
在模型 （ 4-1） —（ 4-4） 中,式 （ 4-2） 为 m 个产地的产量约束；式 （ 4-3） 为 n 个销地的销量约束 。
m n
Min f = cij xij
i=1 j=1
n
s.t,? xij = si i = 1,2,…,m (4-5)
j =1
m? x
ij = dj j = 1,2,…,n (4-6)i =1
xij ≥ 0 (i=1,2,…,m;j=1,2,…,n)
1.运输问题模型及有关概念对于 产销平衡 问题，可得到下列运输问题的模型：
14
在产销平衡问题 中,式 （ 4-2）,（ 4-3）
分别变为 （ 4-5）,（ 4-6）,约束条件成为等式 。
在实际问题建模时,还会出现如下一些变化：
（ 1） 有时目标函数求最大,如求利润最大或营业额最大等；
（ 2） 当某些运输线路上的能力有限制时,
模 型 中可 直 接加 入 （ 等 式或 不等 式 ）
约束；
1.运输问题模型及有关概念
(3)产销不平衡的情况 。 当销量大于产量时可加入一个虚设的产地去生产不足的物资,这相当于在式 （ 4-2）
每一式中加上 1 个松弛变量,共 m
个；当产量大于销量时可加入一个虚设的销地去消化多余的物资,这相当于在式 （ 4-3） 每一式中加上 1 个松弛变量,共 n 个 。
1.运输问题模型及有关概念
16
运输问题是一种特殊的线性规划问题,
在求解时依然可以采用单纯形法的思路,
如图 4-1所示 。
由于运输规划系数矩阵的特殊性,如果直接使用线性规划单纯形法求解计算,
则无法利用这些有利条件 。 人们在分析运输规划系数矩阵特征的基础上建立了针对运输问题的 表上作业法 。
下面主要讨论 基本可行解,检验数 以及基的转换 等问题 。
续下页
1.运输问题模型及有关概念
17
1.运输问题模型及有关概念基本可行解 是否最优解 结束换基是否图 4-1 运输问题的求解思路 返回
18
运输问题求解的有关概念考虑产销平衡问题,由于我们关心的量均在表 4-3与表 4-4中,因此考虑把表 4-3
与表 4-4合成一个表,如下表 4-5
表 4-5 运输问题求解作业数据表
(下页）
1.运输问题模型及有关概念
19
1.运输问题模型及有关概念销地产地
B1 B2 … Bn 产量
A1 c11
x11
c12
x12
… c1n
x1n
a1
A2 c21
x21
c22
x22
… c2n
x2n
a2
┇ ┇ ┇ ┇ ┇
Am cm1
xm1
cm2
xm2
… cmn
xmn
am
销量 b1 b2 … bn
20
运输问题的基变量共有 m + n -1
个,A的秩为 m + n -1。
运输问题的 m + n -1 个变量构成基变量的充分必要条件是不含闭回路。
重要概念,闭回路、闭回路的顶点特点运输问题基变量的
1.运输问题模型及有关概念
21
定义 4.1 在表 4-5的决策变量格中，凡是能够排列成下列形式的
xab,xac,xdc,xde,…,xst,xsb (4-7)
或 xab,xcb,xcd,xed,…,xst,xat (4-8)
其中,a,d,…,s 各不相同； b,c,…,t 各不相同,
我们称之为变量集合的一个 闭回路,并将式
（ 4-7）,式 （ 4-8） 中的变量称为这个 闭回路的顶点 。
为了说明这个特征,我们不加证明的给出一些概念和结论 。 下面的讨论建立在表 4-5
中决策变量格的基础上 。
1.运输问题模型及有关概念
22
例如,x13,x16,x36,x34,x24,x23 ；
x23,x53,x55,x45,x41,x21 ；
x11,x14,x34,x31等都是闭回路 。
若把闭回路的各变量格看作节点,
在表中可以画出如下形式的闭回路：
1.运输问题模型及有关概念闭回路示意图
23
根据定义可以看出闭回路的一些明显特点：
(1)闭回路均为一封闭折线,它的每一条边,或为水平的,或为垂直的；
(2)闭回路的每一条边 （ 水平的或垂直的 ） 均有且仅有两个闭回路的顶点 （ 变量格 ） 。
1.运输问题模型及有关概念
24
关于闭回路有如下的一些重要结论：
(1) 设 xab,xac,xdc,xde,…,xst,
xsb 是一个闭回路,那么该闭回路中变量所对应的系数列向量 pab,pac,pdc,
pde,…,pst,psb 线性相关；
(2) 若变量组 xab,xcd,xef,…,xst
中包含一个部分组构成闭回路,那么该变量组所对应的系数列向量 pab,pcd,
pef,…,pst 线性相关 。
根据上述结论以及线性规划基变量的特点,可以得到下面重要定理及其推论 。
1.运输问题模型及有关概念定理 4.1 变量组 xab,xcd,xef,…,xst 所对应的系数列向量 pab,pcd,pef,…,pst 线性无关的充分必要条件是这个变量组中 不包含闭回路 。
推论 产销平衡运输问题的 m + n -1 个变量构成基变量的充分必要条件是它不含闭回路 。
这个推论给出了运输问题基本解的重要性质,也为寻求基本可行解提供了依据 。
1.运输问题模型及有关概念
2.运输问题求解 — 表上作业法
表上作业法,建立在运输费用矩阵的求解运输问题的方法 。
表上作业法求解运输问题的思想和单纯形法完全类似：
确定一个 初始基本可行解 —— 根据 最优性判别准则 来检查这个基本可行解是不是最优的？
如果是,则计算结束；
如果不是,则进行 换基 。
—— 直至求出最优解为止 。
27
2.运输问题求解
— 表上作业法一,初始基本可行解的确定根据上面的讨论,要求得运输问题的初始基本可行解,必须保证找到 m + n – 1 个不构成闭回路的基变量 。
一般的方法步骤如下：
28
2.运输问题求解
— 表上作业法
(1)在运输问题求解作业数据表中 任选一个单元格 xij ( Ai 行 Bj 列交叉位置上的格 ),令
xij = min { ai,bj }
即从 Ai 向 Bj 运最大量 (使行或列在允许的范围内尽量饱和,即使一个约束方程得以满足 ),填入 xij 的相应位置；
29
2.运输问题求解
— 表上作业法
(2)从 ai 和 bj 中分别减去 xij 的值,修正为新的 ai 和 bj 即调整 Ai 的拥有量及 Bj 的需求量；
(3)若 ai = 0,则划去对应的行 （ 已经把拥有的量全部运走 ）,若 bj = 0 则划去对应的列 （ 已经把需要的量全部运来 ）,且每次只划去一行或一列 （ 即每次要去掉且只去掉一个约束 ） ；
30
2.运输问题求解
— 表上作业法
(4)当最终的运输量选定时,其所在行,
列同时满足,此时要同时划去一行和一列 。 这样,运输平衡表中所有的行与列均被划去,则得到了一个初始基本可行解 。
否则在剩下的运输平衡表中选下一个变量,返回 (1)。
31
上述计算过程可用流程图描述如下（图 4-2）
取未划去的单元格 xij,令
xij = min { ai,bj }
ai’ = ai - xij
bj’ = bj - xij
ai’ = 0? 划去第 i行划去第 j列是否
bj’ = 0
否所有行列是否均被划去是找到初始基本可行解图 4-2 求运输问题的初始基本可行解过程注：为了方便，这里总记剩余的产量和销量为 ai,bj
32
2.运输问题求解
— 表上作业法按照上述方法所产生的一组变量的取值将满足下面条件：
(1)所得的变量均为非负,且变量总数恰好为 m + n – 1 个；
(2)所有的约束条件均得到满足；
(3)所得的变量 不构成闭回路 。
33
2.运输问题求解
— 表上作业法因此,根据定理 4.1及其推论,
所得的解一定是运输问题的基本可行解 。
在上面的方法中,xij 的选取方法并没有给予限制,若采取不同的规则来选取 xij,则得到不同的方法,较常用的方法有 西北角法 和 最小元素法 。 下面分别举例予以说明 。
34
2.运输问题求解
— 表上作业法
1、初始基本可行解的确定
（ 1） 西北角法,从西北角（左上角）格开始，在格内的右下角标上允许取得的最大数。然后按行（列）标下一格的数。若某行（列）的产量
（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解 。
35
（ 2） 最小元素法,从运价最小的格开始，在格内的右下角标上允许取得的最大数。然后按运价从小到大顺序填数。若某行（列）的产量（销量）
已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。
2.运输问题求解
— 表上作业法
36
注,应用西北角法和最小元素法，
每次填完数，都只划去一行或一列，
只有最后一个元例外（同时划去一行和一列）。当填上一个数后行、列同时饱和时，也应任意划去一行（列），
在保留的列（行）中没被划去的格内标一个 0。
2.运输问题求解
— 表上作业法
2.运输问题求解
— 表上作业法表 1
38
2.运输问题求解
— 表上作业法
39
2.运输问题求解
— 表上作业法
40
最优性检验就是检查所得到的方案是不是最优方案 。 检查的方法与单纯形方法中的原理相同,即计算检验数 。 由于目标要求极小,因此,当所有的检验数都大于或等于零时该调运方案就是最优方案；否则就不是最优,
需要进行调整 。 下面介绍两种求检验数的方法,闭回路法 和 位势法二、基本可行解的最优性检验
2.运输问题求解
— 表上作业法
41
1、闭回路法为了方便,我们以表 1给出的初始基本可行解方案为例,考察初始方案的任意一个非基变量,比如 x24。 根据初始方案,
产地 A2 的产品是不运往销地 B4 的 。 如果现在改变初始方案,把 A2 的产品运送 1
个单位给 B4,那么为了保持产销平衡,
就必须使 x14 或 x34 减少 1 个单位；而如果 x14 减少 1 个单位,第 1 行的运输量就必须增加 1 个单位,例如 x13 增加
1 个单位,那么为了保持产销平衡,就必须使 x23 减少 1 个单位 。
2.运输问题求解
— 表上作业法
42
这个过程就是寻找一个以非基变量
x24 为起始顶点的闭回路 —— {x24,
x14,x13,x23 },这个闭回路的其他顶点均为基变量 (对应着填上数字的格 )。
容易计算出上述调整使总的运输费用发生的变化为 8 – 10 + 3 – 2 ＝ -1,
即总的运费减少 1 个单位,这就说明原始方案不是最优方案,可以进行调整以得到更好的方案 。
2.运输问题求解
— 表上作业法
43
可以证明，如果对闭回路的方向不加区别（即只要起点及其他所有顶点完全相同，而不区别行进方向），那么以每一个非基量为起始顶点的闭回路就存在而且唯一。因此，对每一个非基变量可以找到而且只能找到唯一的一个闭回路。
表 4-10中用虚线画出以非基变量
x22 为起始顶点的闭回路 。
2.运输问题求解
— 表上作业法
44
表 4-10 以非基变量 x22 为起始顶点的闭回路销地产地
B1 B2 B3 B4 产量
3
[ ]
11
[ ]
3
4
10
3
7
1
3
9
[ ]
2
1
8
[ ]
4
7
[ ]
4
6
10
[ ]
5
3
9
销量 3 6 5 6 20(产销平衡 )
A1
A2
A3
45
可以计算出以非基变量 x22 为起始顶点的闭回路调整使总的运输费用发生的变化为
9 – 2 + 3 – 10 + 5 – 4 ＝ 1
即总的运费增加 1 个单位,这就说明这个调整不能改善目标值 。
从上面的讨论可以看出,当某个非基变量增加一个单位时,有若干个基变量的取值受其影响 。
2.运输问题求解
— 表上作业法
46
这样,利用单位产品变化 （ 运输的单位费用 ） 可计算出它们对目标函数的综合影响,其作用与线性规划单纯形方法中的检验数完全相同 。 故也称这个综合影响为该非基变量对应的 检验数 。 上面计算的两个非基变量的检验数为?24 =
-1,?22 = 1。 闭回路方法原理就是通过寻找闭回路来找到非基变量的检验数 。
2.运输问题求解
— 表上作业法
47
如果规定作为起始顶点的非基变量为第 1 个顶点,闭回路的其他顶点依次为第 2 个顶点,第 3 个顶点 …… 那么就有
ij = (闭回路上的奇数次顶点单位运费之和 ) - (闭回路上的偶数次顶点单位运费之和 )
其中 ij 为非基变量的下角指标 。
2.运输问题求解
— 表上作业法
48
按上述作法,可计算出表 1的所有非基变量的检验数,把它们填入相应位置的方括号内,如图 4-11所示 。
销地产地
B1 B2 B3 B4 产量
A1 3
[1]
11
[2]
3
4
10
3
7
A2 1
3
9
[1]
2
1
8
[-1]
4
A3 7
[10]
4
6
10
[12]
5
3
9
销量 3 6 5 6 20(产销平衡 )
表 4-11 初始基本可行解及检验数
49
显然,当所有非基变量的检验数均大于或等于零时,现行的调运方案就是最优方案,因为此时对现行方案作任何调整都将导致总的运输费用增加 。
闭回路法的主要缺点是：当变量个数较多时,寻找闭回路以及计算两方面都会产生困难 。
2.运输问题求解
— 表上作业法
2.位势法位势,设对应基变量 xij 的 m +n -1
个 ij,存在 ui,vj 满足
ui+vj=cij,i=1,2 …,m ; j=1,2 …,n,
称这些 ui,vj 为该基本可行解对应的 位势 。
2.运输问题求解
— 表上作业法
51
由于有 m + n 个变量（ ui,vj ），
m + n - 1 个方程（基变量个数），
故有一个自由变量，位势不唯一。
利用位势求检验数：
ij = cij - ui - vj
i = 1,…,m ; j = 1,…,n
2.运输问题求解
— 表上作业法
52
前例，位势法求检验数：
step 1 从任意基变量对应的 cij 开始,任取 ui 或 vj,然后利用公式
cij = ui + vj 依次找出 m + n 个 ui,
vj 从 c14 = 10 开始
step 2 计算非基变量的检验数
ij = cij - ui - vj ；填入圆圈内
2.运输问题求解
— 表上作业法
53
2.运输问题求解
— 表上作业法
54
当非基变量的检验数出现负值时,则表明当前的基本可行解不是最优解 。 在这种情况下,应该对基本可行解进行调整,即找到一个新的基本可行解使目标函数值下降,
这一过程通常称为换基 (或主元变换 )
过程 。
2.运输问题求解
— 表上作业法三,求新的基本可行解
55
（ 1） 选负检验数中最小者?rk，那么 xrk 为主元，作为进基变量（上页图中 x24 ） ;
（ 2） 以 xrk 为起点找一条闭回路，
除 xrk 外其余 顶点必须为基变量格（上页图中的回路） ;
2.运输问题求解
— 表上作业法在运输问题的表上作业法中，换基的过程是如下进行：
56
（ 3） 为闭回路的每一个顶点标号，
xrk 为 1，沿一个方向（顺时针或逆时针）依次给各顶点标号；
（ 4） 求? =Min{xij?xij对应闭回路上的偶数标号格 }= xpq 那么确定 xpq为出基变量,?为调整量；
2.运输问题求解
— 表上作业法
57
（ 5） 对闭回路的各奇标号顶点调整为,xij +?，对各偶标号顶点 调整为,xij -?，特别 xpq -? = 0,xpq变为非 基变量。
重复 (2),(3)步，直到所有检验数均非负，得到最优解。
2.运输问题求解
— 表上作业法
58
2.表上作业法
ij ≥ 0，得到 最优解 x13 = 5,x14 = 2,x21 = 3,x24 = 1,
x32 = 6,x34 = 3,其余 xij = 0 ;
最优值,
f* = 3× 5+10× 2+1× 3+8× 1+4× 6+5× 3 = 85
例：
60
初始基本可行解
61
迭代
62
迭代 2
63
作业：
习题 —1,2(2)
64
四,产销不平衡问题的处理在实际中遇到的运输问题常常不是产销平衡的,而是下列的一般运输问题模型
m n
Min f = cij xij （ 4-1）i=1 j=1
n
s.t.? xij ≤si i = 1,2,…,m （ 4-2）
j=1m
xij ≤(=,≥)dj j = 1,2,…,n (4-3）
i=1
xij ≥ 0 (i=1,2,…,m;j=1,2,…,n)（ 4-4）
2.运输问题求解
— 表上作业法
65
我们已经介绍过，可以通过增加虚设产地或销地（加、减松弛变量）把问题转换成产销平衡问题，下面分别来讨论。
1.产量大于销量的情况
m n考虑?s
i >?dj 的运输问题，得到的数学模i=1 j=1
型为
2.运输问题求解
— 表上作业法
66
2.运输问题求解
— 表上作业法
m n
Min f = cij xij
i=1 j=1
ns.t,? x
ij ≤si i = 1,2,…,mj=1
m?x
ij =dj j = 1,2,…,n
i=1
xij≥0( i=1,2,…,m;j=1,2,…,n)
67
只要在模型中的产量限制约束 （ 前 m
个不等式约束 ） 中引入 m个松弛变量
xin+1 i= 1,2,…,m 即可,变为：
n?x
ij+xin+1=si i=1,2,…,mj=1
然后,需设一个销地 B n+1,它的销量为：
m n
bn+1=?si-?dj
i=1 j=1
2.运输问题求解
— 表上作业法
68
这里,松弛变量 x i n+1 可以视为从产地 A i 运往销地 B n+1 的运输量,
由于实际并不运送,它们的运费为
c i n+1 = 0 i = 1,2,…,m。 于是,
这个运输问题就转化成了一个产销平衡的问题 。
2.运输问题求解
— 表上作业法
69
例 4.2:某公司从两个产地 A1,A2
将物品运往三个销地 B1,B2,B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，
问：应如何调运可使总运输费用最小？
2.运输问题求解
— 表上作业法
70
解：增加一个虚设的销地运输费用为 0
2.运输问题求解
— 表上作业法
71
2.销量大于产量的情况
m n考虑?s
i<?dj的运输问题，得到的数学模型为i=1 j=1
2.运输问题求解
— 表上作业法
m nMin f = c
ij xiji=1 j=1
ns.t.? x
ij =si i = 1,2,…,mj=1
m?x
ij ≤ dj j = 1,2,…,n
i=1
xij≥0( i=1,2,…,m;j=1,2,…,n)
72
只要在模型中的产量限制约束 （ 后
n个不等式约束 ） 中引入 n个松弛变量
xm+1j j = 1,2,…,n即可,变为：
m
xij+xm+1j=dj j=1,2,…,m
i=1
然后,需设一个产地 A m+1,它的销量为：
n m
am+1=?dj-?si
j=1 i=1
2.运输问题求解
— 表上作业法
73
这里,松弛变量 x m+1j 可以视为从产地 A m+1 运往销地 B j 的运输量,由于实际并不运送,它们的运费为 c m+1j = 0 j = 1,2,…,n。 于是,这个运输问题就转化成了一个产销平衡的问题 。
2.运输问题求解
— 表上作业法
74
例 4.3:某公司从两个产地 A1,A2将物品运往三个销地 B1,B2,B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：
应如何调运可使总运输费用最小？
2.运输问题求解
— 表上作业法
75
解：增加一个虚设的产地运输费用为 0
2.运输问题求解
— 表上作业法例 4.4:石家庄北方研究院有一、二、三，三个区。每年分别需要用煤 3000,1000,2000t，
由河北临城、山西盂县两处煤矿负责供应，价格、
质量相同。供应能力分别为 1500,4000t，运价如下表。由于需大于供，经院研究决定一区供应量可减少 0— 300t，二区必须满足需求量，三区供应量不少于 1700t，试求总费用为最低的调运方案。
3.运输问题的应用
77
解,根据题意，作出产销平衡与运价表,取 M 代表一个很大的正数，其作用是强迫相应的 x31,x33,x34取值为 0。
3.运输问题的应用
78
例 4.5:设有 A,B,C三个化肥厂供应 1,2,3,4四个地区的农用化肥。
假设效果相同，有关数据如下表。试求总费用为 最低 的化肥调拨方案。
3.运输问题的应用
79
解,根据题意，作出产销平衡与运价表,
最低要求必须满足，因此把相应的虚设产地运费取为 M,而最高要求与最低要求的差允许按需要安排，因此把相应的虚设产地运费取为 0 。对应 4”的销量 50 是考虑问题本身适当取的数据，根据产销平衡要求确定 D
的产量为 50。
3.运输问题的应用生产与储存问题例 4.6:某厂按合同规定须于当年每个季度末分别提供 10,15,25,20台同一规格的柴油机。
已知该厂各季度的生产能力及生产每台柴油机的成本如右表。如果生产出来的柴油机当季不交货，
每台每积压一个季度需储存、维护等费用 0.15万元。试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。
生产能力 / 台 单位成本 / 万元一季度 25 1 0,8
二季度 35 1 1,1
三季度 30 1 1,0
四季度 10 1 1,3
3.运输问题的应用交货,生产：
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
解,设 xij 为第 i 季度生产的第 j 季度交货的柴油机数目，那么应满足：
3.运输问题的应用把第 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 产量第一季度 10.80 1 0.95 1 1,1 0 1 1.2 0 25
第二季度 M 1 1.10 1 1.25 1 1.40 0 35
第三季度 M M 1 1.00 1 1.15 0 30
第四季度 M M M 1 1.30 0 10
销量 10 15 25 20 30
3.运输问题的应用生产与储存问题例 4.7:光明仪器厂生产电脑绣花机是以销定产的。已知 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
3.运输问题的应用
84
已知上年末库存 103台绣花机，如果当月生产出来的机器当月不交货，则需要运到分厂库房，每台增加运输成本 0.1万元,每台机器每月的平均仓储费、维护费为 0.2万元。在 7--8月份销售淡季，全厂停产 1个月，因此在 6月份完成销售合同后还要留出库存 80台。加班生产机器每台增加成本 1万元。问应如何安排 1--6月份的生产，可使总的生产费用（包括运输、仓储、维护）最少？
运输问题（ 7） § 3 运输问题的应用
85
解,这个生产存储问题可化为运输问题来做。 考虑：各月生产与交货分别视为产地和销地。
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月份加班生产情况。
3.运输问题的应用
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
产销平衡与运价表：
87
例 4.8:腾飞电子仪器公司在大连和广州有两个分厂生产同一种仪器，大连分厂每月生产
450台,广州分厂每月生产 600台。该公司在上海和天津有两个销售公司负责对南京、济南、
南昌、青岛四个城市的仪器供应。另外因为大连距离青岛较近，公司同意大连分厂向青岛直接供货，运输费用如下图，单位是百元。问应该如何调运仪器，可使总运输费用最低？
三、转运问题,原运输问题上增加若干转运站。运输方式有：产地? 转运站、转运站
销地、产地? 产地、产地? 销地、销地? 转运站、销地? 产地等 。
3.运输问题的应用
88
图中 1—广州,2—大连,3—上海,4—天津
5—南京,6—济南,7—南昌,8—青岛
3.运输问题的应用
450
89
解,设 xij 为从 i 到 j 的运输量，可得到有下列特点的线性规划模型：
目标函数,Min f = 所有可能的运输费用 （运输单价与运输量乘积之和）
约束条件,对产地（发点） i,
输出量 - 输入量 = 产量对转运站（中转点）：
输入量 - 输出量 = 0
对销地（收点） j,
输入量 - 输出量 = 销量
3.运输问题的应用
90
约束条件：
s.t,x13+x14 ≤ 600
(广州分厂供应量限制）
x23+x24+x28 ≤ 450
(大连分厂供应量限制）
-x13-x23+x35+x36+x37+x38 = 0
（上海销售公司，转运站）
目标函数：
Min f = 2x13+3x14+3x23+x24+4x28+2x35
+6x36+3x37+6x38+4x45+4x46+6x47+ 5x48
3.运输问题的应用
91
-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
可求得结果：
x13 = 550,x14 = 0
x23 = 0,x24 = 150,x28 = 300
x35 = 200,x36 = 0,x37 = 350,x38 = 0
x45 = 0,x46 = 150,x47 = 0,x48 = 0
3.运输问题的应用例 4.9:某公司有 A1,A2,A3三个分厂生产某种物质，分别供应 B1,B2,B3、
B4四个地区的销售公司销售。假设质量相同，有关数据如下表：
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
3.运输问题的应用
93
试求总费用为最少的调运方案。
假设：
1,每个分厂的物资不一定直接发运到销地,可以从其中几个产地集中一起运；
2,运往各销地的物资可以先运给其中几个销地，再转运给其他销地；
3,除产销地之外，还有几个中转站，在产地之间、销地之间或在产地与销地之间转运。
运价如下表：
3.运输问题的应用
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
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
1 1 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
95
解：把此转运问题转化为一般运输问题：
1.把所有产地、销地、转运站都同时看作产地和销地；
2.运输表中不可能方案的运费取作 M，自身对自身的运费为 0；
3.产量及销量可定为：产地 产量 +20，
销地 销量 +20,中转站及其它点均为 20。 20
为各点可能变化的最大流量；
4.对于最优方案，其中 xi i 为自身对自身的运量，实际上不进行运作。
扩大的运输问题产销平衡表：
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
3.运输问题的应用
97
作业：
习题 — 3,4,5
