网络单纯形法 网络单纯形法是求解最小费用流问题的专门算法，是普通单纯形法在网络流问题上的优化版本。下面我将分步骤说明其核心原理。 第一步：问题表述与基础概念 最小费用流问题可描述为：给定有向图G=(N,A)，其中N为节点集，A为弧集。每条弧(i,j)有容量u_ ij、单位流量费用c_ ij，每个节点i有固定供给量b_ i（正值表示供给，负值表示需求）。目标是在满足流量平衡和容量约束的前提下，使总运输费用最小。该问题的基解对应生成树结构，这是网络单纯形法的核心特性。 第二步：树结构与基本解 算法维护一棵生成树T，其特性为： 树弧数等于节点数减1（|T|=|N|-1） 非树弧的流量取边界值（0或容量上界） 树弧流量通过平衡方程唯一确定 通过预定义根节点，可建立树节点势（对偶变量）π_ i，用于计算简约费用c_ ij^π = c_ ij - π_ i + π_ j 第三步：最优性检验 通过势计算非树弧的简约费用： 若c_ ij^π ≥ 0（对于流量取0的弧） 若c_ ij^π ≤ 0（对于流量取容量上界的弧） 同时满足上述条件时达到最优解。否则选择违反条件的弧作为入基弧。 第四步：基变换操作 入基弧加入后形成唯一圈，沿圈调整流量： 确定调整方向（增加或减少流量） 计算最大调整量θ（受容量和流量非负约束限制） 第一个触达边界的弧为出基弧 通过势更新保持对偶可行性，完成基变换。 第五步：退化处理与终止 当θ=0时出现退化，可能造成循环。通过强制入基弧远离边界或使用 Cunningham 规则防止循环。当所有非树弧满足最优性条件时终止，获得最小费用流。 网络单纯形法通过利用网络结构，将普通单纯形法的矩阵运算转化为图上的树操作，显著提升计算效率，特别适用于大规模网络优化问题。