在线咨询
中国工业与应用数学学会会刊
主管：中华人民共和国教育部
主办：西安交通大学
ISSN 1005-3085  CN 61-1269/O1
工程数学学报

工程数学学报 ›› 2017, Vol. 34 ›› Issue (6): 599-608.doi: 10.3969/j.issn.1005-3085.2017.06.003

• • 上一篇    下一篇

一类带有常系数线性乘积规划问题的分支定界缩减方法

井   霞,   高   磊   

  1. 宝鸡文理学院数学与信息科学学院，宝鸡  721013
  • 收稿日期:2016-10-11 接受日期:2017-07-20 出版日期:2017-12-15 发布日期:2018-02-15
  • 基金资助:
    国家自然科学基金(31600299)；陕西省自然科学基础研究计划项目(2017JQ3020)；陕西省高校科协青年人才托举项目(20160234)；宝鸡文理学院校级项目(ZK2017021; ZK2017095).

A Branch and Bound Reduction Algorithm for Solving a Class of Linear Multiplicative Programming Problems with Constant Coefficients

JING Xia,   GAO Lei   

  1. School of Mathematics and Information Science, Baoji University of Arts and Sciences, Baoji 721013
  • Received:2016-10-11 Accepted:2017-07-20 Online:2017-12-15 Published:2018-02-15
  • Supported by:
    The National Natural Science Foundation of China (31600299); the Natural Science Foundation of Shaanxi Province (2017JQ3020); the Young Talent Fund of University Association for Science and Technology in Shaanxi Province (20160234); the Research Foundation of Baoji University of Arts and Sciences (ZK2017021; ZK2017095).

PDF (PC)

215

摘要： 本文给出了一种求解带有常系数线性乘积规划问题的分支定界缩减算法．我们首先利用两个变量乘积的凸包络技术，分别得到目标函数与约束函数中乘积的上界与下界估计，由此构造出原问题的一个松弛凸规划问题．在此基础之上，借助超矩形的缩减技术，提出了确定原问题全局最优值下界的分支定界缩减算法，并从理论上分析了算法的收敛性．最后，利用数值实验验证了算法的有效性与可行性．

关键词: 全局最优化, 乘积约束, 线性乘积规划, 分支定界, 松弛规划

Abstract: We propose a new branch and bound reduction algorithm for solving a class of linear multiplicative programming problems with constant coefficients. Firstly, by utilizing the convex envelopes of the products of two variables, the lower and upper bounds for the multiplications in the objective and constraint functions are determined. And we use these bounds to construct the corresponding convex programming relaxation for the original problem. Then, resorting to the hyper-rectangular reduction strategy, a new branch and bound reduction algorithm is designed. It is shown that this new algorithm is globally convergent. Numerical examples are presented to illustrate the effectiveness of the proposed algorithm.

Key words: global optimization, multiplicative constraints, linear multiplicative programming, branch and bound, relaxed programming problem

中图分类号: