基于列生成算法的品种柔性需求下的订单分配计划

摘要

针对具有品种柔性需求的订单分配计划进行了研究,以国内某钢铁企业为例,建立了整数规划模型。在模型的求解中,首先根据问题特点对原问题模型进行了Dantzig-Wolfe分解,得到一个具有多个列的主问题和具有背包问题特征的子问题。然后,从一个包含部分列变量的限制主问题出发,采用列生成方法对主问题和子问题进行迭代求解得到原问题的上界,并将列生成作为定界机制嵌入到分支定界算法的框架中形成分支定价算法,执行分支搜索过程获得整数最优解。最后进行了随机实验,验证了该模型的有效性和算法的稳定性。

关键词