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

2016-05-30黄丽嫦林结

科技资讯 2016年11期

关键词：分块

黄丽嫦林结

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

关键词：线性规划问题；单纯形法；分块；并行求解

中图分类号： O15 文献标识码：A 文章编号：1672-3791（2016）04（b）-0000-00

Abstract： 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.

Key words： linear programming problem； simplex method； block； parallel solution

中图分类号：O151.21 文献标识码：A

佛山职业技术学院校级科研基金资助项目： 2014KY017

1 引言

规划问题所涉及的是，对有限的资源进行合理的利用或调配，从而达到所期望的目的。这些问题的特点是，有大量的方案（解）满足每个问题的基本条件，究竟把哪一方案（解）选为最优，则与问题中某一个实际要求或目标有关[1]。而线性规划（Linear Programming）问题则是规划问题中特例，该类问题的数学模型可用线性的关系式进行描述。通常，线性规划所研究的问题有两类，一类为资源（人力、物力、财力）是给定的，要求充分利用这些资源，最大限度地实现预期的目标（产量、产值最大、利润最高等）；另一类为任务是给定的，要求以消耗最少的资源（原料、工时、成本）来完成它。前一类问题称为极大值问题，后一类问题称为极小值问题[2-4]。

在线性规划的解法中，单纯形法是一个最著名的方法。它在理论上是完善和严格的，在实践上是方便和有效的。注意到当前的微机普遍具有多核计算架构，为更好地发挥这一特性，我们对线性规划问题中的单纯形求解法进行了分块并行计算的改进。

2 线性规划问题的数学模型及其标准形式

2.1 线性规划问题的数学模型

现实生活中的线性规划问题是各式各样的，但经过抽象处理后，它们普遍具有如下的共同特点：表示问题的最优化的目标指标是线性函数，表示约束条件的数学式子是一组变量的线性等式或线性不等式组，为此，可以得到线性规划问题其数学模型的一般形式为[5]：

求一组决策变量的值，使之满足下列约束条件：

从图2可知，单纯形的分块并行计算的加速比随着计算规模的增加而增长，在矩阵的阶数为8000阶时，其加速比达到51.2%。

5 结语

在单纯形法的基础上，提出了一种线性规划问题的分块并行求解算法，新算法具有良好的加速比和易于实现的特点，理论分析及相关实验均表明它是有效的。

参考文献：

1·范玉妹，徐尔，赵金玲等.数学规划及其应用（第3版）[M].北京：冶金工业出版社，2009，1-7.

2·张香云.线性规划[M].杭州：浙江大学出版社，2009，1-173.

3·杜红.应用运筹学 [M].杭州：浙江大学出版社，2010，19-72.