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

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

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

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

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

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