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

2、段都需作出最優(yōu)決策，從而使整個(gè)過程達(dá)到最優(yōu)。盡管在理論上動(dòng)態(tài)規(guī)劃是求解可分離整數(shù)規(guī)劃問題的理想方法，但“維數(shù)的災(zāi)難”卻限制了它在大型問題中的應(yīng)用。 替代約束方法通過將多個(gè)約束的原問題變成單個(gè)替代約束的松弛問題，而該松弛問題又可以通過動(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é)合起來，這樣既降低了維數(shù)，又可逐步消除對

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