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

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