数学规划与优化算法
把「怎样最好」写成目标函数加约束，剩下的交给算法。竞赛里最硬的一块工具。
这个模块讲什么
优化是建模里唯一能给出「最优」两个字的部分，也因此最容易被误用——目标写错一点，算出来的最优解就完美地解决了一个错误的问题。这个模块从线性规划的几何直觉开始，把单纯形、对偶、分支定界这些平时只能背结论的东西画出来；后半段讲当问题不再是凸的、规模不再小的时候，启发式算法怎么在「够好」和「算得完」之间取舍。
9专题
35实验台
专题列表
每个专题是一个独立页面，页内按实验台组织。下面列出的是每一页会做的实验。
4.1
线性规划
已上线可行域是个多面体，最优解在顶点上。把这句话画出来，单纯形法就不神秘了。
01二维可行域拖动约束直线，实时看可行域形状与最优顶点的移动
02单纯形路径在顶点之间跳，每一步显示当前基与目标值
03对偶与影子价格松一点约束，目标值涨多少——影子价格的意义当场量出来
04灵敏度分析系数在多大范围内变动，最优基不变
4.2
整数规划
已上线加上「必须是整数」四个字，问题难度就从多项式跳到 NP 难。分支定界是怎么在指数空间里省力的。
01松弛与取整的陷阱线性松弛的解四舍五入，为什么常常既不可行也不最优
02分支定界树看搜索树怎么长、界怎么剪枝，剪掉了多少节点
03割平面一刀一刀削掉非整数顶点，可行域慢慢逼近整数壳
040-1 背包与指派两个最常考的模型，动态规划与匈牙利算法的解法对照
4.3
非线性与凸优化
已上线凸不凸，决定了你是在找「一个最优」还是在「碰运气」。梯度、KKT、拉格朗日乘子的几何含义。
01梯度下降轨迹在等高线图上画出迭代轨迹，学习率太大太小都看得见
02凸与非凸同一个算法在两种地形上的命运对比
03拉格朗日乘子约束曲线与等高线相切的那一刻，就是乘子的几何含义
04KKT 条件带不等式约束时，哪些约束「起作用」
4.4
启发式与元启发式
已上线问题大到无法穷举时，退火、遗传、粒子群靠的是「有策略的乱试」。每一台都配了一张专门画机制的图。
01模拟退火解 TSP温度曲线与当前路径同屏，看降温太快怎么卡在局部最优
02遗传算法种群、交叉、变异逐代演化，适应度曲线实时上升
03粒子群一群粒子在地形上找谷底，惯性与社会项的权重可调
04蚁群算法信息素矩阵可视化，与涌现模块的蚁群觅食共用同一套机制
05大爆炸—大坍缩只靠一个会自己缩小的撒布半径就能收敛，元启发式最干净的骨架
06禁忌搜索不掷骰子也敢变差：被禁的边逼着它爬出局部最优
07差分进化步长不用人定，种群自己散开又收拢，把它一起缩小
4.5
多目标优化
已上线成本要低、质量要高、时间要短——三个目标互相打架时，「最优」不再是一个点，而是一条前沿。
01Pareto 前沿在两个目标的平面上，看哪些解被支配、哪些留在前沿上
02权重法与 ε-约束法换权重扫出前沿，看凹陷段为什么扫不到
03NSGA-II 思想非支配排序与拥挤距离，让种群沿前沿均匀铺开
4.6
动态规划
已上线把一个大问题拆成一串小问题，每个小问题只算一次。动态规划不是某个算法，是一种"别重复算"的纪律。
01从递归到备忘斐波那契：指数级的调用树，加一行缓存就变成线性
02背包的状态表一格一格填出那张二维表，再沿着来路把方案倒推回去
03最短路与编辑距离两个看着毫无关系的问题，状态转移方程几乎一模一样
04什么时候不能用最优子结构与无后效性：破坏其中一条，答案就错在哪里
4.7
博弈与均衡
已上线当你的最优选择取决于对手怎么选，最优化就变成了博弈。纳什均衡是这类问题的"解"，而零和博弈的解恰好就是一个线性规划。
01双矩阵博弈改收益矩阵，看纯策略均衡出现、消失，混合均衡接上
02零和博弈与线性规划最小最大定理：把博弈的值算成一个 LP 的最优值
03演化稳定策略一个策略能不能挡住小股入侵者——用动力学而不是理性来定均衡
04拍卖与机制一价、二价、英式：出价策略变了，卖家收入却可能一样
4.8
不确定下的优化
已上线需求、天气、价格都不确定时，"先定下来再看结果"和"看了再定"是两套完全不同的模型。报童问题是最小的例子。
01报童问题一个临界分位数就定下了最优订货量，看它随成本比例怎么移动
02两阶段随机规划先建产能再看需求：情景树上算期望成本
03鲁棒优化不问概率只问最坏：不确定集一放大，解怎么变保守
04机会约束允许 5% 的概率违约，成本能省多少
4.9
从问题到模型：建模技巧
已上线竞赛里最卡人的往往不是解法，是"怎么把这段话写成约束"。绝对值、逻辑或、固定成本、分段线性，都有标准写法。
01绝对值与最小最大非线性的目标怎么用两条线性约束换掉
02大 M 与逻辑约束"要么开工要么不开工"：0-1 变量把 if-then 写成不等式
03分段线性阶梯电价、批量折扣：用 SOS2 或增量法把折线塞进 LP
04大 M 取多大M 太小会砍掉最优解，太大求解器会崩——现场看它崩给你