一類m個(gè)方程的l

一類m個(gè)方程的l

0基于單純形法的線性規(guī)劃求解本文主要討論了具有線性限制的l。即在滿足1個(gè)等式約束,s個(gè)不等式約束條件下,對(duì)m個(gè)方程的L該類問題在數(shù)值計(jì)算,統(tǒng)計(jì)分析中均很有意義,目前解決此類問題最通常的方法是:將該問題轉(zhuǎn)化為特殊的線性規(guī)劃問題.然后用單純形法求解該線性規(guī)劃得到此類問題的解本文提出的算法是在文獻(xiàn)1算法的基本思想為了方便起見,我們引進(jìn)以下記號(hào):記其中稱集合為有效方程指標(biāo)集,簡(jiǎn)稱酉效集.為破壞約束方程指標(biāo)集.并計(jì)算有效集Z(2)若否則計(jì)算(3)計(jì)算對(duì)所有的j若|λ(4)求若λ(5)若|λ(6)取迭代方向,置(7)計(jì)算若V否則選取δ(8)更新迭代點(diǎn)和有效集.置(9)計(jì)算(10)置k=k+1,轉(zhuǎn)(1).(*)把該算法且有如下性質(zhì).定理1若x證設(shè)d是任意方向,考慮函數(shù)其中由于x由于d的任意性,特別對(duì)滿足證畢.定義1若對(duì)任意的點(diǎn)x,存在λ則稱λ定理2設(shè)x則x證由(7)式,只需證明,對(duì)任意的可行方向d,(8)式成立.由于乘子滿足(10)式和(11)式,并注意到d是可行方向,即證畢.定理2表明,算法的第(5)步在問題(1)的極小點(diǎn)處終止.引理1若在點(diǎn)則的極小點(diǎn).證考慮函數(shù)注意到乘子的意義,對(duì)任何滿足條件的d,均有所以若引理中的條件成立,將意味著集合{定理3若引理1的條件成立,則問題(1)無可行點(diǎn).定理3保證了當(dāng)問題無可行點(diǎn)時(shí),算法終止.定理4若在點(diǎn)證由問題(12)及(13)式,只需證明算法產(chǎn)生的方向d滿足c所以證畢.定理4保證了算法優(yōu)先求出可行點(diǎn).定理5若在點(diǎn)證由(7)是,只需證明由乘子定義及算法,有當(dāng)當(dāng)證畢.定理5保證了在不滿足最優(yōu)條件的情況下,算法產(chǎn)生的方向是下降方向.定義2:設(shè)rank(A)=n,如果在點(diǎn)x處,有n個(gè)線性無關(guān)的有效方程,則稱點(diǎn)x為問題(1)的一個(gè)基點(diǎn).定義3:若在點(diǎn)x處,所有的有效方程是線性無關(guān)的,則稱點(diǎn)x是非退化的.若問題(1)的所有基點(diǎn)均是非退化的,則稱問題(1)是非退化的.引理2:若x是一個(gè)基點(diǎn),其乘子向量λ不滿足最優(yōu)性條件(9)(10),則搜索步長(zhǎng)滿足證由算法第(7)步,無論所以(20)式成立.定理6若問題(1)是非退化的,則算法有限步終止.證分兩種情況討論,當(dāng)其中f(x)是問題(12)的目標(biāo)函數(shù).由于問題(1)的約束方程個(gè)數(shù)有限,經(jīng)有限步迭代達(dá)到問題(1)可行點(diǎn)或得出問題(1)無可行點(diǎn)的結(jié)論.若其中f(x)是問題(1)的目標(biāo)函數(shù).由于超定方程的個(gè)數(shù)有限,經(jīng)有限步迭代達(dá)到問題(