雍龙泉

(陕西理工学院 数学与计算机科学学院， 陕西 汉中 723000)



约束二进制二次规划测试函数的一个构造方法

雍龙泉

(陕西理工学院 数学与计算机科学学院， 陕西 汉中 723000)

[摘要]基于盖尔圆定理, 给出了约束二进制二次规划测试函数的一个构造方法: 对原问题, 通过线性变换, 得到一个新的不定二次规划, 且该不定二次规划恰好以给定初始点为最优解; 进而构造出了一系列具有共同最优解的约束二进制二次规划。

[关键词]二进制二次规划;测试函数;半正定矩阵;盖尔圆定理

非线性整数规划在经济、计算机科学、工程技术中有非常重要的应用。 多年的研究表明, 非线性整数规划是数学规划和运筹学中最困难的研究领域之一。 即使是形式上看起来很简单的线性约束二次整数规划在全空间上求解也是不可判定的, 即不存在求解该问题的算法。 因此, 在求解非线性整数规划问题时, 往往要假定是在有界闭箱上进行求解。 0-1二次规划是一类特殊的非线性整数规划, 国外学者Barhona和Hansen对0-1二次规划做了大量的研究, 并且给出了一些具体的实例[1-2]；国内学者对0-1二次规划也做了大量的研究, 得到了一些比较好的结果[3-5]。 总体上说, 求解非线性整数规划问题的方法到目前为止还不多, 现有的算法可分为3类：(1)化为等价问题，主要包含化为连续优化问题的方法和线性化为整数规划问题的方法； (2)分支定界法，对目标函数和约束函数是可定界的非线性整数规划问题, 这种方法是适用的；……