基于效率最優(yōu)的單純形法的改進(jìn)

謝 振

（運(yùn)城學(xué)院，山西 運(yùn)城 044000）

基于效率最優(yōu)的單純形法的改進(jìn)

謝 振

（運(yùn)城學(xué)院，山西 運(yùn)城 044000）

提高單純形法的運(yùn)算效率是運(yùn)籌學(xué)一直在研究的一個(gè)重要問題.文章通過對(duì)傳統(tǒng)單純形法的計(jì)算機(jī)程序化算法的改進(jìn)，降低了時(shí)間和空間復(fù)雜度，使兩者的效率均達(dá)到了o（1）.經(jīng)過大量實(shí)例證明，改進(jìn)后的算法還減少了進(jìn)行單純形法變換時(shí)所用到的迭代次數(shù).

單純形法；時(shí)間復(fù)雜度；空間復(fù)雜度；迭代次數(shù)

單純形法是為用程序的思想解決線性規(guī)劃問題而提出的，但是在大量解決線性規(guī)劃問題的實(shí)踐中，筆者發(fā)現(xiàn)計(jì)算機(jī)在選取換入基變量時(shí)所用到的內(nèi)存的空間復(fù)雜度和計(jì)算所耗的時(shí)間復(fù)雜度均為o（n）［1］.比如一個(gè)具有n個(gè)決策變量的線性規(guī)劃問題，在每次選取換入基變量時(shí)都要將n個(gè)檢驗(yàn)數(shù)全部調(diào)入內(nèi)存，然后將所有的檢驗(yàn)數(shù)進(jìn)行比較，運(yùn)算極為復(fù)雜［2］.本文試圖研究如何降低計(jì)算時(shí)所產(chǎn)生的時(shí)間和空間復(fù)雜度問題，經(jīng)過大量的實(shí)踐證明本文提出的方法使效率大大提高.

1 問題改進(jìn)

設(shè)標(biāo)準(zhǔn)形式的線性規(guī)劃問題如下：

具體改進(jìn)過程如下：

Step1：將數(shù)學(xué)模型化成標(biāo)準(zhǔn)型后，將目標(biāo)函數(shù)中的自變量x i按其對(duì)目標(biāo)函數(shù)的貢獻(xiàn)率（即系數(shù)ci）大小由大到小重新排列自變量和其系數(shù)組合ci x i位置［3］.

Step2：根據(jù)移動(dòng)后的自變量位置，重新組合約束方程組中每個(gè)約束方程內(nèi)自變量，使其改變后的位置與目標(biāo)函數(shù)中的相對(duì)應(yīng)，按改變后的數(shù)學(xué)模型列出初始單純形表.

Step3：在確定換入基的變量時(shí)，只要有檢驗(yàn)數(shù)“Cj－Zj＞0”，則說明該問題還沒有找到最優(yōu)解，此時(shí)選取第一個(gè)“Cj－Zj＞0”的檢驗(yàn)數(shù)所對(duì)應(yīng)的自變量作為換入基的變量［4］.

Step5：利用單純形表進(jìn)行演算新的基可行解，看其是否達(dá)到所有檢驗(yàn)數(shù)都為非正，如果是則說明該基可行解為最優(yōu)解，否則調(diào)用Step3、Step4，繼續(xù)尋找最優(yōu)解［5］.

2 實(shí)例分析

例1

設(shè)有一線性規(guī)劃問題數(shù)學(xué)模型如下：

根據(jù)改進(jìn)后的算法需將數(shù)學(xué)模型變?yōu)橐韵滦问?/p>

通過增加松弛變量將其變成線性規(guī)劃問題的標(biāo)準(zhǔn)形式為

該問題的初始單純形表如表1所示.

表1 初始單純生表

但由于不同主體在回應(yīng)鄉(xiāng)村問題時(shí)采取不同的策略，差異化的鄉(xiāng)建模式有各自的優(yōu)點(diǎn)和運(yùn)用局限（表2）。鄉(xiāng)建沒有統(tǒng)一的模板，應(yīng)基于不同村莊的自然、社會(huì)、經(jīng)濟(jì)、文化背景，從而探索出適應(yīng)自身發(fā)展的道路[19，20]。任何一種鄉(xiāng)村實(shí)踐，都不可能面面俱到，需要分清主次、懂得取舍，在傳承過去、踐行現(xiàn)在、發(fā)展未來之間取得平衡

表2 第1次切入基變量運(yùn)算表

根據(jù)步驟Step3、Step4同樣可得出表2的換入基變量為X2，換出基變量為X5，然后將表2進(jìn)行相應(yīng)的行變換得出最終表3.

表3 第2次切入基變量運(yùn)算表

最后一行檢驗(yàn)數(shù)均為非正，所以該題存在唯一最優(yōu)解：X1＝0，X2＝8／5，X3＝1／5，X4＝X5＝X6＝0；最優(yōu)值是19／5.

例2

現(xiàn)以文獻(xiàn)［6］中所舉一例來說明.

某水庫灌區(qū)，主要種植小麥、棉花和玉米三種作物，根據(jù)氣象和水文預(yù)報(bào)，明年水庫來水量為22 500萬 m3，預(yù)估小麥、棉花、玉米的毛灌溉定額分別為1 800 m2／hm2，2 400 m2／hm2，1 200 m2／hm2；三種作物預(yù)測(cè)產(chǎn)值分別為1 800元／hm2，3 000元／hm2，1 200元／hm2.灌區(qū)總面積為10萬hm2，根據(jù)地區(qū)種植計(jì)劃要求，棉花種植面積不得大于4萬hm2.問明年這三種作物種植面積應(yīng)如何安排，灌區(qū)總產(chǎn)值為最大［3］.

設(shè)x1，x2，x3分別為小麥、棉花、玉米的種植面積，則該線性規(guī)劃問題的數(shù)學(xué)模型如下：

通過增加松弛變量將其變成線性規(guī)劃問題的標(biāo)準(zhǔn)形式為

解題步驟如表4所示：

由表4可知，X1＝6，X2＝4，X3＝7／4，X5＝17／4，X4＝X6＝X7＝0時(shí)，可得灌溉區(qū)總產(chǎn)值最大為24 000萬元.

表4 效率對(duì)比表

通過以上兩個(gè)例題，本文通過計(jì)算它們的時(shí)空復(fù)雜度與一般單純形計(jì)算時(shí)的時(shí)空復(fù)雜度做以下比較：

項(xiàng)目題 例題1 例題2一般單純形法計(jì)算時(shí)比較次數(shù)18 28改進(jìn)后單純形法計(jì)算時(shí)比較次數(shù)9 13

由表4可知，改進(jìn)后的單純形法的計(jì)算次數(shù)較之一般單純形法減少了很多.

3 結(jié)論

通過該改進(jìn)方法，可以得出5個(gè)結(jié)論：

1）較之用傳統(tǒng)單純形法確定換入基變量所耗的復(fù)雜度要小得多，效率也會(huì)大大提高；

2）并不需要把所有檢驗(yàn)數(shù)都調(diào)入內(nèi)存中，只需單個(gè)調(diào)入內(nèi)存，并找到第一個(gè)正檢驗(yàn)數(shù)所對(duì)應(yīng)的變量作為入基變量即可；

3）將選取換入基變量所耗費(fèi)的時(shí)間和空間復(fù)雜度均為o（n）的不確定性變?yōu)榱薿（1）的確定性；

4）改進(jìn)后的算法大大減少了計(jì)算機(jī)的計(jì)算量和降低了內(nèi)存的使用頻率，并且隨著決策變量的增多，這種算法的優(yōu)勢(shì)會(huì)越來越明顯；

5）經(jīng)過大量的實(shí)例運(yùn)用，改進(jìn)后的單純形法還能減少用單純形表解決問題的計(jì)算迭代次數(shù).

總之，改進(jìn)后的單純形法大大提高了用計(jì)算機(jī)程序解題時(shí)的計(jì)算效率，并且隨著目標(biāo)函數(shù)中決策變量數(shù)量的增加其效果會(huì)更加明顯.

［1］楊 旭.線性規(guī)劃單純形法一種新的解題途徑［J］.河海學(xué)報(bào)，1991，7：134-137

［2］甘應(yīng)愛，田 豐，李維錚，等.運(yùn)籌學(xué)［M］.北京：清華大學(xué)出版社，1995

［3］蘭 艷，李學(xué)勇.一種改進(jìn)的單純形法［J］.長(zhǎng)沙大學(xué)學(xué)報(bào)，1998，12：29-32

［4］張傳平，馮德田.對(duì)改進(jìn)單純形法的探討［J］.石油大學(xué)學(xué)報(bào)（自然科學(xué)版），1999，8：119-120

［5］胡運(yùn)權(quán)，郭耀煌.運(yùn)籌學(xué)教程［M］.北京：清華大學(xué)出版社，2002

［6］朱求長(zhǎng).運(yùn)籌學(xué)及其應(yīng)用［M］.湖北：武漢大學(xué)出版社，2003

Improvement on the Basis of the Efficient Simplex Method

Xie Zhen
（Yuncheng University，Yuncheng 044000，China）

To improve the operational efficiency of simplex method is an important topic that has always been researched in operations research.As is discussed in the paper，by improving the computer programming calculation of the traditional simplex method，the complexity of time and the complexity of space are both lowered，so the efficiency of either type reaches o（1）.And many examples also show that the improved calculation decreases the number of successive times needed in the rotation of the simplex method.

simplex method；complexity of time；complexity of space；the number of iterations

王映苗】

1672-2027（2012）01-0104-05

TP312

A

2011-12-23

謝 振（1984-），男，山西運(yùn)城人，碩士，運(yùn)城學(xué)院助教，主要從事產(chǎn)業(yè)經(jīng)濟(jì)學(xué)、市場(chǎng)營(yíng)銷.