寻找适用于多供应商多组件采购场景的价格优化算法

问题性质说明 #

你描述的是带固定成本的多品类供应商选择问题，属于NP-hard组合优化问题，本质是集合覆盖问题的衍生变种：每个供应商对应一个可供应的零部件子集，选中该供应商需要支付固定运费s(y) + 对应采购的零部件报价总和，目标是覆盖全部x种零部件的前提下总费用最低。

适用算法推荐 #

1. 中小规模场景（x<30，y<100）：精确求解算法 #

• 分支定界法：先构造松弛的线性规划下界，再按供应商选择分支剪枝，可输出全局最优解。
• 整数规划求解器：直接把问题转化为0-1整数规划模型丢给Gurobi、CBC等开源/商业求解器求解，建模逻辑如下：
  定义二元变量a[y]=1表示选中供应商y，b[x,y]=1表示从供应商y采购零部件x
  目标函数：min( sum(a[y]*s(y) for y in 所有供应商) + sum(b[x,y]*p(x,y) for x,y) )
  约束条件：

  对每个零部件x：sum(b[x,y] for 所有供应x的供应商y) = 1
  对每个x,y：b[x,y] ≤ a[y] （只有选中供应商y才能从y买x）
  所有变量为0/1二元变量

2. 大规模场景（如x=100、y=1000）：近似/启发式算法 #

这类算法运算速度快，输出结果和最优值的差距通常可控制在5%以内，完全满足业务需求：

• 贪婪算法：每轮选择「单位新增覆盖零部件的边际成本最低」的供应商，直到覆盖全部零部件。边际成本计算逻辑为：(供应商运费 + 该供应商可供应的、当前未被覆盖零部件的最低报价总和) / 新增覆盖零部件数量。该算法最坏情况近似比为O(log x)，实际业务场景下通常接近最优。
• 遗传算法：编码方式为长度等于y的二进制串，每一位代表是否选中对应供应商，适应度函数为总费用（未覆盖全部零部件的个体设为惩罚值），迭代几十代即可得到非常接近最优的结果，可调参数少，鲁棒性强。
• 模拟退火算法：初始解可以用贪婪算法的输出，再通过随机调整选中的供应商集合，允许一定概率接受更差的解跳出局部最优，收敛速度快，适合y量级较大的场景。

预处理优化技巧 #

不管用哪种算法，都可以先做预处理降维，大幅提升运算效率：

• 过滤掉明显无竞争力的供应商：如果供应商A所有零部件报价都比供应商B高，且运费还更高，可直接剔除A。
• 对每个零部件先统计报价最低的前3-5家供应商，其余不供应该零部件或报价过高的供应商直接排除出该品类的可选范围，可把y的有效量级从1000降到几十。

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