主题：离散数学框架下的最优化理论，包括组合最优化、图论最优化、线性与整数规划的离散表述及其数学推导。
1. 离散最优化的定义与基本结构
1.1 基本定义
离散最优化问题（Discrete Optimization Problem, DOP）可形式化为：
$$ \begin{aligned} \text{minimize } & f(x) \\ \text{subject to } & x \in S, \end{aligned} $$
其中 $S \subseteq \mathbb{Z}^n$ 是离散可行域，$f: S \to \mathbb{R}$ 为目标函数。
常见目标包括：
- 最小化代价（最短路径、最小费用流）；
- 最大化收益（最大流、最大匹配、背包问题）；
- 多目标优化（Pareto 最优、NP-hard 近似算法分析）。
1.2 优化与搜索空间
可行解集合 $S$ 通常为有限集或由布尔向量构成：
$$ S = \{x\in \{0,1\}^n \mid A x \le b\}, $$
对应于组合结构（如图、集合、匹配）的离散约束。
2. 组合最优化（Combinatorial Optimization）
2.1 一般形式
组合最优化问题可表为：
$$ \min_{x \in \mathcal{F}} c^T x, $$
其中 $\mathcal{F}\subseteq\{0,1\}^n$ 为可行集，通常由某种离散结构定义，如路径、匹配或割。
2.2 经典问题与公式
| 问题 | 数学模型 | 性质 |
|---|---|---|
| 最短路径 | $\min \sum w_{ij}x_{ij}$ s.t. flow constraints | 多项式可解（Dijkstra/Bellman-Ford） |
| 最小生成树 | $\min \sum w_e x_e$ s.t. 边集成树结构 | 贪心最优（Kruskal, Prim） |
| 最大匹配 | $\max \sum w_{ij}x_{ij}$ s.t. 每顶点度 ≤ 1 | 二分图多项式可解（Hungarian算法） |
| 最小割 / 最大流 | $\min_{S\subset V} c(\delta(S))$ | 强对偶性成立（Max-Flow = Min-Cut） |
| 旅行商问题 (TSP) | $\min \sum c_{ij}x_{ij}$ s.t. 每点度=2, 子环消除 | NP-困难 |
2.3 数学推导示例：最短路径
设有加权有向图 $G=(V,E)$，边权 $w:E\to\mathbb{R}$。定义变量：
$$ x_{ij}=\begin{cases} 1, & \text{若边 }(i,j)\text{ 在最短路径中},\\ 0, & \text{否则。} \end{cases} $$
优化模型：
$$ \begin{aligned} \min \quad & \sum_{(i,j)\in E} w_{ij}x_{ij} \\ \text{s.t.}\quad & \sum_{j:(i,j)\in E}x_{ij} - \sum_{j:(j,i)\in E}x_{ji} = \begin{cases} 1, & i=s,\\ -1,& i=t,\\ 0,& \text{otherwise,} \end{cases}\\ & x_{ij}\in\{0,1\}. \end{aligned} $$
利用线性松弛（LP Relaxation）可得 Dijkstra 算法的势函数形式。
3. 图论最优化的数学推导
3.1 最大流最小割定理
设网络 $G=(V,E)$，源 $s$、汇 $t$，容量 $c_{ij}\ge0$。定义流函数 $f:E\to\mathbb{R}$：
$$ \begin{cases} 0\le f_{ij}\le c_{ij},\\ \sum_j f_{ij}-\sum_j f_{ji}=0, & \forall i\ne s,t. \end{cases} $$
目标：最大化流量 $v(f)=\sum_j f_{sj}-\sum_j f_{js}$。
对偶问题（最小割）：寻找 $S\subseteq V$ 使得 $s\in S, t\notin S$，最小化割容量：
$$ C(S) = \sum_{i\in S, j\notin S} c_{ij}. $$
定理（强对偶性）：
$$ \max_f v(f) = \min_{S\subseteq V} C(S). $$
证明基于 LP 对偶性：
$$ \begin{aligned} \max & \sum_j f_{sj}-\sum_j f_{js}\\ \text{s.t. } & f_{ij}\le c_{ij}, f_{ij}\ge0, \\ & Af=0 \ (\text{流守恒}) \end{aligned} $$
其对偶 LP 即为最小割问题。
3.2 匹配问题的线性规划推导
最大匹配问题可表为：
$$ \max \sum_{(i,j)\in E} w_{ij}x_{ij}\quad\text{s.t.}\quad\sum_{j:(i,j)\in E}x_{ij}\le1,\ x_{ij}\in\{0,1\}. $$
在二分图情形，该 LP 的松弛具有整性（即所有极点解皆整数），从而可用 Hungarian 算法求解。
4. 线性与整数规划的离散化
4.1 线性规划标准形
$$ \min c^T x \quad\text{s.t. } A x = b,\ x\ge0. $$
若约束 $x\in\mathbb{Z}^n$，则称为整数规划（IP）。
4.2 整数规划的凸包表述
令 $P=\{x\mid A x\le b\}$，$S=P\cap\mathbb{Z}^n$。则：
$$ \min_{x\in S} c^T x = \min_{x\in \text{conv}(S)} c^T x. $$
其中 $\text{conv}(S)$ 为 $S$ 的凸包。若 $P$ 的极点均为整数，则称 $P$ 整性多面体（Integral Polyhedron）。
例：网络流多面体、二分图匹配多面体均为整性多面体，因此 LP 解即整数最优解。
5. 动态规划与最优子结构
5.1 Bellman 最优性原理
若问题可分解为重叠子问题，且满足最优子结构性质，则递推式成立：
$$ F(s) = \min_{a\in A(s)} \{ c(s,a) + F(T(s,a)) \}, $$
其中 $A(s)$ 为可行动作集，$T(s,a)$ 为转移函数。证明依赖归纳法与"局部最优蕴含全局最优"性质。
5.2 应用：背包问题
目标：最大化收益 $\sum v_i x_i$，约束 $\sum w_i x_i\le W$，$x_i\in\{0,1\}$。
递推：
$$ F(i, w) = \max\{F(i-1,w),\ v_i+F(i-1, w-w_i)\}\quad (w\ge w_i). $$
6. 对偶理论与拉格朗日松弛
6.1 拉格朗日函数
对约束 $Ax\le b$ 的问题，引入乘子 $\lambda\ge0$：
$$ L(x,\lambda)=f(x)+\lambda^T(Ax-b). $$
对偶问题：
$$ \max_{\lambda\ge0} \min_{x\in S} L(x,\lambda). $$
对偶界 $\le$ 原问题最优值，可用于下界估计与分支定界（Branch and Bound）。
6.2 例：指派问题的拉格朗日松弛
原问题：$\min \sum c_{ij}x_{ij}$，约束 $\sum_j x_{ij}=1, \sum_i x_{ij}=1, x_{ij}\in\{0,1\}$。
对列约束松弛：
$$ L(u)=\min_x \sum_{i,j}(c_{ij}-u_j)x_{ij}+\sum_j u_j. $$
内部 $x$-最优解可分解为 $n$ 个独立子问题，形成 Hungarian 算法的数学基础。
7. 离散优化复杂度与近似理论
7.1 NP-困难与 P 类问题
| 类别 | 定义 | 示例 |
|---|---|---|
| P | 多项式可解 | 最短路径、最小生成树 |
| NP-hard | 所有 NP 问题可归约 | TSP、SAT、图着色 |
| NP-complete | NP 且 NP-hard | Hamilton 路径、3SAT |
7.2 近似比与贪心分析
若算法输出 $x_A$，最优解 $x^*$，则近似比 $\rho$ 定义为：
$$ \rho = \max\left\{\frac{f(x_A)}{f(x^*)},\ \frac{f(x^*)}{f(x_A)}\right\}. $$
示例：集合覆盖问题的贪心算法近似比 $H_n=1+1/2+\cdots+1/n$。
8. 总结
离散最优化是离散数学、计算复杂性与线性代数交叉的核心领域。其主要分析工具包括：
- 线性/整数规划对偶理论；
- 图论模型与多面体几何；
- 动态规划与最优性原理；
- 随机化与近似算法。