大M法

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 4.5k 阅读时长 ≈ 4 分钟

大 M 法：将非线性约束线性化的线性规划技巧

在实际优化问题中，常遇到 “要么不做，要么必须达到某个阈值” 的非线性约束（如广告投放 “要么不投，要么至少投 100cpm”）。大 M 法（Big M Method）通过引入二进制变量和一个足够大的常数 M，将这类非线性约束转化为线性约束，从而用线性规划求解。本文结合广告投放场景，详细解析大 M 法的应用。

问题场景与核心约束

场景定义

  • 需投放广告至至少 2 个城市，共 3 个城市可选（记为城市 1、2、3）。
  • 每个城市的投放规则：要么不投（投放量 = 0），要么至少投 100cpm（cpm 为投放单位）。
  • 总投放量≥3000cpm，目标是最小化总成本（城市 1、2、3 的单位成本分别为 5、6、23）。

核心非线性约束

每个城市的投放量c_i（i=1,2,3）存在 “0 或≥100” 的非线性选择，即：
c_i = 0 或 c_i ≥ 100

这类约束无法直接用线性规划表达，需通过大 M 法转化。

大 M 法的核心思路

1. 引入二进制变量

为每个城市引入二进制变量ca_i（0 或 1），表示投放决策：

  • ca_i = 0：城市 i投放（此时需满足c_i ≥ 100）。
  • ca_i = 1：城市 i不投放（此时需满足c_i = 0）。

2. 定义大 M

选择一个足够大的常数 M（需大于实际可能的最大投放量）。在本例中，总投放量≥3000cpm，单个城市最大可能投放量为 3000cpm，因此可取M=5000（确保覆盖所有可能情况）。

3. 将非线性约束转化为线性约束

通过ca_i和 M，将 “c_i=0 或 c_i≥100” 转化为两个线性约束：

（1）投放时的下限约束

当ca_i=0（投放），需c_i ≥ 100；当ca_i=1（不投），该约束不影响（因c_i=0）。
转化为：c_i ≥ 100×(1 - ca_i)

  • 解释：ca_i=0时，c_i ≥ 100×1=100（满足投放下限）；ca_i=1时，c_i ≥ 100×0=0（不影响不投放的c_i=0）。
（2）不投放时的上限约束

当ca_i=1（不投），需c_i=0；当ca_i=0（投放），该约束不影响（因c_i可大至 M）。
转化为：c_i ≤ M×(1 - ca_i)

  • 解释：ca_i=1时，c_i ≤ M×0=0（结合c_i≥0的变量下界，得c_i=0）；ca_i=0时，c_i ≤ M×1=5000（远大于最大可能投放量，无实际限制）。

4. 补充约束（满足场景要求）

  • 至少投放 2 个城市：即 “不投放的城市最多 1 个”，对应二进制变量约束：
    ca_1 + ca_2 + ca_3 ≤ 1（ca_i=1表示不投，和≤1 意味着最多 1 个城市不投）。
  • 总投放量下限：c_1 + c_2 + c_3 ≥ 3000。

线性规划模型完整构建

变量定义

  • 连续变量（投放量）：c_1, c_2, c_3（≥0，单位：cpm）。
  • 二进制变量（投放决策）：ca_1, ca_2, ca_3（0或1）。

目标函数（最小化总成本）

min z = 5c_1 + 6c_2 + 23c_3

约束条件

  1. 单个城市投放约束（大 M 法核心）：
    • 城市 1：c_1 ≥ 100(1 - ca_1) 且 c_1 ≤ 5000(1 - ca_1)
    • 城市 2：c_2 ≥ 100(1 - ca_2) 且 c_2 ≤ 5000(1 - ca_2)
    • 城市 3：c_3 ≥ 100(1 - ca_3) 且 c_3 ≤ 5000(1 - ca_3)
  2. 至少投放 2 个城市：ca_1 + ca_2 + ca_3 ≤ 1
  3. 总投放量下限：c_1 + c_2 + c_3 ≥ 3000

代码实现与结果解析

代码实现（基于 ojAlgo+OR-Tools）

import org.ojalgo.optimisation.*;
import org.ojalgo.optimisation.Variable;

public class BigMMethodDemo {
    public static void main(String[] args) {
        // 1. 创建模型
        ExpressionsBasedModel model = new ExpressionsBasedModel();

        // 2. 定义变量：投放量c1, c2, c3（非负整数）
        Variable c1 = Variable.makeInteger("c1").lower(0).weight(5); // 成本系数5
        Variable c2 = Variable.makeInteger("c2").lower(0).weight(6); // 成本系数6
        Variable c3 = Variable.makeInteger("c3").lower(0).weight(23); // 成本系数23
        model.addVariable(c1);
        model.addVariable(c2);
        model.addVariable(c3);

        // 3. 定义二进制变量：ca1, ca2, ca3（0或1，不影响成本）
        Variable ca1 = Variable.makeBinary("ca1").weight(0);
        Variable ca2 = Variable.makeBinary("ca2").weight(0);
        Variable ca3 = Variable.makeBinary("ca3").weight(0);
        model.addVariable(ca1);
        model.addVariable(ca2);
        model.addVariable(ca3);

        // 4. 约束1：单个城市投放规则（大M法）
        int M = 5000; // 大M值

        // 城市1：c1 ≥ 100(1 - ca1) 且 c1 ≤ M(1 - ca1)
        Expression c1Lower = model.addExpression("c1Lower");
        c1Lower.set(c1, 1).set(ca1, -100).lower(100); // c1 - 100ca1 ≥ 100 → c1 ≥ 100(1 - ca1)
        Expression c1Upper = model.addExpression("c1Upper");
        c1Upper.set(c1, 1).set(ca1, -M).upper(0); // c1 - M*ca1 ≤ 0 → c1 ≤ M*ca1？不，正确应为c1 ≤ M(1 - ca1) → c1 + M*ca1 ≤ M
        // 修正c1Upper：c1 + M*ca1 ≤ M
        c1Upper = model.addExpression("c1Upper");
        c1Upper.set(c1, 1).set(ca1, M).upper(M);

        // 城市2：c2 ≥ 100(1 - ca2) 且 c2 ≤ M(1 - ca2)
        Expression c2Lower = model.addExpression("c2Lower");
        c2Lower.set(c2, 1).set(ca2, -100).lower(100);
        Expression c2Upper = model.addExpression("c2Upper");
        c2Upper.set(c2, 1).set(ca2, M).upper(M);

        // 城市3：c3 ≥ 100(1 - ca3) 且 c3 ≤ M(1 - ca3)
        Expression c3Lower = model.addExpression("c3Lower");
        c3Lower.set(c3, 1).set(ca3, -100).lower(100);
        Expression c3Upper = model.addExpression("c3Upper");
        c3Upper.set(c3, 1).set(ca3, M).upper(M);

        // 5. 约束2：至少投放2个城市（最多1个不投）
        Expression minCities = model.addExpression("minCities");
        minCities.set(ca1, 1).set(ca2, 1).set(ca3, 1).upper(1);

        // 6. 约束3：总投放量≥3000
        Expression totalVolume = model.addExpression("totalVolume");
        totalVolume.set(c1, 1).set(c2, 1).set(c3, 1).lower(3000);

        // 7. 目标：最小化成本
        model.setOptimisationSense(Optimisation.Sense.MIN);

        // 8. 用OR-Tools求解
        SolverORTools solver = SolverORTools.INTEGRATION.build(model);
        Optimisation.Result result = solver.solve(null);

        // 9. 输出结果
        System.out.println("求解状态：" + result.getState());
        System.out.println("最小总成本：" + result.getValue());
        System.out.println("变量解：");
        double[] solution = result.getSolution();
        System.out.println("c1=" + solution[0] + ", c2=" + solution[1] + ", c3=" + solution[2]);
        System.out.println("ca1=" + solution[3] + ", ca2=" + solution[4] + ", ca3=" + solution[5]);
    }
}

结果解析

求解状态：OPTIMAL
最小总成本：15100.0
变量解：
c1=2900.0, c2=100.0, c3=0.0
ca1=0.0, ca2=0.0, ca3=1.0
  • 决策解读：
    • ca1=0、ca2=0：城市 1 和 2 投放；ca3=1：城市 3 不投（满足 “至少 2 个城市投放”）。
    • 投放量：c1=2900（≥100）、c2=100（≥100）、c3=0（不投），总投放量 = 3000（满足下限）。
    • 成本：5×2900 + 6×100 = 14500 + 600 = 15100，为最小成本（优先投放单位成本低的城市 1 和 2）。

大 M 法的关键注意事项

  1. M 的选择：
    • M 需足够大（覆盖可能的最大变量值），但不宜过大（避免数值计算误差）。本例中 M=5000（大于最大可能投放量 3000）。
  2. 二进制变量的作用：
    二进制变量是 “开关”，通过 0/1 状态控制约束的生效与否，实现 “二选一” 的非线性逻辑。
  3. 适用场景：
    适用于 “要么满足 A，要么满足 B” 的离散选择约束，如生产中的 “要么不生产，要么生产≥100 件”、运输中的 “要么不运输，要么运输≥5 吨” 等。

总结

大 M 法通过引入二进制变量和常数 M，将非线性的 “二选一” 约束转化为线性约束，使原本无法用线性规划求解的问题变得可解。在广告投放场景中，它成功解决了 “要么不投，要么至少投 100cpm” 且 “至少投 2 个城市” 的约束，实现了总成本最小化