线性约束多项式整数规划问题的全局最优性条件  

Global Optimality Conditions for a Class of Polynomial Integer Programming Problems with Linear Constraints

作　　者：陈露[1] 李国权[1] 

机构地区：[1]重庆师范大学数学科学学院,重庆401331

出　　处：《重庆师范大学学报（自然科学版）》2017年第1期7-11,共5页Journal of Chongqing Normal University:Natural Science

基　　金：国家自然科学基金(No.11471062;No.11401064);重庆市自然科学基金(No.cstc2013jcyjA-00021);重庆市教委科技项目(No.KJ1500302)

摘　　要：【目的】带有线性等式约束的多项式整数规划问题有着广泛地实际应用,而且是NP-难问题。全局最优性条件作为理论研究是对全局最优解进行刻画,同时也是设计算法的重要依据。【方法】利用罚函数方法对此进行讨论,并用数值例子进行验证。【结果】给出了一类带有线性等式约束的多项式整数规划问题的全局最优性条件,包括充分性条件和必要性条件。【结论】通过所给的数值例子说明可以利用所给的全局最优性条件来判断一个给定的点是否是全局极小点。[Purposes]In this paper,a class of polynomial integer programming problems with linear equality constraints is considered.This class of problems has a wide range of practical applications and is NP hard.Global optimality conditions are to character the global minimize as theoretical research,which are also important criterion for designing global optimization methods.[Methods]We study the global optimality conditions by using the penalty function method,and give some examples to illustrate how to use the global optimality conditions to check a given point is or is not a global minimizer.[Findings]Some global optimality conditions for such problems are presented,including the necessary global optimality conditions and sufficient global optimality conditions.[Conclusions]The global optimality conditions can be used to check a given point is or is not a global minimizer.

关 键 词：多项式整数规划 线性等式约束 全局最优性条件 

分 类 号：O221.1[理学—运筹学与控制论]