简介：本资源是一份面向通信工程、网络优化方向高年级本科生及研究生的《最优化复习提纲》教学课件，聚焦最优化方法在通信网络设计中的核心应用，系统梳理最小费用流、最大流与最短路等典型网络流问题的建模与求解逻辑。课件以PPT格式呈现，共1个文件，大小820KB，结构清晰、图文并茂，完整覆盖六大章节：从网络设计问题建模（Link-Path/Node-Link双模型对比与实例推导）到线性规划几何基础与单纯形算法详解，再延伸至整数规划、无约束优化、分解方法及对偶理论等进阶内容，每章均嵌入公式推导、约束建模和目标函数构建等关键训练点。已有122人学习下载，适合作为课程复习纲要、考前速记手册或网络优化算法入门的结构化学习材料，助力读者快速建立理论框架并掌握通信场景下的建模思维。
1. 最优化复习提纲：一张通信网络里的“决策地图”
如果你正在系统复习最优化方法，又恰好在通信网络、资源调度或系统建模方向上做项目或备考——这份《最优化复习提纲：网络做优化》不是泛泛而谈的数学推导集，而是一张可落地、可复现、可查漏的决策地图。它不从“什么是凸集”开始讲，而是直接锚定通信网络中最常出现的三类硬骨头问题：最小费用流、最大流、最短路——所有模型、算法、变量定义，都生长在真实网络拓扑与业务约束之上。比如，当链路单位成本为1、节点间需求矩阵已知、每条链路有明确容量上限时，“怎么分流量”就不再是抽象的线性规划题，而是一个带物理意义的路由决策问题。课程用两种建模范式贯穿始终：Link-Path 模型（路径即决策单元，适合预计算路径集合的场景）和 Node-Link 模型（链路即决策单元，支持动态路由+连续分流，更贴近SDN控制器逻辑）。梳理下来会发现：所谓“网络做优化”，本质是把通信语义（如时延敏感、带宽保障、故障隔离）翻译成数学约束，再用合适工具求解。它适合两类人：一类是正在啃《运筹学》教材但总卡在“这和我做的网络仿真有什么关系”的同学；另一类是已写过路由算法却说不清“为什么选单纯形而不是内点法”的工程师。这不是纯理论补习，而是帮你把“最优化”从黑匣子变成可调试、可验证、可嵌入系统的模块。
2. 网络建模双范式：Link-Path 与 Node-Link 的建模逻辑与适用边界
2.1 Link-Path 模型：路径即变量，适合“路径已知”的确定性优化
Link-Path 模型的核心思想是：先穷举或预生成所有可行路径，再决定每条路径承载多少流量。它把网络流问题转化为一个“路径选择+比例分配”问题，变量维度由路径数量决定，而非链路数量。这种建模方式天然适配多路径传输（MPTCP）、光层波长路由、或已部署固定拓扑的专网场景。
以摘要中给出的三节点网络为例（节点1→2、1→3、2→3），若业务需求为 $ \hat{h}{12}=3, \hat{h}{13}=7, \hat{h}{23}=8 $，链路单位成本均为1，容量上限为 $ c{12}=c_{13}=10, c_{23}=15 $，则所有可能的端到端路径集合 $ P $ 为：
- $ p_{12}^{(1)} $：1→2（直连）
- $ p_{13}^{(1)} $：1→3（直连）
- $ p_{13}^{(2)} $：1→2→3（经2中转）
- $ p_{23}^{(1)} $：2→3（直连）
- $ p_{23}^{(2)} $：2→1→3（经1中转，但因无向链路假设常被剪枝）
于是决策变量为 $ x_{12}^{(1)}, x_{13}^{(1)}, x_{13}^{(2)}, x_{23}^{(1)} $，分别表示对应路径上的流量大小。目标函数即总成本最小化：
$$ \min \quad 1 \cdot x_{12}^{(1)} + 1 \cdot x_{13}^{(1)} + 1 \cdot x_{13}^{(2)} + 1 \cdot x_{23}^{(1)} $$
约束条件包含两层：
- 需求满足约束（每个源宿对的总路径流量 = 需求量）：
$$ x_{12}^{(1)} = \hat{h}{12} = 3,\quad x{13}^{(1)} + x_{13}^{(2)} = \hat{h}{13} = 7,\quad x{23}^{(1)} = \hat{h}_{23} = 8 $$ - 链路容量约束（每条链路上所有经过它的路径流量之和 ≤ 容量）：
$$ x_{12}^{(1)} + x_{13}^{(2)} \leq c_{12} = 10,\quad x_{13}^{(1)} \leq c_{13} = 10,\quad x_{13}^{(2)} + x_{23}^{(1)} \leq c_{23} = 15 $$
提示：Link-Path 模型的变量数随路径数指数增长。实际工程中，若网络规模扩大至10节点，全路径枚举将产生数百条路径，此时需引入K最短路（KSP）剪枝或结合列生成（Column Generation）动态添加有效路径，否则单纯形法迭代步数剧增。
2.2 Node-Link 模型：链路即变量，面向“路由未知”的联合优化
Node-Link 模型不预设路径，而是以每条有向链路 $ (i,j) $ 上承载的源宿对 $ (s,t) $ 流量 $ f_{st}^{ij} $为基本变量。它把路由决策（走哪条路）和流量分配（分多少）统一建模，变量维度为 $ |V|^2 \times |E| $，虽高维但结构清晰，且天然支持任意拓扑与动态需求。
仍以三节点网络为例，设链路为有向：$ (1,2), (1,3), (2,1), (2,3), (3,1), (3,2) $，需求 $ \hat{h}{12}=3, \hat{h}{13}=7, \hat{h}_{23}=8 $。对源宿对 $ (1,2) $，其流量在链路上的守恒约束为：
- 节点1流出平衡：$ f_{12}^{12} + f_{12}^{13} - \hat{h}_{12} = 0 $（流出=需求）
- 节点2流入平衡：$ f_{12}^{12} + f_{12}^{32} - \hat{h}_{12} = 0 $（流入=需求）
- 节点3守恒：$ f_{12}^{13} - f_{12}^{32} = 0 $（流入=流出）
推广为通用形式（见原文公式）：
$$ \sum_{j:(i,j)\in E} f_{st}^{ij} - \sum_{j:(j,i)\in E} f_{st}^{ji} = \begin{cases} \hat{h}{st}, & i=s \ -\hat{h}{st}, & i=t \ 0, & \text{otherwise} \end{cases} \quad \forall (s,t)\in D,\ \forall i\in V $$
链路总流量 $ y_{ij} = \sum_{(s,t)\in D} f_{st}^{ij} $，容量约束即 $ y_{ij} \leq c_{ij} $。目标函数为 $ \min \sum_{(i,j)\in E} \xi_{ij} y_{ij} $，其中 $ \xi_{ij} $ 为链路单位成本。
注意：Node-Link 模型的变量数远超 Link-Path，但约束结构高度稀疏（每条守恒约束仅涉及少数变量），现代LP求解器（如Gurobi、CPLEX）对此类稀疏结构优化极佳。它更适合SDN控制器实时重路由、网络切片资源编排等需在线联合决策的场景。
2.3 两种范式对比：何时该用哪个？
下表从建模粒度、变量/约束规模、求解难度、典型应用场景四方面对比：
| 维度 | Link-Path 模型 | Node-Link 模型 |
|---|---|---|
| 建模粒度 | 路径级（端到端） | 链路级（逐跳） |
| 变量数 | $ O( | P |
| 约束数 | 需求约束 $ O( | D |
| 求解难度 | 小规模网络快；大规模需列生成，否则退化严重 | 大规模稀疏，商用求解器高效；但$ |
| 适用场景 | MPLS-TE预置LSP、光层静态波长分配、教学演示 | SDN集中式路由、网络切片SLA保障、故障恢复重路由 |
实际项目中，某跨平台系统曾因误用 Link-Path 模型处理100节点骨干网（$ |D|=9900 $，K=5时$ |P|≈50000 $），导致单纯形法迭代超2小时未收敛；切换至 Node-Link 后，利用稀疏矩阵优化，求解时间压至47秒。血泪经验：别让建模便利性绑架求解可行性——先看规模，再定范式。
3. 线性规划：从几何直觉到单纯形法的手动推演
3.1 标准形式与几何本质：多面体、极点与最优解的绑定关系
线性规划（LP）的标准形式为：
$$ \min \mathbf{c}^T \mathbf{x} \quad \text{s.t.} \quad A\mathbf{x} = \mathbf{b},\ \mathbf{x} \geq \mathbf{0} $$
其中 $ A \in \mathbb{R}^{m \times n} $，$ \mathbf{b} \in \mathbb{R}^m $，$ \mathbf{c} \in \mathbb{R}^n $，$ \mathbf{x} \in \mathbb{R}^n $。任何LP问题均可通过引入松弛变量、剩余变量、人工变量转化为标准形式。例如，不等式约束 $ a_i^T \mathbf{x} \leq b_i $ 变为 $ a_i^T \mathbf{x} + s_i = b_i,\ s_i \geq 0 $；$ \geq $ 约束则减去剩余变量 $ r_i $。
几何上，可行域 $ \mathcal{F} = { \mathbf{x} \in \mathbb{R}^n \mid A\mathbf{x} = \mathbf{b},\ \mathbf{x} \geq \mathbf{0} } $ 是一个凸多面体（convex polyhedron）。关键性质包括：
- 凸集：任意两点连线仍在集合内 → 保证局部最优即全局最优
- 极点（extreme point）：不能表示为其他两个可行点严格凸组合的点 → 对应基可行解（BFS）
- 极点与最优性：若LP有有限最优解，则必在某个极点处取得。这是单纯形法只搜索极点的理论根基。
以二维问题 $ \min -x_1 - x_2 $，s.t. $ x_1 + x_2 \leq 4 $，$ x_1 \leq 3 $，$ x_2 \leq 3 $，$ x_1,x_2 \geq 0 $ 为例，可行域为四边形，四个顶点（极点）为 $ (0,0), (3,0), (3,1), (0,3) $。目标函数等高线 $ -x_1 - x_2 = k $ 斜率为-1，向右上方移动k减小，最优解在 $ (3,1) $，值为-4。这直观印证了“最优解必在极点”。
3.2 基与基本可行解：如何从代数构造几何顶点
给定标准形式LP，设 $ A = [B\ N] $，其中 $ B \in \mathbb{R}^{m \times m} $ 是满秩子矩阵（基矩阵），$ N \in \mathbb{R}^{m \times (n-m)} $ 为非基列。将变量分为基变量 $ \mathbf{x}_B $ 和非基变量 $ \mathbf{x}_N $，则约束 $ A\mathbf{x} = \mathbf{b} $ 化为：
$$ B\mathbf{x}_B + N\mathbf{x}_N = \mathbf{b} \quad \Rightarrow \quad \mathbf{x}_B = B^{-1}\mathbf{b} - B^{-1}N\mathbf{x}_N $$
令非基变量 $ \mathbf{x}_N = \mathbf{0} $，得基本解$ \mathbf{x} = (B^{-1}\mathbf{b},\ \mathbf{0}) $。若 $ B^{-1}\mathbf{b} \geq \mathbf{0} $，则该解为基本可行解（BFS），对应一个极点。
例如，对问题：
$$ \min z = -2x_1 - 3x_2 \quad \text{s.t.} \quad x_1 + 2x_2 + s_1 = 6,\ 2x_1 + x_2 + s_2 = 6,\ x_1,x_2,s_1,s_2 \geq 0 $$
系数矩阵 $ A = \begin{bmatrix} 1 & 2 & 1 & 0 \ 2 & 1 & 0 & 1 \end{bmatrix} $，取基 $ B = \begin{bmatrix} 1 & 0 \ 0 & 1 \end{bmatrix} $（对应 $ s_1,s_2 $），则 $ B^{-1}\mathbf{b} = \begin{bmatrix} 6 \ 6 \end{bmatrix} \geq 0 $，BFS为 $ (x_1,x_2,s_1,s_2) = (0,0,6,6) $，即原点。
3.3 单纯形法：迭代寻优的代数实现与停止条件
单纯形法本质是沿多面体棱边从一个BFS移动到相邻BFS，使目标值单调下降。其核心步骤如下：
步骤1：计算检验数（Reduced Cost）
对非基变量 $ x_j $，其检验数为：
$$ \bar{c}_j = c_j - \mathbf{c}_B^T B^{-1} A_j $$
其中 $ \mathbf{c}_B $ 为基变量成本向量，$ A_j $ 为第 $ j $ 列。若所有 $ \bar{c}_j \geq 0 $，当前BFS最优；否则选 $ \bar{c}_j < 0 $ 的 $ x_j $ 进基（改善方向）。
步骤2：确定出基变量（最小比值规则）
计算 $ \theta = \min \left{ \frac{(B^{-1}\mathbf{b})_i}{(B^{-1}A_j)_i} \mid (B^{-1}A_j)_i > 0 \right} $。使比值最小的基变量出基，保证新解可行。
步骤3：更新基与解
用进基列替换出基列，更新 $ B $，重新计算 $ B^{-1}\mathbf{b} $ 和 $ \bar{c}_j $。
以原文举例：初始基 $ B = [A_1,A_3,A_6,A_7] $，解 $ \mathbf{x} = (2,0,2,0,0,1,4) $。计算得 $ \bar{c}_5 = -1 < 0 $，故 $ x_5 $ 进基。计算 $ d_B = -B^{-1}A_5 = (-1,-1,0,-1)^T $，则 $ \theta = \min { 2/1, 2/1, 4/1 } = 2 $，对应 $ x_1 $ 出基。新解为 $ \mathbf{x}' = \mathbf{x} + \theta \mathbf{d} = (0,0,0,0,2,1,2) $。
提示：单纯形法迭代次数在最坏情况下为指数级（Klee-Minty立方体），但实际问题中平均为 $ O(m) $ 步。若遇到退化（多个基对应同一BFS），可能循环，需采用Bland规则防死锁。
4. 整数线性规划：分支定界法的树搜索逻辑与剪枝策略
4.1 为什么整数约束让问题变难？离散性与NP-hard的本质
整数线性规划（ILP）要求部分或全部变量取整数值，如网络中的设备开关（0/1）、虚拟机实例数（整数）、波长数（整数）。其难点在于：
- 可行域不再凸：整数点集非凸，无法用LP的极点理论；
- 最优解不在顶点：LP松弛解（去掉整数约束）的最优解常为小数，需向整数格点“取整”，但简单舍入常破坏可行性；
- 计算复杂度跃升：ILP是NP-hard问题，无多项式时间算法，必须依赖启发式或精确搜索。
分支定界法（Branch and Bound, B&B）是求解ILP最主流的精确算法，其思想是：用LP松弛解提供上下界，在解空间树中智能剪枝，避免穷举。
4.2 分支定界算法流程：从根节点到最优整数解的完整路径
设问题为最小化 $ \min \mathbf{c}^T \mathbf{x} $，s.t. $ A\mathbf{x} \leq \mathbf{b},\ \mathbf{x} \geq 0,\ \mathbf{x} \in \mathbb{Z}^n $。算法维护：
- 全局上界 $ U = \infty $（初始无可行整数解）
- 全局下界 $ L = $ 当前最佳LP松弛解目标值（随分支更新）
步骤详解：
- 初始化：求解根节点LP松弛，得最优值 $ z_{LP} $ 和解 $ \mathbf{x}^* $。若 $ \mathbf{x}^* $ 全为整数，则 $ U = z_{LP} $，算法结束；否则，$ L = z_{LP} $，将根节点加入待处理队列。
- 选择节点：从队列选一节点（常用Best-First：选最小 $ z_{LP} $ 的节点）。
- 分支：选一个非整数分量 $ x_i^* = 4.81 $，生成两个子节点：
- 左子：$ x_i \leq \lfloor 4.81 \rfloor = 4 $
- 右子：$ x_i \geq \lceil 4.81 \rceil = 5 $
- 定界：对每个子节点，求解其LP松弛。若：
- 解不可行（如无解），则该子树剪枝；
- 解目标值 $ z_{LP} \geq U $，则剪枝（不可能优于当前最优）；
- 解为整数，则更新 $ U = \min(U, z_{LP}) $；
- 重复：将未剪枝子节点加入队列，直至队列为空。
4.3 分支定界实例手算：从356到340的整数解收敛
原文例题：
$$ \max z = 40x_1 + 90x_2 \quad \text{s.t.} \quad 9x_1 + 7x_2 \leq 56,\ 7x_1 + 20x_2 \leq 70,\ x_1,x_2 \geq 0,\ \text{integer} $$
Step 0（根节点）：LP松弛解 $ x_1=4.81,\ x_2=1.82,\ z_0=356 $。非整数，$ U=\infty,\ L=356 $。
Step 1（分支）：选 $ x_1 $，生成：
- Node A：$ x_1 \leq 4 $，解得 $ x_1=4,\ x_2=2.1,\ z_A=349 $
- Node B：$ x_1 \geq 5 $，解得 $ x_1=5,\ x_2=1.57,\ z_B=341.3 $
Step 2（继续分支）：Node A中 $ x_2=2.1 $ 非整数，分支： - Node A1：$ x_2 \leq 2 $，解得 $ x_1=4,\ x_2=2,\ z_{A1}=340 $（整数！更新 $ U=340 $）
- Node A2：$ x_2 \geq 3 $，解得 $ x_1=3.89,\ x_2=3,\ z_{A2}=345.6 > U $，剪枝
Step 3（剪枝Node B）：$ z_B=341.3 > U=340 $，剪枝。
至此，队列空，最优解为 $ x_1=4,\ x_2=2,\ z^*=340 $。
注意：分支变量选择影响效率。优先选分数部分最接近0.5的变量（如0.48或0.52），因其分支后两子树解空间更均衡；或选对目标函数影响大的变量（检验数绝对值大者）。
5. 易错点与易忽略项：那些让你在考场上拍大腿的细节
5.1 Link-Path 模型中，路径集合 $ P $ 的完备性常被默认，实则决定解的质量
易漏点：直接使用K最短路（如K=3）生成路径，却未验证这些路径是否足以支撑所有源宿对的流量需求。例如，某节点对间KSP全被拥塞链路阻塞，导致LP松弛无可行解。
为什么漏：教学案例常给定“所有路径已知”，掩盖了路径生成本身是NP-hard子问题（KSP是P问题，但“覆盖所有需求的最小路径集”是集合覆盖问题）。
怎么补：在建模前，先运行一次全源最短路（Floyd-Warshall或Dijkstra×|V|），确认每对 $ (s,t) $ 至少有一条路径；对关键业务对，手动添加备份路径（如主路径+绕行路径）；或采用自适应列生成，在单纯形迭代中动态添加负检验数路径。
5.2 单纯形法中，人工变量未正确退出基，导致最终解含人工变量
易错点：用两阶段法求初始可行解时，第一阶段目标为最小化人工变量和 $ \sum a_i $，得最优值0后，第二阶段直接丢弃人工变量列，但未检查人工变量是否仍在基中。若仍在基，新基矩阵 $ B $ 不含原始变量，解无效。
为什么错：教材常简化为“第一阶段最优值为0即成功”，忽略人工变量可能以0值留在基中（退化情况）。
怎么补：第一阶段结束后，若人工变量 $ a_i $ 在基中且 $ (B^{-1}\mathbf{b})_i = 0 $，需用该行主元消去其他行中 $ a_i $ 的系数，再将 $ a_i $ 替换为任一非基原始变量（如 $ x_j $），确保基全由原始变量构成。代码实现中，可用scipy.optimize.linprog的method='highs'自动处理，但手算必须显式检查。
5.3 整数规划分支时，错误地对连续变量分支
易错点：在混合整数规划（MIP）中，仅部分变量需整数（如 $ x_1 \in \mathbb{Z},\ x_2 \in \mathbb{R} $），却对 $ x_2 $ 的非整数解分支。
为什么错：分支操作只针对整数约束变量，对连续变量分支无意义，且污染搜索树，增加计算量。
怎么补：分支前，先遍历所有变量，筛选出整数约束变量集合 $ I = { i \mid x_i \in \mathbb{Z} } $；仅对 $ i \in I $ 且 $ x_i^* \notin \mathbb{Z} $ 的变量分支。商用求解器（如Gurobi）内置此逻辑，但手算或自研求解器必须硬编码校验。
5.4 对偶问题构建时，等式约束对应的对偶变量符号错误
易错点：原问题约束 $ a_i^T \mathbf{x} = b_i $，其对偶变量 $ y_i $ 应为自由变量（unrestricted），但常误写为 $ y_i \geq 0 $。
为什么错：对偶规则中，原问题等式约束 ↔ 对偶变量无符号限制；原问题 $ \leq $ 约束 ↔ 对偶变量 $ \geq 0 $；原问题 $ \geq $ 约束 ↔ 对偶变量 $ \leq 0 $。混淆会导致对偶可行域错误。
怎么补：牢记口诀：“原= → 对偶自由；原≤ → 对偶≥0；原≥ → 对偶≤0”。构建对偶后，用弱对偶定理验证：任取原可行解 $ \mathbf{x} $ 和对偶可行解 $ \mathbf{y} $，必有 $ \mathbf{c}^T \mathbf{x} \geq \mathbf{b}^T \mathbf{y} $。若反例存在，必有符号错误。
5.5 无约束优化中，Hessian矩阵半正定却误判为严格凸
易错点：计算得Hessian $ \nabla^2 f(\mathbf{x}) $ 特征值为 $ {2,0} $（半正定），便断言 $ f $ 是严格凸函数，从而认为驻点即全局唯一最小值。
为什么错：半正定仅保证凸性（convex），严格凸需Hessian处处正定（所有特征值 > 0）。半正定时，函数可能为“平坦凸”（如 $ f(x,y)=x^2 $），存在无穷多最小值点。
怎么补：判断凸性：Hessian正定 → 严格凸；半正定 → 凸；不定 → 非凸。对半正定Hessian，需额外验证：若 $ \nabla^2 f(\mathbf{x}) \mathbf{d} = \mathbf{0} $ 有非零解 $ \mathbf{d} $，则沿 $ \mathbf{d} $ 方向函数为线性，最小值不唯一。此时需结合约束或正则化。
6. 复习清单与查漏技巧：一份可执行的最优化能力自检表
6.1 四级能力自检表：从概念理解到工程落地
以下表格按能力层级设计，每项需能独立完成才算“掌握”。建议打印后逐项打钩，未通过项即为复习重点。
| 能力层级 | 检查项 | 通过标准（请自测） | 典型翻车场景 |
|---|---|---|---|
| Level 1：概念辨析 | 区分Link-Path与Node-Link模型的变量含义 | 能画出3节点网络，标出两种模型下各变量对应的实际物理量（如“$ x_{13}^{(2)} $ 表示1→2→3路径流量” vs “$ f_{13}^{12} $ 表示1→2链路上1→3业务的流量”） | 混淆 $ x_{st}^p $ 与 $ f_{st}^{ij} $，或误以为Link-Path变量是链路流量 |
| Level 2：建模转换 | 将自然语言描述的网络优化问题转为LP标准形式 | 给定“某DC间需保障10G带宽，链路成本不同，求最低成本路由”，能写出目标函数、守恒约束、容量约束，并引入松弛变量标准化 | 忘记添加非负约束；将“最小化成本”写成最大化；守恒方程符号颠倒（流入-流出=需求） |
| Level 3：算法手算 | 手动执行单纯形法1轮迭代 | 给定初始基和解，能计算检验数、选进基变量、用最小比值规则选出基变量、写出新基和新解 | 计算 $ B^{-1}A_j $ 错误；比值计算时未过滤负分母；更新解时符号弄错 |
| Level 4：工程诊断 | 分析求解失败日志定位原因 | 给定Gurobi报错“INFEASIBLE”，能根据约束冲突（conflict）报告，指出是哪条链路容量与需求矛盾 | 盲目调大容量；未检查需求矩阵是否为0；忽略整数约束导致无解 |
6.2 三类高频错题的归因与急救包
错题类型1：LP松弛无可行解（Infeasible）
归因树：
- 需求矩阵 $ \hat{h}_{st} $ 中存在非零值，但对应源宿对间无路径（Link-Path）或守恒约束矛盾（Node-Link）
- 链路容量 $ c_{ij} $ 过小，总容量 $ \sum c_{ij} < \sum \hat{h}_{st} $（必要但不充分条件）
- 符号错误：Node-Link守恒方程写成 $ \sum_{out} - \sum_{in} = \hat{h}{st} $（应为 $ \sum{out} - \sum_{in} = \begin{cases} \hat{h}{st} & s \ -\hat{h}{st} & t \end{cases} $）
急救包：
- 运行Floyd-Warshall，输出所有 $ (s,t) $ 的最短距离，距离为∞则无路径；
- 计算总需求 $ H = \sum_{s<t} \hat{h}{st} $，总链路容量 $ C = \sum{(i,j)} c_{ij} $，若 $ C < H $，必无解；
- 用Python NetworkX构建图，调用
nx.has_path(G, s, t)验证连通性。
错题类型2：ILP求解超时（Slow/Unbounded）
归因树：
- 分支树爆炸：整数变量过多（如100个0-1变量 → $ 2^{100} $ 节点）
- 松弛解界太松：LP松弛最优值 $ z_{LP} $ 远离整数最优值 $ z^* $，导致大量节点需探索
- 模型冗余：存在等价约束或变量，增加求解器负担
急救包：
- 添加割平面（Cutting Plane）：如Gomory割，收紧LP松弛可行域；
- 设置MIP Gap：
mip_gap=0.05，允许5%内近似最优，大幅提速； - 使用启发式初解：先跑贪心算法得整数解，设为初始 $ U $，加速剪枝。
错题类型3：对偶问题解与原问题解目标值不等（Weak Duality Violation）
归因树：
- 对偶变量符号错误（如等式约束配 $ y_i \geq 0 $）
- 原问题目标为最大化，对偶写成最小化但未转置系数
- 约束方向未反转（原 $ \leq $，对偶变量 $ \geq 0 $，但对偶约束写成 $ A^T y \geq c $）
急救包：
- 用对偶规则速查表（下表）核对；
- 代入一个简单可行解：如原问题取 $ \mathbf{x} = \mathbf{0} $（若可行），计算 $ \mathbf{c}^T \mathbf{0} = 0 $，则对偶目标 $ \mathbf{b}^T \mathbf{y} \leq 0 $ 必须成立，否则错。
| 原问题（Primal） | 对偶问题（Dual） |
|---|---|
| $ \min \mathbf{c}^T \mathbf{x} $ | $ \max \mathbf{b}^T \mathbf{y} $ |
| $ A\mathbf{x} \geq \mathbf{b} $ | $ A^T \mathbf{y} \leq \mathbf{c},\ \mathbf{y} \geq 0 $ |
| $ A\mathbf{x} = \mathbf{b} $ | $ A^T \mathbf{y} = \mathbf{c},\ \mathbf{y} $ free |
| $ \mathbf{x} \geq 0 $ | $ |
本文还有配套的精品资源，点击获取
