时间不固定的运输问题的求解研究

李 敏

（湖北文理学院 数学与计算机科学学院，湖北 襄阳 441053）

运输问题可描述为：已知某物资有m个产地Ai，i=1，2，…m，其产量分别为 ai，i=1，2，…m。有 n 个销地 Bj，j=1，2，…n。销量分别为 bj，j=1，2，…n。从 Ai到 Bj的最短时间为 cij，问如何组织调运，才能使完成调运任务的总时间最短?虽然运输问题是线性规划问题，但由于它的特殊结构，并不采用线性规划的单纯形法来求解，一般都是利用表上作业法来求解的，后来人们又陆续提出了各种简易的算法。文章则是在运输时间不固定的情况下，基于简算法及对角线调整法给出了一种能快速找到最优运输方案的新算法。

1 时间不固定的运输问题的数学模型

在上述运输问题的描述中，将从Ai到Bj的最短时间改为fij（xij）=aijxij+cij，其中cij为仅依赖于运输距离长短的基础运输时间，aij为影响系数，xij为产地Ai到销地Bj的运量，在产销平衡条件情况下其数学模型为：

2 时间不固定的运输问题的求解

由于产销不平衡运输问题可以通过添加虚拟的产地或销地而化为产销平衡运输问题，因此下面仅针对平衡运输问题展开叙述。

2.1 算法思想

简算法是求解单目标最短时限的算法，它可求出完成任务的最短时限，但却不一定使时间总和达到最优。在产销平衡条件，本算法的思想为：首先找到完成调运任务的仅依赖于运输距离长短的基础运输时间的最短时限，即min max｛cij|xij＞ ｝

0的最优解T，则C=（cij）中一定存在m+n-1个不大于T的元素，使目标（1）最少。

2.2 算法步骤

Step1找基础运输时间的最短时限。T1=max，其中

Step2将基础运输时间矩阵C中不大于T1的元素全部标出，并记为矩阵 C（T1）。

Step3首先对C（T1）中行和列中大于T1的元素和最大的行或列开始调运，对行（列），如不能将该产地（销地）的产量（销量）按照“先小后大”全部给不大于T1的元素，则转Step4。否则，划去该行（列）所有元素，再对剩余的行和列重复此操作，直至找到关于的最优运输方案，再转Step5。

Step5任取以具有调运量的元素为对角顶点的矩形，检查该对角线上两顶点的aijxij+cij的和，如大于另一对角线上两顶点的aijxij+cij的和，且另一对角线上两顶点中至少有一元素不大于T1，则在保证不给大于T1的元素调运的前提下按实际可调整的量重新调运，否则，保持不变。重复该过程，直至找到最优运输方案。

3 算例

某地区发生地震灾害，发现有2个村庄B1、B2受灾，需从3个城市A1，A2，A3紧急调运救灾物资。已知3个城市可调出的救灾物资量分别为6t、5t和7t；2个村庄的物资需求量分别为7t和8t。已知运输时间函数为fij（xij）=aijxij+cij，其中cij为仅依赖于运输距离长短的基础运输时间（表1），aij为影响系数（表2）。另外，地震造成了A1到B2的道路中断，问如何组织调运才能使救灾物资到达所用总时间最短。

表1 cij和运输物资量

表2 影响系数aij

解 因为总供应量（6+5+7=18）大于总需求量（7+8=15），所以这是一个产销不平衡运输问题，故需要虚拟一个销地B3，且各产地到它的基础运输时间 ci3=0（i=1，2，3）。又因为地震造成了A1到B2的道路中断，所以A1到B2

是禁运的，故将其基础运输时间c12和影响系数a12都更改为∞，则C变为C′。因为B1、B2的需求要全部满足，所以必须优先考虑它们，故由C及Step1得，T1=19。将C′中属于C的且不大于T1的元素做上标记，并记为矩阵C′（T1）：

显然，第5次分配给了大于T1的元素21，故转step4，得T2=21，则有：

经对角线检验，可知已得最优运输方案，总时间Z=113。通过与文献［4］比较发现，本算法所得总时间要少得多，且计算更简单。对于小规模问题可以手工操作，对于大规模问题可编程实现，因此具有较强的可操作性和适用性。

［1］李敏.运筹学基础及应用［M］.武汉：武汉大学出版社，2014.

［2］张劲松.农业运输问题的新算法［J］.安徽农业科学，2009，37（10）：4645-4646.

［3］白国仲.线性不可微规划—基于可持续发展的决策技术［M］.北京：中国社会科学出版社，2007.

［4］董丽，周强，郭淑利.一类产销不平衡最短时限运输问题的求解［J］.2009，22（4）：503-506.