方法选型决策指南：优化类问题怎么选方法（深度版）

面对『在约束下求最好』，先看目标/约束是否可微、连续还是离散，再选线性规划/启发式/智能算法。

分类：⚙ 优化类　适用：排程/调度/配比、路径/网络优化、参数寻优、组合优化

一、这个指南适合谁（适用场景）

排程/调度/配比
路径/网络优化
参数寻优、组合优化

二、选型决策要素

看目标函数：线性/非线性
看变量：连续/整数/0-1
看约束：可微/不可微
看规模与凹凸性
匹配求解器→验证最优性

三、选型的底层逻辑

优化选型的第一判据是"问题结构是否允许精确求解"。线性目标 + 线性约束 + 连续变量 → 凸问题，可用单纯形/内点法求全局最优且可证明；一旦引入整数变量（0-1 决策）、非凸目标或多峰地形，精确求解要么 NP 难、要么陷入局部最优，此时改用启发式（GA/PSO/SA）以"时间换质量"。核心权衡是：精确解慢但可信、可解释；启发式快且鲁棒但只给近似、带随机性。另一个常被忽视的点是多目标——当目标间冲突（成本 vs 质量），不存在单一最优，只能输出帕累托前沿再按决策者偏好选，直接加权会掩盖真实权衡。选型原则：能用精确解就别用启发式；必须启发式时多次运行取统计优并报告前沿。

四、决策模型与推导

凸性与最优性：若目标 $f$ 凸、可行域 $\Omega$ 凸，则任意局部最优即全局最优，KKT 条件成为充要：

$\nabla f(\mathbf{x}^*)+\sum_i\lambda_i\nabla g_i(\mathbf{x}^*)=\mathbf{0},\quad \lambda_i g_i(\mathbf{x}^*)=0$

故"线性/凸问题用 LP/QP"能拿到可证明最优；非凸则 KKT 仅是必要非充分，易卡局部。

整数规划分支定界：松弛整数约束得 LP 上界（最小化时） $\bar z$ ，求整数解得下界 $\underline z$ 。在搜索树上夹逼：当某节点下界 $\ge$ 当前最优上界，剪枝。最终上下界相等即最优。

启发式近似比：设算法输出目标 $f_{alg}$ ，真实最优 $f^*$ （最小化），近似比

$\rho=\frac{f_{alg}}{f^*}\ge1$

GA/PSO 的 $f_{alg}$ 随运行次数 $T$ 波动，应取多次独立运行的最优或均值，并给出 $\rho$ 的经验分布——这是"多次运行取统计优"的依据。

多目标帕累托：解集 $X$ 中 $x$ 帕累托占优 $y$ 当 $\forall k\ f_k(x)\le f_k(y)$ 且 $\exists k\ f_k(x)<f_k(y)$ 。帕累托前沿即不被占优的解集合；加权求和 $\sum w_k f_k$ 只能扫到前沿凸部分，非凸处会遗漏，故 NSGA-II 类直接搜索前沿更全。

五、选型流程（怎么选）

线性目标+线性约束 → 线性规划 LP（单纯形/lingo）。
含整数/0-1 决策 → 整数规划/IP、0-1 规划。
非线性可微 → 梯度下降/牛顿/拉格朗日乘子。
不可微/多峰/组合爆炸 → 遗传算法 GA / 粒子群 PSO / 模拟退火 SA。
多目标 → NSGA-II / 加权求和 / 理想点法。
用已知最优或下界验证算法质量。

六、问题 → 方法映射

LP/整数规划：精确解、可解释；规模大时慢。
GA/PSO/SA：鲁棒、易实现；参数敏感，要调参+多次运行取优。
多目标：输出帕累托前沿，再按偏好选解。

七、常见误选与对策

能精确解却用启发式 → 浪费且难证最优。
GA 只跑一次当最优 → 随机性，要多次+统计。
约束写错导致不可行 → 先小例子验证。
多目标直接加权不留前沿 → 掩盖权衡。

八、选型自检清单

已判断线性/非线性/整数
方法匹配问题结构
约束正确且可行
启发式多次运行取统计优
最优性/质量有验证

九、配套资源与搭配

智能优化算法代码集
算法速成手册（优化类）
建模避坑指南（编程雷区）

本指南由 MCM520 资料站自动生成（深度版），配套算法速成手册可在资源页下载。

10、实战案例

案例：优化问题选题

常见类型：路径优化、资源分配、调度问题
推荐模型：线性规划、整数规划、启发式算法

实战案例

优化类问题选型实战

场景：求目标最大/最小，约束各异，算法需匹配。
任务：按问题规模与类型选优化器。

完整代码（text）

选型矩阵：
| 类型 | 小规模 | 中规模 | 大规模 |
|------|--------|--------|--------|
| 线性 | Simplex | Simplex | 内点法 |
| 整数 | 分支定界 | 分支定界 | 启发式 |
| 非线性 | SQP | IPOPT | 元启发式 |
| 多目标 | NSGA-II | NSGA-III | MOEA/D |

案例：背包(0-1)→动态规划；TSP→遗传；调度→粒子群。

运行效果

选型案例：

生产计划(线性)→ LINGO/Simplex
路径优化(TSP)→ 遗传算法
多目标(成本+质量)→ NSGA-II
黑箱优化→ 贝叶斯优化
坑：非线性硬用线性≈→结果偏差大，先判问题类型。