矩陣單純形法的表上計(jì)算

摘 要：對改進(jìn)單純形法在教學(xué)中的難點(diǎn)進(jìn)行了分析，將其矩陣描述的求解方法總結(jié)為表格形式，使每次迭代中求解新基矩陣的逆矩陣得到簡化。通過算例表明該方法更加簡單直觀，易于學(xué)生理解。

關(guān)鍵詞：線性規(guī)劃 矩陣單純形法 單純形表

中圖分類號：G642 文獻(xiàn)標(biāo)識碼：A 文章編號：1673-9795（2013）04（b）-0019-02

線性規(guī)劃是運(yùn)籌學(xué)課程教學(xué)中的重要內(nèi)內(nèi)容，也是運(yùn)籌學(xué)中最重要的方法之一。單純形法是解線性規(guī)劃問題的主要方法，也是運(yùn)籌學(xué)很多分支中廣泛采用的基本方法，例如，圖論和對策論中的許多問題都可以用線性規(guī)劃的單純形法來求解。當(dāng)用單純形表求解時，每行每列的數(shù)據(jù)都要計(jì)算，而實(shí)際上有些行或列的數(shù)據(jù)在下一步計(jì)算時并不需要。為了減少不必要的計(jì)算，人們提出了改進(jìn)單純形法，改進(jìn)單純形法[3～4]與單純形法[1～2]相比，省略了對非基向量的重復(fù)變換，有較高的計(jì)算效率，但目前主要是通過矩陣形式來實(shí)現(xiàn)的。

在教學(xué)中我們發(fā)現(xiàn)，矩陣形式的改進(jìn)單純形法比較抽象，學(xué)生對換入換出變量也容易混淆，常常給教學(xué)和理解帶來不便。通過對實(shí)際應(yīng)用進(jìn)行總結(jié)后我們提出一種改進(jìn)單純形表的實(shí)現(xiàn)形式，這種簡易表格法只需從一個表格變換到另一表格，而不需在表格之外做太多的代數(shù)運(yùn)算，能以較少的計(jì)算量比較容易的求出每次迭代中基的逆矩陣，同時又克服了矩陣形式的不足。這種改進(jìn)的表格方法清晰直觀易于理解，學(xué)生能很好的掌握，為學(xué)生學(xué)習(xí)改進(jìn)單純形法提供了一種重要參考，同時也便于運(yùn)籌學(xué)老師對這部分內(nèi)容的講解。

1 改進(jìn)單純形法原理

2 改進(jìn)單純形表與計(jì)算步驟

實(shí)際上，在單純形法迭代過程中，當(dāng)基矩陣的逆求出后，單純形表上其它行與列的數(shù)據(jù)會隨之確定，且上一步迭代的基與下一步迭代的基之間只差一個變量?？梢愿鶕?jù)當(dāng)前基矩陣的逆和換入變量的系數(shù)列向量來計(jì)算出下一步迭代中基矩陣的逆（而不是直接求逆），從而簡化計(jì)算，下面是本文設(shè)計(jì)的改進(jìn)單純形表。

2.1 改進(jìn)單純形表（如表1）

2.2 計(jì)算步驟

3 算例

現(xiàn)用下例的線性規(guī)劃問題來說明上述計(jì)算步驟。

max z=6x1-2x2+3x3

（1）根據(jù)其標(biāo)準(zhǔn)型，取松馳變量x4，x5為基變量，它們對應(yīng)的單位矩陣作為初始基矩陣B0，將有關(guān)數(shù)字填入表中，得到初始改進(jìn)單純形表。（見表2）

在上表中B0-1b列和CBB0-1列可以由表格很容易得到。

（2）確定換入變量。

（3）確定換出變量。

（4）計(jì)算新基矩陣的逆矩陣。

5 結(jié)語

本文將改進(jìn)單純形法的矩陣描述以表格的形式直觀地呈現(xiàn)出來，解決了原來通過矩陣計(jì)算時尋找換入換出變量的麻煩，具有計(jì)算量小且學(xué)生容易理解的優(yōu)點(diǎn)，并且簡化了改進(jìn)單純形法中每次迭代求新基矩陣的逆矩陣B-1這一關(guān)鍵點(diǎn)，讓學(xué)生學(xué)習(xí)改進(jìn)單純形法時易于接受和掌握，同時，也為運(yùn)籌學(xué)老師對這部分內(nèi)容的講解提供一種借鑒。

參考文獻(xiàn)

[1]Zhou Qing-hua.A new algorithm on quadraric interpolation[J].Chinese Journal of engineering mathematics，2006，23（6）：1075-1087.

[2]Nelder J A，Mead R.A simplex method for function mini mization[J].The Comput J，1965，7：308-313.

[3]清華大學(xué)運(yùn)籌學(xué)教材編寫組.運(yùn)籌學(xué)[M].北京：清華大學(xué)出版社，1990.

[4]郭耀煌.運(yùn)籌學(xué)原理與方法[M].成都：西南交通大學(xué)出版社，1994.

[5] 鄭亞林，安凱，李彩萍.單純形法的一種改進(jìn)[J].曲阜師范大學(xué)學(xué)報(bào)：自然科學(xué)版，1999（2）：16-18.

[6] 王志軍，陳麗.求標(biāo)準(zhǔn)正交基的初等變換法[J].高等教育研究，2005（6）：41-43.

[7] 王芳華.一種簡易的單純形表[J].數(shù)學(xué)實(shí)踐與認(rèn)識，2007，37（10）：102-106.