从问题到模型：建模技巧

"最小化绝对值之和"看起来是非线性的，其实是一个标准的线性规划。诀窍是给每个数据点引入一个辅助变量 t_i，然后写两条线性约束把它夹住：t_i ≥ y_i − a·x_i − b 和 t_i ≥ −(y_i − a·x_i − b)，目标改成最小化 Σ t_i。因为目标在往下压 t_i，最优时它一定恰好等于那个绝对值。n 个点换来 n 个新变量和 2n 条约束——这就是最后一行读数的意思。同样的技巧可以处理最小最大问题："最小化最大偏差"只要引入一个 t，写 2n 条 t ≥ ±(...) 即可。但这一页真正想让你看见的是右边的对比。把"离群点个数"设成 2、"偏移"设成 40：红线（最小二乘）被拽到斜率 2.70，而绿线（最小一乘）还停在 1.64，真实值是 1.50。平方会放大大误差，所以少数几个离群点就能主导整条线；绝对值不放大，离群点只算一票。把离群点个数拖到 0 再看：这时最小二乘反而略好一点（1.58 对 1.60）——在纯高斯噪声下最小二乘是最有效率的估计，这是它的主场。所以选哪个不是品味问题：数据干净选二乘，数据脏选一乘，而"数据脏不脏"这件事，常常要等你画出这张图才知道。

"要么开工，要么不开工"是一句逻辑话，把它写进线性模型要靠 0-1 变量加一条链接约束。设 y_i ∈ {0,1} 表示第 i 个厂开不开，x_i 是它的产量，关键的一行是 x_i ≤ cap_i · y_i。这一行同时做了两件事：y_i = 0 时逼着 x_i = 0（没开工就不能生产），y_i = 1 时放开到产能上限。目标里就可以放心地写 Σ(f_i·y_i + c_i·x_i)。漏掉这一行会怎样？读数第三行给出了答案。如果你只按单位成本 c 从小到大装货、把固定成本当作事后再加，得到的方案往往会开一堆"单位成本很低但开厂费很贵"的厂，算下来比最优方案贵好几成。这是建模里最典型的一类错误：目标函数里写了某项成本，约束里却没有能触发它的机制。模型跑得出来、数字也漂亮，就是答案不对。实务上的检查方法很简单：把每个 0-1 变量拿出来问一句"是什么约束在逼它变成 1"，如果找不到，这个变量在模型里就是自由的，求解器一定会把它设成 0 来省钱。

同样是"分段线性"，凸的和非凸的难度差了一个量级。第一个选项是阶梯电价：单价随用量递增，总费用曲线是凸的。这种情况可以直接用普通 LP：把用量拆成三段 x₁+x₂+x₃，各段有上限，目标写成 1.0x₁+1.8x₂+3.0x₃。注意这里没有任何东西逼着"先用满第一档"——但因为第一档最便宜、目标是最小化，求解器自己就会先把便宜的段用满。凸性替你做了排序。换成第二个选项：批量折扣。单价随用量递减，费用曲线变成凹的。这时同样的写法就崩了：求解器会优先用最便宜的第三段，也就是直接跳到最大折扣，而不管前两档有没有用满。图上那条蓝虚线就是 LP 松弛实际认的费用——它是真实曲线的下凸包，永远低于或等于真实值。在 x=100 处，真实费用 244，LP 松弛只算 178.6，差了 27%。这就是为什么非凸的分段线性必须引入 0-1 变量（每段一个开关，加上"前一段用满才能用下一段"的约束），或者用 SOS2 让求解器只允许相邻两个断点非零。一个实用的判别法：把断点连起来，如果曲线向上弯（凸），普通 LP 就够；向下弯（凹），一定要上整数变量。最小化问题里凸的免费、凹的要钱；最大化问题里正好反过来。

大 M 有一个两难：太小会砍掉最优解，太大会让求解器算不动。这一页把两头都量出来给你看。先看左边（M 小的一侧）。M=15 时模型直接不可行——每个厂最多只能产 15，几个厂加起来凑不够需求。M=20 时可行了，但整数最优是 1242，而 M 足够大时的真正最优只有 443。接近三倍的差距，全是被那条 x ≤ M·y 人为砍出来的。这类错误特别隐蔽：模型跑得出来，返回一个看起来完全正常的最优解，你根本不会怀疑它已经把好方案排除在外了。再看右边（M 大的一侧），下面那张图更说明问题。M=80 时松弛间隙 10.7%，M=120 时 18.7%，滑杆推到头的 M=400 时 27.6%——真实模型里随手写的 999999 只会把它推得更高。为什么？因为 LP 松弛允许 y 取小数，它会把 y_i 设成 x_i/M——M 越大，这个数越接近 0，固定成本在松弛里就几乎不用付。而分支定界的效率完全取决于这个下界有多紧：间隙大一倍，搜索树可能大几个数量级。所以结论很明确：M 应该取"仍然有效的最小值"。在这个问题里就是各厂的真实产能上限 cap_i，而不是随手写的 999999。每个约束都该单独算它自己的 M，这几分钟的功夫，常常比换求解器更管用。