第四章-最优化理论运输问题

对工厂1必须有 对工厂2必须有 对工厂3必须有
X11+X12+X13 X21+X22+X23 X31+X32+X33
= 50 = 70 = 20
对商店1必须有 对商店2必须有 对商店3必须有
X11+X21+X31 X12+X22+X32 X13+X23+X33
= 50 = 60 = 30
8
于是，解此问题的线性最优化模型为：
+由工厂2运出产品的总费用(10X21+ 5X22+ 8X23) +由工厂3运出产品的总费用( X31+ 3X32+10X33)
写成表达式就是：
Min Z = 3X11+ 2X12+ 3X13+10X21+ 5X22+ 8X23+X31+ 3X32+10X33
7
约束条件
主要是对工厂的产量约束和商店的销量约束，由 于产量与销量相同，因而有：

ai

n
bj
（4.2）
i 1
j 1
m
n
如果 ai bj ，就称此运输
mn
Min Z
cij X ij
问题为i非1 平衡j1运输问题，包含
i1 j1
产大于销和销大于产两种情况，

这我们将在第3节介绍。 下面我们只考虑产销平衡

s.t

n
X ij ai
如下表4-5所示. 问如何确定调运方案，使总费用达到最小？
工厂
商店 1
2
3
供应量
1
3
2
3
50
2
10
5
8
70
3 需求量
1
3
10
20
50
60
30
6
解 模型建立 决策变量
送到第用j双（下j=标1决，策2，变3量）X家ij商表店示产从品第的i 数（量i=。1，2，3）家工厂运
目标函数 利用单位运价表和产销平衡表中的数据，我们希望总的 运费达到最小，即 Min Z = 由工厂1运出产品的总费用( 3X11+ 2X12+ 3X13)
= 50 = 70 = 20 = 50 = 60 = 30
上述模型显然是线性规划模型，我们可以使用线性规划的
单纯形法对它进行求解. 但是，当用单纯形法求解运输问题
时，先得给每个约束条件中引入一个人工变量，这样模型
的变量个数就会达到15个ห้องสมุดไป่ตู้求解是比较繁琐的，因而有必 要寻求更简便的解法.
9
为了说明适于求解运输问题的更好的解法，先看一下运输问 题的一般描述及模型的一般形式. 运输问题的一般形式为：
《运筹学通论》
1
第四章 运输问题
◆4.1 运输问题的数学模型 ◆4.2 表上作业法 ◆4.3 产销不平衡的运输问题 ◆4.4 运输问题应用举例
2
在经济建设中，经常遇到大宗物资的调运问题， 如煤、钢材、粮食等. 如果在我们考虑范围之内有 若干个生产基地和若干消费地点，根据已有的交 通网络，如何制定调运方案，使总的运费达到最 小，这就是运输问题.
运输问题是特殊的线性规划问题，故可以用单纯 形法来求解，又因为它具有特殊性，因而它还具 有比单纯形法更为简便的解法，这就是我们专门 研究运输问题的目的.
4.1 运输问题的数学模型
本节我们先引入运输问题的数学模型，然后讨论运输问题 数学模型的特点.
3
4.1.1 运输问题的数学模型
先通过一个简单的例子来说明运输问题及其数学模型.
中，目标函数要求运输总费用最小；前m个约束条件的意义
是：由某一产地运往各个销地的物资数量之和等于该产地的
产量；中间n个约束条件的意义是：由各产地运往某一销地
的物资数量之和等于该销地的销量；后mn个约束条件是变量
的非负条件.
12
4.1.2 运输问题数学模型的特点
对于产销平衡运输问题（4.3），将其约束条件加以整理，
j 1
m
X ij b j
(i 1,2, , m)
（4.3）
( j 1,2, , n)
问题，产销平衡运输问题的一 般模型为：
i1

X ij 0
(i 1,2, , m; j 1,2, , n)

其中约束条件右端常数ai 和bj满足（4.2），在运输问题（4.3）
例1 假设有三家工厂，都将产品运往三个不同的商店(如图)， 每家工厂每周的生产能力和每个商店每周的需求量如表4-1和
表4-2所示.
工厂1
商店1
表4-1
工厂
123
供应量（吨/周） 50 70 20
工厂2
商店2
表4-2
商店
123
工厂3
商店3
需求量（吨/周） 50 60 30
4
显然，每周的供应总量与需求总量是相等的，即产销平 衡，这可以用表4-3来表示，称为产销平衡表.
已知有m个生产地点Ai， i=1，2，…，m，可供应某种物 资，其供应量是ai， i=1，2，…，m. 有n个销地Bj，需求量 是bj，j=1，2，…，n. 从Ai到Bj运送单位物资的运价为cij， i=1，2，…，m；j=1，2，…，n，问如何安排运输可使总运费 最小？
这是多个产地供应多个销地的单一物品运输问题，我们用 Xij表示从产地Ai到销地Bj的运量，为直观起见，可以单独将Xij 列出得该问题的运输表. 但我们也可以将运输表和单位运价表、 产销量放在一起，如下表4-6所示.
10
销地
产地
B1
B2
…
A1
X11 c11
X12 c12
A2
X21 c21
X22 c22
Bn X1n c1n X2n c2n
产量 a1 a2
…
Am
Xm1 cm1
cm Xm2 2
Xmn cmn
am
销量
b1
b2
bn
表中每格元素Xij代表运量，右上角元素 cij代表单位运价.
11
在产销平衡条件下，可知
m
表4-3 产销平衡表
单位：吨
工厂
商店 1
2
3
供应量
1
50
2 3 需求量
70
20
50
60
30
由于运货距离和运货公路的路况不同，各个工厂运往各商 店物资的单位运输费用是不同的，单位费用如表4-4所示， 称为单位运价表.
5
表4-4 单位运价表
商店
工厂
1
单位：元/吨
2
3
1
3
2
3
2
10
5
8
3
1
3
10
当然，我们也可以将产销平衡表和单位运价表放在一个表中，
Min Z = 3X11+ 2X12+ 3X13 + 10X21+ 5X22+ 8X23+X31+3X32+10X33
s. t.
X11+X12+X13
X21+X22+X23
X31+X32+X33
X11+
X21+
X31
X12+
X22+
X32
X13+
X23+
X33
Xij≥0 i=1，2，3 j=1，2，3
可知其系数矩阵具有下述形式：
x11 x12 x1n x21 x22 x2n xm1 xm2 xmn