求解幾類二層規(guī)劃最優(yōu)解的相關(guān)算法研究.pdf

1、重慶師范大學(xué)碩士學(xué)位論文求解幾類二層規(guī)劃最優(yōu)解的相關(guān)算法研究碩士研究生：趙禮陽(yáng)指導(dǎo)教師：霍永亮教授學(xué)科專業(yè)：運(yùn)籌學(xué)與控制論所在學(xué)院：數(shù)學(xué)科學(xué)學(xué)院重慶師范大學(xué)二零一六年五月重慶師范大學(xué)碩士學(xué)位畢業(yè)論文中文摘要I求解幾類二層規(guī)劃最優(yōu)解的相關(guān)算法研究摘要在現(xiàn)實(shí)生活中很多的實(shí)際問(wèn)題比如交通規(guī)劃、跨國(guó)貿(mào)易、物流分配、生產(chǎn)計(jì)劃等問(wèn)題都需要用層次性的系統(tǒng)問(wèn)題來(lái)刻畫問(wèn)題本身而在這種復(fù)雜的系統(tǒng)問(wèn)題中決策者可能不止一個(gè)不同的決策者同時(shí)還控制著不同的目標(biāo)函數(shù)

2、用常規(guī)的數(shù)學(xué)規(guī)劃模型不能更好的解決這類具有層次性的問(wèn)題.二層規(guī)劃模型是多層規(guī)劃模型最簡(jiǎn)單的表現(xiàn)形式多層規(guī)劃模型雖然比二層規(guī)劃模型要復(fù)雜很多其研究基礎(chǔ)還是離不開二層規(guī)劃想要進(jìn)一步研究多層規(guī)劃對(duì)二層規(guī)劃進(jìn)行詳細(xì)全面的分析探討是很有必要而又非常有意義的.本文從最簡(jiǎn)單的二層線性規(guī)劃到二層非線性規(guī)劃都做了詳細(xì)的介紹分析根據(jù)模型的特點(diǎn)和求解規(guī)模的不同對(duì)不同規(guī)模和特點(diǎn)的二層規(guī)劃問(wèn)題本文都給出了適合該模型特點(diǎn)的最優(yōu)化方法.由于二層線性規(guī)劃問(wèn)題的約束條件

3、和目標(biāo)函數(shù)的特殊性也就決定了其最優(yōu)解的特殊性.從求解單層線性規(guī)劃問(wèn)題中得到啟發(fā)二層線性規(guī)劃在閉區(qū)域上的最優(yōu)解也可以在該閉區(qū)域的頂點(diǎn)處搜索到.本文針對(duì)于這一性質(zhì)給出了改進(jìn)的二層線性規(guī)劃極點(diǎn)算法.該方法僅需要求解出約束域的極點(diǎn)和下層對(duì)偶問(wèn)題約束域的極點(diǎn)通過(guò)檢驗(yàn)得到的極點(diǎn)組合是否使得下層問(wèn)題對(duì)偶間隙等于零就可以判斷該極點(diǎn)是否為最優(yōu)解.該方法主要是避免了求解上、下層目標(biāo)函數(shù)在相應(yīng)約束域中的最優(yōu)解使得求解過(guò)程簡(jiǎn)單易行尤其針對(duì)求解小規(guī)模的二層線性規(guī)

4、劃問(wèn)題該方法具有計(jì)算難度小求解過(guò)程快精確度高等優(yōu)點(diǎn).但是對(duì)于問(wèn)題規(guī)模的擴(kuò)大隨著極點(diǎn)個(gè)數(shù)的增加對(duì)于求解約束域極點(diǎn)耗時(shí)過(guò)長(zhǎng).針對(duì)于這一缺點(diǎn)第三章進(jìn)一步給出了罰函數(shù)方法目前絕大多數(shù)的罰函數(shù)的基本思想都是想通過(guò)構(gòu)造某一懲罰項(xiàng)以此達(dá)到轉(zhuǎn)化二層規(guī)劃為單層規(guī)劃問(wèn)題的目的.與極點(diǎn)算法相比較而言該方法在求解大規(guī)?；蛘呒s束條件相對(duì)復(fù)雜的二層線性規(guī)劃問(wèn)題更具優(yōu)勢(shì).對(duì)于下層問(wèn)題為非線性或者上、下層都為非線性的二層規(guī)劃問(wèn)題利用對(duì)偶問(wèn)題來(lái)等價(jià)轉(zhuǎn)化二層規(guī)劃問(wèn)題為單層