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

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

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

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

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

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

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