同解視角下對單純形法的理解

賀學(xué)海，張 彬

同解視角下對單純形法的理解

賀學(xué)海，張 彬

(商丘職業(yè)技術(shù)學(xué)院，河南 商丘 476000)

對線性方程組的增廣矩陣實(shí)施初等變換，變換后所對應(yīng)方程組與原線性方程組同解．借助該理論，將線性規(guī)劃問題標(biāo)準(zhǔn)型中的目標(biāo)函數(shù)系數(shù)及約束條件中的增廣矩陣按一定方法組成新的矩陣，通過基變量的換基迭代原理對新矩陣進(jìn)行初等變換，符合一定要求后，通過變換后的矩陣求出線性規(guī)劃問題的最優(yōu)解．

同解；線性規(guī)劃；單純形；最優(yōu)解

引言

線性規(guī)劃基礎(chǔ)模型是數(shù)學(xué)模型的重要類型，其在運(yùn)籌學(xué)方面的應(yīng)用非常廣泛，單純型法是美國數(shù)學(xué)家G.Dantzig1947年創(chuàng)建，它在解決線性規(guī)劃模型時(shí)簡捷、實(shí)用，是公認(rèn)的行之有效的方法．文獻(xiàn)[1]通過實(shí)例探討了單純形法步驟和應(yīng)注意的問題，文獻(xiàn)[2]就線性規(guī)劃的單純形法及其發(fā)展進(jìn)行了探討，文獻(xiàn)[3]就線性規(guī)劃問題的廣義單純形法進(jìn)行了研究，文獻(xiàn)[4]討論了對偶單純形法實(shí)質(zhì)就是單純形法,本質(zhì)是在運(yùn)用對偶單純形法解決線性規(guī)劃問題將單純形表旋轉(zhuǎn)90°進(jìn)行．由于信息技術(shù)的發(fā)展，單純型法在解決線性規(guī)劃問題時(shí)可以應(yīng)用標(biāo)準(zhǔn)軟件通過計(jì)算機(jī)來求解，然而理論基礎(chǔ)作為原理性的東西不能拋棄．本文根據(jù)單純形法理論結(jié)構(gòu)，巧妙的利用目標(biāo)函數(shù)和約束條件決策變量的系數(shù)構(gòu)造出一個(gè)矩陣，利用“換基迭代”原理對矩陣進(jìn)行初等變換，通過對變換后的矩陣的觀察，得出線性規(guī)劃問題何時(shí)出現(xiàn)無解、有最優(yōu)解、無窮多最優(yōu)解．

1 單純形法原理

1.1 基本思想

先找出一個(gè)基可行解,其方法是由約束方程組的系數(shù)矩陣找出子塊為單位陣In×n,則可作為初始可行基，在沒有的情況下可采用人工變量法尋找[7]．然后根據(jù)最優(yōu)性原則確定是否為最優(yōu)解,是則結(jié)束；不是則利用換基迭代尋找下一個(gè)基可行解，并且使下一個(gè)基可行解的目標(biāo)函數(shù)有所改變，反復(fù)多次，直到找出最優(yōu)解，或判斷出原問題無最優(yōu)解．

1.2 基本理論

用單純形法求線性規(guī)劃問題最優(yōu)解時(shí),常將問題化為標(biāo)準(zhǔn)型(非標(biāo)準(zhǔn)型可通過恒等變換和引入松馳變量等方法化為標(biāo)準(zhǔn)型):

其矩陣形式為

minf=CX

將A的列向量重排次序成A=(BN) ,相應(yīng)X=(XBXN)T,C=(CBCN),XB為基變量,XN為非基變量(若約束方程組中沒有現(xiàn)成的初始基,用人工變量法可得到初始基).于是

f=CBXB+CNXNAX=BXB+NXN=b

則:

XB=B-1b-B-1NXNf=CBB-1b+(CN-CBB-1N)XN

令非基變量XN=0,解得基變量XB=B-1b,稱(XBXN)為基解,當(dāng)XB的值都非負(fù)時(shí),則稱為基可行解.

若進(jìn)一步滿足:CN-CBB-1N≥0,則對一切可行解X,必有f≥CBB-1b,此時(shí)稱基可行解X=(B-1b,0)T為最優(yōu)解，當(dāng)條件不滿足時(shí),可通過“換基迭代”使條件滿足，從而得到線性規(guī)劃問題最優(yōu)解．

1.3 初等變換視角下的“換基迭代”

1.4 最優(yōu)解的討論

2 利用矩陣初等變換求線性規(guī)劃最優(yōu)解

單純形法求線性規(guī)劃問題最優(yōu)解的過程,實(shí)際是在表格中實(shí)施的,稱之為單純形表.而每個(gè)單純形表可用一個(gè)矩陣來代替,每次的換基迭代本質(zhì)上是對矩陣的初等變換.

2.1 矩陣的構(gòu)成

2.2 應(yīng)用舉例

此例來源于某工廠生產(chǎn)計(jì)劃，求目標(biāo)函數(shù)f的最小值．

minf=x1-3x2+2x3minf=x1-3x2+2x3

根據(jù)2.1構(gòu)成矩陣并做初等變換

矩陣中滿足-ci≤0(-11為f除外)，這說明非基變量從0增大為一個(gè)正數(shù)時(shí)，f必然增大，因此minf=-11，此時(shí)其最優(yōu)解為(x1,x2,x3,x4,x5,x6)T=(4,5,0,0,0,11)T．

本文介紹的方法最大的優(yōu)點(diǎn)是避開冗長的理論和論證，只要掌握矩陣的初等變換，就可以解決一般的線性規(guī)劃問題．

[1]賀學(xué)海．單純型法解決LP問題的研究 [J]．沈陽師范大學(xué)學(xué)報(bào)，2010,01，14-16.

[2]燕子宗 費(fèi)浦生 萬仲平．線性規(guī)劃的單純形法及其發(fā)展[J]．計(jì)算數(shù)學(xué)，2007，29(1)1-14.

[3]鄒自德．線性規(guī)劃問題的廣義單純形法 [J]． 電子科技大學(xué)學(xué)報(bào)，1997，26(增刊)， 143-148.

[4]林海明．線性規(guī)劃對偶單純形法的常識性經(jīng)濟(jì)解釋[J]．?dāng)?shù)學(xué)的實(shí)踐與認(rèn)識，2003，33(10).

[5]閻章杭，周建國，黃士林．高等數(shù)學(xué)與應(yīng)用數(shù)學(xué)基礎(chǔ)[M]．北京：中國人民公安大學(xué)出版社，2001，127-144.

[6]羅雁，簡金寶，吳志遠(yuǎn)．線性規(guī)劃一種改進(jìn)的對偶單純形法[J]．桂林工學(xué)院學(xué)報(bào)，2005,25(2)，263-266.

[7]王全文，吳育華，吳振奎，等．單純形法選擇進(jìn)出基變元的一個(gè)新準(zhǔn)則[J]．?dāng)?shù)學(xué)的實(shí)踐與認(rèn)識，2009，39(14)．

The Interpretation of the Simplex Method from the Perspective of Same Solution

HE Xue-hai，ZHANG Bin

(Shangqiu Vocational and Technical College, Shangqiu Henan 476000, China)

After the elementary transformation of the augmented matrix of linear equations, the transformed equation system and the original linear equation system are equivalent. With the aid of the theory above, the new matrix could be formed based on the augmented matrix of objective function and constraint condition in standard form of linear programming. Then, after the elementary transformation on the new matrix by the way of basis iteration and meeting certain requirements, the optimal solution in linear programming could be obtained by the transformed matrix.

the same solution; linearity programming; simplex; optimal solution

1673-2103(2017)02-0005-03

2017-02-12

河南省教育廳教學(xué)改革資助項(xiàng)目(2014SJGX386)

賀學(xué)海(1962-)，男，河南社旗人，教授，碩士，研究方向：函數(shù)論及應(yīng)用數(shù)學(xué).

O221．1

A