跳到主要内容

混合整数线性规划

一、直观理解：开关是整数，流量是连续的​

混合整数线性规划（Mixed-Integer Linear Programming, MILP）同时包含：

  • 整数 / 0-1 变量：开不开厂、用不用某条线、第几天检修；
  • 连续变量：产量、运输量、库存、功率。

现实中的计划问题几乎都是这种「骨架离散、血肉连续」的结构。例如：

  • 是否启用某台机器（0-1），启用后在产能范围内连续安排工时；
  • 是否建设配送中心（0-1），建成后连续分配客户需求量；
  • 是否在某时段充电（0-1），充电功率连续可调。

MILP 仍要求目标与约束对所有变量是线性的。它是数学建模里处理复杂运营决策的「首选重型武器」：能建 MILP 并在时限内求得可接受间隙，就不要先上智能优化。

二、适用场景与优缺点​

类型说明
适用场景生产计划与排程、设施选址+运输、库存-路径、电网机组组合（简化线性）、项目选择+资源连续分配、带固定成本的网络设计。
核心优点表达力远强于纯 LP；精确求解器（intlinprog 等）可给界与证明；固定成本、逻辑、分段线性（多段）均可建模。
局限与缺点计算难度通常由整数部分主导；弱公式导致长时间高间隙；非线性物理规律需近似；调参与建模经验要求高。

使用前确认：

  1. 整数变量是否必要、能否减少；
  2. 固定成本、若则逻辑是否用紧的大 M 或 indicator 思路表达；
  3. 连续部分上下界是否合理；
  4. 可接受的时间与 gap；
  5. 是否有自然分解（先选址后分配等）便于检验。

三、核心原理：LP 松弛 + 离散决策​

1. 标准形式​

min⁡cxTx+cyTys.t.Axx+Ayy≤bℓx≤x≤ux,ℓy≤y≤uyyj∈Z （或 {0,1}）\begin{aligned} \min\quad & c_x^\mathsf{T}x+c_y^\mathsf{T}y \\ \text{s.t.}\quad & A_x x+A_y y\le b \\ & \ell_x\le x\le u_x,\quad \ell_y\le y\le u_y \\ & y_j\in\mathbb{Z}\ \text{（或 }\{0,1\}\text{）} \end{aligned}

xx 连续，yy 整数。求解仍主要依赖 Branch-and-Cut：对整数分量分支，节点上解 LP 松弛。

2. 固定成本结构​

活动水平 x≥0x\ge 0，是否开展 y∈{0,1}y\in\{0,1\}，固定成本 ff，变动成本 cc：

min⁡ cx+fy,0≤x≤Uy\min\ cx+fy,\quad 0\le x\le U y

无 yy 时强制 x=0x=0 且不付 ff；有 yy 时付 ff 且 xx 可至 UU。

3. 分段线性（凸/非凸）​

成本随用量呈折线时，可用多个连续片段变量 + 0-1 选择段，或用特殊有序集（SOS2）思想。非凸分段必须借助整数，否则 LP 会「抄近路」。

4. 与纯 IP、纯 LP 的关系​

  • 无整数 → LP；
  • 无连续 → 纯 IP / 0-1；
  • MILP 是二者的合流，也是多数竞赛「规划类」大题的最终形态。

四、关键决策​

1. 公式强度（formulation strength）​

同样逻辑，不同不等式的 LP 松弛可紧可松。优先：

  • 最小必要大 M；
  • 聚合并约束、覆盖不等式等；
  • 避免把本可连续的量设为整数。

2. 尺度与单位​

连续流量可能是 10510^5，0-1 系数是 11，注意约束中系数平衡，必要时缩放连续变量。

3. 初始可行解​

先用启发式构造一组可行的 (x,y)(x,y)，再让求解器改进并证明，常比冷启动快。

4. 终止与报告​

设定 MaxTime、RelativeGapTolerance。终稿必须写清：是否最优、gap、时间、机器环境（可选）。

5. 验证​

固定所有整数变量后，剩余应是 LP，可用 linprog 复核连续部分；也可固定 yy 做 what-if 分析。

五、MATLAB 示例​

带固定成本的生产：两种产品，连续产量 x1,x2x_1,x_2；是否生产 y1,y2∈{0,1}y_1,y_2\in\{0,1\}。

min⁡3x1+4x2+20y1+15y2s.t.x1+x2≥10（需求）x1≤8y1,x2≤9y2x≥0, y∈{0,1}\begin{aligned} \min\quad & 3x_1+4x_2+20y_1+15y_2 \\ \text{s.t.}\quad & x_1+x_2\ge 10 \quad \text{（需求）}\\ & x_1\le 8y_1,\quad x_2\le 9y_2 \\ & x\ge 0,\ y\in\{0,1\} \end{aligned} 
% 变量 z = [x1; x2; y1; y2]
f = [3; 4; 20; 15];

% x1 + x2 >= 10  ->  -x1 -x2 <= -10
% x1 - 8 y1 <= 0
% x2 - 9 y2 <= 0
A = [
   -1, -1,  0,  0;
    1,  0, -8,  0;
    0,  1,  0, -9
];
b = [-10; 0; 0];

lb = [0; 0; 0; 0];
ub = [8; 9; 1; 1];
intcon = [3, 4];   % 仅 y 为整数（0-1）

opts = optimoptions("intlinprog", ...
    "Display", "iter", ...
    "MaxTime", 60, ...
    "RelativeGapTolerance", 1e-4);

[z, fval, exitflag, output] = intlinprog( ...
    f, intcon, A, b, [], [], lb, ub, opts);

x = z(1:2); y = z(3:4);
fprintf("exitflag=%d, 成本=%g, gap=%g\n", ...
    exitflag, fval, output.relativegap);
fprintf("产量 x = [%.4f, %.4f], 开关 y = [%g, %g]\n", ...
    x(1), x(2), y(1), y(2));

% 固定 y 后用 LP 复核
yFix = round(y);
A_lp = [-1, -1; 1, 0; 0, 1];
b_lp = [-10; 8*yFix(1); 9*yFix(2)];
[x2, f2] = linprog([3;4], A_lp, b_lp, [], [], [0;0], [8;9]);
fprintf("固定 y 后连续最优成本（含固定成本）= %g\n", ...
    f2 + 20*yFix(1) + 15*yFix(2));

选址-分配（有容量）也可写成 MILP：0-1 建仓 + 连续运量，容量约束 ∑ixij≤Capjyj \sum_i x_{ij}\le Cap_j y_j。

六、如何解释结果​

完整结果应包括：

  1. 整数决策（开哪些、选哪些）与连续决策（产多少、运多少）分开陈述；
  2. 总成本/利润构成：固定部分 vs 变动部分；
  3. 容量与逻辑约束是否绑紧；
  4. exitflag、相对间隙、求解时间；
  5. 与「强制全开」「全关不可行」等对照方案的差值；
  6. 管理含义：固定成本是否被规模摊薄、哪个设施处于临界。

好的表述：「仅开启产线 2，产量 10，总费用 55；若两线都开，变动成本下降但固定成本上升，总费用反而更高。」

七、常见误区​

1. 把 MILP 当成「LP 加 round」​

整数与连续耦合时，圆整连续最优通常既不正也不优。

2. 所有变量都标成整数​

产量本可连续却设为整数，只会更慢；只对真正离散的决策用 intcon。

3. 固定成本用非线性写法​

f⋅1x>0f\cdot\mathbf{1}_{x>0} 不能直接进线性求解器；必须引入 0-1 与 x≤Uyx\le Uy。

4. 间隙很大仍当精确最优​

报告「当前最好方案」与「下界」两者，避免误导。

5. 过早转向遗传算法​

先改进公式、加界、给初值、延长时间；确认精确法不可行后，启发式才能作为兜底，并与 MILP 下界比较。

6. 忽略不可行诊断​

需求超过「全部设施开启」的总容量时模型必不可行。先做最大流/简单容量检查。

八、小结​

混合整数线性规划的核心思想可以概括为：

用整数变量编码离散结构，用连续变量描述数量流动，在全部线性约束下联合优化；求解器通过松弛与分支给出可行方案及最优性间隙。

它是连接「逻辑选择」与「资源配置」的标准框架，应作为复杂运营类题目的首选。写紧公式、分清变量类型、诚实报告 gap，再考虑是否需要非线性或智能优化扩展。