文档介绍：前面我们学过了线性规划的解法,单纯形法,运输问题是一类特殊的线性规划问题,由于最早是从物资运输问题中产生出来的,故称运输问题。该问题可以用单纯形法,但由于本身的特殊性,可以使用更加简便的办法求解,例如我们现在将要介绍表上作业法。
第三节运输问题
仓库
路程
公里数
营地
A1
A2
…
Am
需求量
(吨)
B1
B2
………
Bn
c11
c12
c1n
………
………
………
………
c21
c22
c2n
…
…
…
cm1
cm2
cmn
储量
(吨)
b1
b2
bn
………
a1
a2
am
…
运输问题的特点定理
定理1
运输问题有解的充要条件是该运输问题是平衡运输问题
定理2
平衡运输问题必有最优解
定理3
运输问题的约束方程组得系数矩阵 A 得秩为 m + n -1,
即 R(A)= m + n -1。
2 运输问题的表上作业法
表上作业法的作业步骤是:
(1)求出初始基本可行解(也就是初始调运方案)
(2)判断此初始调运方案是否是最优调运方案,当然这也要用求检验数的办法。
(3)迭代(也就是采用某种方法改进调运方案,以使运输费用减少)
设有三个弹药库要用汽车四个部队驻地运送弹药,具体数据如下表。请安排调运方案使总的运输里程最小。
引例
B1
B2
B3
B4
储量(吨)
A1
50
20
50
20
120
A2
30
50
30
100
130
A3
40
60
50
40
150
需要量
(吨)
100
100
100
100
仓库
路程
(公里)
营地
400
400
平衡的含义
(1)求出初始调运方案
——采用最小元素法
随便找出一个调运方案是不可以的,
(2)判断是否最优
——采用计算检验数的办法
(3)迭代
——采用闭回路的办法
表上作业法的基本步骤
不平衡运输