优化问题

在约束条件下寻找使目标函数最好的一组决策。真正困难的通常不是调用求解器，而是把目标、变量、约束和可行性写对。

这一门类解决什么问题

数学建模中的「优化问题」可以概括为：在一组可行决策中，选出使得某个（或多个）目标尽可能好的方案。题目往往已经隐含了资源限制、逻辑约束、时间窗口或网络结构，建模者需要把这些信息翻译成可求解的数学形式。

学习本门类时，先把题目中的输入、输出、约束和不确定性说清楚，再选择能够回答问题且可以验证的方法。复杂模型只有在基础方法无法解释关键现象时才有必要。

常见输出并不是「一个最优数字」本身，而是：

• 最优决策变量（产量、路径、选址、排班等）；
• 最优目标值及其可解释含义；
• 约束是否活跃、资源是否紧张；
• 最优性证明或间隙（gap）、敏感性结论；
• 在多目标情形下的权衡曲线或满意解。

如何选择方法

选型应优先「能精确求解、可解释、可复现」的方法，再逐步放宽。

问题信号	优先考虑	说明
目标与约束均为线性，变量连续	线性规划（LP）	首选。linprog 可求全局最优，对偶与影子价格可解释资源价值
变量必须取整数（人数、台数、车次）	整数规划（IP）	在 LP 基础上加整数约束；规模中等时 intlinprog 常够用
决策是「是否」二选一	0-1 规划	选址、指派、背包、开关机等；注意线性化技巧
同时含连续与整数变量	混合整数线性规划（MILP）	生产计划、库存+开关、设施选址+流量等标准形态
多个相互冲突的目标	多目标规划	先用加权法、ε-约束或目标规划；不要假装只有一个目标
目标/约束光滑非线性，可求导	非线性规划（NLP）	fmincon、梯度法、牛顿法；凸问题有全局最优保证
带等式/不等式约束的最优性刻画	拉格朗日 / KKT	用于推导条件、检验候选点，不一定替代数值求解
具有阶段递推、最优子结构	动态规划（DP）	背包、路径分段、库存多期、资源分配等
图上的路径、树、流、费用	网络优化	最短路、最小生成树、最大流、最小费用流；优先专用算法
目标非凸、黑箱、组合爆炸且精确法不可行	智能优化（仅作兜底）	遗传算法、模拟退火、粒子群等；必须与基线比较

这张表用于初步定位，不是机械的选型规则。最终选择还要结合变量规模、数据质量、解释需求和验证条件。

何时用线性规划

当决策变量可视为连续（或松弛后连续即可），目标与约束都能写成线性式时，应毫不犹豫地先建 LP。即便最终需要整数解，LP 松弛也能提供下界、检验建模是否正确，并帮助发现冗余约束。

何时升级到整数 / 0-1 / 混合整数

出现「人数必须整数」「设备要么开要么关」「线路要么建要么不建」时，才引入整数约束。整数会显著增加难度：同样规模下 MILP 可能比 LP 慢几个数量级。建模时应尽量：

1. 先写清逻辑，再写成线性不等式；
2. 用紧的大 M、避免不必要的整数变量；
3. 报告求解状态、相对间隙（relative gap）与时间限制。

何时用非线性规划

目标或约束中出现二次项、比值、指数、对数等，且无法合理线性化时，进入 NLP。若问题是凸的，局部最优即全局最优；若非凸，需多初值、全局优化或接受局部最优并说明。

何时用动态规划与网络算法

若问题天然按阶段展开（天、站、层），或定义在图上，优先 DP 或网络专用算法，而不是一上来用通用整数规划硬套。专用算法往往更快、更稳，也更容易写清复杂度。

何时才考虑智能优化

智能优化（元启发式）仅作兜底，触发条件应同时接近下列情形：

1. 精确方法（LP/MILP/凸 NLP/网络算法/DP）在时限内不可行或模型无法写紧；
2. 已有简单基线（贪心、随机搜索、松弛圆整、局部搜索）；
3. 能定义清晰的目标评价与约束处理（罚函数、修复算子）；
4. 结果以统计方式报告：随机种子、多次独立运行、均值/最优/方差，并与基线比较。

禁止在能用 linprog/intlinprog 精确求解的小规模线性整数问题上，直接宣称遗传算法「求出了最优解」。

推荐学习顺序

1. 线性规划与对偶解释：建立「目标—约束—可行域—最优」的完整语言。
2. 整数 / 0-1 / MILP：学会把逻辑写成线性约束，并读懂求解器输出。
3. 多目标规划：理解权衡，而不是强行合成单一分数。
4. 非线性规划与 KKT：从无约束到有约束，从算法到最优性条件。
5. 动态规划与网络优化：利用结构降维，避免通用求解器暴力搜索。
6. 智能优化：只在前述路径走不通时使用，并严格做可复现实验。

建模检查清单

动手写代码前，建议逐条确认：

1. 决策变量是什么？连续、整数还是 0-1？单位与量纲是否明确？
2. 目标是最大化还是最小化？是否只有一个目标？
3. 约束是否穷尽？资源、逻辑、流量守恒、上下界是否都写了？
4. 可行性：空模型（只求可行）能否先跑通？
5. 尺度：系数数量级是否相差过大？是否需要规范化？
6. 验证：特殊情形（无约束、单变量、已知答案的小例子）是否通过？
7. 报告：最优值、解向量、活跃约束、求解状态、间隙或与基线差距。

使用提醒

• 先验证可行性，再谈目标值优劣；不可行时优先检查约束冲突，而不是换算法。
• 线性与凸问题应报告全局最优；非凸与启发式应明确「局部 / 近优」。
• 整数规划报告最优性间隙、下界或时间限制下的 incumbent。
• 智能优化得到的是候选近优解，不能默认宣称全局最优；必须固定并报告随机种子。
• 结果解释应回到业务语言：多生产一单位的边际价值、哪条路最关键、哪个约束真正卡脖子。

进入具体方法页后，建议依次阅读直观理解、适用边界、核心原理、关键决策、MATLAB 实践、结果解释和常见误区，并亲自复现示例。