黃麗嫦 林結(jié)

摘 要：在線性規(guī)劃問題的眾多求解算法中，單純形法仍然是最有效和最常用的算法。分析了單純形法的計(jì)算原理及過程，并對換基迭代過程中的相關(guān)運(yùn)算進(jìn)行了分塊處理，在此基礎(chǔ)上，設(shè)計(jì)實(shí)現(xiàn)了一種具有并行處理機(jī)制的線性規(guī)劃問題的求解算法。實(shí)際應(yīng)用表明，新算法具有良好的加速比，且在具有多核架構(gòu)的微機(jī)中易于實(shí)現(xiàn)。

關(guān)鍵詞：線性規(guī)劃問題；單純形法；分塊；并行求解

中圖分類號： O15 文獻(xiàn)標(biāo)識碼：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 文獻(xiàn)標(biāo)識碼：A

佛山職業(yè)技術(shù)學(xué)院校級科研基金資助項(xiàng)目： 2014KY017

1 引言

規(guī)劃問題所涉及的是，對有限的資源進(jìn)行合理的利用或調(diào)配，從而達(dá)到所期望的目的。這些問題的特點(diǎn)是，有大量的方案（解）滿足每個(gè)問題的基本條件，究竟把哪一方案（解）選為最優(yōu)，則與問題中某一個(gè)實(shí)際要求或目標(biāo)有關(guān)[1]。而線性規(guī)劃（Linear Programming）問題則是規(guī)劃問題中特例，該類問題的數(shù)學(xué)模型可用線性的關(guān)系式進(jìn)行描述。通常，線性規(guī)劃所研究的問題有兩類，一類為資源（人力、物力、財(cái)力）是給定的，要求充分利用這些資源，最大限度地實(shí)現(xiàn)預(yù)期的目標(biāo)（產(chǎn)量、產(chǎn)值最大、利潤最高等）；另一類為任務(wù)是給定的，要求以消耗最少的資源（原料、工時(shí)、成本）來完成它。前一類問題稱為極大值問題，后一類問題稱為極小值問題[2-4]。

在線性規(guī)劃的解法中，單純形法是一個(gè)最著名的方法。它在理論上是完善和嚴(yán)格的，在實(shí)踐上是方便和有效的。注意到當(dāng)前的微機(jī)普遍具有多核計(jì)算架構(gòu)，為更好地發(fā)揮這一特性，我們對線性規(guī)劃問題中的單純形求解法進(jìn)行了分塊并行計(jì)算的改進(jìn)。

2 線性規(guī)劃問題的數(shù)學(xué)模型及其標(biāo)準(zhǔn)形式

2.1 線性規(guī)劃問題的數(shù)學(xué)模型

現(xiàn)實(shí)生活中的線性規(guī)劃問題是各式各樣的，但經(jīng)過抽象處理后，它們普遍具有如下的共同特點(diǎn)：表示問題的最優(yōu)化的目標(biāo)指標(biāo)是線性函數(shù)，表示約束條件的數(shù)學(xué)式子是一組變量 的線性等式或線性不等式組，為此，可以得到線性規(guī)劃問題其數(shù)學(xué)模型的一般形式為[5]：

求一組決策變量 的值，使之滿足下列約束條件：

從圖2可知，單純形的分塊并行計(jì)算的加速比隨著計(jì)算規(guī)模的增加而增長，在矩陣 的階數(shù)為8000階時(shí)，其加速比達(dá)到51.2%。

5 結(jié)語

在單純形法的基礎(chǔ)上，提出了一種線性規(guī)劃問題的分塊并行求解算法，新算法具有良好的加速比和易于實(shí)現(xiàn)的特點(diǎn)，理論分析及相關(guān)實(shí)驗(yàn)均表明它是有效的。

參考文獻(xiàn)：

1·范玉妹，徐爾，趙金玲等.數(shù)學(xué)規(guī)劃及其應(yīng)用（第3版）[M].北京：冶金工業(yè)出版社，2009，1-7.

2·張香云.線性規(guī)劃[M].杭州：浙江大學(xué)出版社，2009，1-173.

3·杜紅.應(yīng)用運(yùn)籌學(xué) [M].杭州：浙江大學(xué)出版社，2010，19-72.

4·張惠恩.管理線性規(guī)劃[M].大連：東北財(cái)經(jīng)大學(xué)出版社，2001，1-91.

5·胡運(yùn)權(quán).運(yùn)籌學(xué)教程[M].北京：清華大學(xué)出版社，2007，11-14.

6·龐碧君.線性規(guī)劃與隨機(jī)線性規(guī)劃[M].鄭州： 鄭州大學(xué)出版社，2007，17-55.

7·周偉明.多核計(jì)算與程序設(shè)計(jì)[M].武漢：華中科技大學(xué)出版社，2009，75-124.

8·武漢大學(xué)多核架構(gòu)與編程課程組編.多核架構(gòu)與編程技術(shù)[M].武漢：武漢大學(xué)出版社，2010，23-96·

9·尚月強(qiáng).局域網(wǎng)上求解線性方程組的一種并行Gauss-Seidel迭代算法研究[J].計(jì)算機(jī)應(yīng)用與軟件，2008，25（9），245-247·

作者簡介：黃麗嫦（1962-），女，學(xué)士，講師，研究方向：計(jì)算數(shù)學(xué)及運(yùn)籌學(xué)。