【作者】 王粉兰；

【导师】 孙小玲；

【作者基本信息】 上海大学 ， 运筹学与控制论， 2006， 博士

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

【Abstract】 Integer programming deals with the problem of optimizing an objective function subjected to equality and/or inequality constraints and integer variables. If all the functions are linear, the problem is of a linear integer program. Otherwise, the problem is called a nonlinear integer program. The ultimate goal in integer optimization study is to develop efficient implementable algorithms for solving problems with integer variables. The development of efficient and robust algorithms and softwares for linear integer programming and the advent of high-speed computers have made linear integer programming an important tool for solving many real-world problems. However, many real-world problems cannot be modelled or approximated adequately by linear integer program problems, due to the nature of the nonlinearity of the objective function and/or the nonlinearity of the constraints. Rapid progress has been made in designing efficient solution methods for nonlinear integer programming during the past three decades. This thesis is devoted to develop efficient and robust algorithms for three classes of nonlinear integer programming problems.The thesis consists of five chapters. The motivations of the algorithms are presented in each chapter. The algorithms are then described with detailed numerical examples and graphical illustrations. Extensive computational experiments and numerical results are presented for each algorithm.Chapter 1 discusses the background of nonlinear integer programming and gives several examples of nonlinear integer programming problems from different application fields. such as stratified sampling and capital planning in manufacturing, etc.Chapter 2 presents an algorithm for a class of concave knapsack problem with a single linear constraint. The algorithm is of branch-and-bound method where lower bounds and upper bounds of the problem are computed by linearly underestimating the objective function. Domain cut-partition scheme is adopted to eliminate the duality gap. The lower bound can be improved during the iteration process. The algorithm finds an optimal solution of the primal problem in a finite number of iterations. Promising computational results are reported for large-scale concave更多还原