一罐可乐

1. 产销平衡运输模型#

设某物资有 $m$ 个产地 $A_i$（产量为 $a_i$），$n$ 个销地 $B_j$（销量为 $b_j$）。从 $A_i$ 到 $B_j$ 运送单位物资的运价为 $c_{ij}$。设决策变量 $x_{ij}$ 为从 $A_i$ 到 $B_j$ 的运量。 在产销平衡的前提下（即 $\sum_{i=1}^m a_i = \sum_{j=1}^n b_j$），数学模型为： $\min z = \sum_{i=1}^m \sum_{j=1}^n c_{ij} x_{ij}$ $\text{s.t. } \begin{cases} \sum_{j=1}^n x_{ij} = a_i, & i = 1, 2, \dots, m \quad \text{（产量约束）} \\ \sum_{i=1}^m x_{ij} = b_j, & j = 1, 2, \dots, n \quad \text{（销量约束）} \\ x_{ij} \ge 0, & \forall i, j \end{cases}$

2. 模型系数矩阵的特殊性#

• 约束条件个数与变量数：运输问题有 $m \times n$ 个变量，有 $m+n$ 个约束条件。
• 系数矩阵的秩：由于 $\sum a_i = \sum b_j$，约束方程组中存在线性相关性，因此系数矩阵的秩最多为 $m+n-1$。这意味着基可行解中基变量（数字格）的个数恒等于 $m+n-1$ 个。
• 解的必然性：产销平衡的运输问题必定存在可行解，且由于变量有上界（$0 \le x_{ij} \le \min(a_i, b_j)$），可行域有界，因此运输问题必定存在最优解。

1. 最小元素法（Least Cost Method）#

• 核心思想：就近供应。优先在单位运价表里挑选最小的运价 $c_{ij}$，分配尽可能大的运量：$x_{ij} = \min(a_i, b_j)$。
• • 若 $a_i < b_j$，则 $A_i$ 产量耗尽，划去运价表中第 $i$ 行，并更新 $B_j$ 的销量为 $b_j - a_i$。
  • 若 $a_i > b_j$，则 $B_j$ 需求满足，划去第 $j$ 列，更新 $A_i$ 产量。
  • 在剩余未划去的格子中重复上述过程。

2. 伏格尔法（Vogel’s Approximation Method, VAM）#

• 核心思想：避免“因贪图一处便宜而导致其他处运费暴增”的弊端。通过计算“惩罚量”来决策。
• 计算步骤：
  1. 算差额（惩罚量）：计算每一行和每一列中“最小运价”与“次小运价”的差额。差额越大，代表如果该行（或列）不按最小运价走，造成的潜在损失越大。
  2. 定位置：找出差额最大的行或列，在该行（或列）中选择运价最小的格子，分配最大运量。
  3. 删行列：满足供需后划去相应行列，重新计算剩余部分的行、列差额，直至确定所有 $m+n-1$ 个基变量。
• 评价：伏格尔法得到的初始解最接近最优解，甚至往往直接就是最优解，但计算过程较繁琐。

3. 西北角法（Northwest Corner Rule）#

• 核心思想：从产销表的左上角（西北角）格子开始，向右下角逐步分配运量。
• 评价：不考虑运价高低，得到的初始解质量最差（总运费高），但计算极其简单，在缺乏成本数据、只要求快速排程的实际实时系统（如服务器网络流量分发）中应用广泛。

1. 最优性判别（位势法）#

对于极小化问题，当所有非基变量（空格）的检验数 $\sigma_{ij} \ge 0$ 时，当前方案即为最优方案。

• 位势计算：引入对偶变量 $u_i$（行位势）和 $v_j$（列位势），对于所有基变量（数字格），有： $u_i + v_j = c_{ij}$ 这是一个含有 $m+n-1$ 个方程、$m+n$ 个未知数的方程组。令初始位势 $u_1 = 0$，即可递推解出所有的 $u_i$ 和 $v_j$。
• 检验数计算：对于所有非基变量（空格），计算其检验数： $\sigma_{ij} = c_{ij} - (u_i + v_j)$

2. 方案调整（闭回路调整法）#

若存在空格的检验数 $\sigma_{kl} < 0$，说明该空格可以作为换入变量（调入格）来降低总运费。

• 寻找闭回路：从选定的换入空格 $(k,l)$ 出发，水平或垂直移动，在数字格（基变量）处可作 $90^\circ$ 转弯，最终回到起点，形成唯一的闭回路（回路顶点除起点外必须都是数字格）。
• 调整量确定：给回路顶点标上正负号（起点 $(k,l)$ 为 $+$，其余依次为 $-, +, -$）。找到负号顶点中运量的最小值，即为调整量 $\theta$： $\theta = \min \{ x_{ij} \mid (i,j) \text{ 是回路中的“$-$”顶点} \}$
• 运量调整：回路上的所有“$+$”顶点加上 $\theta$，“$-$”顶点减去 $\theta$。原有的某个“$-$”顶点运量减为 0，成为换出变量（空格）。

1. 产大于销问题（$\sum a_i > \sum b_j$）#

• 转化方法：引入假想的销地 $B_{n+1}$（相当于仓库），其需求量为 $b_{n+1} = \sum a_i - \sum b_j$。
• 运价设置：若无库存费用，则 $c_{i, n+1} = 0$；若各产地库存费用不同，则 $c_{i, n+1}$ 设为各产地的单位存储费用。

2. 销大于产问题（$\sum b_j > \sum a_i$）#

• 转化方法：引入假想的产地 $A_{m+1}$，其供应量为 $a_{m+1} = \sum b_j - \sum a_i$。
• 运价设置：若允许缺货，运价 $c_{m+1, j}$ 设为各销地的单位缺货损失费；若某些销地必须保证供应（不允许缺货），则设运价为罚金大 $M$。

3. 最低运出量限制#

• 转化方法：若要求产地 $A_i$ 必须至少运出 $S_i$ 单位物资（$S_i < a_i$）。可将该产地拆分为两个产地：$A_i'$（产量为 $S_i$）和 $A_i''$（产量为 $a_i - S_i$）。在产大于销增加假想销地时，规定 $A_i'$ 运往假想销地的运价为大 $M$，以此强迫这部分物资必须运往真实销地。