量
需 求
3 d3=60
4 d4=20 7
运输问题线性规划模型
设xij为由第i个工厂运到第j个门市部的 电视机台数，cij为由第i个工厂运到第j 个门市部的运费，则原运输问题的线 性规划模型为：
.
8
Min Z= 9x11 +12x12 +9x13 +6x14 +7x21 +3x22+7x23+7x24 +6x31+5x32+9x33 +11x34
m
xij d j
i1
(j= 1,2,…,n) 需求约束
xij≥0，i=1,1,…,m; j=1,2,…,n 由 cij、si、dj 组成的 （m+1)×(n+1) 矩阵称为运输矩阵
.
12
约束方程共有m+n个，由于∑si=∑dj， 因此约束方程只有m+n-1个方程是线性
独立的。因此运输问题的基本可行解
如果第一个工厂的生产量小于第一个销售点的需求量， 则先将第一个工厂的全部产品运往第一个销售点，不 足的需求由第二个补足。
.
18
销地
1
2
3
4 供应量
9 12 9
6
1
40
10
50 10
产
7 2
地
6 3
需求量 40
3
7
7
30
30
5
9 11
30
20
40 60 20
60 30 50
20
30
30
x11,x12,x22,x23,x33,x346个变量.构成一个基本初始可行解19。
重复上述步骤，直到把所有的空格都划去为止。
如果这样选出的空格共有m+n-1个，则构成一 个初始基本可行解。
.
21
初前例始中：可最行小元解素法的求初获始得解
1
2
3
4
9
12
9
6
1
30
20
7 2
3
7
7
40
20
6
5
3
40
9
11
10
dj
40
40
60
20
0
0
40
0
10
.0
si 50 30 0 60 20 0 50 10 0
i1
n
x ij s i （i= 1,2,…,m)
j1
产小于销时约束条件
n
x ij s i （i= 1,2,…,m)
j1
m
x ij d j （j= 1,2,…,n)
i1
.
15
不平衡的运输问题
门市部
工厂
12
供应量总
3
计
1
9 12 9
50
2
737
60
需求量总计 40 40 60
.
16
平衡运输问题的表上作业法
第3章 运输问题
线性规划续
.
1
主要内容
运输问题的特点及模型描述
网络图 线性规划模型 表上作业
表上作业法
平衡运输问题 不平衡运输问题
.
2
一、运输问题的特点及模型
原问题：产地到销地之间运送货物的最佳 路径
特点：
多个产地和多个销地； 每个产地的产量不同，每个销地的销量也不同； 各产销两地之间的运价不同。
.
5
单位：元/台
门市部
工厂
1 2 3 4 供应量总计
1
9 12 9 6
50
2
7377
60
3
6 5 9 11
50
需求量总计 40 40 60 20
160
.
6
运输问题网络图
供应地
运价
量供 应
9
s1=50 1 12
9 6
7
s2=60 2
3 7
7
6
5
s3=50 3 9
11
.
需求地
1 d1=40
2
d2=40
1 2 3 … n 供应
1 c11
出2
发 地
c21 …
m cm1
成本 cij
c1n s1 c2n s2 ……
cmn sm
需求 d1
到达地
dn
.
∑
4
运输问题
引例：设某电视机厂有三个分厂，生产同 一种彩色电视机，供应该厂在市内的四个 门市部销售。已知三个分厂的日生产能力 分别是50，60，50台，四个门市部的日销 量分别为40，40，60，20台。从各个分厂 运往各门市部的运费如下表所示，试安排 一个运费最低的运输计划。
m
n
产销平衡： Si d j
i 1
j 1
m
n
产大于销： Si d j
i 1
j 1
m
n
产小于销： Si d j
i 1
j 1
.
11
运输问题
产销平衡的运输问题模型
令xij为 从i地运到j地的数量
Min Z =
nn
cij xij
i1 j1
n
x ij si
j1
（Cij≥0) （i= 1,2,…,m) 供应约束
西北解法的特点
优点：简单易行，容易得到基本初始可行解； 缺点：没有考虑运费的因素，因此距离最优解
较远。
.
20
最小元素法（最小费用法）：“就近供应”
从单位运价表中选取最低运价的空格开始供求 分配：
当供应量大于需求量，取值为需求量，划去该空格 所在的列
当供应量小于需求量，取值为供应量，划去该空格 所在的行
x11 +x12 +x13 +x14 x21
+x22 +x23 +x24
=50 供
=束60
应 地
s.t.
x31 +x32 +x33 +x34
=50 约
x11 x12 x13
+x21
+ x31
+x22
+x32
+x23
+x33
x14
+x24
+x34
=40 需
=40
束
=60
求 地
约
=20
xij ≥0
i= 1,2,3; j=1,2, 3,4
(一)运输问题初始可行解的获得
西北角法——从西北角的第一格开始安排运输 计划
具体步骤
.
17
平衡运输问题的表上作业法
具体步骤
取其相应的供应量和需求量中的最小值作为初始 基本可行解的第一个分量
如果第一个工厂的生产量大于第一个销售点的需求， 那么就由第一个工厂全部满足第一个销售点的需要， 工厂商品的剩余部分运八第二个销售点；
目标
合理组织调运，既满足各销地的要求，又使总 的运输费用（或里程、时间等）最小。
.
3
运输问题
设有同一种货物从m个出发地1，2，…，m运往n个到 达地1，2，…，n。第i个出发地的供应量（Supply） 为si（si≥0），第j个到达地的需求量（Demand）为 dj （dj≥0）。 每单位货物从产地 i 运到销地 j 的运价为Cij。 求一个使总运费最小的运输方案。
m×n个变量，. m+n个条件
9
运输问题的表格表示
cij xij
1
1
9
273Fra bibliotek6需求量 40
2 12 X11 3 X21 5 X31 40
3 9 X12 7 X22 9 X32 60
4 6 X13 7 X23 11 X33 20
供应量 50 X14 60 X24 50 X34
.
运输问题
三类运输问题：
有m+n-1个分量。
.
13
引例——方程组中方程的线性独立问题：
x1+x2+x3=3 2x1+x2+x4=6 3x1+2x2+x3+x4=9 系数的增广矩阵为：
11103
11103
21016 → 21016
32149
00000
.
14
运输问题
产销不平衡的运输问题模型
产大于销时约束条件
m
x ij d j （j= 1,2,…,n)