線性規(guī)劃問的有效集法

線性規(guī)劃問的有效集法

該算法是在20世紀(jì)80年代形成的，具有單純形理論的一些突出優(yōu)勢。有效集法可補(bǔ)充單純形法，在實(shí)踐中重要應(yīng)用。從本質(zhì)上講，有效集法和單純形法是一致的。在本文中，我們展示了有效集法的實(shí)際算法，并證明了上述兩種方法的一致性。1有效收集方法的實(shí)用算法單純形法是針對線性規(guī)劃問題的標(biāo)準(zhǔn)形式求解的.使用矩陣和向量的符號可以寫為其中設(shè)該基本可行解對應(yīng)的Ax=b典范型為其中1.1線性規(guī)劃初始可行解的確定(1)計(jì)算檢驗(yàn)數(shù).對(2)令(3)若αiq≤0(i=1,…,m),則(1.1)式有無限解:否則令其中p是使上式成立的最小下標(biāo),主元行標(biāo)號.(4)對j=1,…,n計(jì)算對i=1,…,m,i≠p,j=1,…,n計(jì)算轉(zhuǎn)(1).為確定初始基本可行解,考慮輔助線性規(guī)劃這里有效集法是針對線性規(guī)劃問題的一般形式求解的.(1.5)式可以寫為設(shè)1.2算法2下標(biāo),當(dāng)m(1)確定x線性無關(guān).記計(jì)算(3)若(4)計(jì)算其中s是使上式成立的最小下標(biāo).(5)若(6)若對所有i∈G-F(x其中r是使上式成立的最小下標(biāo).(8)對i=1,…,n計(jì)算,轉(zhuǎn)(2).為求初始可行點(diǎn),對任意點(diǎn)x令k=1,使用算法2求解(1.7)式,得x2使用有效集法求解線性規(guī)劃的標(biāo)準(zhǔn)則有2.1設(shè)從而當(dāng)在頂點(diǎn)轉(zhuǎn)移時(shí),選取使式成立的最小下標(biāo)s,把相應(yīng)的下標(biāo)從迭代步長為其中α其中p=r-m.新頂點(diǎn)這與單純形法也是一致的.因此,頂點(diǎn)的轉(zhuǎn)移就是基本可行解的轉(zhuǎn)移,幷且容易看出,在無限解的情形發(fā)生時(shí),結(jié)論也是一樣的.2.2使用有效集法中求可行點(diǎn)的方法,求(2.1)式的初始可行點(diǎn),首先取x從而求解引入松馳變量x同樣可以得到,使用有效集法求解系列線性規(guī)劃(1.7)式,對應(yīng)了使用單純形法求解輔助線性規(guī)劃(1.4)式:(1.7)式中的等式約束條件3使用條件約束下的乘子下面將證明,使用有效集法求解線性規(guī)劃的標(biāo)準(zhǔn)形式和一般形式,結(jié)果是相同的.不失一般性,考慮如下形式的線性規(guī)劃將x其中幷且y設(shè)x是(3.1)式的可行域的非退化頂點(diǎn),記并不妨設(shè)是對于相應(yīng)的矩陣其中-T是矩陣對(3.1)式,這里在求最小乘子時(shí),注意到不等式約束(3.3)式已成為等式約束,但是這些約束中的松馳變量所對應(yīng)的非負(fù)約束y關(guān)于迭代方向,對(3.1)式,3.1如果q對應(yīng)x≥0中的某個(gè)有效約束的下標(biāo),則在求解(3.2)式時(shí),最小乘子是3.2如果q對應(yīng)了不等式約束(3.3)式中的某個(gè)約束的下標(biāo),則在求解(3.2)式時(shí),最小乘子的下標(biāo)對應(yīng)了約束y由(3.5)式和(3.6)式可知,關(guān)于迭代步長,對(3.2))式,步長為式中:其中從而記容易得到即對(3.1)式和(3.2)式,步長也是一樣的.綜上所述,單純形法和有效集方法在本質(zhì)上是一致的.則由上述基本可行解開始求解(1.1)式的單純形法的具體步驟