闭回路

闭回路((loop)求解运输问题时产生的闭合回路。

在调运方案表中，从一个空格出发，沿水平或垂直方向前进;遇到一个适当的有数字的格子，则转90。前进;这样必会又遇到一个适当的有数字的格子，同样再转90“向前进.经若干次后，必然会回到出发的那个空格.这样形成一条由水平线与垂直线 构成的封闭折线，称为一个闭回路.2100433B

下面举例说明闭回路调整法的计算步骤。下图2是一个产销平衡的运输问题的运输表并且已使用最小元素法填入了基变量。

闭回路调整法计算检验数

蓝色方框中的是运价，橙色数字是基变量的值。如(A2,B1)表示从产地A2运送8个单位的货物到销地B1，其运价为2个单位。

首先考虑表中的空格(A1,B1)，设想由产地A1供应1个单位的物品给销地B1，为使运入销地B1的物品总数量不大于它的销量，就应该将产地A2运到B1的物品数量减去一个单位，即将格子(A2,B1)中填入的数字8改为7；为了使由产地A2运出的物品正好等于它的产量，且保持新的到的解仍为基可行解，需将x23由原来的2增加1，改为3。然后将x13由10减去1，即变为9，以使运入销地B3的物品数量正好等于它的销量，同时使由A1运出的物品数量正好等于它的产量。显然，由于x11的的调整将影响到x21、x23、x13这三个变量的取值，即(A1,B1)，(A2,B1)，(A2,B2)，(A1,B3)这四个格子中填入的数据。在运输表中，每一个空格都可以和一些有数字的格子用水平线段和垂直线段交替连接在一闭合回路上，而且这种闭合回路是唯一的。而且，运输问题的检验数的定义是产地到销地供给1个单位物品所引起的总运费的变化。非基变量或者说空格(A1,B1)的检验数σ11即由此引起的总运费变化是：σ11=c11-c21 c23-c13=4-2 3-4=1。可以看出在计算检验数时，符号在起点时为正，任意时针往下到下个顶点，此时符号为负，由此正负交替直到所有顶点包括进去。

检验方案的数据指标，编排各个闭合回路，这样的工作熟练可以在。现再看空格(A2,B2)，它的闭回路的顶点由以下各格组成：(A2,B2)，(A3,B2)，(A3,B4)，(A1,B4)，(A1,B3)，(A2,B3)，最后再回到(A2,B2)。

在实际操作中由于涂改不便，熟练则可以不用编制各个闭合回路，在心中假想即可，其检验数为σ22=c22-c32 c34-c14 c13-c23=10-5 6-11 4-3=1。检验数为正数，表明修改这个基变量只会增加总运费，因此观察其他空格的检验数。

按照同样的方法，可得表中其他的非基变量的检验数如下：

σ12=c12-c32 c34-c14 c13=12-5 6-11=2

σ24=c24-c14 c13-c23=9-11 4-3=-1

σ31=c31-c21 c23-c13 c14-c34=8-2 3-4 11-6=10

σ33=c33-c34 c14-c14 c13=11-6-11 4=12

由于σ24=-1<0，故知表中的解不是最优解。

用上述闭回路法算出的初始调运方案中各个空格的检验数，表示在下图3的检验数表中。

闭回路调整法解的改进

若最优性检验时某非基变量

解改进的具体步骤为：

（1）

（2）以空格(Ai,Bj)为第一个奇数顶点，沿闭回路的顺（或逆）时针方向前进，对闭回路上的顶点依次编号；

（3）在闭回路上的所有偶数顶点集合L(e)中，找出运输量最小

（4）以

然后，再对得到的新解进行最优性检验，如不是最优解，就重复以上步骤继续进行调整，一直到得出最优解为止 。2100433B

闭回路调整法基格和非基格

定义1：将变量

闭回路调整法闭合回路

所谓闭合回路，就是指在调运方案表中，从一个空格出发，沿水平或垂直方向前进，遇到一个适当的有数字的格子时，转90°继续前进，直到回到起始空格为止，形成一条由水平线段和垂直线段所组成的封闭折线 。

定义2：若一组格点经过适当的排序后，能写成以下形式：

则称这组格点构成了闭合回路。

如下图1中(1，1)， (1，2)，(3，2)， (3，1)构成一个闭合回路。

闭回路调整法是借助图表作业方式，计算比较两种（或两种以上）变量值，以调整部分经济指标实现优化经营提高管理效益的管理统计方法。

用表上作业法求解运输问题时，可仿照一般的单纯形法，检验这个解的各个非基变量（对应运输表中是的空格）的检验数是否都是正数。若有某空格

为了计算出运输表中空格（非基变量）的检验数，引入闭回路的概念，使用闭回路可以直观地为满足约束条件换入变量增值后，再从原来的某一基变量中减去相应数值，变成数值为零的换出变量，完成换入换出即运量的调整。