一罐可乐

1. 数学模型的一般结构#

线性规划（Linear Programming，简称 LP）解决的是在有限资源限制下，如何实现特定目标最大化或最小化的问题。其数学模型由三要素组成：

• 决策变量（$x_1, x_2, \dots, x_n$）
• 目标函数：要求实现最大化（$\max z$）或最小化（$\min z$）
• 约束条件：由一组线性等式或不等式构成，且决策变量通常满足非负约束（$x_j \ge 0$）

2. 线性规划的标准型#

线性规划问题的数学标准型定义如下： $\max z = \sum_{j=1}^n c_j x_j$ $\text{s.t. } \begin{cases} \sum_{j=1}^n a_{ij} x_j = b_i, & i = 1, 2, \dots, m \\ x_j \ge 0, & j = 1, 2, \dots, n \end{cases}$ 其中右端项常数必须满足非负性，即 $b_i \ge 0$ ($i = 1, \dots, m$)。

3. 非标准型向标准型的转化方法#

实际建模得到的线性规划问题往往不是标准型，需按以下规则进行转化：

1. 目标函数极小化：若原要求为 $\min z = CX$，则令 $z' = -z$，转化为求 $\max z' = -CX$。
2. 约束条件为不等式：
   • 对于“$\le$”型不等式 $\sum a_{ij} x_j \le b_i$，可在等式左端加入一个非负松弛变量（Slack Variable） $x_{s} \ge 0$，化为等式。
   • 对于“$\ge$”型不等式 $\sum a_{ij} x_j \ge b_i$，可在等式左端减去一个非负剩余变量（Surplus Variable） $x_{e} \ge 0$，化为等式。
3. 变量无约束（取值无限制）：若某变量 $x_k$ 取值无约束，可引入两个非负变量 $x_k', x_k'' \ge 0$，令 $x_k = x_k' - x_k''$ 替换原变量。
4. 右端常数项为负：若某约束条件右端常数 $b_i < 0$，必须在不等式或等式两端同乘以 $-1$，使右端项常数变为非负。

1. 图解法（Graphical Method）#

仅适用于含有两个决策变量的线性规划问题。

• 步骤：
  1. 建立直角坐标系，将各约束条件不等式画为边界直线，并根据不等号方向确定半平面。
  2. 求出所有半平面的交集，确定可行域（Feasible Region）。
  3. 绘制目标函数等值线 $c_1 x_1 + c_2 x_2 = z$。
  4. 将目标函数等值线沿其梯度方向（即利润增加方向）平移，寻找与可行域边界最后的交点，该点即为最优解对应的顶点。

2. 几何与代数性质#

• 凸集（Convex Set）：若集合 $K$ 中任意两点连线上的所有点都在 $K$ 内，则称 $K$ 为凸集。
• 顶点（Extreme Point）：凸集中不能表示为该集合内其他两点严格凸组合的点。
• 核心定理：
  1. 线性规划问题的可行域（若存在）是一个凸集（通常为凸多面体）。
  2. 线性规划问题的基可行解对应于可行域的顶点。
  3. 若可行域有界且存在最优解，目标函数的最优值一定可以在可行域的某个顶点上达到。

1. 代数迭代核心步骤#

1. 确定初始基可行解：选择 $m$ 个线性独立的列向量作为基，令其余 $n-m$ 个非基变量为零，解出 $m$ 个基变量。通常选择松弛变量对应的单位矩阵作为初始基。
2. 用非基变量表示基变量和目标函数：通过高斯行初等变换消元，将基变量 $X_B$ 和目标函数 $z$ 表达为非基变量 $X_N$ 的线性函数。
3. 最优性检验（检验数计算）： 目标函数中非基变量 $x_j$ 的系数即为检验数 $\sigma_j$：
   • 对于极大化问题：若所有非基变量的检验数 $\sigma_j \le 0$，则当前基可行解已是最优解。
   • 若存在某个非基变量的检验数 $\sigma_k > 0$，说明将该变量换入基变量可增加目标函数值。
4. 基变换：
   • 确定换入变量（Entering Variable）：通常选择正检验数最大者对应的非基变量 $x_k$ 换入基。
   • 确定换出变量（Leaving Variable）：利用比值判别规则（$\theta$ 规则）防止变量出现负值： $\theta = \min_{i} \left\{ \frac{b_i}{a'_{ik}} \ \middle|\ a'_{ik} > 0 \right\}$ 比值最小的行对应的基变量换出。
5. 旋转运算（Pivot）：以主元（主行与主列交点系数 $a'_{lk}$）进行初等行变换，完成基变量的替换，并转入下一步迭代。

2. 矩阵表示法#

将约束矩阵分块为基矩阵 $B$ 和非基矩阵 $N$： $A = [B, N], \quad X = [X_B, X_N]^T$ 约束方程 $AX=b \implies B X_B + N X_N = b$。左乘 $B^{-1}$ 得到： $X_B = B^{-1}b - B^{-1}N X_N$ 代入目标函数 $z = C_B X_B + C_N X_N$ 得到： $z = C_B B^{-1}b + (C_N - C_B B^{-1}N)X_N$ 定义非基变量的检验数向量为： $\sigma_N = C_N - C_B B^{-1}N$ 当 $\sigma_N \le 0$ 时，令 $X_N=0$，得到最优解 $X_B^* = B^{-1}b$，最优值 $z^* = C_B B^{-1}b$。

1. 大 M 法（Big-M Method）#

• 核心思想：在原目标函数中，对每个引入的人工变量 $x_a$ 施加一个极大的惩罚系数（极大化问题中系数取 $-M$，极小化问题中系数取 $+M$，其中 $M$ 是一个任意大的正数）。
• 求解流程：构建好标准型及目标函数后，直接填入单纯形表进行普通单纯形迭代。在计算检验数时，把 $M$ 当作符号常数参与计算。

2. 两阶段法（Two-Phase Method）#

大 $M$ 法在计算机中因数值精度问题（大 $M$ 与普通系数相加减易产生舍入误差）较难精确实现，故通常采用两阶段法：

• 第一阶段：不考虑原目标函数，构造一个仅以最小化人工变量之和为目标的新问题： $\min w = \sum_{i} x_{a,i}$ 在约束中加入人工变量，使其具有单位可行基，并用单纯形法求解。
  • 若最终表的最优值 $w^* > 0$，说明原问题无可行解，计算终止。
  • 若最优值 $w^* = 0$（且人工变量均出基），说明原问题存在基可行解，进入第二阶段。
• 第二阶段：从第一阶段的最终单纯形表中剔除人工变量所在的各列，将目标函数行的系数替换回原问题的目标函数系数，重新计算当前基的检验数，作为第二阶段的初始表继续单纯形迭代，直至找到原问题的最优解。