矩陣單純形法的表上計算

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

關鍵詞：線性規劃 矩陣單純形法 單純形表

中圖分類號：G642 文獻標識碼：A 文章編號：1673-9795（2013）04（b）-0019-02

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

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

1 改進單純形法原理

2 改進單純形表與計算步驟

實際上，在單純形法迭代過程中，當基矩陣的逆求出后，單純形表上其它行與列的數據會隨之確定，且上一步迭代的基與下一步迭代的基之間只差一個變量。可以根據當前基矩陣的逆和換入變量的系數列向量來計算出下一步迭代中基矩陣的逆（而不是直接求逆），從而簡化計算，下面是本文設計的改進單純形表。

2.1 改進單純形表（如表1）

2.2 計算步驟

3 算例

現用下例的線性規劃問題來說明上述計算步驟。

max z=6x1-2x2+3x3

（1）根據其標準型，取松馳變量x4，x5為基變量，它們對應的單位矩陣作為初始基矩陣B0，將有關數字填入表中，得到初始改進單純形表。（見表2）

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

（2）確定換入變量。

（3）確定換出變量。

（4）計算新基矩陣的逆矩陣。

5 結語

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

參考文獻

[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]清華大學運籌學教材編寫組.運籌學[M].北京：清華大學出版社，1990.

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

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

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

[7] 王芳華.一種簡易的單純形表[J].數學實踐與認識，2007，37（10）：102-106.