生產(chǎn)作業(yè)計(jì)劃的單純形矩陣優(yōu)化算法研究

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

關(guān)鍵詞：生產(chǎn)作業(yè)計(jì)劃；單純形矩陣；優(yōu)化算法；基變量

中圖分類號(hào)：F22 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1673-291X（2012）09-0191-02

引言

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

一、生產(chǎn)作業(yè)計(jì)劃建模

1.數(shù)據(jù)來源。調(diào)查一家機(jī)械制造企業(yè)，獲取生產(chǎn)作業(yè)計(jì)劃數(shù)據(jù)。該企業(yè)使用A、B兩種設(shè)備，生產(chǎn)甲、乙、丙三種產(chǎn)品，生產(chǎn)每件產(chǎn)品需要的設(shè)備臺(tái)時(shí)、設(shè)備有效臺(tái)時(shí)及單位產(chǎn)品產(chǎn)值（如表1所示）。

表1 生產(chǎn)作業(yè)計(jì)劃的基本數(shù)據(jù)

2.建模。現(xiàn)要安排生產(chǎn)作業(yè)計(jì)劃，設(shè)法充分發(fā)揮設(shè)備生產(chǎn)能力，使企業(yè)獲得最大的產(chǎn)品總產(chǎn)值。假定甲、乙、丙的產(chǎn)量分別為x1、x2、x3，利潤(rùn)為z。生產(chǎn)作業(yè)計(jì)劃的線性規(guī)劃模型為：

maxz=3x1+2x2+x3

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

加入松馳變量，將生產(chǎn)作業(yè)計(jì)劃線性規(guī)劃模型化為標(biāo)準(zhǔn)形，

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）

二、初始單純形矩陣的構(gòu)建

1.初始單純形矩陣的寫法。依據(jù)標(biāo)準(zhǔn)形，按照約束方程（1）、（2）和目標(biāo)方程（0）中變量系數(shù)和常數(shù)項(xiàng)的順序，寫出初始單純形矩陣：

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.初始單純形矩陣的結(jié)構(gòu)。初始單純形矩陣的一般形式為：

（4）

矩陣（4）包括4個(gè)分塊矩陣。

左上角的分塊矩陣為標(biāo)準(zhǔn)形的變量系數(shù)，x1，x2，…，xm為基變量。

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

右下角的z0為目標(biāo)函數(shù)值，初始單純形矩陣的目標(biāo)函數(shù)值為0，z0的計(jì)算方法為：

z0=cTBb （5）

其中，cB為目標(biāo)函數(shù)的價(jià)值系數(shù)cj構(gòu)成的列向量，b為基解構(gòu)成的列向量。

左下角為檢驗(yàn)數(shù)σj，基變量的檢驗(yàn)數(shù)為0。檢驗(yàn)數(shù)是檢驗(yàn)當(dāng)前的基本可行解是否最優(yōu)的一個(gè)標(biāo)志。在單純形矩陣中，只要存在負(fù)檢驗(yàn)數(shù)，就意味著目標(biāo)值還能增加，就需要把它所對(duì)應(yīng)的非基變量變?yōu)榛兞俊Ｒ虼耍瑱z驗(yàn)數(shù)成為是否進(jìn)行換基迭代的決策依據(jù)。檢驗(yàn)數(shù)的計(jì)算方法為：

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

其中，aj為變量xj的系數(shù)列向量。

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

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

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

處于進(jìn)基變量所在列和出基變量所在行的元素2為主元。標(biāo)記后的初始單純形矩陣為：

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

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.檢查檢驗(yàn)數(shù)確定最優(yōu)解。檢查檢驗(yàn)數(shù)，若σj≥0，則停止運(yùn)算，得到最優(yōu)解。否則，重復(fù)上述步驟，繼續(xù)換基迭代過程，直到得到最優(yōu)解為止。

在本例中，依據(jù)一次改進(jìn)的單純形矩陣，根據(jù)最小檢驗(yàn)數(shù)數(shù)規(guī)則，確定x2為進(jìn)基變量，x2列為主列。根據(jù)最小比值規(guī)則，確定x4為出基變量，即x2取代x4為新的基變量。處于x2列、 x4行的元素1.5為主元。標(biāo)記后的一次改進(jìn)單純形矩陣為：

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

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

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

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

可知，產(chǎn)品甲生產(chǎn)200件，乙生產(chǎn)100件，丙不生產(chǎn)時(shí)，該企業(yè)可獲最大產(chǎn)值800千元。至此，生產(chǎn)作業(yè)計(jì)劃完成了優(yōu)化過程。

綜上所述，在根據(jù)標(biāo)準(zhǔn)形寫出初始單純形矩陣后，生產(chǎn)作業(yè)計(jì)劃的求解過程就變成了對(duì)單純形矩陣進(jìn)行初等變換的過程，這一過程的結(jié)果是將新的基變量系數(shù)化為單位向量。在實(shí)際運(yùn)算中，算例中單純形矩陣的初等變換過程可按如下簡(jiǎn)化方式進(jìn)行：

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

結(jié)論

由本文的算例可以看出，單純形矩陣優(yōu)化算法可以使生產(chǎn)作業(yè)計(jì)劃的數(shù)據(jù)結(jié)構(gòu)變得更為簡(jiǎn)單和清晰。這種算法的關(guān)鍵是在建模后，編制出初始單純形矩陣。對(duì)單純形矩陣的換基迭代，變成了簡(jiǎn)單的矩陣初等變換運(yùn)算，提高了運(yùn)算速度和效率。可見，單純形矩陣優(yōu)化算法簡(jiǎn)化了運(yùn)算過程，是生產(chǎn)作業(yè)計(jì)劃問題一種很好的簡(jiǎn)易算法。

參考文獻(xiàn)：

[1] 原和平.中小企業(yè)利潤(rùn)規(guī)劃研究[J].財(cái)會(huì)通訊，2009，(1):82-83.

[2] 呂志明.利潤(rùn)規(guī)劃模型的設(shè)計(jì)與應(yīng)用[J].財(cái)會(huì)通訊，2006，(12):64-65.

[3] 韓大衛(wèi).管理運(yùn)籌學(xué)[M].大連:大連理工大學(xué)出版社，1998:31-41.

[4] 趙全勝，張春會(huì)，佟德君.改進(jìn)單純形法及其應(yīng)用[J].遼寧工程技術(shù)大學(xué)學(xué)報(bào)，2010，(6).

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

[責(zé)任編輯 王玉妹]