产销平衡问题的运输规划

子任务3.1　产销平衡问题的运输规划

3.1.1　任务引入

【任务3-1】　某煤炭集团有A₁，A₂，A₃3个煤矿，下属的煤炭物流公司每天要把生产的煤炭运往B₁，B₂，B₃，B₄4个地区。各地区煤炭的产量、各地区的销量（百t/天）以及各厂矿间的运价（百元/百吨）如表3-1所示。问如何组织调运才能使总运费最少？

表3-1

3.1.2　任务分析

运输规划是一类特殊的线性规划问题，它最早是从物资调运中产生的。但以后有些其他问题的模型也归结为运输问题。虽然运输问题也是线性规划问题，可以用单纯形法解决，但考虑到运输问题数学模型的特点，人们提出了更简单的求解方法——表上作业法。目前运输规划已成为现代物流管理中一项最基本也最重要的功能。

本项目的运输问题就是研究把某种商品从若干个产地运至若干个销售地而使总运费最小的一类问题。然而更广义地讲，运输问题是具有一定模型特征的线性规划问题。它不仅可以用来求解商品的调运问题，还可以解决诸多非商品的调运问题。运输问题是一种特殊的线性规划问题，由于其技术系数矩阵具有特殊的结构，这就有可能找到比一般单纯形法更简便高效的求解方法，用列表的方法求解线性规划问题中运输模型的计算方法，是指线性规划一种求解方法。当某些线性规划问题采用图上作业法难以进行直观求解时，就可以将各元素列成相关表，作为初始方案，然后采用检验数来验证这个方案，否则就要采用闭回路法、位势法或矩形法等方法进行调整，直至得到满意的结果。这种列表求解方法就是表上作业法。这正是单独研究运输问题的目的所在。

3.1.3　知识建构

1）运输问题概述

运输是物流系统中最直观的功能要素之一，也是物流的最基本功能。它可以克服空间距离上的障碍，通过一定时间内商品的空间位移，使商品产生价值增量。

（1）运输的地位

①运输是物流的主要功能要素之一。根据物流的概念，物流是“物”的物理性运动，这种运动不但改变了物的时间状态，也改变了物的空间状态。而运输承担了改变空间状态的主要任务，运输是改变空间状态的主要手段，运输再配以搬运、配送等活动，就能圆满完成改变空间状态的全部任务。在现代物流观念未诞生之前，甚至就在今天，仍有不少人将运输等同于物流，其原因是物流中很大一部分责任是由运输担任的，它是物流的主要部分。

②运输是社会物质生产的必要条件之一。运输是国民经济的基础和先行。马克思将运输称之为“第四个物质生产部门”，是将运输看成是生产过程的继续，这个继续虽然以生产过程为前提，但如果没有这个继续，生产过程便不能最后完成。所以，虽然运输这种生产活动和一般生产活动不同，它不创造新的物质产品，不增加社会产品数量，不赋予产品以新的使用价值，而只变动其所在的空间位置，但这一变动则使生产能继续下去，使社会再生产不断推进，所以将其看成是一种物质生产部门。

③运输可以创造“场所效用”。场所效用的含义是：同种“物”由于空间场所不同，其使用价值的实现程度则不同，其效益的实现也不同。由于改变场所而最大限度发挥使用价值，最大限度提高产出投入比，这就称之为“场所效用”。通过运输，将“物”运到场所效用最高的地方，就能发挥“物”的潜力，实现资源的优化配置。从这个意义上讲，也相当于通过运输提高了物的使用价值。

④运输是“第三个利润源”的主要源泉。首先，运输是运动中的活动，它和静止的保管不同，要靠大量的动力消耗才能实现这一活动，而运输又承担大跨度空间转移之任务，所以活动的时间长、距离长、消耗也大。消耗的绝对数量越大，其节约的潜力也就越大。其次，从运费来看，运费在全部物流费用中占最高的比例，一般综合分析计算社会物流费用，运输费在其中占接近50%的比例，有些产品运费高于产品的生产费用，所以节约的潜力是较大的。此外，由于运输总里程长，运输总量大，通过体制改革和运输合理化可大大缩短运输吨公里数，从而获得较大节约。

（2）物流运输

运输需求可以通过3种基本方式实现。第一，可以使用私营的车队设备；第二，与专业运输公司签订运输合同；第三，一个企业可以向各种提供以单独装运为条件的运输承运人预订服务。这3种形式的运输就是典型的私人运输、合同运输和公共运输。

从物流系统的观点来看，有3个因素对运输来讲是十分重要的，即成本、速度和一致性。

运输成本是指为两个地理位置间的运输所支付的款项以及与行政管理和维持运输中的存货有关的费用。物流系统的设计应该利用能把系统总成本降到最低程度的运输，这意味着最低费用的运输并不总是导致最低的运输总成本。

运输速度是指完成特定运输所需的时间。运输速度和成本的关系，主要表现在以下两个方面：首先，能够提供更快速服务的运输商往往要收取更高的运费；其次，运输服务越快，运输中的存货越少，无法利用的运输间隔时间就越短。因此，在选择期望的运输方式时，至关重要的问题就是如何平衡运输服务的速度和成本。

运输的一致性是指在若干次装运中履行某一特定的运次所需的时间与原定时间的一致性。它是运输可靠性的反映。多年来，运输经营人已把一致性看作是高质量运输的最重要特征。如果给定的一项运输服务第一次花费2天、第二次花费了6天，这种意想不到的变化就会产生严重的物流作业问题。运输一致性会影响买卖双方承担的存货义务和有关风险，如果运输缺乏一致性，就需要安全储备存货，以防预料不到的服务故障。

在物流系统的设计中，必须精确地维持运输成本和服务质量之间的平衡。在某些情况下，低成本和慢运输将是令人满意的，而在另外一些情况下，快速服务也许是实现作业目标的关键所在。发掘并管理所期望的低成本、高质量的运输，是物流的一项最基本的责任。

2）运输规划模型

（1）一般表达式

一般地，设某种物资有m个产地（用A₁，A₂，A₃，…，A_m表示），n个销地（用B₁，B₂，B₃，…，B_n表示），第A_i个产地的产量为a_i，第B_j个销地的销量为b_j，把物资从产地A_i运到销地B_j的单位运价为C_ij　（i=1，2，…，m，j=1，2，…，n）。假定产销平衡。这些数据可汇总于产销平衡表（表3-2）和单位运价表（表3-3）中。有时也把这两表合一（表3-4）。

表3-2　产销平衡表

表3-3　单位运价表

表3-4　产销平衡表和单位运价表

设x_ij表示从A_i调运到B_j的物资数（i=1，2，…，m；j=1，2，…，n），则可建立如下数学模型。

一般表达式：

其中

（2）表式运输模型

由于运输问题模型的特殊性，还有如表3-5所示模型。

表3-5　表式运输模型

在表3-5中，A_i所在行和B_j所在列对应的表格中，右上角填的是从A_i到B_j的资源的单位运价，左下角填的是从A_i到B_j的运量。产销平衡的运输问题的解法——表上作业法就是在表3-5中进行的。

（3）运输问题的相关概念及定理

①闭回路的概念。为了给出运输问题的性质以及表上作业法解的判定和解的调整，先介绍一个重要的概念——闭回路。

定义：若运输问题的2r（r≥2）个变量可以排成：

x_i1j1x_i1j2x_i2j2x_i2j3…x_irjrx_irj1　　（i₁，i₂，…，i_r两两不同，j₁，j₂，…，j_r两两不同）

则称以此2r个变量为顶点构成了一条闭回路。

例如：

a.e式闭回路　x₁₁，x₁₂，x₃₂，x₃₁，见表3-6。

表3-6　e式闭回路

b.f式闭回路　x₂₁，x₂₄，x₁₄，x₁₂，x₃₂，x₃₁，见表3-7。

c.g式闭回路　x₁₁，x₁₂，x₂₂，x₂₄，x₃₄，x₃₁，见表3-8。

表3-7　f式闭回路

表3-8　g式闭回路

由上述3个例子可以看出，闭回路的几何特征有：

a.闭回路上任一点均为拐角点；

b.每条边均为水平或垂直；

c.一行（列）若有闭回路的顶点，有且只有两个顶点。

②运输问题若干定理。

定理1　在产销平衡的运输问题中，m+n个约束条件中独立的只有m+n-1个。即有一个约束是多余的。

定理2　运输问题中变量x_i1j1，x_i2j2，…，x_irjr对应的系数列向量组是线性无关的充要条件是它们不含闭回路。

定理3　运输问题中m+n-1个变量x_i1j1，x_i2j2，…，x_irjr（r=m+n-1）是基变量的充要条件是它们不包含闭回路。

定理4　产销平衡的运输问题必有最优解。以上定理证明略。

3.1.4　任务实施

步骤一　建立模型

目标函数为：

min S=6x₁₁+3x₁₂+2x₁₃+5x₁₄+7x₂₁+5x₂₂+8x₂₃+4x₂₄+3x₃₁+2x₃₂+9x₃₃+7x₃₄

满足产地产量的约束条件为：

x₁₁+x₁₂+x₁₃+x₁₄=5

x₂₁+x₂₂+x₂₃+x₂₄=2

x₃₁+x₃₂+x₃₃+x₃₄=3

满足销地销量的约束条件为：

x₁₁+x₂₁+x₃₁=2

x₁₂+x₂₂+x₃₂=3

x₁₂+x₂₃+x₃₃=1

x₁₄+x₂₄+x₃₄=4

所以，此运输问题的线性规划模型如下：

min S=6x₁₁+3x₁₂+2x₁₃+5x₁₄+7x₂₁+5x₂₂+8x₂₃+4x₂₄+3x₃₁+2x₃₂+9x₃₃+7x₃₄

运输问题模型是线性规划诸多模型中较早引起人们关注的一类特殊模型。由于这类模型在结构上有其特殊性，我们可以用比单纯形法更为简便的算法——表上作业法来求解。此算法不仅适用于运输问题本身，还适用于其他相当多的应用问题，因此得到人们的高度重视和广泛应用。

步骤二　用表上作业法进行运输规划

运输规划问题求解时，主要涉及产销平衡与产销不平衡两种情况，因为产销不平衡问题可以通过虚设收发点的方式将其转化为产销平衡的运输问题。因此我们着重介绍产销平衡运输问题的求解方法。

运输问题一般采用表上作业法来进行求解。表上作业法的基本思想与单纯形法十分类似。它需要先找出一个基本可行解，称为初始方案；然后按一定准则来检验这个方案是否最优；如果不是，则按一定方法加以调整、改进，直到求出最优解为止。因此，表上作业法可分为3个基本步骤：确定初始方案；进行最优性检验；调整、改进非最优方案。

（1）初始方案的确定

由前面知识构建中的定理可知，产销平衡运输问题必存在最优解，进而存在基本可行解、基本最优解。而基本可行解包含的基变量的个数为m+n-1，且不包含闭回路，所以在形如表3-5的表格中，要选出不含闭回路的m+n-1个格安排运量，作为基变量，即初始方案。

确定初始方案的方法较多，有左上角法（又称西北角法或阶梯法）、最小元素法、最大差额法（又称Vogel法）等，下面我们分别介绍。

①用左上角法实施确定初始方案任务。

左上角法的思想是：先给作业表中左上角那格安排运量，然后划去该格所在的行或列；重复进行，直到求出初始方案为止。具体步骤为：

a.从运输表中左上角点（1，1）开始，先选x₁₁为基变量，并令x₁₁=min｛a₁，b₁｝，将x₁₁的值填写在产销平衡表中，并将a₁，b₁均减去x₁₁；

b.若a₁-x₁₁=0，则划去a₁所在行，否则，划去b₁所在列；

c.然后在运输表余下表格中选取左上角上的点，重复上述步骤，直到最后必选取x_mn为基变量，这时同时划去最后一行和最后一列。

这些被选取的基变量在运输表中的每一行每一列至少有一个，其个数恰好有m+n-1个，并且不出现闭回路，它们正好构成了一个基本可行解。

下面以任务3-1来说明此方法。

列出产销平衡表，见表3-9。

表3-9　产销平衡表

a.因为左上角为（1，1）格，所以取x₁₁=min｛5，2｝=2，填入表中，表明从产地A₁调运到销地B₁2个单位的物资。同时，因B₁已经不需要物资了，故划去第一列，修改a₁的值，a′1=5-2=3，表示还可以从A₁调运3个单位的物资到销地，结果见表3-10。

表3-10

b.在余下的方格中，左上角为（1，2）格，取x₁₂=min｛3，3｝= 3，于是划去第一行，修改b₂的值，b′=3-3=0，结果见表3-11。

表3-11

c.在余下的方格中，左上角为（2，2），取x₂₂=min｛0，2｝=0。虽然x₂₂=0，但表示x₂₂为基变量。划去第二列，修改a₂的值，a′2=2-0=2，结果见表3-12。

表3-12

d.左上角为（2，3）格，取x₂₃=min｛1，2｝=1，于是划去第三列，修改a₂的值，a′2=2-1=1，结果见表3-13。

表3-13

e.左上角为（2，4）格，取x₂₄=min｛4，1｝=1，于是划去第二行，修改b₄的值，b₄′=4-1=3，结果见表3-14。

表3-14

f.此时，仅余下（3，4）格，取x₃₄=min｛3，3｝=3，划去第三行，第四列。这时所有方格都已划去，并依次确定了m+n-1=6个变量为基变量，结果见表3-15。

表3-15

在表3-15中，填数字的格就是用左上角法确定的初始基本可行解的基变量的取值。

x₁₁=2，x₁₂=3，x₂₂=0，x₂₃=1，x₂₄=1，x₃₄=3

其余空格处为非基变量，隐含着取值为0，其对应的目标函数值为S=54。

实际上，上述过程可以放在一个表格中，见表3-16。

表3-16

表3-16中右侧和下面的数字表示的是步骤序号。

为了对该方案进行检验，一般将表3-16中的结果填入表3-17。

表3-17

②用最小元素法实施确定初始方案任务。

所谓“最小元素”，是指运价表中最小运价c_ij。该法的基本思想是“运价小者优先供应”，即先给运价表中最小运价那格安排运量，然后划去该运价所在行或列；接下去继续这样做，每次总在表中剩余运价的最小元素那格确定运量，直到求出初始方案为止。

仍就任务3-1具体说明该法的实现过程，先画出产销平衡和运价表，见表3-18。

表3-18　产销平衡及运价表

然后在表上进行作业，确定初始基本可行解。由线性规划的理论知道，基本可行解的非基变量取值为零，因此，只需确定基变量x_ij及其数值，过程如下：

a.从表3-18中选出数值最小的c_ij，并将它所对应的变量x_ij作为第一个基变量。若有几个c_ij同时最小，则可从中任选一个。在表3-18中，c₁₃=c₃₂=2是最小元素，所以可任选其一，比如选c₁₃，则确定x₁₃为第一个基变量。x₁₃的值表示A₁矿的产量到B₃地区的销量，为了满足约束条件，应取x₁₃=min｛a₁，b₃｝=min｛5，1｝=1，把1填入表3-19的x₁₃格内，这样B₃地区的销量已经满足，因此不再需要往B₃调运煤炭，故将B₃所在列的运价和销量划去，表示B₃列的其余变量x₂₃，x₃₃只能取0值，即都为非基变量。同时，由于A₁的煤炭已经运出1个单位，只剩下4个单位，所以将a₁由5变为5-1=4。结果如表3-19所示。

表3-19

b.在表3-19的剩余运价中，c₃₂=2最小，于是又确定x₃₂为基变量，取x₃₂=min｛a₃，b₂｝=min｛3，3｝=3，在x₃₂的空格中填写3。此时，a₃=b₂=3，在这种情况下，可以把第三行其余变量都取0值，定为非基变量，也可把第二列其余变量都取0值，定为非基变量。现在把第三行的其余变量都定为非基变量，为此划去第三行，同时，b₂处由3变为0（注意：虽然b₂变为0，但表示B₂列还要填基变量），结果如表3-20。

表3-20

c.在表3-20的剩余的运价中，c₁₂=3最小，故又确定x₁₂为基变量。因x₁₂=min｛4，0｝=0，故在x₁₂处填写0（虽然x₁₂=0，但必须把其填入到表格中，表示x₁₂也是基变量，只不过取值为0），此时，第二列已经满足，所以划去第二列的运价与销量，得表3-21。

表3-21

d.类似地，取x₂₄=min｛2，4｝=2，划去第二行，b₄由4变为4-2=2，见表3-22。

表3-22

e.取x₁₄=min｛4，2｝=2，划去第四列，同时，b₄由4变为4-2=2，见表3-23。

表3-23

f.取最后一个x₁₁=2，划去第一行，第一列，见表3-24。

至此，作业表中x_ij的数值全部确定，表3-24中黑体数字就是用最小元素法确定的初始基本可行解的基变量值。

x₁₁=2，x₁₂=0，x₁₃=1，x₁₄=2，x₂₄=2，x₃₂=3

其余x_ij=0（空格），为初始基本可行解的非基变量。其对应的目标函数值为S=38。

表3-24

上述过程可总结为以下步骤：

①在单位运价表中找出最小元素c_ij，令x_ij=min｛a_i，b_j｝。

②将x_ij的值填写在产销平衡表中，并将a_i，b_j均减去x_ij。

③若a_i-x_ij=0，则在单位运价表中划去A_i对应的第i行；否则，划去B_j所在列。

④在单位运价表中未划去的部分，重复上述步骤。

可以证明，最小元素法确定的方案肯定不会构成闭回路，因此，它必可作为表上作业法的初始方案。事实上，上述过程可以综合到一个表中，具体过程如下：

先列出问题的产销平衡表和单位运价表，见表3-25。

表3-25

在表3-25中：

①因c₁₃=min｛c_ij｝=2，故x₁₃=min｛5，1｝= 1，所以将x₁₃的值填入表3-26中，并且将B₃所在列的运价划去，a₁变为4；

②在未划去的地方，因c₃₂=min｛c_ij｝=2，故x₃₂=min｛3，3｝=3，所以将x₃₂的值填入表3-26中，并且将A₃所在行的运价划去，b₂变为0；

以下步骤同上。表3-25中右侧的数字以及在纵线下面的数字表示第几步。

表3-26

③用Vogel法实施确定初始方案任务

该法的计算步骤如下：

a.对每行每列的运价c_ij分别计算两最小元素之差（取正值），将“行差”记于表右侧，“列差”记于表下端。

b.在所有行差、列差中选一最大差额，若有几个同时最大，则可任选其一。

c.在最大差值所在行（列）中选一最小运价，若有几个同时最小，则可任选其一确定供需关系和供应数量，然后划去其所在行（列），方法同最小元素法。

d.重复上述步骤，但当只剩下最后一行（列）时，不再计算行差（列差），而直接按最小元素法分配运量，并划去相应的行（列）。

下面仍就任务3-1加以具体说明。按作业表分别计算行差、列差得表3-27。

表3-27

续表

从表3-27中可知，最大差额为6，它位于第三列，该列的最小运价c₁₃=2，给它所在格内填写运量x₁₃=1，然后划去第三列，重新计算行差（列差没变），见表3-28。

表3-28

由表3-28知，最大差额为3，位于第一列，该列最小运价为c₃₁=3，在（3，1）处填写运量2，划去第一列，见表3-29。

表3-29

续表

继续下去，过程见表3-30和表3-31。

表3-30

表3-31

续表

在表3-31中，只剩下最后一列（第四列），故此时不再计算行差、列差，而直接按最小元素法分配运量x₂₄=2，划去第二行；再分配x₁₄=2，于是得到一个初始方案，见表3-32。

表3-32

表3-32中填数字的格代表初始基本可行解的6个基变量的取值：

x₁₂=2，x₁₃=1，x₁₄=2，x₂₄=2，x₃₁=2，x₃₂=1

其余x_ij=0，为非基变量，该方案对应的目标函数值S=34。

步骤三　求出检验数，判别方案是否最优

确定初始方案后，就要对它进行最优性检验，即检验初始基本可行解对应的目标值是否达到最优。在表上作业法中，计算检验数的方法有：闭回路法、位势法等。下面分别介绍这两种方法。

①用闭回路法实施检验任务。

前面我们已经知道：所谓的闭回路，是指在已给定调运方案的运输表上从一个代表非基变量的空格出发，沿水平或垂直方向前进，只有遇到代表基变量的填入数字的格才能向左或右旋转90°（当然也可以不改变方向）继续前进，这样继续下去，直到回到出发的那个空格。

可以证明：每一空格均对应唯一的一条闭回路，其中闭回路上除空格外其余拐角点均为基变量。

所谓闭回路法，就是在代表非基变量的空格（其调运量为零）对应的闭回路上作运量的调整，首先在此空格处运量加上1，其次在闭回路的顶点上依次减1，加1，减1，……，最后我们计算出由于这些变化给整个运输方案的总运费带来的变化。例如，以表3-26中非基变量x₂₁的格子为始点的闭回路（见表3-33）来说明。

表3-33

空格x₂₁对应的闭回路为：x₂₁→x₂₄→x₁₄→x₁₁，现在把x₂₁的调运量从0增加为1，运费增加了7，为了A₂的产量平衡，x₂₄就减少了1，运费减少了4；为了B₄的销量平衡，x₁₄就增加1，运费增加了5；为了A₁的产量平衡，x₁₁就减少了1，运费就减少了6。这样调整之后，运费就增加了7-4+5-6=2。这说明x₂₁为非基变量，取值为零是对的。如果让x₂₁变为基变量，则运费要增加，这是我们把运费的改变值作为x₂₁的检验数。如果某一个空格按上述算法求出的检验数为负值，则说明此方案不是最优方案。一般地，设空格x_ij对应闭回路的顶点为x_ij，x_ij1，x_i1j1，x_i1j2，…，x_itjt，x_itj，则其检验数λ_ij=c_ij-c_ij1+c_i1j1-c_i1j2+…+c_itjt-c_itj。

如果将x_ij，x_ij1，x_i1j1，x_i1j2，…，x_itjt，x_itj中的顶点依次称为第一顶点，第二顶点，第三顶点，……，那么，检验数实际就是奇数顶点运价之和减去偶数顶点运价之和。如果每个非基变量的检验数λ_ij≥0，则该方案为最优方案。

这样，我们找出表3-26中所有空格的检验数，结果见表3-34。

表3-34

将所有空格的检验数也填入表3-33中，为了与基变量区分开，我们将检验数用括号括起来，见表3-35。

表3-35

由于λ₃₁=-2，所以，此方案不是最优方案，需要调整。

用闭回路法求检验数，需要给每一个空格找一条闭回路，当产销点很多时，这种计算步骤繁杂。下面介绍一种较为简单的方法——位势法。

②用位势法实施检验任务。

对一切i，j有x_ij（c_ij-u_i-v_j）=0因此，在m+n-1个基变量｛x_ij｝处，应有

在非基变量处，应有

首先，在基变量处，u_i+v_j=c_ij等价于求m+n-1个方程、m+n个未知数的线性方程组的解。我们只要让其中的一个变量为自由未知变量，就可求出所有的u_i和v_j的值。其次，在非基变量处，我们可以计算出λ_ij=c_ij-u_i-v_j的值。由松弛互补定理可知，解x_ij是最优解的充分必要条件为λ_ij≥0（见式3-3）。因此，我们将λ_ij=c_ij-u_i-v_j定义为所有变量x_ij的检验数。

由式3-3知，基变量对应的检验数显然全为0，因此，只需计算非基变量的检验数即可。这种计算检验数的方法就是位势法。

下面我们仍以任务3-1中最小元素法求出的初始方案（见表3-36）为例说明求解过程。

表3-36

我们先给u₁赋个任意值c，即令u₁=c，在基变量处x_ij，有u_i+v_j=c_ij，即：

在x₁₁处，有u₁+v₁=c₁₁，即c+v₁=6，求出v₁=6-c；

在x₁₂处，有u₁+v₂=c₁₂，即c+v₂=3，求出v₂=3-c；

在x₁₃处，有u₁+v₃=c₁₃，即c+v₃=2，求出v₃=2-c；

在x₁₄处，有u₁+v₄=c₁₄，即c+v₄=5，求出v₄=5-c；

在x₂₄处，有u₂+v₄=c₂₄，即u₂+5-c=4，求出u₂=-1+c；

在x₃₂处，有u₃+v₂=c₃₂，即u₃+3-c=2，求出u₃=-1+c。

利用u₁，u₂，u₃，v₁，v₂，v₃，v₄的值，再计算非基变量的检验数：

λ₂₁=c₂₁-u₂-v₁=7-（-1+c）-（6-c）=2；

λ₂₂=c₂₂-u₂-v₂=5-（-1+c）-（3-c）=3；

λ₂₃=c₂₃-u₂-v₃=8-（-1+c）-（2-c）=7；

λ₃₁=c₃₁-u₃-v₁=3-（-1+c）-（6-c）=-2；

λ₃₃=c₃₃-u₃-v₃=9-（-1+c）-（2-c）=8；

λ₃₄=c₃₄-u₃-v₄=7-（-1+c）-（5-c）=3。

从上述结果可知，非基变量的检验数与自由未知变量的取值（u₁=c）无关，所以在实际计算时，一般令u₁=0，同时，为了简化计算，将u₁，u₂，u₃的值分别放在表3-36的右方，将v₁，v₂，v₃，v₄的值分别放在表3-36的上方（见表3-37），同时，可将产量所在列、销量所在行去掉。之后，先计算（u_i+v_j）的值（称为位势表，见表3-38），再计算c_ij-（u_i+v_j）的值（称为检验数表，见表3-39）。

将检验数填入表3-36中，为了避免与基变量的取值混淆，检验数用括号括起来，由于基变量的检验数为零，所以不必写出。显然，用位势法求得的检验数与用闭回路法求得的检验数是一样的。

由于λ₃₁=-2，所以，该方案不是最优方案，需要调整。

表3-37

表3-38　位势表u_i+v_j

表3-39　检验数表c_ij-（u_i+v_j）

步骤四　方案的调整

当作业表中存在负检验数时，如表3-37中就存在一个负检验数λ₃₁=-2，若用闭回路法定义的检验数来解释，这表明若让λ₃₁对应的非基变量x₃₁从0增加到1t，可使总运费相应地减少200元，从而表明表3-36所示方案非最优。这时需要调整非最优方案，以求出另一个方案，使总运费减少，调整时仍采用闭回路法。

因为让x₃₁从0增加到正值能使总运费减少，所以首先确定让x₃₁入基。但是，究竟让x₃₁增加多少呢？这就要看其闭回路了。故先按表3-36画出x₃₁的闭回路（见表3-40）。

表3-40

如前所述，若让x₃₁从0增加到θ，这时为保持它所在行、列的运量仍分别与产、销量平衡，则在x₃₁的闭回路上，所有奇点的值都要加θ，所有偶点的值都要减θ，但运量的值不能为负，所以偶点的值不能减少到负值，因此入基变量的增加值θ取决于偶点的值。另一方面，让一个非基变量入基，相应地就要让一个基变量出基，也就是说，至少要有一个基变量从原有的值减少到0，而这也只能从偶点中寻找。综上所述，应当在入基变量x₃₁所在闭回路上的所有的偶点中选择数值最小的那个作为出基变量，并且取它的值作为调整量θ，即在奇点处应该增加、偶点处应该减少的量。

由于表3-40所示x₃₁的闭回路上，偶点中数值最小的是x₁₁=2，所以令x₁₁出基，取调整量θ=2，并让闭回路上所有奇点的值都加上2，偶点的值都减去2，这样就得到一个新的调整方案（见表3-41）。其中出基变量x₁₁=0，不再标记0，而留作空格，因为调整后它已经变为一个非基变量了。

进一步求出表3-41中空格的检验数，由于所有检验数均为非负，因此从表3-41可得到任务3-1的最优解：

x₁₂=2，x₁₃=1，x₁₄=2，x₂₄=2，x₃₁=2，x₃₂=1

即：A₁煤矿运200t煤到地区B₂，运100t煤到地区B₃，运200t煤到地区B₄，A₂煤矿运200t煤到地区B₄，A₃煤矿运200t煤到地区B₁，运100t煤到地区B₂。最少总费用为S=3×200+2×100+5×200+4×200+3×200+2×100=3400（元）。

表3-41

注意到表3-41所示最优方案与前面用Vogel法得出的初始方案（见表3-32）完全一致。

下面给出用闭回路法实施调整非最优方案的任务。

①入基变量的确定：

按　min｛λ_ij｜λ_ij＜0｝=λ_st确定x_st入基。

若有多个λ_st同时最小，则选其中最小运价min｛c_st｝对应的那个变量入基；又若有多个这样的c_st同时最小，则从中任选一个c_st对应的x_st入基。

②出基变量的确定：

在入基变量x_st的闭回路上，按

θ=min｛x_ij｜x_ij为偶点｝=x_pq

确定x_pq出基，同时也就确定x_pq的值θ为调整量。

若有多个奇点x_pq的值同时最小，则选其中最大运价max｛c_pq｝所对应的那个x_pq出基；又若有多个这样的c_pq同时最大，则从中任选一个c_pq对应的x_pq出基。

③非最优方案的调整：

在入基变量x_st的闭回路上，所有偶点的值都减去θ，所有奇点的值都加上θ，其他基变量的值不变，其中出基变量的格子留作空格，这样就得到一个新方案。