兩層規(guī)劃的逼近理論及算法研究.pdf

1、兩層規(guī)劃問題在經(jīng)濟、管理和軍事等領域都有著廣泛的應用.從數(shù)學上來講，兩層規(guī)劃問題的求解非常復雜:兩層規(guī)劃問題是NP-hard問題;對由兩層規(guī)劃轉化成的單層規(guī)劃問題，傳統(tǒng)的約束規(guī)格在可行域上經(jīng)常不成立.本文主要研究兩層規(guī)劃問題的逼近問題，啟發(fā)式算法及在交通網(wǎng)絡中的應用.
　　第二章，研究非凹兩層規(guī)劃問題的近似問題.將兩層規(guī)劃轉化成單層規(guī)劃問題傳統(tǒng)的方法是:KKT值函數(shù)方法和值函數(shù)方法，但是對于非凹兩層規(guī)劃問題來說，這兩種方法經(jīng)常會同

2、時失效.通過值函數(shù)方法和ε-精確罰函數(shù)方法組合的方法克服這一困難.給下層問題一個擾動，引入下層問題的ε-解集，和ε-誤差界.將擾動后的問題轉化成單層近似問題，最后證明了在一定條件下，當擾動ε充分小時，近似問題的解趨近于原兩層規(guī)劃問題的解.最后用一個非凹兩層規(guī)劃的例子分析了理論的正確性.
　　第三章，考慮具有連續(xù)控制變量的網(wǎng)絡優(yōu)設計問題，其網(wǎng)絡用戶滿足Wardrop第一均衡原理.對這類網(wǎng)絡優(yōu)化問題，我們研究一種啟發(fā)式算法的效率評價問

3、題，該算法最早是由[41]提出.啟發(fā)式算法是一種能在可接受的費用內尋找最好的解的技術，但不一定能保證所得解的可行性和最優(yōu)性，甚至在多數(shù)情況下，無法闡述所得解同最優(yōu)解的近似程度.我們將POA(Price of Anarchy)引入到算法的效率評價理論中，利用函數(shù)的廣義非線性度和廣義陡峭度對該算法進行了定量的評價.最后利用一個算例驗證了算法效率評價標準的合理性和有效性.
　　第四章，討論Hilbert空間中帶均衡約束的優(yōu)化問題的弱穩(wěn)定