生產作業計劃的單純形矩陣優化算法研究

摘 要：利用單純形矩陣進行生產作業計劃的優化，可使運算過程更為簡易和高效。單純形矩陣優化算法的關鍵是在建模后，編制出初始單純形矩陣。對單純形矩陣的換基迭代，變成了簡單的矩陣初等變換運算，提高了運算速度和效率。算例的計算過程表明，單純形矩陣優化算法是生產作業計劃的一種很好的簡易算法。

關鍵詞：生產作業計劃；單純形矩陣；優化算法；基變量

中圖分類號：F22 文獻標志碼：A 文章編號：1673-291X（2012）09-0191-02

引言

在生產作業計劃中，圖解法是尋求最優解的一種有效方法。不過，對于三種以上產品的生產作業計劃問題，圖解法無能為力。這時，通常采用單純形法確定最優解。單純形法是從一個基本可行解出發，經過有限次的換基運算，逐漸改善直至獲得最優的目標函數值或判明問題無解為止。利用單純形法進行生產作業計劃十分高效。然而，單純形法多采用表格形式進行運算，求解過程較為煩瑣。其實，利用單純形矩陣進行生產作業計劃的優化，運算過程更為簡易。本文試圖通過一個算例，說明生產作業計劃的單純形矩陣優化算法的原理和過程。

一、生產作業計劃建模

1.數據來源。調查一家機械制造企業，獲取生產作業計劃數據。該企業使用A、B兩種設備，生產甲、乙、丙三種產品，生產每件產品需要的設備臺時、設備有效臺時及單位產品產值（如表1所示）。

表1 生產作業計劃的基本數據

2.建模。現要安排生產作業計劃，設法充分發揮設備生產能力，使企業獲得最大的產品總產值。假定甲、乙、丙的產量分別為x1、x2、x3，利潤為z。生產作業計劃的線性規劃模型為：

maxz=3x1+2x2+x3

s.t.z-3x1-2x2-x3=0x1+2x2+x3≤4002x1+x2+2x3≤500x1，x2，x3≥0

加入松馳變量，將生產作業計劃線性規劃模型化為標準形，

maxz=3x1+2x2+x3

s.t.z-3x1-2x2-x3-0·x4-0·x5=0 （0）x1+2x2+x3+x4+0·x5=400 （1）2x1+x2+2x3+0·x4+x5=500 （2）x1，x2，x3，x4，x5≥0 （3）

二、初始單純形矩陣的構建

1.初始單純形矩陣的寫法。依據標準形，按照約束方程（1）、（2）和目標方程（0）中變量系數和常數項的順序，寫出初始單純形矩陣：

x1 x2 x3 x4 x5 bix4 1 2 1 1 0 400x5 2 1 2 0 1 500σj -3 -2 -1 0 0 0

2.初始單純形矩陣的結構。初始單純形矩陣的一般形式為：

（4）

矩陣（4）包括4個分塊矩陣。

左上角的分塊矩陣為標準形的變量系數，x1，x2，…，xm為基變量。

右上角的bi為基解，即基變量的取值。

右下角的z0為目標函數值，初始單純形矩陣的目標函數值為0，z0的計算方法為：

z0=cTBb （5）

其中，cB為目標函數的價值系數cj構成的列向量，b為基解構成的列向量。

左下角為檢驗數σj，基變量的檢驗數為0。檢驗數是檢驗當前的基本可行解是否最優的一個標志。在單純形矩陣中，只要存在負檢驗數，就意味著目標值還能增加，就需要把它所對應的非基變量變為基變量。因此，檢驗數成為是否進行換基迭代的決策依據。檢驗數的計算方法為：

σj=cTBaj-cj，j=1，2，…，n （6）

其中，aj為變量xj的系數列向量。

三、單純形矩陣的換基迭代

1.確定進基變量、出基變量和主元。在初始單純形矩陣中，由于minσj=min（-3，-2，-1，0，0）=-3，根據最小檢驗數規則，確定x1為進基變量，x1列為主列。

由于minmin（，）=250，根據最小比值規則，確定x5為出基變量，即x1取代 x5為新的基變量，基變量仍為2個。

處于進基變量所在列和出基變量所在行的元素2為主元。標記后的初始單純形矩陣為：

2.通過初等變換進行換基迭代。進行初等變換，將初始單純形矩陣中的主元2化為1，主列其余元素化為0，實現換基迭代。進行初等變換時，要對檢驗數行、基解列和目標函數值一并處理。此時，x1、x4成為新的基變量組合，目標函數值由0增大到750。調換進基變量和出基主量，寫出一次改進的單純形矩陣：

x1 x2 x3 x4 x5 bix4 1 1.5 0 1 0.5 150x1 2 0.5 1 0 0.5 250σj 0 -0.5 2 0 1.5 750

3.檢查檢驗數確定最優解。檢查檢驗數，若σj≥0，則停止運算，得到最優解。否則，重復上述步驟，繼續換基迭代過程，直到得到最優解為止。

在本例中，依據一次改進的單純形矩陣，根據最小檢驗數數規則，確定x2為進基變量，x2列為主列。根據最小比值規則，確定x4為出基變量，即x2取代x4為新的基變量。處于x2列、 x4行的元素1.5為主元。標記后的一次改進單純形矩陣為：

進行初等變換，將主元化為1，主列其余元素化為0。換基迭代后，x1、 x2成為新的基變量組合，目標函數值由750調整為800。調換進基變量和出基變量，寫出二次改進的單純形矩陣：

x1 x2 x3 x4 x5 bix２ 0 1 0 - 100x1 1 0 1 - 200σj 0 0 2 800*

在二次改進的單純形矩陣中，全部σj≥0，停止運算，獲取最優解。在最優解中，基變量x1=200，x2=100，x3是非基變量，所以x3=0。目標函數的最大值為：

maxz=z（200，100，0）=3×200+2×100+1×0=800

可知，產品甲生產200件，乙生產100件，丙不生產時，該企業可獲最大產值800千元。至此，生產作業計劃完成了優化過程。

綜上所述，在根據標準形寫出初始單純形矩陣后，生產作業計劃的求解過程就變成了對單純形矩陣進行初等變換的過程，這一過程的結果是將新的基變量系數化為單位向量。在實際運算中，算例中單純形矩陣的初等變換過程可按如下簡化方式進行：

x1 x2 x3 x4 x5 bix２ 0 1 0 - 100x1 1 0 1 - 200σj 0 0 2 800*

結論

由本文的算例可以看出，單純形矩陣優化算法可以使生產作業計劃的數據結構變得更為簡單和清晰。這種算法的關鍵是在建模后，編制出初始單純形矩陣。對單純形矩陣的換基迭代，變成了簡單的矩陣初等變換運算，提高了運算速度和效率。可見，單純形矩陣優化算法簡化了運算過程，是生產作業計劃問題一種很好的簡易算法。

參考文獻：

[1] 原和平.中小企業利潤規劃研究[J].財會通訊，2009，(1):82-83.

[2] 呂志明.利潤規劃模型的設計與應用[J].財會通訊，2006，(12):64-65.

[3] 韓大衛.管理運籌學[M].大連:大連理工大學出版社，1998:31-41.

[4] 趙全勝，張春會，佟德君.改進單純形法及其應用[J].遼寧工程技術大學學報，2010，(6).

[5] 李裕梅，曹顯兵，吳巧梅，蔣心力，趙晉.線性規劃單純形代數7小步法與簡易矩陣表格法[J].數學的實踐與認識，2011，(13):119-126.

[責任編輯 王玉妹]