一类整数规划问题的Lagrange求解方法

Lagrange Method for Solving a Class of Linear Integer Programming Problem

对企业人力资源培训问题,建立时间受限费用最小的分阶段培训的线性整数规划模型。并运用La-grange松弛的方法求解该模型,在所给的解法中Lagrange松弛问题可以分解为多个规模较小的子问题,而这些子问题容易求解并且可以并行计算,同时给出次梯度调整Lagrange乘子的方法。最后利用该方法求解某企业具体的培训计划,说明算法的有效性和实用性。

In the paper a linear integer programming model of a time-limit with the minimal cost for HR （Human Resource） Training is presented. The method for solving the model is also given. Based on the Lagrange Relaxation the original integer programming model is decomposed many smaller size sub-problems, which can be solved easily and in parallel manner. The technique to update the Lagrange multiplier using the subgradient method is presented. An example shows the model and the method given in the paper is efficient.