文档介绍：第 4 篇数学方法在物流运输中的应用
第12章货物运输的优化求解
本章学习目的:了解常见货物运输问题,如产销运输问题、分配运输问题、最短路径
问题、最小费用最大流问题、送货(集货)问题等,并掌握对这些问题进行系统分析、数
学模型建立和优化求解的一些方法,以提高货物运输的科学管理水平。
降低物流成本、提高物流效率,要求对货物运输进行优化组织,即要运用掌握的资源
(人力、物力、财力)合理安排运输任务,消灭对流、迂回、重复等不合理现象,尽量以
最少的资源来完成最多的任务。这就需要对货物运输问题进行系统分析,建立模型,并应
用各种数学方法进行求解,以实现货物运输的科学管理。常见的货物运输问题有产销运输
问题、分配运输问题、最短路径问题、最小费用最大流问题、送货(集货)问题等,下面
就这些问题的优化求解进行介绍。
产销运输问题
销售商在组织某一产品销售时,需要从多个厂家或产地采购,运输到其不同的销售门
店,而每个厂家或产地可提供的产品数量和运价各不相同,如何组织运输才能使总运费最
低?或生产厂家从多个地方采购原料时,各地原料可供数量和运价不同,如何确定各地原
料调拨量,才能使运输费用最省?这就是产销运输问题,根据供求双方的物资数量关系,
可分为产销平衡的运输问题和产销不平衡的运输问题。
产销平衡的运输问题
模型分析
产销平衡的运输问题一般可表述为:某种物资有m个产地A1,A2,...,Am,其供应量分为
a1,a2,...,am;有n 个销地B1,B2,...,Bn,其销量分为b1,b2,...,bn;产地物资供应量总合等于销
地物资销量(需求量)总合;从产地Ai到销地Bj的物资量和单位物资运价为分为xij,cij,求
此时调运物资最佳方案。
对此问题可有下述线性规划模型:
m n
min = ∑∑ xcz ijij
i==11j
ts ..
n
∑ ij = ax i = mi ),...,1(
j=1
()
m
∑= bx jij = nj ),...,1(
i=1
n m
∑∑j = ab i
j==11i
xij ==≥ njmi ),...,1;,...,1(0
表上作业法求解
12-1
上述模型是一种线性规划模型,自然可以用单纯形法求解,但是根据其特殊结构而建
立的表上作业法比起用单纯形法要简单得多。其思路为:由初始运输方案开始,通过检
验、改进,最后获得最优运输方案。
下面结合例12-1具体说明表上作业法的步骤和方法:
例12-1 设有两个煤矿供应三个城市用煤,煤矿A1和A2的日产量分别为a1=200吨;a2=250
吨。三城市(B1,B2,B3)的日销量分别为b1=100吨,b2=150吨,b3=200吨。假定每吨货物的
社会运输费与出行公里线性有关,取cij代表煤矿I至城市j的最短距离。已知c11=90公里,
c12=70公里,c13=100公里,c21=80公里,c22=65 公里,c23=80公里。问如何安排运输使运输
费用最省?
解:设xij为煤矿I运往j的煤量,根据每个煤矿产煤总量和城市的用煤总量,
xij(I=1,2;j=1,2,3)必须满足下列条件:
x11+x12+x13=200
x21+x22+x23=250
x11+x21=100
x12+x22=150
x13+x23=200
目标函数为:minz=90x11+70x12+100x13+80x21+65x22+80x23
列表时要求表内供销平衡,并将运费标入表内空格,如下表12-1所示:
表 12-1 运输平衡表
需 B1 B2 B3 供应量
供
90 70 100
A1 X11 X12 X13 200
80 65 80
A2 X21 X22 X23 250
需求量 100 150 200 450
鉴于最好运输方案是使总运费最小,采用最小元素法,即在平衡表中挑取运价最小或
较小的供需点格子尽量优先分配的调运方法。一行(或一列)满足了,就划去一行(或一
列),如果运费相等时可任选一个,直到全部分配完为止。分配时注意一个问题,即分配
数字的格数要为“行数+列数-1”,若分配完时出现规定数时,应在适当的空格补零,这个
补零的格子在数量上是零,但要当成非零数字格对待。如表12-2所示:
表 12-2 初始调运方案表
需 B1 B2 B3 供应量
供