線性規(guī)劃主元算法研究.pdf

1、G.B.Dantzig于1947年開創(chuàng)的線性規(guī)劃理論及其單純形算法,是影響最深遠(yuǎn)和應(yīng)用最廣泛的數(shù)學(xué)工具之一.它在國民經(jīng)濟(jì)、科學(xué)技術(shù)、管理和工程等諸多領(lǐng)域有著廣泛的應(yīng)用.在線性規(guī)劃諸算法中,G.B.Dantzig的單純形算法,Khachiyan的橢球算法以及Karmarkar的內(nèi)點(diǎn)算法可謂為三大里程碑.本文的貢獻(xiàn)主要在線性規(guī)劃的主元算法這一領(lǐng)域,包括以下內(nèi)容:一.在潘平奇教授提出的虧基理論的框架下,本文首次將虧基理論推廣到帶有界約束的線性

2、規(guī)劃求解,建立了有界變量單純形算法的理論基礎(chǔ).在虧基單純形算法的基礎(chǔ)上,進(jìn)一步提出了虧基有界變量線性規(guī)劃單純形算法,證明了算法的收斂性,并建立了一個(gè)相應(yīng)的簡潔的一階段算法.二.在虧基概念及最鈍角規(guī)則的基礎(chǔ)上,本文利用最鈍角法則,在虧基的框架下建立了一個(gè)新的求原始可行解的一階段單純形算法.由于虧基的引入,在很大的程度上克服了退化帶來的困難;而最鈍角法則的應(yīng)用,則使我們能每次簡單地選取恰當(dāng)?shù)淖兞窟M(jìn)基,從而使新算法具有簡單易行且計(jì)算量小的特點(diǎn)

3、.三.Criss-cross算法的主要優(yōu)點(diǎn)是其簡潔優(yōu)美.它可從任一個(gè)基本解開始,僅用一個(gè)階段在有限步內(nèi)就可求解一般線性規(guī)劃問題,且求解的過程具有對稱性.但可惜其實(shí)際計(jì)算效率不高.本文提出一種新的有限的criss-cross算法,利用重排下標(biāo)的技巧,一方面保持了criss-cross算法原有的優(yōu)點(diǎn),另一方面提高了計(jì)算效率.同時(shí),新算法的有限性也得到了證明.四.線性規(guī)劃的主元算法(如單純形算法)最后可以到達(dá)一個(gè)精確的最優(yōu)解,但在計(jì)算過程中會(huì)

4、受到退化現(xiàn)象的嚴(yán)重干擾.內(nèi)點(diǎn)法雖沒有這個(gè)缺陷,但通常只能產(chǎn)生一個(gè)∈最優(yōu)解.要獲得精確最優(yōu)解,必須要有一個(gè)計(jì)算量不小的所謂的純化過程.本文將內(nèi)點(diǎn)算法與主元算法的技巧有機(jī)的結(jié)合起來,建立了一個(gè)混合算法.該算法具有兩者的優(yōu)點(diǎn).它不僅克服了退化現(xiàn)象帶來的困難,還可獲得一對精確的原始與對偶的最優(yōu)解.五.潘平奇教授提出的求解線性規(guī)劃的射影單純形算法,盡管在實(shí)踐中非常有效,卻仍然沒有完全擺脫由于退化而帶來的停頓現(xiàn)象.本文提出一個(gè)修正的射影單純形算法.