求解可分離非線性整數(shù)規(guī)劃的新途徑.pdf

1、非線性整數(shù)規(guī)劃是最優(yōu)化理論的一個(gè)重要分支。當(dāng)所求解的非線性整數(shù)規(guī)劃問(wèn)題的目標(biāo)函數(shù)和約束函數(shù)都是可分函數(shù)時(shí)，稱(chēng)為可分離非線性整數(shù)規(guī)劃問(wèn)題。這一類(lèi)問(wèn)題在實(shí)際生活中有著廣泛的應(yīng)用，因此，近30年來(lái)受到了相當(dāng)大的關(guān)注。由于最優(yōu)化工作者的努力和計(jì)算機(jī)技術(shù)的高速發(fā)展，可分離非線性整數(shù)規(guī)劃的理論分析和計(jì)算方法取得了可喜的進(jìn)展。由于它的可分離性，該問(wèn)題可以通過(guò)動(dòng)態(tài)規(guī)劃來(lái)求解。動(dòng)態(tài)規(guī)劃是在最優(yōu)性原理的基礎(chǔ)上，將待解決問(wèn)題看成是一個(gè)多階段決策過(guò)程，每一個(gè)階

2、段都需作出最優(yōu)決策，從而使整個(gè)過(guò)程達(dá)到最優(yōu)。盡管在理論上動(dòng)態(tài)規(guī)劃是求解可分離整數(shù)規(guī)劃問(wèn)題的理想方法，但“維數(shù)的災(zāi)難”卻限制了它在大型問(wèn)題中的應(yīng)用。 替代約束方法通過(guò)將多個(gè)約束的原問(wèn)題變成單個(gè)替代約束的松弛問(wèn)題，而該松弛問(wèn)題又可以通過(guò)動(dòng)態(tài)規(guī)劃有效地求解，從而為減輕“維數(shù)的災(zāi)難”提供了一個(gè)很好的平臺(tái)，進(jìn)而被廣泛應(yīng)用于整數(shù)規(guī)劃中。因此，本文的主要工作就是在替代約束這一平臺(tái)上，將動(dòng)態(tài)規(guī)劃與割方法結(jié)合起來(lái)，這樣既降低了維數(shù)，又可逐步消除對(duì)

3、偶間隙，從而提供了一種求解可分離非線性整數(shù)規(guī)劃問(wèn)題的途徑。 對(duì)偶理論是構(gòu)造求解可分離非線性整數(shù)規(guī)劃問(wèn)題有效算法的基礎(chǔ)工具之一。替代對(duì)偶能夠?yàn)樽顑?yōu)值提供比拉格朗日對(duì)偶更佳的界，所以本文的另一主要工作就是改進(jìn)傳統(tǒng)的替代對(duì)偶方法，將替代對(duì)偶方法與割方法相結(jié)合，利用割方法達(dá)到更新替代對(duì)偶乘子、消除對(duì)偶間隙的目的，從而提出了又一種求解可分離非線性整數(shù)規(guī)劃問(wèn)題的算法。 全文共分四章。第一章介紹了可分離的非線性整數(shù)規(guī)劃的發(fā)展背景，給出