基于表上作业法的运输问题研究

文/陈子书，桂林理工大学

1 产销平衡问题概述

近年来，现代物流在中国发展迅速。据统计，目前，我国已有20多个省市和50多个经济中心城市制定了物流发展规划。这些地区通过发展现代物流，促进了增长方式的转变，提高了企业和区域经济的竞争力。现代物流在结构调整，产业升级和经济社会发展中发挥着越来越重要的作用[2]。在社会和经济生活中，散装材料从原产地转移到销售地点是一个普遍的问题。特殊企业生产的成品交付需要根据现有的交通网络图和车辆的具体里程调整费。来自不同生产地点的相同材料被转移到各个销售地点，从而使总运输成本最小化并且效率最高。所谓的生产和销售余额意味着在不同生产地点生产的产品与每个销售地点所需的材料总量相同，然后确定从每个原产地到每个销售地点的运费，以确定总运输计划以最小化总成本。这就是产销平衡的问题。

2 问题提出

某公司在三个地方的分厂A1,A2,A3生产同一种产品,需要把产品运送到四个销售点B1,B2,B3,B4去销售。各分厂的产量、各销地的销量和各分厂运往各销地每箱产品的运费(百元)如表1所示。问：问应如何调运,可使得总运输费最小?

表2-1

3 问题分析

3.1 问题描述

图表数据显示销量的总和为1200吨，产量总和为300+400+500=1200吨，,说明了此问题是一个产量等于总销量的运输问题（1200=1200）。该问题一方面要求满足B1、B2、B3、B4四个销售地的供货需求，而另一方面又要考虑A1、A2、A3三个产地的运往销售地的运输费用，此外问题不但要求满足销售地分配要足，与此同时，我们还必须确保最大限度地降低运输成本。这里选择何种分配方案，将涉及不同的运输费用，所以其是一个典型的线性规划问题，同时也是一个总产量等于总销量的产销平衡运输问题。

根据题目已知可以得出以下图论：

图3-1

3.2 产销平衡运输问题模型建立

假设A1、A2、…、Am表示某物品的m个产地，各产地的产量是s1、s2、…、sm； B1、B2、…、Bn表示某物品的n个销地，各销售地销量分别为d1、d2、…、dn；假定从产地Ai（i=1,2，…，m）向销售地Bj（j=1，2，…，n）运价单位物品的运价是cij，问这样调运这些物品才能使运费最少？

设 xij为从产地Ai运往销地Bj的运输量，若各产地产量等于各销地销量之和，即有：

?

?

则得到下列产销平衡运输量问题的模型[3]：

其中，约束条件右侧常数si和dj，约束条件最多有m+n-1个有效，即最多有m+n-1个基可行解。

3.3 求解方法

针对该运输问题，为了方便计算，可设B1、B2、B3和B4四个城市销售量为x11、x12、x13、x14、x21、x22、x23、x24、x31、x32、x33、x34。Cij为从产地Ai（i=1,2，…，m）向销售地Bj（j=1，2，…，n）运价单位物品的运价，xij为从产地Ai（i=1,2，…，m）运往销地Bj（j=1，2，…，n）的运输量。Z即为整个运输过程涉及的运输费用。MinZ则为该运输问题中的最小费用。

3.3.1 线性规划

目标（Theobjective）

最少费用：

3.3.2 表上作业法

步骤一：按某种规则找出一个初始基可行解。规则主要为西北角法与最小元素法。西北角法：西北角法是从西北角（左上角）格开始，在格内的右下角标上允许取得的最大数，然后按行（列）标下一格的数；若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去，如此进行下去，直至得到一个基本可行解的方法；最小元素法：最小元素法是找出运价表中最小的元素，再重复类似于西北角法一样的步骤。本文采用的是最小元素法。

步骤二：对进行解作最有判断，即求个非基变量的检验数，是否均大于等于零，若是，则是最优解；若否，则不是。如果已经是最优解，则停止计算；如果不是最优解，则进行下一步骤。

步骤三：在表上对初始方案进行改进，找出新的基可行解，再按照步骤二进行判别，直至找出最优解。

图3-2[4]

本题表上作业法具体求解如下：

表3-3

步骤一：从表4-3中运费最小（C21=10）的变量开始，给x21尽可能大的数值，A2产地产量等于B1销量（400=400），故在表4-3的（A2，B1）交叉格填上400，由于A2产地产量、B1销地销量已经饱和，故划去表4-3中的A2行与B1列得表4-4。

表3-4

步骤二：从表4-4中找出最小运价为17，故首先考虑此项，由于A1产地产量大于B2销量（300＞250），故可以满足其250吨销量，在表4-3的（A1，B2）交叉格填上250，A1的产量变成50，并划去B 2列，得到表4-5。

表3-5

步骤三：从表4-5中找出最小运价为20，故首先考虑此项，由于A3产地产量大于B3销量（500＞350），故可以满足其350吨销量，故在表2的（A3，B3）交叉格填上350，A3的产量变为150，由于B4销量已经饱和，故划去表4-3中的B3列得表4-6。

表3-6

步骤四：由于A1与A3的产量相加为200吨（50+150=200）,B4的销量为200，故可以两两对应，在表4-3的（A1，B4）交叉格填上50，在表2的（A3，B4）交叉格填上150，由于A1、A2产地产量已经饱和，故划去表4-3中的A1、A3行。

由于此时表中已没有数据可以划去，因此已完成。经以上步骤得到一个总产量等于总销量，且销量全部满足的调配方案。

表3-7

经计算，最小费用为198万元。

3.3.3 R语言求解模型

3.3.3.1 程序脚本

3.3.3.2 运行结果

图3-4

由此可看出运费最少为198万元。

4 结果分析

从计算结果可以得出（以第一个最优解为例），A1分别销往B、B2、B3和B4四个地方销售量为分别为0台、250台、0台、50台；A2分别销往B1、B2、广B3和B4四个地方销售量为别为40 0台、0台、0台、0台；A3分别销往B1、B2、B3和B4四个地方销售量为分别为0台、0台、350台、150台；总费用为198万元。

通过两个求解法最终得出的结果加以比较分析，无论是表上作业法还是R语言求解法，求解出来的结果都是相同的。

5 总结

对于平衡问题，首先建立相关数学模型，再运用表上作业法进行解决。如果是产销不平衡运输问题，应该先将其转化为平衡问题，再运用产销平衡问题的相关解决方法进行分析。供过于求，为使其转化为产销平衡，则需虚拟一销地；若出现供不应求，则需要虚拟一产地，将其转化为产销平衡。

以运筹学中的表上作业法求初始基可行解，位势法对最优解进行判定，闭回路调整法对解进行改进为基础，此方法对实际工作的决策有着重要意义，对以后关于运输相关方案的解决起到借鉴作用。掌握运输问题的模型以及求解方法，这对解决诸多问题有非常大的帮助；如：调拨问题，供销问题，以及合理的造船问题和船舶的调度问题等。我们应加快对运筹学相关知识的研究，更好地发展我国的物流运输领域。