一罐可乐

1. 单纯形法矩阵分块描述#

设原线性规划标准型模型为： $\max z = CX + 0X_s, \quad \text{s.t. } [A, I] \begin{bmatrix} X \\ X_s \end{bmatrix} = b, \quad X, X_s \ge 0$ 如果最优可行基为 $B$，非基矩阵为 $N$，对应的变量分为基变量 $X_B$ 和非基变量 $X_N$，其对应价值系数分为 $C_B$ 和 $C_N$。 通过矩阵变换，原等式可整理为用非基变量表示基变量的通用形式： $X_B = B^{-1}b - B^{-1}NX_N$ 代入目标函数得到： $z = C_B B^{-1}b + (C_N - C_B B^{-1}N)X_N$ 在最终单纯形表中：

• 系数矩阵区：初始表中松弛变量对应的单位矩阵 $I$ 列，在最终表中的系数转换为 $B^{-1}$（基逆矩阵）。
• 右端项常数（RHS）：在最终表中转换为 $B^{-1}b$。
• 检验数行：非基变量的检验数计算公式为 $\sigma_N = C_N - C_B B^{-1}N$。在最终表中，初始松弛变量位置对应的检验数即为对偶变量的负值（对极大化问题而言为 $-C_B B^{-1} = -Y$）。

2. 对偶问题的经济解释与数学定义#

• 经济解释： 若原问题是合理安排生产以实现最大利润，则对偶问题可视为将生产资源（如设备工时、原材料）出租或出让给代加工厂。对偶变量 $y_i \ge 0$ 代表资源的估价（租金或单价）。 代加工厂的目标是以最低的价格 $w = Yb$ 租进所有资源，但要价必须使原厂出让资源所获收益不低于其自行生产产品所能获得的单位利润，即 $YA \ge C$。

• 数学定义（对称形式对偶）：

  原问题（Primal, LP）	对偶问题（Dual, DP）
  $\max z = CX$	$\min w = Yb$
  $AX \le b$	$YA \ge C$
  $X \ge 0$	$Y \ge 0$

• 非对称形式对偶关系（通用对应法则）：

  原问题（极大化 $\max$）	对偶问题（极小化 $\min$）
  第 $i$ 个约束为 “$\le$”	第 $i$ 个变量 $y_i \ge 0$
  第 $i$ 个约束为 “$\ge$”	第 $i$ 个变量 $y_i \le 0$
  第 $i$ 个约束为 “$=$”	第 $i$ 个变量 $y_i$ 无约束（自由变量）
  第 $j$ 个变量 $x_j \ge 0$	第 $j$ 个约束为 “$\ge$”
  第 $j$ 个变量 $x_j \le 0$	第 $j$ 个约束为 “$\le$”
  第 $j$ 个变量 $x_j$ 无约束	第 $j$ 个约束为 “$=$”

1. 适用场景#

对偶单纯形法用于求解满足对偶可行性（即单纯形表中所有检验数均非正 $\sigma_j \le 0$，对偶问题已可行），但原问题不可行（即右端项常数 bi 存在负数）的线性规划问题。常用于灵敏度分析中重构最优解及整数规划割平面法。

2. 计算步骤#

1. 确定换出变量： 按最小常数项规则，选择 RHS $b'_i$ 为负且绝对值最大者对应的基变量换出： $(B^{-1}b)_l = \min_{i} \left\{ (B^{-1}b)_i \ \middle|\ (B^{-1}b)_i < 0 \right\}$ 第 $l$ 行对应的基变量为换出变量。
2. 确定换入变量（比值判别规则）： 检查换出变量所在第 $l$ 行的系数 $a'_{lj}$。若对于一切 $j$ 均有 $a'_{lj} \ge 0$，则说明原问题无可行解，计算终止。 若存在 $a'_{lj} < 0$，计算检验数与系数的比值： $\theta = \min_{j} \left\{ \frac{\sigma_j}{a'_{lj}} \ \middle|\ a'_{lj} < 0 \right\}$ 比值最小处对应的非基变量 $x_k$ 为换入变量（这能确保基变换后检验数依然全部保持非正，即对偶可行性不被破坏）。
3. 旋转变换：以 $a'_{lk}$ 为主元素进行初等行变换，更新单纯形表，重复上述步骤直至所有 $b'_i \ge 0$。

1. 资源数量 $b_i$ 发生变化#

• 分析方法： 设资源向量变动为 $b' = b + \Delta b$，最优基变量的取值变为 $X'_B = B^{-1}b' = B^{-1}b + B^{-1}\Delta b$。由于目标函数中非基变量的检验数只与 $C$ 和 $A$ 有关，检验数保持非正（最优性条件不破坏）。
  • 若计算出的 $X'_B \ge 0$，则最优基不变，直接得到新的最优解 $X'_B$。
  • 若计算出的 $X'_B$ 出现负数，则说明原问题可行性被破坏，需将更新后的数据填入表，使用对偶单纯形法继续迭代直至恢复可行性。
• 基不变时 $\Delta b_i$ 的范围：令 $B^{-1}(b + \Delta b) \ge 0$，可解得 $\Delta b_i$ 的允许变动区间。

2. 价值系数 $c_j$ 发生变化#

• 非基变量价值系数 $c_k$ 变动： 由于 $c_k$ 不在基变量价值系数 $C_B$ 中，它仅影响自身的检验数。 若要保持原最优解不变，只需更新后的检验数仍非正： $\sigma'_k = (c_k + \Delta c_k) - C_B B^{-1}P_k \le 0 \implies \Delta c_k \le -\sigma_k$
• 基变量价值系数 $c_r$ 变动： 由于 $c_r \in C_B$，它的变化 $\Delta c_r$ 会影响所有非基变量的检验数。 $\sigma'_j = \sigma_j - \Delta c_r \cdot \alpha'_{rj} \le 0 \quad (\forall j \in \text{非基变量})$ 其中 $\alpha'_{rj}$ 是最终表中第 $r$ 个基变量行、第 $j$ 列的约束系数。根据上述不等式组，可解出 $\Delta c_r$ 的允许变动范围。若变动超出范围导致某些检验数变正，需要使用主单纯形法继续迭代求出新最优解。

3. 技术系数 $a_{ij}$ 发生变动 / 引入新产品（新变量）#

• 添加新变量 $x_{n+1}$： 相当于引入一种新产品。在最终表的基础上，计算该新变量的检验数： $\sigma'_{n+1} = c_{n+1} - C_B B^{-1}P_{n+1}$
  • 若 $\sigma'_{n+1} \le 0$，则无需安排生产该产品，最优解不变。
  • 若 $\sigma'_{n+1} > 0$，说明生产该新产品有利。需计算该变量在最终表中的转换列向量 $P'_{n+1} = B^{-1}P_{n+1}$，将其作为新的一列填入最终单纯形表，并使用主单纯形法迭代求解。
• 技术系数 $a_{ij}$ 发生变动： 计算该变量的新列向量及检验数。若是基变量发生变动，可能需要通过初等行变换将基矩阵重新恢复为单位矩阵，然后视可行性与检验数情况选择单纯形法或对偶单纯形法。

4. 引入新的约束条件#

• 分析方法： 直接将最终最优解代入新约束。
  • 若最优解满足新约束，则该约束在最优解处为松弛约束（无活性约束），最优解和最优值保持不变。
  • 若最优解不满足新约束，则需要将该约束化为等式，添加对应的松弛变量，并根据最终表中的 $B^{-1}$ 和基本代数关系，利用行初等变换将新约束中的基变量系数消为 0（即在最终单纯形表下方增加一行新约束）。由于代入后原最优解在新松弛变量处的取值为负数，故需采用对偶单纯形法重新求解恢复可行性。