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

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

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

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