切平面在混合整數(shù)非線性規(guī)劃中的應用.pdf

1、混合整數(shù)非線性規(guī)劃（Mixed Integer Nonlinear Programming，MINLP）是一類包含連續(xù)和整數(shù)變量的非線性規(guī)劃問題。MINLP是整數(shù)規(guī)劃的一個重要分支，近幾十年來MINLP的應用有了快速的發(fā)展，其應用領域包括流程工業(yè)、金融、工程、管理科學和運籌學等各個領域。MINLP問題的求解算法包括確定型算法和啟發(fā)式算法，確定型算法是將難于求解的MINLP問題分解為相對容易求解的混合整數(shù)線性規(guī)劃問題（Mixed Inte

2、ger Linear Programming，MILP），其中一類分解方法是通過投影及對偶等方法將MINLP問題分解為MILP問題，另外一類是利用迭代構(gòu)造切平面的方法將原問題分解為簡單問題。 本文的目標是通過對求解凸MINLP問題的各種確定型算法的研究，明確切平面在確定型算法中的重要作用，利用切平面的構(gòu)造方法對已知算法進行改進，并爭取構(gòu)造出新的算法。 本文首先給出了切平面在確定型算法中的作用，給出了切平面構(gòu)造的位置和方法

3、與各種算法收斂速度的關系，得出結(jié)論：切平面的構(gòu)造影響算法的收斂速度，一般來說在非線性可行域邊界上構(gòu)造切平面的算法具有快的收斂速度，非線性可行域邊界上構(gòu)造的切平面稱為支撐超平面；又MINLP問題的性質(zhì)要求最優(yōu)解為整數(shù)點，因此如果可以給出在整數(shù)點處快速生成支撐超平面的方法，就得到了一個簡潔且收斂速度快的確定型算法。 基于此我們給出了求解MINLP問題的支撐超平面算法的一般形式，并證明了其收斂性，同時提出了三個具體支撐超平面算法，分別

4、為平行下降支撐超平面算法，基于內(nèi)點的支撐超平面算法和不基于內(nèi)點的支撐超平面算法。 外逼近（Outer Approximation， OA）算法是求解MINLP問題的一個重要算法，有著很廣泛的應用，該算法的缺點是需要利用兩個NLP問題的求解。我們將SHP算法的思想引入到OA算法中，給出改進的OA算法，我們稱新的算法為EOA（Extended Outer Approximation，EOA）算法。在EOA算法中，當?shù)谝粋€非線性規(guī)劃問

5、題無解時，利用Vinott's SHP算法生成一個支撐超平面，替換OA算法中通過求解第二個NLP問題生成的切平面。新算法繼承了OA算法在非線性可行域邊界整數(shù)點生成切平面的優(yōu)勢，同時減少了NLP問題的求解次數(shù)。 啟發(fā)式算法和確定型算法是求解MINLP問題的兩個不同類型的算法，確定型算法在求解MINLP問題時可以保證解的全局最優(yōu)性，但對大規(guī)模問題的求解需要很長的計算時間，啟發(fā)式方法不能保證解的全局最優(yōu)，但求解問題時具有快速、簡單的特