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

黄丽嫦 林结

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

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

中图分类号： 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.

4·张惠恩.管理线性规划[M].大连：东北财经大学出版社，2001，1-91.

5·胡运权.运筹学教程[M].北京：清华大学出版社，2007，11-14.

6·庞碧君.线性规划与随机线性规划[M].郑州： 郑州大学出版社，2007，17-55.

7·周伟明.多核计算与程序设计[M].武汉：华中科技大学出版社，2009，75-124.

8·武汉大学多核架构与编程课程组编.多核架构与编程技术[M].武汉：武汉大学出版社，2010，23-96·

9·尚月强.局域网上求解线性方程组的一种并行Gauss-Seidel迭代算法研究[J].计算机应用与软件，2008，25（9），245-247·

作者简介：黄丽嫦（1962-），女，学士，讲师，研究方向：计算数学及运筹学。