1
线性规划 Linear Programming（ LP）
第三章特殊线性规划 ——
运输问题
2
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题运输问题的一般描述 模型的一般形式引例 这里有三家工厂，都将产品运往三个不同的商店（见下图）。每个工厂以产品件数表示出每周生产能力见下表 1。每家商店平均需求量见下表 2。
工厂 1
工厂 3
工厂 2
商店 1
商店 3
商店 2
表 1
表 2
商店 1 2 3
供应量（件 /周） 50 70 20
工厂 1 2 3
需求 量（件 /周） 50 60 30
3
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题但是，由于运货距离不同，各个工厂运往各商店的货物的运输费用是不同的。费用如下表，我们的问题是确定由哪家工厂运送多少件产品到哪家商店。
能否列出线性最优化模型？ 决策存在什么样的约束条件？
模型评价涉及什么样的准则？ 有那些决策变量？
由工厂每件产品运往各商店的费用（元）
1 2 3
1
2
3
3
10
1
2
5
3
3
8
10
4
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题模型建立决策变量 —— 有待确定的是从每家工厂 i（ i=1,2,3）运输多少件产品到每家商店 j（ j=1,2,3）去。因此，方便的办法是用双下标来表示决策变量即 Xij。
目标函数 —— 利用运输费用表中的数据，我们希望其值为最小的是：
Min Z = 由工厂 1运出产品的总费用 ---- 3X11+ 2X12+ 3X13
+由工厂 2运出产品的总费用 ----10X21+ 5X22+ 8X23
+由工厂 3运出产品的总费用 ---- X31+ 3X32+10X33
即,Min Z = 3X11+ 2X12+ 3X13 + 10X21+ 5X22+ 8X23 + X31+ 3X32+10X33
约束条件 —— 需要把决策变量的约束条件当作方案生成源。
对工厂 1必须有 X11+X12+X13 = 50 （对工厂 1的供应约束）
对工厂 2必须有 X21+X22+X23 = 70 （对工厂 2的供应约束）
对工厂 3必须有 X31+X32+X33 = 20 （对工厂 3的供应约束）
5
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题约束条件 —— 对每家商店来说，也需要一个逻辑关系式来说明每个星期运到的产品总数应等于每周的需求量。
对商店 1必须有 X11+X21+X31 = 50
对商店 2必须有 X12+X22+X32 = 60
对商店 3必须有 X13+X23+X33 = 30
于是，用于解此问题的线性最优化模型是：
Min Z = 3X11+ 2X12+ 3X13 + 10X21+ 5X22+ 8X23 + X31+ 3X32+10X33
X11+X12+X13 = 50
X21+X22+X23 = 70
X31+X32+X33 = 20
X11+ X21+ X31 = 50 Xij≥0 且为整数
X12+ X22+ X32 = 60 i=1,2,3
X13+ X23+ X33 = 30 j=1,2,3
s,t.
6
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题运输问题模型分析一般形式：
某种物资有 m个产地 Ai，产量（供应量）是 ai（ i=1,2,…,m），有 n
个销地 Bj，销量（需求量）是 bj（ j=1,2,…,n）。从运到的单位运价为
cij（ i=1,2,…,m； j=1,2,…,n），如何安排运输可使总运费最小？
产大于销 ——? ai ≥? bj
Min Z=CijXij
xij≤ ai （ i=1,2,…,m）
xij =bj （ j=1,2,…,n）
xij≥ 0 （ i=1,2,…,m；
j=1,2,…,n）
销大于产 ——? ai ≤? bj
Min Z=CijXij
xij=ai （ i=1,2,…,m）
xij≤ bj （ j=1,2,…,n）
xij≥ 0 （ i=1,2,…,m；
j=1,2,…,n）
7
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题产销平衡 ——? ai =? bj
注意！这种模型具有特殊的形式：所有决策变量的约束条件，
其系数均等于 1；而且，每个决策变量仅出现于两个约束条件之中。
这些特性表明，解这类线性最优化模型的单纯形法中有一种特殊的方法可用来解这个问题 —— 这是解这类模型的特别有效的一种方法。
而且上述特性还表明，可以给这类线性最优化模型以一种象网络模型式的形象化的说明。
Min Z= CijXij
xij =ai （ i=1,2,…,m）
xij =bj （ j=1,2,…,n）
xij≥ 0 （ i=1,2,…,m； j=1,2,…,n）
8
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题模型特点
1、运输问题有有限最优解
2、运输问题约束条件系数矩阵
A =
1 1 … 1 1
1 1 … 1
……………………………………………………
1 1 … 1
1 1 … 1
1 1 1
……………………………………………………
1 1 1 （ m+n） × （ mn）
9
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题产销平衡运输问题的对偶问题
（ P） Min Z= CijXij
xij =ai （ i=1,2,…,m）
xij =bj （ j=1,2,…,n）
xij≥ 0 （ i=1,2,…,m； j=1,2,…,n）
（ D） Max W = ∑ai Ui + ∑bj Vj
Ui + Vj ≥ Cij
Ui,Vj,自由变量
（ i = 1,2,…,m ； j = 1,2,…,n ）
10
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题运输问题的求解方法求解此问题的一个十分有效的方法是 表上作业法：
（ 1） 产销平衡问题 —— 总产量等于总销量的运输问题
a、建立作业表
b、确定初始调运方案（最小元素法）
c、现行方案的最优性检验（位势法）
d、现行方案的调整（闭回路法）
11
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题例 1——
甲（ B1）、乙（ B2）、丙（ B3）、丁（ B4）三城市所需煤炭由三个煤矿 A1,A2,A3供应，有关数据如表，表中数字为单位运费
（万元／万吨），请制订使总运费最小的调运计划。
销地 B1 销地 B2 销地 B3 销地 B4 产量产地 A1 3 7 6 4 5
产地 A2 2 4 3 2 2
产地 A3 4 3 8 5 3
销量 3 3 2 2
12
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题
a、建立平衡调运作业表
B1 B2 B3 B4 产
A1
3 7 6 4
5
A2
2 4 3 2
2
A3
4 3 8 5
3
销 3 3 2 2
3 运价
Xij
调运量，当其为非基变量时不予填写
ij
检验数，当其为基变量的检验数时不予填写
13
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题
b、确定初始调运方案（最小元素法） 3 运价
Xij
调运量，当其为非基变量时不予填写
ij
检验数，当其为基变量的检验数时不予填写
3 7 6 4
2 4 3 2
4 3 8 5
A1
A2
A3
B1 B2 B3 B4 产量销量 3 3 2 2
5
2
3
2
1
1 4
3
0 2 22
14
线性规划 Linear Programming（ LP）
b、确定初始调运方案（ Vogel —— 沃格尔法）
销地产地 B1 B2 B3 B4 产量行罚数
1 2 3 4
A1 3 7 6 4 5 1 1 1
A2 2 2 3 2 2 0
A3 4 3 8 5 3 1 1
销量 3 3 2 2 10
列罚数
1 1 1 3 2
2 1 4 1
3 0 0
4
5
20
3
3 220
15
线性规划 Linear Programming（ LP）
b、确定初始调运方案（ Vogel —— 沃格尔法）
销地产地 B1 B2 B3 B4 产量
A1 3 7 6 4 53 0 2
A2 2 2 3 2 20 2
A3 4 3 8 5 33
销量 3 3 2 2 10
16
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题
c、现行方案的最优性检验（位势法）
1 0 2 2
2
3
3 7 6 4
2 4 3 2
4 3 8 5
A1
A2
A3
B1 B2 B3 B4 Ui
Vj
由?ij=Cij-（ Ui+Vj）
计算位势 Ui,Vj,
因对基变量而言有
ij=0,即
Cij-（ Ui+Vj） = 0
令 U1=0
0
3 7 6 4
-1
-4
再由?ij=Cij-（ Ui+
Vj）计算非基变量的检验数?ij
-2 -2 -1
5 6 5
当存在非基变量的检验数?kl < 0 且?kl=min{?ij}时，令 Xkl 进基。从表中知可选 X23进基。
17
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题
d、现行方案的调整（闭回路法）
1 0 2 2
2
3
3 7 6 4
2 4 3 2
4 3 8 5
A1
A2
A3
B1 B2 B3 B4 Ui
Vj
0
3 7 6 4
-1
-4
-2 -2 -1
5 6 5
调整量? = {从 进基变量 X23出发的 闭回路中 奇 拐点上 基 变量的最小值 }=2。
调整步骤为：
闭回路上 偶 拐点处基变量的值 +?
闭回路上 奇 拐点处基变量的值 -?
2
3
0
18
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题
d、现行方案的调整（闭回路法）
1 0 2 2
2 2
3
3 7 6 4
2 4 3 2
4 3 8 5
A1
A2
A3
B1 B2 B3 B4 Ui
Vj
重复步骤 C,检验当前调运方案（基可行解）的最优性如非最优方案，则擦去 Ui,Vj和?ij然后重新计算。
3
0
0
3 7
-1
4 4
-4
2
-2 -1
5 8 5
0
19
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题
d、现行方案的调整（闭回路法）
1 0 2 2
0 2
3
3 7 6 4
2 4 3 2
4 3 8 5
A1
A2
A3
B1 B2 B3 B4 Ui
Vj
重复步骤 C,检验当前调运方案（基可行解）的最优性如非最优方案，则擦去 Ui,Vj和?ij然后重新计算。
3 0
3 7 4
-3
-4
6
0
2 1
5 6 5
当所有非基变量的检验数均非负时，
则当前调运方案即为最优方案，如表此时最小总运费
min Z =9+0+8+0+
6+9 = 32
20
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题表上作业法的几点说明：
1、若运输问题的某一基可行解有多个非基变量的检验数为负时，
在迭代时可取它们中任一非基变量进基均可使目标函数值得到改善，
但通常取最小者对应的非基变量进基。
2、当迭代到最优解时，有某非基变量的检验数为 0 时，则问题有无穷多最优解。
3、当在表上作业时，同时划去了一行和一列运输价格时，就出现了退化，此时必须在当前划去的运价中某一空格填入一个 0,表示该格中的变量是取值为 0 的基变量。
21
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题进一步讨论一,产销不平衡的运输问题 —— 总产量小于总销量的运输问题例 2—— 有三个化肥厂供应四个地区的农用化肥。等量化肥在这些地区使用效果相同。相关数据如下表，试分析总运费最节省的化肥调运方案。
需求地区化肥厂 B1 B2 B3 B4 产量（万吨）
A1 16 13 22 17 50
A2 14 13 19 15 60
A3 19 20 23 --- 50
最低需求（万吨）
最高需求（万吨）
30
50
70
70
0
30
10
不限运价：万元 /万吨
22
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题进一步讨论分析：
这是一个产销不平衡的运输问题，总产量为 160万吨，四个地区的最低需求为 110万吨，最高需求为无限。根据现有产量，地区
B4每年最多能分配到 60万吨，这样最高总需求为 210万吨，大于产量。为了求得平衡，在产销平衡表中增加一个虚拟的化肥厂 D,其年产量为 50万吨。由于各个地区的需要量包含两部分，如地区 B1，
其中 30万吨是最低需求，故不能由虚拟的化肥厂 D供给，令其相应的运输价格为 M（任意大正数），而另一部分 20万吨满足或不满足均可，因此可以由虚拟的化肥厂 D供给，并令其相应的运输价格为 0
（没有发生的运输）。对凡是需求分两种情况的地区，实际上可按照两个地区看待。这样可以建立这个问题的产销平衡表 ——
23
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题进一步讨论例 2 产销平衡表
A1
A2
A3
D
B'1 B''1 B2 B3 B'4 B''4 产量销量
17 17
14 14 13 19 15 15
19 19 20 23 M M
M 0 M 0 M 0
50
60
50
50
30 20 70 30 10 50
16 16 2213
20 30
20
30
50
20
20 4030 10100
30 2020
24
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题进一步讨论产销平衡表
A1
A2
A3
D
B'1 B''1 B2 B3 B'4 B''4 Ui
Vj
13
50
14
30
13
20
19
0
15
10
23
30
M
20
0
20
0
30
0
13
0
14 19 15
4
-4+M
4-M
-4+M
2 20-M 3 2 21-M
18-M 19-M
1 19-M 3 M-19
2M-18 2M-17 M-23 2M-19
16 22 17 17
14 15
19 19 20 M
M M 0 M
16
0
25
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题进一步讨论产销平衡表
A1
A2
A3
D
B'1 B''1 B2 B3 B'4 B''4 Ui
Vj
50
14
30
14
0
13
20
15
10
23
30
M
20
0
20
0
30
0
0
-14+M
-14
14 14 13 37-M 15 14
2 2 -15+M 2 3
-18+M 1
19-M 19-M 21-M -1
M 1+M -23+M -1+M
10 20
0
50
20
16 13 22 17 17
19 15
19 19 20 M
M M 0 M
16
26
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题进一步讨论产销平衡表
A1
A2
A3
D
B'1 B''1 B2 B3 B'4 B''4 Ui
Vj
16 13
50
22 17 17
14
10
14
20
13
20
19 15
10
15
19
20
19 20 23
30
M M
0
M 0 M 0 M 0
50
16
0
0
5
5-M
14 14 13 18 15 -5+M
2 2 4 2 22-M
1 20-M
0 2 -20+M
-19+2M -19+M -18+M -23+M -20+2M
0
27
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题进一步讨论产销平衡表
A1
A2
A3
D
B'1 B''1 B2 B3 B'4 B''4 Ui
Vj
16 13
50
22 17 17
14
10
14
20
13
20
19 15
10
15
0
19
20
19 20 23
30
M M
M 0 M 0 M 0
50
16
0
0
6
0
14 14 13 17 15 15
2 2 5 2 2
2
-1 1 -21+M -21+M
-14+M -14 -13+M -17 -15+M10
10
30 20
40
28
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题进一步讨论产销平衡表
A1
A2
A3
D
B'1 B''1 B2 B3 B'4 B''4 Ui
Vj
13
50
14
20
13
20
15
10
15
10
19
30
23
20
0
10
0
40
0
0
8
-15
11 14 13 15 15 15
5 2 7 2 2
3 4
-3 -1 M-23 M-23
M+4 1 M+2 M
30
0
30 20
20
16 22 17 17
14 19
19 20 M M
M 0 M M
16
29
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题进一步讨论产销平衡表
A1
A2
A3
D
B'1 B''1 B2 B3 B'4 B''4 Ui
Vj
16 13
50
22 17 17
14 14 13
20
19 15
10
15
30
19
30
19
20
20 23
0
M M
M 0 M 0
30
M 0
20
16
0
0
8
-15
11 11 13 15 15 15
5 5 7 2 2
3 3 4
-1 M-23 M-23
M+4 4 M+2 M
0
30
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题进一步讨论产销平衡表
A1
A2
A3
D
B'1 B''1 B2 B3 B'4 B''4 Ui
Vj
13
50
13
20
15
10
15
30
19
30
19
20
20
0
0
30
0
20
0
0
7
-15
12 12 13 15 15 15
4 4 7 2 2
2 2 4
1 M-22 M-22
M+3 3 M+2 M
16 22 17 17
14 14 19
23 M M
M 0 M M
16
31
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题进一步讨论产销平衡表
A1
A2
A3
D
16 13
50
22 17 17
14 14 13
20
19 15
10
15
30
19
30
19
20
20
0
23 M M
M 0 M 0
30
M 0
20
50
60
50
50
30 20 70 30 10 50
16
B'1 B''1 B2 B3 B'4 B''4 产量销量
32
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题进一步讨论二、有转运的运输问题在上面所讨论的问题中，我们都假定物品是由产地直接运送到目的地的，没有经过任何中间转运。然而，在实际当中常常会遇到一种情形：需要先将物品由产地运到某个中间转运站（可能是另外的产地、销地或中间转运仓库），然后再转运到目的地。有时，可能经过转运比直接运到目的地更加经济。因此，在决定运输方案时有必要把转运也考虑进去。这样，将使运输问题更加复杂。
33
线性规划 Linear Programming（ LP）
第三章结束谢谢！
线性规划 Linear Programming（ LP）
第三章特殊线性规划 ——
运输问题
2
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题运输问题的一般描述 模型的一般形式引例 这里有三家工厂，都将产品运往三个不同的商店（见下图）。每个工厂以产品件数表示出每周生产能力见下表 1。每家商店平均需求量见下表 2。
工厂 1
工厂 3
工厂 2
商店 1
商店 3
商店 2
表 1
表 2
商店 1 2 3
供应量（件 /周） 50 70 20
工厂 1 2 3
需求 量（件 /周） 50 60 30
3
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题但是，由于运货距离不同，各个工厂运往各商店的货物的运输费用是不同的。费用如下表，我们的问题是确定由哪家工厂运送多少件产品到哪家商店。
能否列出线性最优化模型？ 决策存在什么样的约束条件？
模型评价涉及什么样的准则？ 有那些决策变量？
由工厂每件产品运往各商店的费用（元）
1 2 3
1
2
3
3
10
1
2
5
3
3
8
10
4
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题模型建立决策变量 —— 有待确定的是从每家工厂 i（ i=1,2,3）运输多少件产品到每家商店 j（ j=1,2,3）去。因此，方便的办法是用双下标来表示决策变量即 Xij。
目标函数 —— 利用运输费用表中的数据，我们希望其值为最小的是：
Min Z = 由工厂 1运出产品的总费用 ---- 3X11+ 2X12+ 3X13
+由工厂 2运出产品的总费用 ----10X21+ 5X22+ 8X23
+由工厂 3运出产品的总费用 ---- X31+ 3X32+10X33
即,Min Z = 3X11+ 2X12+ 3X13 + 10X21+ 5X22+ 8X23 + X31+ 3X32+10X33
约束条件 —— 需要把决策变量的约束条件当作方案生成源。
对工厂 1必须有 X11+X12+X13 = 50 （对工厂 1的供应约束）
对工厂 2必须有 X21+X22+X23 = 70 （对工厂 2的供应约束）
对工厂 3必须有 X31+X32+X33 = 20 （对工厂 3的供应约束）
5
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题约束条件 —— 对每家商店来说，也需要一个逻辑关系式来说明每个星期运到的产品总数应等于每周的需求量。
对商店 1必须有 X11+X21+X31 = 50
对商店 2必须有 X12+X22+X32 = 60
对商店 3必须有 X13+X23+X33 = 30
于是，用于解此问题的线性最优化模型是：
Min Z = 3X11+ 2X12+ 3X13 + 10X21+ 5X22+ 8X23 + X31+ 3X32+10X33
X11+X12+X13 = 50
X21+X22+X23 = 70
X31+X32+X33 = 20
X11+ X21+ X31 = 50 Xij≥0 且为整数
X12+ X22+ X32 = 60 i=1,2,3
X13+ X23+ X33 = 30 j=1,2,3
s,t.
6
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题运输问题模型分析一般形式：
某种物资有 m个产地 Ai，产量（供应量）是 ai（ i=1,2,…,m），有 n
个销地 Bj，销量（需求量）是 bj（ j=1,2,…,n）。从运到的单位运价为
cij（ i=1,2,…,m； j=1,2,…,n），如何安排运输可使总运费最小？
产大于销 ——? ai ≥? bj
Min Z=CijXij
xij≤ ai （ i=1,2,…,m）
xij =bj （ j=1,2,…,n）
xij≥ 0 （ i=1,2,…,m；
j=1,2,…,n）
销大于产 ——? ai ≤? bj
Min Z=CijXij
xij=ai （ i=1,2,…,m）
xij≤ bj （ j=1,2,…,n）
xij≥ 0 （ i=1,2,…,m；
j=1,2,…,n）
7
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题产销平衡 ——? ai =? bj
注意！这种模型具有特殊的形式：所有决策变量的约束条件，
其系数均等于 1；而且，每个决策变量仅出现于两个约束条件之中。
这些特性表明，解这类线性最优化模型的单纯形法中有一种特殊的方法可用来解这个问题 —— 这是解这类模型的特别有效的一种方法。
而且上述特性还表明，可以给这类线性最优化模型以一种象网络模型式的形象化的说明。
Min Z= CijXij
xij =ai （ i=1,2,…,m）
xij =bj （ j=1,2,…,n）
xij≥ 0 （ i=1,2,…,m； j=1,2,…,n）
8
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题模型特点
1、运输问题有有限最优解
2、运输问题约束条件系数矩阵
A =
1 1 … 1 1
1 1 … 1
……………………………………………………
1 1 … 1
1 1 … 1
1 1 1
……………………………………………………
1 1 1 （ m+n） × （ mn）
9
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题产销平衡运输问题的对偶问题
（ P） Min Z= CijXij
xij =ai （ i=1,2,…,m）
xij =bj （ j=1,2,…,n）
xij≥ 0 （ i=1,2,…,m； j=1,2,…,n）
（ D） Max W = ∑ai Ui + ∑bj Vj
Ui + Vj ≥ Cij
Ui,Vj,自由变量
（ i = 1,2,…,m ； j = 1,2,…,n ）
10
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题运输问题的求解方法求解此问题的一个十分有效的方法是 表上作业法：
（ 1） 产销平衡问题 —— 总产量等于总销量的运输问题
a、建立作业表
b、确定初始调运方案（最小元素法）
c、现行方案的最优性检验（位势法）
d、现行方案的调整（闭回路法）
11
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题例 1——
甲（ B1）、乙（ B2）、丙（ B3）、丁（ B4）三城市所需煤炭由三个煤矿 A1,A2,A3供应，有关数据如表，表中数字为单位运费
（万元／万吨），请制订使总运费最小的调运计划。
销地 B1 销地 B2 销地 B3 销地 B4 产量产地 A1 3 7 6 4 5
产地 A2 2 4 3 2 2
产地 A3 4 3 8 5 3
销量 3 3 2 2
12
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题
a、建立平衡调运作业表
B1 B2 B3 B4 产
A1
3 7 6 4
5
A2
2 4 3 2
2
A3
4 3 8 5
3
销 3 3 2 2
3 运价
Xij
调运量，当其为非基变量时不予填写
ij
检验数，当其为基变量的检验数时不予填写
13
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题
b、确定初始调运方案（最小元素法） 3 运价
Xij
调运量，当其为非基变量时不予填写
ij
检验数，当其为基变量的检验数时不予填写
3 7 6 4
2 4 3 2
4 3 8 5
A1
A2
A3
B1 B2 B3 B4 产量销量 3 3 2 2
5
2
3
2
1
1 4
3
0 2 22
14
线性规划 Linear Programming（ LP）
b、确定初始调运方案（ Vogel —— 沃格尔法）
销地产地 B1 B2 B3 B4 产量行罚数
1 2 3 4
A1 3 7 6 4 5 1 1 1
A2 2 2 3 2 2 0
A3 4 3 8 5 3 1 1
销量 3 3 2 2 10
列罚数
1 1 1 3 2
2 1 4 1
3 0 0
4
5
20
3
3 220
15
线性规划 Linear Programming（ LP）
b、确定初始调运方案（ Vogel —— 沃格尔法）
销地产地 B1 B2 B3 B4 产量
A1 3 7 6 4 53 0 2
A2 2 2 3 2 20 2
A3 4 3 8 5 33
销量 3 3 2 2 10
16
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题
c、现行方案的最优性检验（位势法）
1 0 2 2
2
3
3 7 6 4
2 4 3 2
4 3 8 5
A1
A2
A3
B1 B2 B3 B4 Ui
Vj
由?ij=Cij-（ Ui+Vj）
计算位势 Ui,Vj,
因对基变量而言有
ij=0,即
Cij-（ Ui+Vj） = 0
令 U1=0
0
3 7 6 4
-1
-4
再由?ij=Cij-（ Ui+
Vj）计算非基变量的检验数?ij
-2 -2 -1
5 6 5
当存在非基变量的检验数?kl < 0 且?kl=min{?ij}时，令 Xkl 进基。从表中知可选 X23进基。
17
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题
d、现行方案的调整（闭回路法）
1 0 2 2
2
3
3 7 6 4
2 4 3 2
4 3 8 5
A1
A2
A3
B1 B2 B3 B4 Ui
Vj
0
3 7 6 4
-1
-4
-2 -2 -1
5 6 5
调整量? = {从 进基变量 X23出发的 闭回路中 奇 拐点上 基 变量的最小值 }=2。
调整步骤为：
闭回路上 偶 拐点处基变量的值 +?
闭回路上 奇 拐点处基变量的值 -?
2
3
0
18
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题
d、现行方案的调整（闭回路法）
1 0 2 2
2 2
3
3 7 6 4
2 4 3 2
4 3 8 5
A1
A2
A3
B1 B2 B3 B4 Ui
Vj
重复步骤 C,检验当前调运方案（基可行解）的最优性如非最优方案，则擦去 Ui,Vj和?ij然后重新计算。
3
0
0
3 7
-1
4 4
-4
2
-2 -1
5 8 5
0
19
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题
d、现行方案的调整（闭回路法）
1 0 2 2
0 2
3
3 7 6 4
2 4 3 2
4 3 8 5
A1
A2
A3
B1 B2 B3 B4 Ui
Vj
重复步骤 C,检验当前调运方案（基可行解）的最优性如非最优方案，则擦去 Ui,Vj和?ij然后重新计算。
3 0
3 7 4
-3
-4
6
0
2 1
5 6 5
当所有非基变量的检验数均非负时，
则当前调运方案即为最优方案，如表此时最小总运费
min Z =9+0+8+0+
6+9 = 32
20
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题表上作业法的几点说明：
1、若运输问题的某一基可行解有多个非基变量的检验数为负时，
在迭代时可取它们中任一非基变量进基均可使目标函数值得到改善，
但通常取最小者对应的非基变量进基。
2、当迭代到最优解时，有某非基变量的检验数为 0 时，则问题有无穷多最优解。
3、当在表上作业时，同时划去了一行和一列运输价格时，就出现了退化，此时必须在当前划去的运价中某一空格填入一个 0,表示该格中的变量是取值为 0 的基变量。
21
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题进一步讨论一,产销不平衡的运输问题 —— 总产量小于总销量的运输问题例 2—— 有三个化肥厂供应四个地区的农用化肥。等量化肥在这些地区使用效果相同。相关数据如下表，试分析总运费最节省的化肥调运方案。
需求地区化肥厂 B1 B2 B3 B4 产量（万吨）
A1 16 13 22 17 50
A2 14 13 19 15 60
A3 19 20 23 --- 50
最低需求（万吨）
最高需求（万吨）
30
50
70
70
0
30
10
不限运价：万元 /万吨
22
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题进一步讨论分析：
这是一个产销不平衡的运输问题，总产量为 160万吨，四个地区的最低需求为 110万吨，最高需求为无限。根据现有产量，地区
B4每年最多能分配到 60万吨，这样最高总需求为 210万吨，大于产量。为了求得平衡，在产销平衡表中增加一个虚拟的化肥厂 D,其年产量为 50万吨。由于各个地区的需要量包含两部分，如地区 B1，
其中 30万吨是最低需求，故不能由虚拟的化肥厂 D供给，令其相应的运输价格为 M（任意大正数），而另一部分 20万吨满足或不满足均可，因此可以由虚拟的化肥厂 D供给，并令其相应的运输价格为 0
（没有发生的运输）。对凡是需求分两种情况的地区，实际上可按照两个地区看待。这样可以建立这个问题的产销平衡表 ——
23
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题进一步讨论例 2 产销平衡表
A1
A2
A3
D
B'1 B''1 B2 B3 B'4 B''4 产量销量
17 17
14 14 13 19 15 15
19 19 20 23 M M
M 0 M 0 M 0
50
60
50
50
30 20 70 30 10 50
16 16 2213
20 30
20
30
50
20
20 4030 10100
30 2020
24
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题进一步讨论产销平衡表
A1
A2
A3
D
B'1 B''1 B2 B3 B'4 B''4 Ui
Vj
13
50
14
30
13
20
19
0
15
10
23
30
M
20
0
20
0
30
0
13
0
14 19 15
4
-4+M
4-M
-4+M
2 20-M 3 2 21-M
18-M 19-M
1 19-M 3 M-19
2M-18 2M-17 M-23 2M-19
16 22 17 17
14 15
19 19 20 M
M M 0 M
16
0
25
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题进一步讨论产销平衡表
A1
A2
A3
D
B'1 B''1 B2 B3 B'4 B''4 Ui
Vj
50
14
30
14
0
13
20
15
10
23
30
M
20
0
20
0
30
0
0
-14+M
-14
14 14 13 37-M 15 14
2 2 -15+M 2 3
-18+M 1
19-M 19-M 21-M -1
M 1+M -23+M -1+M
10 20
0
50
20
16 13 22 17 17
19 15
19 19 20 M
M M 0 M
16
26
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题进一步讨论产销平衡表
A1
A2
A3
D
B'1 B''1 B2 B3 B'4 B''4 Ui
Vj
16 13
50
22 17 17
14
10
14
20
13
20
19 15
10
15
19
20
19 20 23
30
M M
0
M 0 M 0 M 0
50
16
0
0
5
5-M
14 14 13 18 15 -5+M
2 2 4 2 22-M
1 20-M
0 2 -20+M
-19+2M -19+M -18+M -23+M -20+2M
0
27
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题进一步讨论产销平衡表
A1
A2
A3
D
B'1 B''1 B2 B3 B'4 B''4 Ui
Vj
16 13
50
22 17 17
14
10
14
20
13
20
19 15
10
15
0
19
20
19 20 23
30
M M
M 0 M 0 M 0
50
16
0
0
6
0
14 14 13 17 15 15
2 2 5 2 2
2
-1 1 -21+M -21+M
-14+M -14 -13+M -17 -15+M10
10
30 20
40
28
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题进一步讨论产销平衡表
A1
A2
A3
D
B'1 B''1 B2 B3 B'4 B''4 Ui
Vj
13
50
14
20
13
20
15
10
15
10
19
30
23
20
0
10
0
40
0
0
8
-15
11 14 13 15 15 15
5 2 7 2 2
3 4
-3 -1 M-23 M-23
M+4 1 M+2 M
30
0
30 20
20
16 22 17 17
14 19
19 20 M M
M 0 M M
16
29
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题进一步讨论产销平衡表
A1
A2
A3
D
B'1 B''1 B2 B3 B'4 B''4 Ui
Vj
16 13
50
22 17 17
14 14 13
20
19 15
10
15
30
19
30
19
20
20 23
0
M M
M 0 M 0
30
M 0
20
16
0
0
8
-15
11 11 13 15 15 15
5 5 7 2 2
3 3 4
-1 M-23 M-23
M+4 4 M+2 M
0
30
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题进一步讨论产销平衡表
A1
A2
A3
D
B'1 B''1 B2 B3 B'4 B''4 Ui
Vj
13
50
13
20
15
10
15
30
19
30
19
20
20
0
0
30
0
20
0
0
7
-15
12 12 13 15 15 15
4 4 7 2 2
2 2 4
1 M-22 M-22
M+3 3 M+2 M
16 22 17 17
14 14 19
23 M M
M 0 M M
16
31
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题进一步讨论产销平衡表
A1
A2
A3
D
16 13
50
22 17 17
14 14 13
20
19 15
10
15
30
19
30
19
20
20
0
23 M M
M 0 M 0
30
M 0
20
50
60
50
50
30 20 70 30 10 50
16
B'1 B''1 B2 B3 B'4 B''4 产量销量
32
线性规划 Linear Programming（ LP）
特殊线性规划 —— 运输问题进一步讨论二、有转运的运输问题在上面所讨论的问题中，我们都假定物品是由产地直接运送到目的地的，没有经过任何中间转运。然而，在实际当中常常会遇到一种情形：需要先将物品由产地运到某个中间转运站（可能是另外的产地、销地或中间转运仓库），然后再转运到目的地。有时，可能经过转运比直接运到目的地更加经济。因此，在决定运输方案时有必要把转运也考虑进去。这样，将使运输问题更加复杂。
33
线性规划 Linear Programming（ LP）
第三章结束谢谢！
