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

方案（解）满足每个问题的基本条件，究竟把哪一方案（解）选为最优，则与问题中某一个实际要求或目标有关[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-），女，学士，讲师，研究方向：计算数学及运筹学。