線性規劃問題的分塊并行求解及應用

黃麗嫦 林結

摘 要：在線性規劃問題的眾多求解算法中，單純形法仍然是最有效和最常用的算法。分析了單純形法的計算原理及過程，并對換基迭代過程中的相關運算進行了分塊處理，在此基礎上，設計實現了一種具有并行處理機制的線性規劃問題的求解算法。實際應用表明，新算法具有良好的加速比，且在具有多核架構的微機中易于實現。

關鍵詞：線性規劃問題；單純形法；分塊；并行求解

中圖分類號： 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-），女，學士，講師，研究方向：計算數學及運籌學。