摘要
针对传统的多商品流问题,引入成本上涨因素,建立了最大化利润的非线性规划模型。通过引入节点价格变量,将非线性模型分解为线性主问题和二次规划子问题,设计相应的列生成算法来求解。对于二次规划子问题,通过动态添加破圈约束来消除冗余圈的存在。通过算例测试表明,该算法在解决考虑成本上涨的多商品流问题方面具有很大的潜力。
A nonlinear programming model maximizing profits was established for the traditional multi-commodity network flow problem by considering cost rising constraint.With introduction of a node price variable,the nonlinear model was decomposed into a linear restricted master problem and a quadratic programming subproblem,and a column generation algorithm was designed to solve it.For the quadratic programming subproblem,the redundant circles were eliminated by dynamic adding constraints.Computational results showed that the algorithm had great potential in solving the multi-commodity network flow problem by considering cost rising constraint.
出处
《计算机集成制造系统》
EI
CSCD
北大核心
2015年第12期3330-3335,共6页
Computer Integrated Manufacturing Systems
关键词
多商品流
成本上涨
列生成
multi-commodity network flow
cost rising
column generation
