运输问题的求解方法

《运输问题的求解方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第3章运输问题的求解方法物资最佳调运问题是属于线性规划的一种特殊类型——运输问题。它的解法很多，在这一章里将介绍两种求解方法-----------表上作业法和图上作业法。3.1平衡运输问题及数模3.1.1问题的提出社会生产活动川流不息、工农之间、地区之间、各生产企业之间、各企业车间之间，必然产生不间断的，错综复杂的经济联系。这种联系是由交通运输业的货物运输来实现的。无论地区范围内的运输或者工地范围内的运输，在组织运输时，必须选择合理的物资调运方案。选择合理的物资调运方案是运输工作组织中十分重要的问题，特别是当物资的需要特点（收点）及供应地

2、点（发点）较多，而需要的供应数量又各不相同时，如何根据具体条件，各个收发点的分布，交通运输线路的位置及其他条件等，科学地确定最为合理，经济的调运方案，对于充分发挥运输工具的潜力，降低运输成本，保证建设任务的完成有着极为重要的作用。3.1.2平衡运输问题的数模设Ai(1=,2,⋯,m)为出发点，B(1j=,2,⋯,n)为收点，a和b分别表示A和B的ijijij发量和收量，C和x分别表示A到B的单位运费和运量。ijijij则有线性规划模型。mnminfx()=∑∑cijxijij==11nst⋅=∑xijai(1i=,2,?,m)j=1

3、m∑xbij==j(1j,2,?,n)i=1x≥=0(im1,2,??,;j=1,2,,n)ijmn在这里假定∑ai=∑bj，且abij,0≥，cij≥0。满足以上条件的运输问题被称为平衡运ij==11输模型，为了叙述方便起见，采用（T，P）表示。3.1.3（T，P）的特性1．（T，P）的系数矩阵A的秩为mn++1。因为，A的前m行相加的结果等于后n行相加的结果，所以，它的m+n行的行向量是线性相关的，秩不可能超过mn++1。另一方面，我们还可以在A中找到一个m+n-1阶的非奇异方阵，从而可知A的秩只能为mn++1。并由此可推

4、知，（T，P）的每个基本可行解的基变量的个数为mn++1个。2.任一个（T，P）问题至少有一个最优解存在。（1）（T，P）至少有如下的一个可行解：abijx==(im1,2,??,;j=1,2,,n)ijQmn其中，Qa==∑ij∑b。ij==11（2）它的目标函数显然有下界零(非负)。故由（1），（2）知（T，P）必有最优解存在。3.2图上作业法图上作业法是解决（T，P）问题的一个方法，它是在一张运输交通上通过一定步骤的规划和计算来完成物资调运计划的编制工作，以便使物资运行的总吨-----------公里数最小可使物资运费降低，并缩短了

5、运输时间，所以，在一定条件下称这样的方案为最优方案。制定一个物资调运方案时，首先要编制物资平衡表（如表3-1）。在编制物资平衡表时需要做3件事。1.出需要调出物资的地点（即发点）及发量。2.出需要调进物资的地点（即收点）及收量。3.求：总发量=总收量。第二步，根据物资平衡表和收点，发点间的相互位置绘制交通图。所谓交通图就是表明收点和发点间的相互位置以及联结这些点之间的交通线路的简要地图。在交通图上，用圆圈“〇”表示发点，将该发点的发量填入圆圈“〇”内。用方框“□”表示收点，将该收点的收量填入方框“□”内。两点间的距离，记在交通线路的旁边。

6、交通图绘制好后，即可在其上面进行物资调运，找出初始调运方案(初始基可行解)。即第三步，作物资调运流向图。BA我们用箭头“→”表示物资调运的方向即称BAB流向，并规定：流向“→”必须画在沿着线路前A(a)(b)(c)进的右侧。把运送物资的数量记在流向“→”图3-1的旁边并加括号（），以区别于两点之间的距离数。另一方面，为了保持图面的整洁，流向量最好不要通过收，发点以及交叉路口，如图3-1中，(a)，(b)是正确的。图3-2中，AE是正确的。由此可知，当一个交通图成圈时，若运输方向沿逆时针方向，则需将流向“→”画在圈外，称外圈流向；若运输方向

7、是沿顺时针方向，则将流向“→”画在圈内，称为内圈流向。若在图中每个发点吨数全部运完，每个收点所需吨数均已满足，则称此图为流向图。BC在物资运输中，把某种物资从各发点调到各收点的调运方案是很多的，但我们的目的是找出吨—公里数是最小的调运方案。这就要注意在调运中不要发生对物流DA运输和迂回运输，因此，我们在制定流向图时，就要避免它的出现。F（1）对流：所谓对流就是在一段线路上有同一种物图3-2资往返运输（同一（10）B1A2段线路上，两各方向都有流向），如图3-3。20302010101010将某种物资10吨从A1运往B2，同时又有同样A1B

8、2（10）的物资10图3-3（10）B1A1吨同时从20302010101010A运往B，于是在AA之间就出现了对流现象.2112A2B2（10）如果把流向图改成图3-4，即将A的10吨运往B