运筹学运输问题分析

B1 3-1=2B2 A1 A2 B3 B4 产量 行差额 7
方法2：Vogel法
3 1 9-4=5 7
3 2
8-5=3 11 9 4
6 5
3 2 10
5 1
10 7 3-2=1 8 5
6 3
4
9
1
1
A3
销量 列差额
表上作业法
2）再从差值最大的行或列中找出最小运价确定供需关系和 供需数量。当产地或销地中有一方数量供应完毕或得到满足 时，划去运价表中对应的行或列。 重复1)和2)，直到找出初始解为至。
( ai b j )
运输规划问题的数学模型
当产小于销时，其模型如下：
m inZ c ij x ij x ij a i x ij b j ( a i b j ) x 0 ij 并假设：a ij 0, b j 0, c ij 0
销地 产地 B1 4 B2 12 B3 4 B4 11 产量
行差额
A1 2 10 3 9
16
0
A2
10
1
8
5
11
6
A3
14
销量 8 2 14 12 1
8
14 3
22
48
1
列差额
所以，初始基可行解为：……目标函数值Z＝244
表上作业法
例3.4 某运输资料如下表所示：
销地 产地 B1 4 B2 12 B3 4 B4 11 产量
13
7
14
A2
2
5
13
9
12
10 6
27
A3 销量
19
22 13 12 13
19
表上作业法
（2）西北角法（或左上角法） 此法是纯粹的人为的规定，没有理论依据和实际背景，但 它易操作，特别适合在计算机上编程计算，因而受欢迎。 方法如下：
3
4 2
2 3 5 5 5 5 3 0
3 0 0 0 0 0
6 6 2 0 0 0
7 4 0 0 0 0 4 4 4 2 0 0 6 9 9 9 9 9 0 6 6 3 4 0 0 6 0 2 2 0 6 0 0 3 6 6 0
表上作业法
例3.3 某运输资料如下表所示：
在满足约束条件下尽可能的给最左上角的变量最大值.
销地 产地 B1 B2 4 B3 12 4 B4 11 产量
A1
B1 A1 6 B2 4 B3 6 产量 200
A2
销量
6
150
5
150
5
200
300
运输规划问题的数学模型
解：产销平衡问题：总产量 = 总销量＝500 设 xij 为从产地Ai运往销地Bj的运输量，得到下列运输量 表：
B1 A1 x11 B2 x12 B3 x13 产量 200
A2
销量
x21
150
第二步
第三步
表上作业法
例3.2 某运输资料如下表所示：
单位 运价 产地 销地
B1 B2 B3 B4
3 1 7 11 9 4 3 2 10 10 8 5
产量 7 4 9
A1 A2 A3
销量
3
6
5
6
问：应如何调运可使总运输费用最小？ 1、求初始方案：最小元素法、西北角法、伏格尔法
表上作业法
方法1：最小元素法 基本思想是就近供应，即从运价最小的地方开始供应（调 运），然后次小，直到最后供完为止。
分析：
z z0 11 x11 12 x12 21 x21 L mn xmn
若令 则 11 z z0
x11 1, x12 L xmn 0
—运费的增量
表上作业法
以最小元素法的初始解为例。假设产地A1供应1个单位的 物品给销地B1。则解的变化和目标函数的变化如何。
16
0
A2
8
8 5 11 6
10
1
A3
14
销量 8 14 12 1
8
14 3
22
48
列差额
所以，初始基可行解为：……目标函数值Z＝244
表上作业法
例3.4 某运输资料如下表所示：
销地 产地 B1 4 B2 12 B3 4 B4 11 产量
行差额
A1 2 10
12
3
4
9
16
0
A2
8
8 5 11
2
6
10
B1
A1 A2
B2
B3
B4
产量
7 4
行差额
7 1
A3
销量 列差额
3 1 7
3 2
11 9 4
6 5
3
5
2 10
5 1
10 8 5
6 3
9
1
表上作业法
单位 运价 产地 销地
B1 B2 B3 B4
A1 A2 A3
3 × 11 1 3 9 3 5 10 2 × 8
产量 7 4
行差额 7 7
7
× 4
3 2 6 5
产量 a1 a2 ┇
xm1 b1
xm2 b1
… …
xmn bn
am
运输规划问题的数学模型
运输问题的求解思路
基本可行解 是否最优解
是
结束
否
换基
二、表上作业法
计算步骤：
(1) 找出初始调运方案。即在(m×n)产销平衡表上给出 m+n-1个数字格。(最小元素法、西北角法或伏格尔法）
确定m+n-1个基变量
x22
150
x23
200
300
Min C = 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）
8
8 6
16
A2
2
10
3
9
4
5 11 6
10
A3 销量 8
8
8
14 12
14
14
22 48
所以，初始基可行解为：(8,8,4,8,14)目标函数值Z＝372
表上作业法
练习
销地 产地 A1 B1 6 B2 7 B3 5 B4 3 产量
14
8 4 2 7
14
A2
8
5
13
9
6
10 6
27
A3 销量 22
i 1 j 1
m
n
xij ai xij b j x 0 ij
( ai b j )
运输规划问题的数学模型
当产大于销时，其模型如下：
m inZ cij xij
i 1 j 1
m
n
xij ai xij b j x 0 ij
min z c ij x ij
i 1, L , m xij ai j 1 m s.t xij b j j 1, L , n i 1 xij 0, i 1, L , m; j 1, L , n
n
i 1 j 1
m
n
运输规划问题的数学模型
1 1 L 1 1 O
m
n
运输规划问题的数学模型
平衡表、运价表合二为一：
销 产 A1 A2 ┇ B1 c11 x11 c21 x21 ┇ cm Am 销量
1
B2 c12 x12 c22 x22 ┇ cm
2
… … … ┇
Bn c1n x1n c2n x2n ┇ cmn
已知资料如下：
销 产 地 地
cij为Aij到Bij的单位运价
B1 L Bn
产 量
A1 M Am
销 量
c11 L c1n M 运价 M cm1 L cmn
a1 M am
m n i 1 i ji j
b1
L
bn a b
产销平衡
运输规划问题的数学模型
当产销平衡时，其模型如下：
minZ cij xij
运输规划问题的数学模型
特征： 1、平衡运输问题必有可行解，也必有最优解；
2、运输问题的基本可行解中应包括 m+n－1 个基变量。
运输规划问题的数学模型
运输问题约束条件的系数矩阵
x11 x12 L x1n x21 x22 L x2n L xm1 xm2 L xmn
1 1 1 L 1 O 1 1 L 1 1 O 1 1 O 1 1 O 1 1
1
A3
14
销量 8 14 12
8
14 3
22
48
列差额
所以，初始基可行解为：……目标函数值Z＝244
表上作业法
练习
销地 产地 B1 6 B2 7 B3 5 B4 3 产量
A1
1
8 4 2
13
7
14
A2
2
5
13
9
12
10 6
27
A3
19
22 13 12 13
19
销量
表上作业法
2、 最优解的判别（检验数的求法） 求检验数的方法有两种： 闭回路法 对偶变量法（位势法） （1）闭合回路法： σij≥0 （因为目标函数要求最小化）
10 × 5
5 6 3
9
1
销量 列差额
表上作业法
单位 运价 产地 销地
B1 B2 B3 B4
3 × 11 × 3 1 5 10 2
产量 7 4
行差额 1 1 1
A1 A2 A3
销量 列差额
3
9
× 2 × 8 1
6 10 × 5 3 6 5 5 6 3
7 × 4
3
9
该方案的总运费: (1×3)＋(4×6)＋(3×5)＋(2×10)＋(1×8)＋(3×5)＝85元
B1 A1 A2 A3 销量 3 B2 B3 B4 产量 7 4 9
3 1 7
11 9 4
4 1
3 2 10
3
10
8 5
3
6
6 5
3
6
总的运输费＝(3×1)+(6×4) +(4×3) +(1×2)+(3×10)+(3×5)=86元
表上作业法
练习
销地
产地 B1 B2 B3 B4 产量
A1
6
7
5
3
1
8 4 2
表格中有调运量的地方为基变量，空格处为非基变量。 基变量的检验数σij＝0，非基变量的检验数σij≥0。
σij< 0 表示运费减少， σij> 0 表示运费增加。
表上作业法
闭回路：从空格出发顺时针(或逆时针)画水平(或垂直 )直线，遇到填有运量的方格可转90°，然后继续前进，直 到到达出发的空格所形成的闭合回路。 调运方案的任意空格存在唯一闭回路。 注：1.每一空格有且仅有一条闭回路； 2.如果某数字格有闭回路，则此解不是可行解。
最小元素法：
8 2
10 5
另一种方法：
10 8 2
15
5 1
15
5 1
10 5
15
15
总运费是z=10×8 +5×2+15×1=105
总运费z=10×5 +15×2+5×1=85
表上作业法
2-1=1 10-3=7 1）从运价表中分别计算出各行和各列的最小运费和次最小运 5-4=1 费的差额，并填入该表的最右列和最下行。
表上作业法
例3.4 某运输资料如下表所示：
销地 产地 B1 4 B2 12 B3 4 B4 11 产量
行差额
A1 2 10 3 9
16
0
A2
10
1
8
5
11
6
A3
22
1
14
销量 8 2 14 5 12 1 14 3 48
列差额
所以，初始基可行解为：……目标函数值Z＝244
表上作业法
例3.4 某运输资料如下表所示：
运输规划问题的数学模型
运输问题的一般形式：产销平衡
A1、 A2、…、 Am 表示某物资的m个产地； B1、B2、…、Bn 表示 某物质的n个销地；ai 表示产地Ai的产量； bj 表示销地Bj 的销量； cij 表示把物资从产地Ai运往销地Bj的单位运价。设 xij 为从产地Ai 运往销地Bj的运输量，得到下列一般运输量问题的模型：
(2) 求检验数。（闭回路法或位势法） 判别是否达到最优 解。如已是最优解，则停止计算，否则转到下一步。
空格
(3) 对方案进行改善，找出新的调运方案。（表上闭回 路法调整）
(4) 重复（2）、（3），直到求得最优调运方案。
表上作业法
表上作业法是一种求解运输问题的特殊方法，其实质是单纯 形法。
步骤 第一步 描述 求初始基行可行解（初始调运方案） 求检验数并判断是否得到最优解当非基变量的 检验数σi j全都非负(求min)时得到最优解，若 存在检验数σi j <0，说明还没有达到最优，转 第三步。 调整运量，即换基，选一个变量出基，对原运 量进行调整得到新的基可行解，转入第二步 方法 最小元素法、 西北角法、 伏格尔法 闭回路法和位 势法
Chapter3 运输规划
( Transportation Problem )
本章主要内容：
运输规划问题的数学模型
表上作业法 运输问题的应用
运输规划问题的数学模型
例3.1 某公司从两个产地A1、A2将物品运往三个销地B1, B2, B3，各产地的产量、各销地的销量和各产地运往各销地每件 物品的运费如下表所示，问：应如何调运可使总运输费用最 小？
行差额
A1 2 10 3 9
16
0
A2
8
8 5 11 6
10
1
A3
14
销量 8 2 14 12 1
8
14 3
22
48
1
列差额
所以，初始基可行解为：……目标函数值Z＝244
表上作业法
例3.4 某运输资料如下表所示：
销地 产地 B1 4 B2 12 B3 4 B4 11 产量
行差额
A1 2 10
12
3 9
19
6
13 12
13
13
表上作业法
最小元素法的缺点是：为了节省一处的费用，有时造成在其他处 要多花几倍的运费。伏格尔法考虑到，一产地的产品假如不能按最 小运费就近供应，就考虑次小运费，这就有一个差额。差额越大， 说明不能按最小运费调运时，运费增加越多。因而对差额最大处， 就应当采用最小运费调运。例如下面两种运输方案。