闭回路调整法原理-闭回路法原理

运筹学中的智慧：深入解析闭回路调整法原理

在运筹学（Operations Research）的广阔领域中，运输问题（Transportation Problem）是最经典且应用最广泛的模型之一。它旨在解决如何在多个供应点和多个需求点之间分配货物，以使总运输成本最小化的问题。 当通过表上作业法求得初始基本可行解（如最小元素法或伏格尔法）后，如何判断该解是否最优？如果不是，如何改进？这时，闭回路调整法（Stepping Stone Method / Closed Loop Adjustment Method）便成为了核心的优化工具。本文将深入探讨其原理、步骤及实际应用价值。

一、 核心概念：什么是闭回路？

在运输表中，每一个单元格代表一个从供应点（行）到需求点（列）的运输路径。所谓闭回路，是指从某个非基变量（即当前运输量为0的格子）出发，沿水平或垂直方向前进，遇到适当的基变量（即当前有运输量的格子）后转弯，最终回到起点所形成的封闭折线。

闭回路的关键特性：

1. 顶点交替：闭回路的顶点必须是基变量和非基变量交替出现（起点是非基变量，其余顶点均为基变量）。 2. 唯一性：对于任何非基变量，在基本可行解中，存在且仅存在一条闭回路。 3. 平衡性：在闭回路上，奇数位置的顶点增加运输量，偶数位置的顶点必须减少同等数量的运输量，以保持供需平衡。

二、 闭回路调整法的原理逻辑

闭回路调整法的本质是检验数计算与方案迭代优化。其逻辑链条如下： 1. 检验最优性：计算每个非基变量的检验数（）。检验数表示将单位货物分配到该非基变量路径上，对总运输成本的影响。 若所有 ，则当前解为最优解。 若存在 ，说明将该路径纳入运输方案可以降低总成本，需进行调整。 2. 确定入基变量：选择检验数最小（负值最大）的非基变量作为入基变量，因为它能带来最大的成本节约。 3. 构建闭回路：以该非基变量为起点，构建唯一的闭回路。 4. 调整运输量： 在闭回路的奇数顶点（+）增加运输量 。 在闭回路的偶数顶点（-）减少运输量 。 的取值由偶数顶点中运输量的最小值决定，以确保所有运输量非负。 5. 更新基变量：运输量变为0的偶数顶点出基，入基变量入基，形成新的基本可行解，重复上述过程直至最优。

检验数的计算公式

对于非基变量 ，其检验数 可通过闭回路上的单位成本交替加减求得： 其中 代表对应格子的单位运价。

三、 操作步骤详解

为了更清晰地展示，我们将闭回路调整法分为以下四个标准步骤：

步骤 1：计算检验数

使用位势法（对偶变量法）或闭回路法本身计算所有非基变量的检验数。若使用闭回路法直接计算，需为每个非基变量画出闭回路并求代数和。

步骤 2：判断最优性

检查所有 。若有负数，进入步骤3；若全为非负，停止计算，当前解即为最优。

步骤 3：选择调整方向

选取 对应的非基变量作为调整对象。

步骤 4：执行调整

1. 画出该非基变量的闭回路。 2. 标记奇偶顶点：起点为第1个顶点（+），顺时针或逆时针交替标记为 - , + , - ... 3. 确定调整量 。 4. 更新表格：奇数顶点 ，偶数顶点 。

四、 实例数据说明

假设有一个简单的运输问题，包含3个产地（A1, A2, A3）和3个销地（B1, B2, B3）。 单位运价表 与初始调运方案 ：

产地 销地	B1	B2	B3	产量
A1	3	7	2	10
A2	1	4	5	15
A3	6	2	8	20
销量	12	15	18	45

注：此处为简化演示，假设已通过最小元素法求得初始解，基变量为 等（具体需满足 个基变量，此处仅为示意结构，实际计算需严格匹配供需）。 假设我们关注非基变量 （A1到B2），其单位运价 。构建闭回路如下： 检验数计算： 若 ，则说明调整 会增加成本，不应调整。 若存在另一个非基变量 ，其闭回路为 ： （注：此例中检验数均为正，说明当前解可能已最优，或需检查其他非基变量。若计算出的 为负，如 ，则需调整。） 调整后的运量表对比：

状态	关键指标	说明
调整前	总成本	基于初始基变量计算
调整后	总成本
变化量		，表示成本降低

五、 闭回路调整法的优势与局限

优势

1. 直观易懂：几何意义明确，闭回路的构建过程直观反映了供需平衡的调整逻辑。 2. 适用于小规模问题：对于变量较少的问题，手动计算检验数和调整非常高效。 3. 教学价值高：是理解单纯形法在运输问题中具体应用的最佳入口。

局限

1. 计算繁琐：当问题规模较大时（如 ），为每个非基变量画闭回路并计算检验数工作量巨大。 2. 效率较低：相比位势法（Dual Simplex Method for Transportation），闭回路法在计算检验数时缺乏系统性公式，容易出错。

六、 结语

闭回路调整法是运筹学运输问题求解过程中的基石。它不仅提供了一种判断解是否最优的方法，更通过具体的调整步骤，展示了如何通过局部优化实现全局最优。尽管在现代大规模计算中，位势法或线性规划软件更为常用，但深刻理解闭回路调整法的原理，对于掌握运筹学思维、优化物流成本以及解决复杂分配问题具有不可替代的价值。 在实际应用中，建议先利用位势法快速计算所有检验数以判断最优性，仅在需要具体调整某一路径时，再使用闭回路调整法进行精确的量值修正。两者结合，方能高效解决运输优化难题。