# 运输问题求解器（最小费用流）

把平衡运输问题作为最小费用流求解（2–8 个供应地 × 2–8 个目的地，要求总供应 = 总需求，不平衡会提示先补哑行/哑列）：每次增广沿残差网络中最短路径发货（SPFA 容忍残差弧的负费用），累计最短距离的相反数恰为 MODI 对偶变量 (u_i, v_j)。输出每次增广的路径与运量、完整运输方案、行列合计核对，以及 u/v 检验数矩阵与最优性证书（所有检验数 ≥ 0、基格 = 0）。经典例：3 供应地 [30,40,30]、4 目的地 [20,30,30,20]、单位运费 [[2,3,1,4],[4,2,5,3],[3,1,4,2]] → 最小总运费 200。

> 标准页面: https://elysiatools.com/zh/tools/transportation-problem

- **分类:** Math & Numbers

- **关键词:** 运输问题, 最小费用流, 最小成本流, 位势法, uv 法, 对偶变量, 运筹学, 物流, 运输方案, 供需平衡

## 概述

运输问题求解器基于最小费用流算法与连续最短路增广机制，专门用于快速计算 2 至 8 个供应地与 2 至 8 个目的地之间的最优物流调配方案。工具不仅输出最低总运费与完整发货矩阵，还自动生成 MODI 位势法对偶变量 (u_i, v_j) 与检验数矩阵，为平衡运输方案提供严谨的最优性数学证明。

## 输入项

- **成本矩阵（行 = 供应地，每行一行）** (textarea): Unit shipping cost from each source (row) to each destination (column). 2–8 rows × 2–8 columns.
- **供应量（每个供应地）** (text): Amount available at each source, one per matrix row (non-negative).
- **需求量（每个目的地）** (text): Amount required at each destination, one per matrix column (non-negative).
- **小数位数** (number)

## 适用场景

- 需要为多仓库与多销售点制定最低成本货物调配路线时
- 运筹学教学或课程作业中需要核对位势法 (u-v 法) 对偶变量与检验数矩阵时
- 物流规划中需要验证现有运输调度方案是否达到全局最优时

## 工作原理

- 输入供应地的供应量、目的地的需求量及对应的单位运费成本矩阵，系统自动核验总供应与总需求是否平衡。
- 算法构建残差网络，使用容忍负权费用的 SPFA 算法寻找最短增广路径并逐步分配流量。
- 累计最短路径距离得出 MODI 对偶位势 (u_i, v_j)，计算所有单元格的检验数并验证最优性条件。
- 输出每一步增广记录、最终发货方案矩阵、行列供需核对以及最优性证书。

## 使用案例

- 区域仓储物流调拨：在多个中心仓与区域门店之间分配库存以最小化干线运输费用。
- 运筹学教学与验证：快速获取标准运输平衡表的基变量分配、增广步骤与位势法检验数。
- 生产工厂供料调度：将多个原料产地的物料以最低单位运价分配至各个装配车间。

## 常见问题

### 如果总供应量与总需求量不相等怎么办？

本求解器要求供需平衡。若总供应与总需求不相等，请根据运筹学规范手动添加虚拟供应地（哑行）或虚拟目的地（哑列）以补齐差额。

### 该工具支持的最大问题规模是多少？

支持 2 至 8 个供应地（矩阵行）与 2 至 8 个目的地（矩阵列）的运输规划问题。

### 输出结果中的 u 和 v 代表什么？

它们是位势法（MODI 法）中的对偶变量，用于计算非基变量的检验数，证明当前运输方案已达到理论最低成本。

### 单位运费矩阵的数据格式应该如何填写？

每一行代表一个供应地到各目的地的运费，数值间使用逗号或空格分隔，不同供应地换行输入。

### 计算结果支持保留几位小数？

支持在 0 到 8 位小数之间自定义调节，默认保留 4 位小数。

## 相关工具

- [线性规划单纯形法求解器（两阶段）](https://elysiatools.com/zh/tools/linear-programming-simplex): 用两阶段单纯形法求解小规模线性规划（2–6 个变量、1–8 个约束）：支持 max/min 与 ≤/≥/= 约束（右端为负自动规范化，≥/= 走阶段一人工变量），Bland 规则防循环；逐步输出每次迭代的进基/离基变量与目标值，报告最优解 x*、目标值及状态（最优/无界/无可行解），并将目标值代回验证。经典例：max 3x+5y s.t. x≤4, 2y≤12, 3x+2y≤18 → (2,6)，z=36；min 2x+3y s.t. x+y≥4, x+3y≥6 → (3,1)，z=9。
- [轴的临界转速计算器](https://elysiatools.com/zh/tools/shaft-critical-speed): 计算转轴的临界转速（共振转速）。ω_n = √(k/m)，n_cr = (60/2π)·√(k/m) rpm。同时输出固有频率 f_n（Hz）。
- [PDF PAdES 证书签名器](https://elysiatools.com/zh/tools/pdf-pades-certificate-signer): 使用 PKCS#12 证书和 ETSI CAdES 分离式签名签署 PDF。
- [原根查找器](https://elysiatools.com/zh/tools/primitive-root-finder): 查找模 n 的原根：先判断 n 是否属于 {2, 4, p^k, 2p^k}（乘法群为循环群），再给出最小原根及其判别证书（对每个整除 φ(n) 的素数 q 都有 g^(φ/q) ≠ 1）、原根总数 φ(φ(n))，可列出最多 50 个原根，或验证指定候选 g 的阶是否等于 φ(n)。支持 n ≤ 10¹²。
- [二次剩余判定器（Legendre / Jacobi 符号）](https://elysiatools.com/zh/tools/quadratic-residue-checker): 计算 Jacobi 符号 (a/n)（n 为奇数，可达 10¹⁸；素数时即 Legendre 符号）：素数模下 a^((n−1)/2) ≡ 1 判定为二次剩余，并用 Tonelli–Shanks（或 p ≡ 3 (mod 4) 时的直接公式）给出平方根 ±√a；符号为 −1 则 a 一定不是二次剩余。合数模下 Jacobi 符号只是必要条件：−1 证明非剩余，+1 不确定（n ≤ 10⁵ 时自动暴力枚举求真相）。经典例：10 是 mod 13 的二次剩余，根为 ±6。
- [科学计算器](https://elysiatools.com/zh/tools/scientific-calculator): 高级科学计算器，支持复杂数学函数和表达式
- [圆柱螺旋弹簧刚度计算器](https://elysiatools.com/zh/tools/spring-rate-calculator): 计算圆柱螺旋压缩/拉伸弹簧的刚度系数。k = G·d⁴ / (8·D³·n)（N/mm）。支持常见弹簧材料的剪切模量预设。
- [杨氏模量计算器](https://elysiatools.com/zh/tools/youngs-modulus-calculator): 线弹性段杨氏模量 E = σ/ε（胡克定律）。选择求弹性模量、应力或应变：求 E 给 σ 与 ε；求 σ 给 E 与 ε；求 ε 给 E 与 σ。任一方向输入另两个正量即可反算，结果以 MPa 输出并附 GPa 读数。

## 示例

- [Android Java 图像处理示例](https://elysiatools.com/zh/samples/android-image-processing-java): Android Java 图像处理示例，包括图像读取保存、缩放和格式转换
- [Android Kotlin 图像处理示例](https://elysiatools.com/zh/samples/android-image-processing-kotlin): Android Kotlin 图像处理示例，包括图像读取保存、缩放和格式转换
- [Web Python 图像处理示例](https://elysiatools.com/zh/samples/web-image-processing-python): Web Python 图像处理示例，使用 PIL/Pillow 包括读取、保存、缩放和格式转换
- [Web Rust 图像处理示例](https://elysiatools.com/zh/samples/web-image-processing-rust): Web Rust 图像处理示例，包括图像读取保存、缩放和格式转换