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

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

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

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