第5章 · 第一部分
优化模型的转化
将非线性、非标准形式的优化问题转化为可高效求解的标准形式
⚡ 核心问题
在实际建模中，我们经常会遇到含绝对值、分式、极小极大等"非标准"形式的优化问题。以下哪种思路是正确的？
✅ 正确！这正是本章的核心思想：通过巧妙的变量替换和约束重构，许多看似非线性的优化模型可以等价（或近似）转化为线性规划，从而利用成熟的LP算法高效求解。
❌ 再想想。回顾优化建模的基本方法论——我们并非束手无策，但也并非无所不能。关键在"转化"二字。
🎯 学习目标
- 掌握 Minimax / Maximin 目标函数的线性化转化方法
- 理解分式目标函数与分式约束的线性化技术（Charnes-Cooper变换）
- 能够处理含绝对值的目标函数
- 区分硬约束与软约束，掌握约束松弛化技巧
- 掌握对偶理论的视角及其在模型转化中的应用
- 理解 McCormick 包络及其在双线性项线性化中的应用
1 优化问题的建模流程
解决一个优化问题，需要经历以下完整流程：
- 数学建模（Formulate）：确定决策变量、约束条件、目标函数。变量类型决定问题性质：0-1？整数？实数？
- 求解（Solve）：选择合适的算法或开发新算法求解模型
- 解释（Interpret）：解释求得的解是否满意
- 迭代（Iterate）：若不满意，回到建模阶段重新审视模型假设
💡 关键洞察
如果一个问题没有目标函数而只有约束，本质上是一个可行性问题（feasibility problem），而非优化问题。此时可以通过引入辅助变量（如松弛变量的和）来构造一个目标函数。对于多目标问题，常用方法是加权求和——但需注意量纲统一，必要时通过逐步收紧上界（ε-约束法）来逼近 Pareto 前沿。
2 Minimax 与 Maximin 目标的线性化
Minimax 问题是博弈论和鲁棒优化中的经典形式：在最坏情况下最小化代价。
Minimax → 线性规划
原始问题：
$$\min_{x} \max_{j} \{ f_j(x) \}$$
转化思路：引入辅助变量 $t$，令其作为所有 $f_j(x)$ 的上界，则最小化上界等价于原问题。
等价转化：
$$\begin{aligned}
\min_{x,t} \quad & t \\
\text{s.t.} \quad & f_j(x) \le t, \quad \forall j
\end{aligned}$$
当 $f_j(x)$ 本身是线性函数时，转化后的问题就是一个标准的线性规划。
Maximin → 线性规划
原始问题：
$$\max_{x} \min_{j} \{ g_j(x) \}$$
转化思路：引入辅助变量 $s$，令其作为所有 $g_j(x)$ 的下界，则最大化下界。
等价转化：
$$\begin{aligned}
\max_{x,s} \quad & s \\
\text{s.t.} \quad & g_j(x) \ge s, \quad \forall j
\end{aligned}$$
3 分式目标函数的线性化
分式规划出现在效率评估（如 DEA）、投资回报率最大化等场景中：
$$\min_{x} \frac{c^T x + \alpha}{d^T x + \beta}, \quad \text{s.t. } x \in X$$
Charnes-Cooper 变换（当分母恒正时）
令 $t = \frac{1}{d^T x + \beta} > 0$，并设 $y = t \cdot x$，则：
$$\begin{aligned}
\min_{y,t} \quad & c^T y + \alpha t \\
\text{s.t.} \quad & d^T y + \beta t = 1, \\
& y \in t \cdot X, \quad t > 0
\end{aligned}$$
当 $X$ 为多面体（线性约束定义）时，$y \in t \cdot X$ 仍保持线性，因此转化为线性规划。
4 分式约束的线性化
$$\frac{a^T x + \alpha}{b^T x + \beta} \le \gamma$$
当分母 $b^T x + \beta > 0$ 时，可以直接通分：
$$a^T x + \alpha \le \gamma(b^T x + \beta)$$
这是一个线性约束。注意：分母符号不确定时需要分情况讨论，引入0-1变量。
5 含绝对值的目标函数转化
$$\min_x |f(x)|$$
引入 $t \ge 0$，转化为：
$$\begin{aligned}
\min_{x,t} \quad & t \\
\text{s.t.} \quad & -t \le f(x) \le t
\end{aligned}$$
等价于 $f(x) \le t$ 且 $-f(x) \le t$。
对于最小化 $\sum_i |a_i^T x - b_i|$（L1回归）：
$$\begin{aligned}
\min_{x, t_i} \quad & \sum_i t_i \\
\text{s.t.} \quad & -t_i \le a_i^T x - b_i \le t_i, \quad t_i \ge 0
\end{aligned}$$
6 Minimax + 绝对值：组合转化
$$\min_{x} \max_{j} \left| a_j^T x - b_j \right|$$
这是 Chebyshev 逼近问题，需要双重转化：
$$\begin{aligned}
\min_{x, t} \quad & t \\
\text{s.t.} \quad & -t \le a_j^T x - b_j \le t, \quad \forall j
\end{aligned}$$
先引入 $t$ 作为最大值上界（Minimax转化），再用双边不等式处理绝对值。
7 硬约束 → 软约束（约束松弛化）
硬约束（Hard Constraint）：必须严格满足，违反即不可行。
软约束（Soft Constraint）：允许一定程度的违反，但违反量会被惩罚加入目标函数。
将不等式约束 $a^T x \le b$ 软化为：
$$a^T x \le b + s, \quad s \ge 0$$
同时目标函数中加入惩罚项 $\lambda \cdot s$（$\lambda > 0$ 为惩罚系数）。
💡 实际应用中的启发
在真实问题中，$b$ 可能代表某种资源的可用量。如果轻微违反某约束能带来显著提升的目标值，那么将约束松弛化并惩罚是合理的——这是一种"花钱买资源"的建模思路。
8 对偶视角：从原问题到对偶问题的转化
对偶理论是优化中最深刻的概念之一。对偶问题提供原问题最优值的界，且在一些条件下两者等价。
标准形式的原-对偶关系：
原问题 (P)
$$\begin{aligned} \min \;& c^T x \\ \text{s.t.} \;& Ax \ge b \\ & x \ge 0 \end{aligned}$$
对偶问题 (D)
$$\begin{aligned} \max \;& b^T y \\ \text{s.t.} \;& A^T y \le c \\ & y \ge 0 \end{aligned}$$
含等式约束的情况：
原问题 (P)
$$\begin{aligned} \min \;& c^T x \\ \text{s.t.} \;& Ax = b \\ & x \ge 0 \end{aligned}$$
对偶问题 (D)
$$\begin{aligned} \max \;& b^T y \\ \text{s.t.} \;& A^T y \le c \\ & y \text{ 无限制} \end{aligned}$$
🔑 对偶的核心价值
- 弱对偶定理：原问题任意可行解的目标值 ≥ 对偶问题任意可行解的目标值（对 min 问题）
- 强对偶定理：若原问题有最优解，对偶也有，且最优值相等
- 互补松弛性：可用于验证最优性和敏感性分析
9 双线性函数的线性化：McCormick 包络
双线性项 $x \cdot y$ 出现在许多应用中（如混合整数非线性规划 MINLP）。McCormick (1976) 提出了利用变量上下界的凸松弛方法。
McCormick 包络：设 $x \in [x^L, x^U]$，$y \in [y^L, y^U]$，令 $w = x \cdot y$。则 $w$ 可用以下四个线性不等式松弛：
$$\begin{aligned}
w &\ge x^L y + y^L x - x^L y^L \quad &\text{(凸下界 1)}\\
w &\ge x^U y + y^U x - x^U y^U \quad &\text{(凸下界 2)}\\
w &\le x^U y + y^L x - x^U y^L \quad &\text{(凹上界 1)}\\
w &\le x^L y + y^U x - x^L y^U \quad &\text{(凹上界 2)}
\end{aligned}$$
📊 几何解释
这四个不等式定义了一个包围双线性曲面 $w = xy$ 的多面体。初始边界越紧（$x^L, x^U, y^L, y^U$ 越精确），松弛效果越好。
获取紧边界的方法：在原始约束下分别最大化/最小化 $x$ 和 $y$，得到其取值范围。然后在此范围内使用 McCormick 松弛。
⚠️ 注意事项
McCormick 包络是一种松弛，而非等价转化。它提供了双线性项的凸/凹近似，结果是原问题的下界（对最小化问题）或上界（对最大化问题）。在分支定界框架中迭代收紧边界可以提高精度。
10 综合案例：2018 研究生数模竞赛 F题
在实际竞赛建模中，多种转化技术会组合使用。例如，2018 年中国研究生数学建模竞赛 F 题涉及：
- 多目标优化 → 引入优先级权重或 ε-约束
- 分段线性成本 → 利用 SOS2 或 0-1 变量转化
- 绝对值偏差最小化 → 引入辅助变量
- 双线性项 → McCormick 包络松弛
💡 关键启示：实际的优化建模往往是多种转化技术的组合运用，需要根据问题结构灵活选择。
📝 章节检测（共3题）
请认真作答每题，选择后查看解析。
将 $\min_x \max\{f_1(x), f_2(x), f_3(x)\}$ 转化为线性规划，需要引入几个辅助变量？
关于 McCormick 包络，以下说法正确的是：
使用 Charnes-Cooper 变换将分式规划转化为线性规划，必须满足的关键条件是：