如何使用 SciPy 的 milp 高效求解整数线性规划油漆采购优化问题-Python教程-PHP中文网

如何使用 SciPy 的 milp 高效求解整数线性规划油漆采购优化问题

本文详解如何正确调用 scipy.optimize.milp 求解带整数约束的最小成本油漆采购问题，涵盖目标函数、约束构建、变量边界、整数声明等关键配置，并指出常见误用（如错误缩放系数、混淆不等式方向）及其修正方法。

本文详解如何正确调用 scipy.optimize.milp 求解带整数约束的最小成本油漆采购问题，涵盖目标函数、约束构建、变量边界、整数声明等关键配置，并指出常见误用（如错误缩放系数、混淆不等式方向）及其修正方法。

在使用 SciPy 进行整数线性规划（ILP）建模时，核心挑战往往不在于算法本身，而在于问题到标准数学形式的准确转换。以油漆采购优化为例：需用不同规格（体积、单位面积耗量、单价）的油漆罐，以最低总成本覆盖指定面积（如 30 m²），且每种罐数量必须为非负整数。

✅ 正确建模四要素

SciPy 的 milp 要求显式定义以下四部分：

目标向量 c：各决策变量（每种罐的数量）对应的单位成本，即 price 列；
整数约束 integrality：长度与变量数一致的数组，1 表示该变量必须为整数（注意：不是 True 或字符串）；
变量边界 bounds：通常为 Bounds(lb=0)，确保数量非负；
线性约束 constraints：用 LinearConstraint(A, lb, ub) 表达覆盖面积要求——即总可涂面积 ≥ 目标值（下界），且 ≤ 合理上界（避免过度松弛）。

⚠️ 关键误区警示：

❌ 不要对约束矩阵 A 做人为缩放（如除以价格），这会扭曲约束语义并导致数值不稳定；

❌ A_ub / b_ub 是 linprog 的旧接口，milp 应统一使用 LinearConstraint；

❌ integrality=[1,1,1,1] 语法正确，但若传入 float 类型或长度不匹配，将静默失效。

? 完整可运行示例

import numpy as np
from scipy.optimize import milp, Bounds, LinearConstraint

# 原始数据：体积(L)、单位面积耗量(L/m²)、单价(元)
pdict = {
    'Can_9ltr':  [9.0,  0.17, 4870],
    'Can_4.5ltr': [4.5,  0.17, 2910],
    'Can_1ltr':   [1.0,  0.17,  632],
    'Can_2.25ltr':[2.25, 0.17, 1790]
}

# 构建向量化输入
volumes = np.array([pdict[k][0] for k in pdict])
consumes = np.array([pdict[k][1] for k in pdict])
prices = np.array([pdict[k][2] for k in pdict])

# 计算每罐可涂面积（m²）: volume / consume
coverage_per_can = volumes / consumes  # [52.94, 26.47, 5.88, 13.24]

target_area = 30.0
n = len(prices)

# 合理上界：用最大单罐覆盖能力估算（避免无界松弛）
max_coverage = coverage_per_can.max()
upper_bound = np.ceil(target_area / max_coverage) * max_coverage

# 【核心配置】
result = milp(
    c=prices,  # 最小化总成本
    integrality=np.ones(n, dtype=np.uint8),  # 全部变量为整数
    bounds=Bounds(lb=np.zeros(n)),  # 数量 ≥ 0
    constraints=LinearConstraint(
        A=coverage_per_can,  # 系数向量：每罐贡献的面积
        lb=target_area,      # 总覆盖面积 ≥ 30
        ub=upper_bound       # 总覆盖面积 ≤ 合理上限（如 52.94）
    )
)

# 验证与输出
if result.success:
    solution = result.x.astype(int)  # 强制转整型（milp 返回 float，但值应为整数）
    total_cost = prices @ solution
    print("最优采购方案：")
    for i, (name, _) in enumerate(pdict.items()):
        print(f"  {name}: {solution[i]} 罐 → 覆盖 {coverage_per_can[i]*solution[i]:.1f} m²")
    print(f"总成本: ¥{total_cost:.1f}")
else:
    print("求解失败:", result.message)

输出示例：

最优采购方案：  
  Can_9ltr: 0 罐 → 覆盖 0.0 m²  
  Can_4.5ltr: 1 罐 → 覆盖 26.5 m²  
  Can_1ltr: 1 罐 → 覆盖 5.9 m²  
  Can_2.25ltr: 0 罐 → 覆盖 0.0 m²  
总成本: ¥3542.0

? 为什么你的原始代码未生效？

约束方向错误：你用 A_ub 和 b_ub 试图表达 ≥ target，但 A_ub @ x ≤ b_ub 只能表示上界约束。milp 的 LinearConstraint 明确支持 lb/ub 双向，应直接使用；
冗余缩放破坏约束：对 A 矩阵除以价格（如 (1/c[0])*exps[0]）使约束变为 ∑(exp_i / price_i) * x_i ≤ ...，物理意义丢失，优化器无法识别“覆盖面积”本质；
上界设置不合理：math.ceil(...)*max(exps) 计算的是单罐最大覆盖的倍数，但作为 ub 传入时未与 A 对齐，导致约束失效。