| 中国科学院数学研究所运筹学研究室 |
1959-03-30 00:00 |
卓越的数学方法——合理运输的图上作业法
第7版()
专栏：
卓越的数学方法——合理运输的图上作业法
中国科学院数学研究所运筹学研究室
一个计算方法上的新创造
图上作业法，是我国从事物资调运工作的干部（首先是经济委员会及粮食部负责这方面工作的同志），在解决合理运输问题的实际工作中创造出来的一个卓越的数学方法。我们所以说它是卓越的，首先是因为它可以得到物资调运中运行的吨公里最少的方案，为国家节约了大量的运力和资金。例如，粮食部应用这个方法修定了1957年的流向，调整了一百五十余万吨粮食的运输路线，按每吨粮食少运十公里计算（这是很低的估计），那末，节约的运输力就大致相当于用一辆运货汽车绕地球运行一百圈。其次，这个图上作业法，对数学中线性规划这一分支的理论，突破了它的传统的代数运算方法（这种运算方法往往涉及上百个未知数的计算），而采取了纯粹利用图形的关系来解决问题。它的数学表现形式也很完美和具有独特的风格。第三，这个方法另一突出的优点，是既简单又明确，并且计算非常迅速，易于为一般干部所掌握。应用这种方法，常常是用几小时的时间就可以完成一个全国的某一粮食品种的调运方案。如果要用传统的方法，由于计算繁复常常需要几天的时间，因而不易推广。图上作业法是把内容复杂的数学问题用通俗化、大众化的形式加以解决的一个范例。
为什么物资调运中有不合理现象
在物资调运中，产生的不合理的运输现象，首先是对流运输。例如，有某一品种的煤50吨自唐山运往北京，而同时又有同一品种的煤80吨自大同运往天津。这样，在京、津间就产生了对流运输。要避免这种对流运输的现象是不难的，只要在编制调运方案时，把唐山的50吨煤运往天津，把大同的80吨煤运给北京50吨，运给天津30吨即可。
是否没有对流的调运方案一定就合理呢？事实告诉我们，假如产生迂回运输情况也是不合理的。例如，某月份张家口、石家庄各运出小麦分别为50吨、100吨，而太原、丰台又分别各需要50吨、100吨，这就可以有两种不同的调运方案，见图一图二
〔注：图中的圈表示发点，×表示收点，箭头表示小麦前进方向。画在沿着铁路线前进方向的右侧，我们称它为流向。收点和发点旁注的数字，是小麦调入和发出的吨数，流向线右旁注的数字是沿此方向运输小麦的吨数，左旁注的是收发点间距离。〕
从这两个调运图表可以看出，它们都没有对流的不合理现象。但是，只要我们计算一下就可以知道，图一所表示的调运方案，需要的运行吨公里数是53250，而图二所表示的调运方案，仅需要吨公里33800。因此很显然，图一所表示的调运方法是不合理的，因为它有迂回运输的现象。而第二图就没有这个缺点。图上作业法，就是我国从事物资调运工作的干部，针对避免迂回运输这一实际需要而逐渐摸索创造出来的。下面我们就来介绍这个方法。
图上作业法简要介绍
合理运输的图上作业法的第一步，是平衡工作，就是使各发点发出的物资总吨数，等于各收点需要的总吨数。第二步，是根据经验初步绘出一个流向图。见图三
如果这张流向图上有对流，我们就可以很容易地按着前面介绍的方法来调整。但现在我们的流向图上并没有对流，而是要检查一下有无迂回现象。检查的方法是这样的：对于每一个铁路环状线（简单的称之为“圈”）含在圈内的流向线（称之为内圈流向线）总长和含在圈外的流向线（简称外圈流向线）总长加以计算，如果这两个总长都小于或等于整个圈长的一半，那末，这个调运方案就一定是合理的，否则，它就不是合理的。我们把上面的图例计算一下就可以知道，这个图的外圈流向线总长是715公里，大于整个圈长的（1381公里）的一半，因此，这个调运方案不是合理的。这是第一步。
我们怎样使这个不合理的调运方案成为合理的呢？方法是缩短外圈流向线，延长内圈流向线。我们在重新绘制第二个图表时，就可以在外圈诸流向线中涂去物资通过的数量最小的数字，如涂去郑州到兰封和衡水到邯郸间运输量各为20吨的流向。然后，把其余外圈流向线运量各减20吨，再把内圈诸流向相应地延长，并作适当的改变，使之保持产销平衡。见图四
我们把新的流向图再计算一下，图的外圈流向线总长为317公里，内圈流向线总长为666公里，都小于整个圈长的一半。这个新调运方案就是最好的，也就是运行的吨公里数最小的调运方案。如果我们经过改变后新流向图的外圈流向线总长仍大于整个圈长的一半，我们就应当再按以上的方法，缩短外圈来进行调整。
此中道理在哪里呢？这两个调运方案之所不同，就在于旧方案中，邯郸所需的30吨物资中有20吨物资是由衡水供应，10吨由郑州供应，其运行的吨公里数有8180吨公里；而在新方案中变成全由郑州供应，其运行的吨公里数为7560吨公里。旧方案中兰封所需的20吨本是由郑州供应，运行的吨公里数是2300；而新方案中把它变成由徐州供应，其吨公里数就是4680。此外，济南所需要的30吨，原来全部由徐州供应，其运行的吨公里数为9510；而在新方案中就变为由徐州供应10吨，由衡水供应20吨，其运行的吨公里数则为6770。
我们仔细地观察一下就会发现，新流向图中的内圈诸流向线与旧流向图中的外圈诸流向线凑在一起，恰好充满整个图圈，而且没有重复。因此，既然旧流向图外圈诸流向线总长大于整个圈长的一半，那末新流向图内圈诸流向线总长必小于整个圈长的一半，也就是它小于旧流向图外圈诸流向线的总长。这就使新调运方案较旧调运方案花费的吨公里数要少。
在编制调运方案时，往往联结各收发点的铁路线不只构成一个环状线，而构成几个环状线。例如京、津、德、石，京、津、徐、郑，德、石、郑、徐就有三个圈。判定几个圈的调运方案是否合理的标准是，要从它的每一个圈来说，每个圈的内外圈流向线总长，都应当小于或等于整个圈长的一半。如果在检查时发现某一个圈不符合判定标准，就对这个圈用缩外圈或缩内圈的方法来进行调整，使运输的吨公里数减少。
到这里，人们会提出这样的疑问：是否会有这样的现象：尽管缩短外圈流向线或内圈流向线，它始终不会达到内外圈流向线都小于或等于全长的一半呢？是否会有两个运行吨公里数不同的调运方案，他们都是内外圈流向线总长都小于或等于全长的一半呢？我们的答复是这种现象不会有的。道理就是使其内外圈流向线总长都小于或等于全圈的一半的流向图，其吨公里数都是相同的。
图上作业法优于传统计算法
在这里，我们谈一谈图上作业法的价值，把它与线性规划传统方法作个比较。用传统的方法来制定调运方案，是把一切产地到一切销地都假定为一个未知数，来表示它们间的运输量；如果有10个产地20个销地，就共有10×20＝200个未知数。每一个产地、销地根据产销平衡条件，都要列出一个方程，这就需要列出10＋20＝30个关于产销量平衡的方程式。这比图上作业法麻烦得多。其主要原因是，传统的方法，要考虑所有产地到所有销地的各种调运情况，而其中有很多产、销地实际上是不必发生调运关系的。图上作业法就是从线路图形出发，有几个产销地，就划几个产销地，避免了大量不必要的因素，因此，在方法上，显得格外简便、准确。这一突出的优点，是图上作业法比传统方法简单得多（几倍到十几倍）的根本原因，也就是图上作业法在数学上的重大贡献。
一切科学的目的，都是为了寻求事物的规律，并尽量使其结果简化而准确。简化和精练正是图上作业法的特点。这也就说明它在数学上更进一步成熟和达到了更高的水平。不仅如此，正因为它能非常迅速和准确地解决问题，在许多场合就与传统性方法有着根本的差别。如这两种方法同样用于汽车调度上，结果是因为传统性方法计算繁复，甚至不能应用；而图上作业法，就能很好地选出最好的调度方案。应用图上作业法，我们曾在北京市马公庄车场成功的进行过调车的试验，它不仅使得载重里程增多，而且还减少了空驶里程。
随着我国社会主义建设事业的日益发展，随着交通运输事业的发展，图上作业法也会更加丰富和完善。现在，应用这种方法，在改善交通和粮食调运方面已取得了许多成绩，我们应当继续在实际中运用这种方法，并使其同传统的数学方法结合起来，逐步在全国范围内推广，这对我国社会主义建设具有极大的经济意义。（附图片） |
|