线性规划问题的分块并行求解及应用

Block Parallel Solution of Linear Programming Problem and its Application

在线性规划问题的众多求解算法中,单纯形法仍然是最有效和最常用的算法。分析了单纯形法的计算原理及过程,并对换基迭代过程中的相关运算进行了分块处理,在此基础上,设计实现了一种具有并行处理机制的线性规划问题的求解算法。实际应用表明,新算法具有良好的加速比,且在具有多核架构的微机中易于实现。

Simplex method is still the most effective and most commonly used algorithm for solving linear programming problems.Analysis of the calculation principle and process of the simplex method and the correlation operation and swapping based iterative process were divided into blocks, on this basis, design and implementation of the a kind of parallel processing algorithm for solving the mechanism of the linear programming problem. The practical application shows that the new algorithm has a good speedup, and is easy to be implemented in a computer with multi core architecture.