第4篇 数学方法在物流运输中的应用 第12章 货物运输的优化求解.docVIP

第 4 篇 数学方法在物流运输中的应用 第12章 货物运输的优化求解 本章学习目的：了解常见货物运输问题，如产销运输问题、分配运输问题、最短路径问题、最小费用最大流问题、送货（集货）问题等，并掌握对这些问题进行系统分析、数学模型建立和优化求解的一些方法，以提高货物运输的科学管理水平。 降低物流成本、提高物流效率，要求对货物运输进行优化组织，即要运用掌握的资源（人力、物力、财力）合理安排运输任务，消灭对流、迂回、重复等不合理现象，尽量以最少的资源来完成最多的任务。这就需要对货物运输问题进行系统分析，建立模型，并应用各种数学方法进行求解，以实现货物运输的科学管理。常见的货物运输问题有产销运输问题、分配运输问题、最短路径问题、最小费用最大流问题、送货（集货）问题等，下面就这些问题的优化求解进行介绍。 12.1 产销运输问题 销售商在组??某一产品销售时，需要从多个厂家或产地采购，运输到其不同的销售门店，而每个厂家或产地可提供的产品数量和运价各不相同，如何组织运输才能使总运费最低？或生产厂家从多个地方采购原料时，各地原料可供数量和运价不同，如何确定各地原料调拨量，才能使运输费用最省？这就是产销运输问题，根据供求双方的物资数量关系，可分为产销平衡的运输问题和产销不平衡的运输问题。 12.1.1 产销平衡的运输问题 12.1.1.1 模型分析 产销平衡的运输问题一般可表述为：某种物资有m个产地A1，A2,...,Am，其供应量分为a1,a2,...,am;有n 个销地B1,B2,...,Bn,其销量分为b1,b2,...,bn;产地物资供应量总合等于销地物资销量（需求量）总合；从产地Ai到销地Bj的物资量和单位物资运价为分为xij,cij,求此时调运物资最佳方案。 对此问题可有下述线性规划模型： mnminz=cx∑∑ijiji=1j=1s.t.nx=a(i=1,...,m)∑ijij=1 （12.1） mx=b(j=1,...,n)∑ijji=1nmb=a∑j∑ij=1i=1x≥0(i=1,...,m;j=1,...,n)ij12.1.1.2 表上作业法求解 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+80x231.列运输平衡表 列表时要求表内供销平衡，并将运费标入表内空格，如下表12-1所示： 表 12-1 运输平衡表 需 B1B2B3供应量 供 90 70 100A1X11X12 X13200 80 65 80 A2X21X22 X23250 需求量 100 150 200 450 2.建立初始调运方案 鉴于最好运输方案是使总运费最小，采用最小元素法，即在平衡表中挑取运价最小或较小的供需点格子尽量优先分配的调运方法。一行（或一列）满足了，就划去一行（或一列），如果运费相等时可任选一个，直到全部分配完为止。分配时注意一个问题，即分配数字的格数要为“行数+列数-1”，若分配完时出现规定数时，应在适当的空格补零，这个补零的格子在数量上是零，但要当成非零数字格对待。如表12-2所示： 表 12-2 初始调运方案表 需 B1B2B3供应量 供 90 70 100A10 200 200 80 65 80 12-2 A2100 150 250 需求量 100 150 200 450 表12-2先从A2,B2（c22最小）开始，确定c22=150,划去余下的B2 列，然后确定x21=100(c21为剩下方格中最小运价)，划去余下的B1列，A2的供应量