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

Order Allocation Planning with Variety Flexible Demand Based on Column Generation Methods

作　　者：商宇 SHANG Yu(Faculty of Management and Economics,Kunming University of Science and Technology,Kunming 650093,China)

机构地区：[1]昆明理工大学管理与经济学院

出　　处：《物流工程与管理》2019年第11期126-129,139,共5页Logistics Engineering and Management

摘　　要：针对具有品种柔性需求的订单分配计划进行了研究,以国内某钢铁企业为例,建立了整数规划模型。在模型的求解中,首先根据问题特点对原问题模型进行了Dantzig-Wolfe分解,得到一个具有多个列的主问题和具有背包问题特征的子问题。然后,从一个包含部分列变量的限制主问题出发,采用列生成方法对主问题和子问题进行迭代求解得到原问题的上界,并将列生成作为定界机制嵌入到分支定界算法的框架中形成分支定价算法,执行分支搜索过程获得整数最优解。最后进行了随机实验,验证了该模型的有效性和算法的稳定性。An order allocation plan with variety flexibility demands is studied in this paper which takes the production practice of a domestic steel industry as an example. An integer programming model is formulated. In the solution method,we first use the Dantzig-Wolfe decomposition method to split the integer programming model into a master problem which contains multiple columns and some subproblems which have the knapsack characteristics according to the model’s characters. Then,the column generation algorithm starts from a restricted master problem which contains only a subset of columns,and executes iterative processes between the restricted master problem and subproblems to obtain a upper bound of the integer programming model. The column generation algorithm acting as a bounding mechanism is embedded into the branch-and-bound framework to form a branch-and-price algorithm which performs the branch search process to obtain an integer optimal solution. Finally,a random experiment is carried out to verify the validity of the model and the stability of the algorithm.

关 键 词：品种柔性需求 订单分配 列生成 分支-定价 

分 类 号：F251.2[经济管理—国民经济]