非线性整数规划问题的若干新算法

论文摘要

整数规划问题是指在一些等式约束、不等式约束和整数变量的限制下，最小化或最大化一个目标函数的优化问题。如果问题中的所有函数都是线性的，那就是线性整数规划问题。否则，就称之为非线性整数规划问题。研究整数规划的主要任务就是要设计一些有效算法来解决各种涉及整数变量的实际问题。随着解决线性整数规划问题的一系列高效算法和软件的发展，再加上高速计算机的发明，线性整数规划已经成为解决各个领域实际问题的一个重要工具。然而，由于目标函数的非线性性或者约束函数的非线性性，使得应用领域中的许多实际问题，不能用一个线性整数规划问题来表示，甚至也不能用一个线性整数规划问题来充分逼近。近30年来，人们在求解非线性整数规划问题方面作出了很大努力，并且取得了很大进展。与线性整数规划和非线性连续优化不同的是，非线性整数规划几乎没有一种能应用广泛的有效算法，针对不同结构和特性的问题所设计的算法有时差异会很大。在这一点非线性整数规划与组合优化很类似。本文就三类不同的非线性整数规划问题给出了几种有效的精确算法。 全文共分五章，每章都有详细的数值例子和图形说明，而且还包含大量的计算实验，并且以表格的形式给出数值计算结果。 第一章介绍了非线性整数规划问题的发展背景，并且给出几个非线性整数规划问题在不同应用领域的实际模型，问题涉及分层抽样的最优样本配置问题和制造业中的容量计划问题等。 第二章研究了一类带有单个线性约束的凹背包问题。我们对这类问题提出了一种有效的精确算法。该算法利用线性函数来下逼近目标函数，通过求解松弛后的线性规划问题得到问题的下界和上界。然后运用区域分割来消除对偶间隙。对

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 非线性整数规划的发展背景
• 1.2 非线性整数规划模型
• 1.2.1 分层抽样中的最优样本配置
• 1.2.2 制造业容量计划问题
• 1.2.3 投资组合问题
• 1.3 非线性整数规划问题的一般形式及常用解法
• 1.4 可分离的非线性整数规划问题
• 1.4.1 混合算法
• 1.5 非线性背包问题
• 1.5.1 一般形式及应用
• 1.5.2 非线性背包问题的现有解法
• 1.5.3 非凸背包问题的现状及本文所做的相关工作
• 1.6 目标函数是二次函数的可分离整数规划问题
• 1.6.1 二次可分离整数规划问题的应用及现有的解法
• 1.6.2 拉格朗日对偶方法和本文所做的相关工作
• 1.7 不可分离凸背包问题
• 1.7.1 不可分离凸背包问题的现有解法
• 1.7.2 拉格朗日分解方法和本文所做的相关工作
• 第二章 凹背包问题的一种精确算法
• 2.1 用线性下逼近求原问题的界
• 2.2 区域分割
• 2.3 求精确解的算法
• 2.4 数值结果
• 2.5 结论
• 第三章 具有二次目标函数的可分离整数规划问题的一种收敛的拉格朗日等值面切割算法
• 3.1 拉格朗日对偶及对偶搜索
• 3.1.1 对偶搜索
• 3.2 二次目标函数的等值面切割法
• 3.2.1 椭球体等值面
• 3.2.2 等值面切割
• 3.3 单约束问题的收敛拉格朗日等值面切割法
• 3.3.1 算法提出的动机
• 3.3.2 主要算法
• 3.4 多个约束的情况
• 3.5 目标函数为不定二次函数的情况
• 3.6 数值结果
• 3.6.1 测试问题
• 3.6.2 数值实验
• 3.6.3 与其它方法的比较
• 3.7 结论
• 第四章 不可分离凸背包问题的拉格朗日分解和域分割法
• 4.1 拉格朗日分解法
• 4.2 求解最优解的算法
• 4.3 数值结果
• 4.4 结论
• 第五章 总结
• 参考文献
• 本人在博士期间所发表的论文
• 致谢