有界約束整數(shù)規(guī)劃的廣義非線性Lagrangian方法.pdf

1、非線性Lagrangian方法是解決有界約束的整數(shù)規(guī)劃問(wèn)題的有效方法.在大多數(shù)情況下,線性Lagrangian松弛方法的強(qiáng)對(duì)偶性條件很難滿足,從而在求解此類問(wèn)題的最優(yōu)解的過(guò)程中會(huì)產(chǎn)生對(duì)偶間隙.也就是說(shuō),傳統(tǒng)的線性Lagrangian方法所求的最優(yōu)解僅僅是原問(wèn)題的一個(gè)下界,而不是原問(wèn)題的最優(yōu)解,從而致使線性Lagrangian搜索失效.相比之下,非線性Lagrangian方法針對(duì)線性Lagrangian這一弱點(diǎn),能夠有效地克服對(duì)偶間隙,直

2、接求解到有界約束整數(shù)規(guī)劃問(wèn)題的最優(yōu)解.目前,已經(jīng)有一些研究文獻(xiàn)針對(duì)有界約束的整數(shù)規(guī)劃問(wèn)題提出了不同形式的非線性Lagrangian函數(shù).這些非線性函數(shù)都具有近似強(qiáng)對(duì)偶性質(zhì),從而保證了該算法通過(guò)求解Lagrangian對(duì)偶問(wèn)題一定能求解出原問(wèn)題最優(yōu)解,保證了算法的可靠性.該文基于非線性Lagrangian方法的這一優(yōu)點(diǎn),在現(xiàn)有的各種Lagrangian方法的基礎(chǔ)上,研究非線性Lagrangian的共同的性質(zhì).該文通過(guò)構(gòu)造一族曲線形成對(duì)原問(wèn)

3、題的最優(yōu)解對(duì)應(yīng)的點(diǎn)的非線性支撐,根據(jù)這類曲線的基本特征提出了廣義的非線性Lagrangian方法.通過(guò)這一方法,我們可以構(gòu)造出各種形式的非線性Lagrangian函數(shù).同時(shí),各種現(xiàn)有的Lagrangian函數(shù)都是此廣義Lagrangian函數(shù)的特殊形式.這些函數(shù)都具有上述的非線性Lagrangian的近似強(qiáng)對(duì)偶性.也就是問(wèn)題的Lagrangian對(duì)偶問(wèn)題的最優(yōu)解必定是原問(wèn)題的最優(yōu)解.廣義Lagrangian函數(shù)的另一個(gè)重要的性質(zhì)是,只要