非線性整數(shù)規(guī)劃問題的若干新算法.pdf

1、整數(shù)規(guī)劃問題是指在一些等式約束、不等式約束和整數(shù)變量的限制下，最小化或最大化一個(gè)目標(biāo)函數(shù)的優(yōu)化問題。如果問題中的所有函數(shù)都是線性的，那就是線性整數(shù)規(guī)劃問題。否則，就稱之為非線性整數(shù)規(guī)劃問題。研究整數(shù)規(guī)劃的主要任務(wù)就是要設(shè)計(jì)一些有效算法來解決各種涉及整數(shù)變量的實(shí)際問題。隨著解決線性整數(shù)規(guī)劃問題的一系列高效算法和軟件的發(fā)展，再加上高速計(jì)算機(jī)的發(fā)明，線性整數(shù)規(guī)劃已經(jīng)成為解決各個(gè)領(lǐng)域?qū)嶋H問題的一個(gè)重要工具。然而，由于目標(biāo)函數(shù)的非線性性或者約束函

2、數(shù)的非線性性，使得應(yīng)用領(lǐng)域中的許多實(shí)際問題，不能用一個(gè)線性整數(shù)規(guī)劃問題來表示，甚至也不能用一個(gè)線性整數(shù)規(guī)劃問題來充分逼近。近30年來，人們?cè)谇蠼夥蔷€性整數(shù)規(guī)劃問題方面作出了很大努力，并且取得了很大進(jìn)展。與線性整數(shù)規(guī)劃和非線性連續(xù)優(yōu)化不同的是，非線性整數(shù)規(guī)劃幾乎沒有一種能應(yīng)用廣泛的有效算法，針對(duì)不同結(jié)構(gòu)和特性的問題所設(shè)計(jì)的算法有時(shí)差異會(huì)很大。在這一點(diǎn)非線性整數(shù)規(guī)劃與組合優(yōu)化很類似。本文就三類不同的非線性整數(shù)規(guī)劃問題給出了幾種有效的精確算法

3、。 全文共分五章，每章都有詳細(xì)的數(shù)值例子和圖形說明，而且還包含大量的計(jì)算實(shí)驗(yàn)，并且以表格的形式給出數(shù)值計(jì)算結(jié)果。 第一章介紹了非線性整數(shù)規(guī)劃問題的發(fā)展背景，并且給出幾個(gè)非線性整數(shù)規(guī)劃問題在不同應(yīng)用領(lǐng)域的實(shí)際模型，問題涉及分層抽樣的最優(yōu)樣本配置問題和制造業(yè)中的容量計(jì)劃問題等。 第二章研究了一類帶有單個(gè)線性約束的凹背包問題。我們對(duì)這類問題提出了一種有效的精確算法。該算法利用線性函數(shù)來下逼近目標(biāo)函數(shù)，通過求解松弛后的線

4、性規(guī)劃問題得到問題的下界和上界。然后運(yùn)用區(qū)域分割來消除對(duì)偶間隙。對(duì)每個(gè)子問題重復(fù)上述過程，下界在迭代過程中不斷更新。該算法經(jīng)過有限步迭代即可找到原問題的最優(yōu)解。數(shù)值結(jié)果表明該算法可以計(jì)算大規(guī)模的凹背包問題，變量個(gè)數(shù)可達(dá)1200個(gè)整數(shù)變量。我們還將算法與現(xiàn)有的其它算法進(jìn)行了比較，比較結(jié)果表明我們所提出的算法能更有效地解決凹背包問題。 第三章針對(duì)二次目標(biāo)函數(shù)的可分離非線性整數(shù)規(guī)劃問題，提出了一種收斂的拉格朗日和等值面切割法。該算法把

5、拉格朗日對(duì)偶方法和一種新穎的等值面切割法有效地結(jié)合起來。在算法的迭代過程中，拉格朗日對(duì)偶法用來產(chǎn)生問題的下界和上界，等值面切割法用來減小對(duì)偶間隙。我們首先給出單約束問題的算法，然后將其推廣到多約束情形和目標(biāo)函數(shù)是不定二次函數(shù)的情況。計(jì)算結(jié)果表明該算法是非常有效的，可以求解含有2000個(gè)整數(shù)變量的大規(guī)模二次可分離整數(shù)規(guī)劃問題。與其它算法的比較結(jié)果也表明我們的算法是令人滿意的。 第四章提出了一種拉格朗日和區(qū)域分割法用來求解多個(gè)線性約

6、束、有界變量的不可分離凸背包問題。該算法利用拉格朗日分解對(duì)偶法產(chǎn)生問題的一個(gè)上界、一個(gè)下界、一個(gè)可行解和一個(gè)不可行解。得到的可行解和不可行解用來進(jìn)行區(qū)域分割，這樣可以逐步減小對(duì)偶間隙。上界和下界可以用來去掉一些不存在最優(yōu)解的子問題。該算法經(jīng)過有限步迭代可以找到問題的最優(yōu)解。初步計(jì)算結(jié)果也在文中給出。 第五章總結(jié)了前面幾章提出的算法。這些算法本質(zhì)上都屬于分枝定界法的框架。算法的創(chuàng)新性在于針對(duì)不同的非線性整數(shù)規(guī)劃問題的特殊結(jié)構(gòu)，導(dǎo)出