论文部分内容阅读
非线性整数规划是最优化理论的一个重要分支。当所求解的非线性整数规划问题的目标函数和约束函数都是可分函数时,称为可分离非线性整数规划问题。这一类问题在实际生活中有着广泛的应用,因此,近30年来受到了相当大的关注。由于最优化工作者的努力和计算机技术的高速发展,可分离非线性整数规划的理论分析和计算方法取得了可喜的进展。由于它的可分离性,该问题可以通过动态规划来求解。动态规划是在最优性原理的基础上,将待解决问题看成是一个多阶段决策过程,每一个阶段都需作出最优决策,从而使整个过程达到最优。尽管在理论上动态规划是求解可分离整数规划问题的理想方法,但“维数的灾难”却限制了它在大型问题中的应用。
替代约束方法通过将多个约束的原问题变成单个替代约束的松弛问题,而该松弛问题又可以通过动态规划有效地求解,从而为减轻“维数的灾难”提供了一个很好的平台,进而被广泛应用于整数规划中。因此,本文的主要工作就是在替代约束这一平台上,将动态规划与割方法结合起来,这样既降低了维数,又可逐步消除对偶间隙,从而提供了一种求解可分离非线性整数规划问题的途径。
对偶理论是构造求解可分离非线性整数规划问题有效算法的基础工具之一。替代对偶能够为最优值提供比拉格朗日对偶更佳的界,所以本文的另一主要工作就是改进传统的替代对偶方法,将替代对偶方法与割方法相结合,利用割方法达到更新替代对偶乘子、消除对偶间隙的目的,从而提出了又一种求解可分离非线性整数规划问题的算法。
全文共分四章。第一章介绍了可分离的非线性整数规划的发展背景,给出它的一般形式。第二章介绍几种求解可分离非线性整数规划问题的解法,包括分支定界方法、拉格朗日对偶方法和动态规划方法。第三章在替代约束方法基础上,将动态规划与目标水平割方法相结合,提出了一种收敛的替代约束目标水平割的动态规划算法。第四章,我们结合扰动函数说明了最优目标值界的情况。进一步,将传统的替代对偶搜索与目标水平割方法结合,通过目标水平割方法逐步消除替代对偶间隙,从而找到原问题的最优值。数值计算结果说明了所给方法是可行的、有效的。