第一章 组合优化概述
大家好，我是这门课的主讲人。做了十几年算法优化，我最大的感受就是——组合优化这东西，听着高大上，其实就在我们身边。
你每天用导航软件找最快路线，快递公司安排货车送货，工厂排生产计划……这些背后，全是组合优化在干活。说白了，组合优化就是「在有限的选择里，找到最好的那个组合」。
什么是组合优化
先给个正式定义：组合优化是在一个有限的、离散的候选集合中，寻找满足约束条件的最优解。
嗯，这句话有点绕。我换个说法：
你面前有10个城市，你要找一条最短的路线，每个城市只去一次。这就是典型的组合优化问题——旅行商问题（TSP）。候选方案有多少？10! = 3628800种。你不可能一个个试，对吧？
组合优化的任务，就是用聪明的方法，从这海量方案里快速找到最优解，或者接近最优的解。
核心要点：组合优化的本质是「离散空间中的最优决策」。变量是整数、是0/1、是排列，而不是连续的小数。
组合优化问题的三要素
我习惯把每个组合优化问题拆成三块：决策变量、约束条件、目标函数。这三块搞清楚了，问题就清晰了一半。
1. 决策变量
你要决定什么？这就是决策变量。
- 物流调度：每辆车去哪个客户点？——0/1变量
- 路径规划：先走A还是先走B？——排列变量
- 资源分配：给项目A投多少钱？——整数变量
我在项目中遇到过一个问题：一开始把变量定义得太细，结果模型爆炸了。后来简化变量，反而跑得更快。记住：变量不是越多越好，够用就行。
2. 约束条件
现实世界总有各种限制。你不能让一辆车同时出现在两个地方，对吧？
- 容量约束：货车不能超载
- 时间窗约束：必须在上午10点前送达
- 资源约束：只有3台机器可用
避坑指南：我曾经在项目里漏掉了一个「司机连续驾驶不能超过4小时」的约束，结果模型给出的方案在现实中根本没法用。约束条件一定要和业务方反复确认，少一条都不行。
3. 目标函数
你想优化什么？
- 最小化总运输距离
- 最小化总成本
- 最大化客户满意度
- 最小化总完成时间
你想想看，有时候多个目标会冲突。比如你想成本最低，又想速度最快——这俩往往不能兼得。这时候就需要权衡，或者做成多目标优化。
组合优化与连续优化的区别
这个问题，我经常被问到。其实区别很直观：
| 对比维度 | 组合优化 | 连续优化 |
|---|---|---|
| 变量类型 | 整数、0/1、排列 | 实数 |
| 解空间 | 离散、有限但巨大 | 连续、无限 |
| 常用方法 | 分支定界、启发式算法 | 梯度下降、牛顿法 |
| 难度来源 | 组合爆炸 | 非凸、非线性 |
连续优化可以用导数找方向，组合优化不行。你没法对「走哪条路」求导，对吧？所以组合优化需要完全不同的工具。
组合优化在实际中的应用
说了这么多理论，来点实际的。我挑三个最常见的场景聊聊。
物流调度
这是组合优化的「主战场」。每天几万辆货车在城市里穿梭，怎么安排路线、怎么分配货物，全是组合优化问题。
我记得有个项目，帮一家快递公司优化配送路线。原来司机凭经验跑，一天送80单。用了优化模型后，一天能送110单，效率提升了近40%。
路径规划
不只是导航。无人机巡检、机器人路径规划、电路板钻孔……这些都需要找最优路径。
说白了，路径规划就是「在图上找一条满足约束的最优路径」。约束可能是时间、能耗、安全性等等。
资源分配
资源总是有限的。怎么把有限的资源分给多个任务，让整体效益最大？
- 云计算：把计算任务分配给服务器
- 生产制造：把订单分配给机器
- 项目管理：把人力分配给任务
个人经验：做资源分配问题，我建议先从「最简单的约束」开始建模。先跑通一个基础版本，再逐步加约束。一上来就想把所有细节都塞进去，模型很容易跑不动。
本章知识体系
下面这张图，是我梳理的本章核心逻辑。你可以把它当作一个「地图」，后面每章都会在这个框架里展开。
这张图把本章内容串起来了。左边是「三要素」，中间是和连续优化的对比，右边是实际应用场景。后面每章都会围绕这些核心概念展开。
好了，第一章就到这里。记住三要素：决策变量、约束条件、目标函数。这是你后面所有建模的基础。
公众号:蓝海资料掘金营，微信deep3321