一类带单源约束的选址运输问题算法研究

Research into the Computation of the Single Source Capacitated Plant Location Problem

带单源约束的选址运输问题是在经典的选址运输问题基础上考虑每个顾客需求的产品仅由一家工厂供应的情况。所建立的模型是整数规划,是NP难的。本文先考虑了开办费用为零的带单源约束的选址运输问题,即带单源约束的运输问题,松弛其中一种变量约束,借鉴求解运输问题的表上作业法,给出了一种修正的表上作业法,然后将算法推广。最后给出了将算法应用在Excel随机生成的测试问题上所得到的结果,与LINDO求得的最优解相比,差距很小。由此得出结论:对规模较小的带单源约束的选址运输问题,本文提出的算法是简便且行之有效的。

The single source capacitated plant location problem（SSCPLP）is the capacitated plant location problem（CPLP）with single source constraints where clients must be served by a single plant. The model is an integer linear Programming and is NP-hard. We propose a modified algorithm based on a relaxation of the problem. We also use it to test problems generated by a random number generator in excel, and ues LINDO software to obtain the optimal solution to the problems for comparative purposes. So it is a good option for this algorithm to solve small-scale single source capacitated plant location problems.