surplus variable

剩余变量 (Surplus Variable)

剩余变量是线性规划中用于将"大于等于"（$\geq$）型不等式约束转化为标准等式约束的非负人工变量。它与松弛变量 (Slack Variable) 功能互补——松弛变量处理 $\leq$ 型约束，剩余变量处理 $\geq$ 型约束——两者共同构成单纯形法将任意线性规划问题化为标准型的基础工具。

定义与构造

考虑线性规划中一个典型 $\geq$ 型约束：

引入剩余变量 $s_i \geq 0$，将约束转化为标准等式形式：

剩余变量 $s_i$ 衡量的是左侧线性组合超出右端常数 $b_i$ 的量。换言之，$s_i = (\sum a_{ij}x_j) - b_i$ 表示"剩余"或"超额"。注意符号：剩余变量前面是减号，与松弛变量前的加号相反。

与松弛变量的对比

• 松弛变量 (Slack Variable)：用于 $\leq$ 约束，形式为 $\sum a_j x_j + s = b$，表示"未使用的资源量"。$s = b - \sum a_j x_j$。
• 剩余变量 (Surplus Variable)：用于 $\geq$ 约束，形式为 $\sum a_j x_j - s = b$，表示"超出最低要求的量"。$s = \sum a_j x_j - b$。

两者在单纯形初始基可行解的构造中作用截然不同：松弛变量系数为 $+1$，可直接作为初始基变量；剩余变量系数为 $-1$，不能直接作为基变量，因此 $\geq$ 约束通常还需要额外引入人工变量 (Artificial Variable) 来构造初始基。

经济解释

在经济学和运筹学应用中，剩余变量常具有直观的物理或经济含义：

• 营养配方问题：约束要求某种营养成分至少达到最低日摄入量 $b$。剩余变量 $s$ 表示实际摄入量超出最低标准的数值。
• 生产计划问题：约束要求至少完成 $b$ 单位的订单交货量。剩余变量 $s$ 表示超产数量。
• 投资组合约束：约束要求某类资产配置比例不低于下限 $b$。剩余变量 $s$ 表示超额配置的百分比。
• 运输问题：需求约束要求运入某目的地的货物量至少满足需求 $b$。剩余变量 $s$ 表示超额供应量。

在单纯形法中的处理

因为剩余变量在约束方程中系数为 $-1$，它不能直接充当初始基变量。标准解法有两种：

1. 大M法 (Big-M Method)：引入人工变量 $a_i \geq 0$，约束变为 $\sum a_j x_j - s_i + a_i = b$，并在目标函数中对人工变量施加极大惩罚系数 $M$（最小化问题中为 $+M$，最大化问题中为 $-M$），迫使人工变量在最优解中取零。
2. 两阶段法 (Two-Phase Method)：第一阶段以最小化人工变量之和为目标，求得原问题的一个可行基；第二阶段在原可行基上优化原目标函数。

对偶理论中的角色

在对偶理论中，原问题的剩余变量与对偶变量的符号约束密切关联。对于标准形式的原问题（$\geq$ 约束最小化），每个约束对应的剩余变量取值与该约束的对偶变量之积在最优解处为零（互补松弛性）。剩余变量的正值意味着该约束为非紧约束，对应的对偶变量必为零。

与松弛变量、人工变量的综合比较

• 松弛变量：$+s$，用于 $\leq$，可直接为初始基变量，目标函数系数为 0。
• 剩余变量：$-s$，用于 $\geq$，不可直接为初始基变量，目标函数系数为 0。
• 人工变量：$+a$，用于 $\geq$ 或 $=$，可直接为初始基变量，目标函数系数为 $\pm M$ 或在第一阶段被惩罚。

剩余变量是线性规划标准化过程中不可或缺的概念节点。正确区分剩余变量与松弛变量，并理解前者在初始基构造中的特殊性，是掌握单纯形法求解一般线性规划问题的关键前提。