1、组合优化概述：定义、应用场景与问题分类
大家好，我是这门课的主讲人。今天咱们聊聊组合优化的开篇内容。
说实话，我第一次接触组合优化是在做物流路径规划的项目里。当时老板丢给我一个任务：给200个配送点排路线，要求成本最低。我心想这还不简单？结果一算，可能的方案数量比宇宙中的原子还多……嗯，从那以后我就老老实实开始啃组合优化了。
1.1 什么是组合优化？
组合优化，说白了就是从有限个离散方案里，找出最好的那个。
你想想看，生活中到处都是这种问题：
- 快递小哥怎么走最省油？
- 工厂里先做哪个订单最赚钱？
- 投资组合里买哪几只股票风险最小？
这些问题都有一个共同点：候选方案是有限的、离散的，但数量往往大得吓人。
核心定义：组合优化 = 在离散的可行解集合中，寻找使目标函数最优的解。
数学上可以写成：
min f(x) 或 max f(x)
subject to x ∈ X
其中 X 是有限或可数无限的离散集合
f(x) 是目标函数（比如成本、时间、收益）我个人习惯把组合优化问题拆成三块来看：决策变量、约束条件、目标函数。搞清楚了这三样，问题就清晰了一半。
1.2 应用场景：我踩过的坑
组合优化不是纸上谈兵。我在实际项目中遇到过不少典型案例，挑几个说说：
物流领域
最经典的就是车辆路径问题（VRP）。我曾经给一家生鲜电商做配送优化，200个订单点，30辆车，要求在3小时内送完。一开始我用贪心算法，结果有一辆车跑了80公里，司机直接罢工……后来改用遗传算法+局部搜索，总里程降了18%。
避坑指南：我曾经以为算法越复杂越好，结果发现实际落地时，计算时间才是最大的敌人。客户要的是5分钟内出方案，不是最优解但等半小时。
调度领域
车间调度问题（JSP）我也做过。一个工厂有5台机器、20个工件，每个工件要经过不同的工序。我一开始用整数规划，求解器跑了2小时还没出结果。后来改用启发式算法，30秒搞定，虽然不是最优，但工厂老板说“够用了”。
金融领域
投资组合优化，说白了就是怎么分配资金让风险最小、收益最大。我记得有个量化团队找我帮忙，他们用均值-方差模型，但约束条件一多（比如不能买超过5%的某只股票），模型就变得特别难解。最后我们用二次规划+启发式才搞定。
| 领域 | 典型问题 | 我的经验 |
|---|---|---|
| 物流 | 车辆路径、仓库选址 | 实际约束比论文多得多（比如司机休息时间） |
| 调度 | 车间调度、员工排班 | 实时性要求高，算法必须快 |
| 金融 | 投资组合、风险管理 | 数据噪声大，模型要鲁棒 |
1.3 问题分类：P vs NP
这里要聊一个绕不开的话题：P vs NP。
你想想看，为什么有些问题好解，有些问题难解？
P类问题：能在多项式时间内找到解。比如排序、最短路径。我刚开始学算法时，觉得所有问题都应该属于P类……直到遇到了旅行商问题。
NP类问题：能在多项式时间内验证一个解是否正确，但找到解可能很难。比如：
- 旅行商问题（TSP）
- 背包问题
- 图着色问题
NP完全问题（NPC）：NP里最难的那一批。只要有一个NPC问题能被快速求解，所有NP问题都能快速求解。嗯，目前还没人做到。
注意：我见过不少新手一上来就想找“最优解”，结果发现问题是NP难的，求解器跑了一天都没结果。这时候就要考虑近似算法或启发式算法了。
为什么会这样？因为组合优化问题的解空间往往是指数级增长的。比如：
- 10个城市的TSP：约181,440种路线
- 20个城市：约6×10¹⁶种路线
- 50个城市：比宇宙原子总数还多
所以，不是所有问题都值得求最优解。我在项目中经常用“95%最优”的方案，客户已经非常满意了。
1.4 课程目标与路线图
这门课的目标很明确：让你能动手解决实际的组合优化问题。
我们会从基础讲起，逐步深入到实战。下面是知识体系图：
具体来说，我们会覆盖：
- 基础篇：贪心、动态规划、分支定界——这些是基本功，我建议你熟练掌握
- 进阶篇：遗传算法、模拟退火、蚁群算法——处理大规模问题的利器
- 实战篇：物流路径优化、车间调度、投资组合——直接拿来用的代码
我的建议：不要跳过基础篇直接看实战。我曾经带过一个实习生，上来就想用遗传算法解TSP，结果连“邻域搜索”是什么都没搞懂……嗯，后来他老老实实回去补基础了。
好了，第一章就到这里。记住一句话：组合优化不是魔法，是工程。后面我们会一步步把每个方法讲透、写透。
公众号:蓝海资料掘金营，微信deep3321