能力受限批量问题的启发式算法与CPLEX仿真优化

能力受限批量问题多数都是NP-hard问题,解决方法之一就是构造启发式算法获取尽量接近最优解的可行解。目前多数文献通过大规模计算分析来评价启发式算法的性能,但是这种评价方式只能表明该算法针对特定实例的适应性。利用商业优化软件求解同一实例并与算法计算结果进行对比分析,可以体现算法的有效性。针对一种运输能力外包且费用时变的多产品动态经济批量问题,建立混合整数规划模型,通过约束松弛与模型分解,设计出一个基于拉格朗日松弛理论的启发式算法进行模型求解。大量随机实验计算结果以及CPLEX仿真优化结果对比分析表明,在某些实例情况下,启发式算法获取的最优值与CPLEX获取的相当,但是求解时间要明显优于CPLEX,因此选择启发式算法求解此类实例是较优的。

Heuristic Algorithm and CPLEX Optimization for Multi-Product Capacitated Lot Sizing Problem

The capacitated lot sizing problem is known to be NP-hard,even for many special cases.One of the methods is to design the heuristic algorithm,through which to obtain a feasible solution adjacent to the optimal solution.At present,many authors evaluate the calculated performance of their algorithm based on mass of experiments,but it is indicated that the algorithm is only to be fitted for the special instance of the problem.Comparing the result of the algorithm with commercial optimization software,the efficiency of the algorithm can be revealed.A multi-product capacitated lot sizing problem with subcontracting and time-varying transportation costs was dealt with.As the problem is NP-hard,a Lagrangian-based heuristic algorithm is proposed to compute lower and upper bounds,of which the comprehensive computational experiments show the compelling performance in terms of quality and speed,compared with the result of CPLEX.