教育发展规划中的布点问题的最优性算法

An Optimal Algorithm for the Allocation Problem in Education Development Planning

“教育发展规划中的布点问题及其算法”(系统工程.7,2(1989),57～63)提出了布点问题的数学横型及求解该横型的分解方法.本文的例子说明分解方法得到的解不一定是最优的.我们构造了一个简单网络,将布点问题转化为该网络中的最小费用最大流问题,从而给出了求解布点问题的最优性算法.

'Allocation Problem and Its Algorithm in Education Development Planning' (SYSTEMS ENGINEERING, 7,2(1989),57-63)presented a mathematical model of allocation problem and the Decomposition Method for solving the model. But an example in our paper shows that the solution obtained through the decomposition method is not sure to be optimal. Constructing a simple network and converting the allocation problem into the min-cost max-flow in the network, we have developed an optimal algorithm for the allocation problem.