如何找到拆分订单的最优方案？多供应商成本优化求解指导

一、核心建模逻辑拆解 #

这是一个混合整数线性规划问题，需把业务规则转化为数学模型：

• 变量定义：
  • 连续变量 x[i,j]：从供应商i采购商品j的数量
  • 0-1变量 y[i]：是否从供应商i采购（1=是，0=否），用于控制"单次运费"规则
• 目标函数：最小化总成本 = 采购总成本 + 总运费
  • 采购总成本：所有供应商-商品组合的x[i,j] × 单位成本[i,j]之和
  • 总运费：所有y[i] × 供应商i的运费之和
• 约束条件：
  • 需求满足：每个商品j的总采购量等于其需求数量，即Σ(x[i,j]) = 需求[j]（对所有供应商i）
  • 供应上限：每个供应商i对商品j的供应量不超过其可供应数量，即x[i,j] ≤ 可供应数量[i,j]
  • 运费触发：若从供应商i采购任意商品（Σ(x[i,j]) > 0），则y[i]必须为1。用大M法实现：Σ(x[i,j]) ≤ M × y[i]，M取所有商品需求总量之和（确保足够大）
  • 非负约束：x[i,j] ≥ 0，y[i] ∈ {0,1}

二、CVXPY适配步骤 #

1. 数据预处理

   • 整合三个DataFrame，对齐供应商、商品的索引/列，确保每个供应商-商品组合的单位成本、可供应数量有明确值（无供应能力的组合可设可供应数量为0）
   • 提取核心数据：需求向量（商品→需求数量）、单位成本矩阵（供应商×商品）、可供应数量矩阵（供应商×商品）、运费向量（供应商→运费）

2. 定义变量

   • 用cvxpy.Variable(shape=(供应商数, 商品数), nonneg=True)定义连续采购量变量x
   • 用cvxpy.Variable(shape=(供应商数,), boolean=True)定义0-1采购决策变量y

3. 构建目标函数

   • 采购成本：cvxpy.sum(cvxpy.multiply(x, 单位成本矩阵))
   • 运费成本：cvxpy.sum(cvxpy.multiply(y, 运费向量))
   • 总目标：cvxpy.Minimize(采购成本 + 运费成本)

4. 添加约束

   • 需求约束：遍历每个商品，添加cvxpy.sum(x[:, j]) == 需求[j]（j为商品索引）
   • 供应约束：添加x <= 可供应数量矩阵
   • 运费触发约束：遍历每个供应商，添加cvxpy.sum(x[i, :]) <= M * y[i]（M为需求总量之和）

5. 求解模型

   • 定义问题：prob = cvxpy.Problem(目标函数, 约束列表)
   • 选择混合整数规划求解器（如ECOS_BB、GLPK_MI），执行求解：prob.solve(solver=cvxpy.ECOS_BB)

三、关键注意事项 #

• 大M的取值必须足够大，确保只要有采购量，y[i]会被强制设为1，建议取所有商品需求的总和
• 免费求解器在处理大规模数据时速度较慢，若供应商/商品数量较多，建议使用商业求解器（如Gurobi、Cplex）
• 务必确保所有数据的维度对齐，避免因索引不匹配导致的模型错误
• 若业务允许超额采购，可将需求约束调整为Σ(x[i,j]) >= 需求[j]，但通常以刚好满足需求为最优

内容的提问来源于stack exchange，提问作者Andrew Knoesen