一类多乘积规划问题的单纯形分支定界方法  

Simplex branch and bound method of a class multi-product programming problem

作　　者：魏飞[1] 高岳林[1] 刘俊梅[1] 

机构地区：[1]北方民族大学信息与系统科学研究所,银川750021

出　　处：《黑龙江大学自然科学学报》2011年第1期61-66,共6页Journal of Natural Science of Heilongjiang University

基　　金：国家自然科学基金资助项目(60962006)

摘　　要：利用对数函数的性质将一类多乘积规划问题等价地转化为一个凹最小问题。针对这个问题的凹和特殊结构,利用单纯形上凹函数凸包络的线性性质,给出线性规划松弛问题以确定原问题最优值的下界,由此提出一类多乘积规划问题的单纯形分支定界算法,并且给出收敛性证明。数值例子表明所提出的算法是可行的和有效的。A class of multi-product programming problems is equivalently converted into a concave minimum prob- lem by using the properties of logarithmic function. For the concave-sum special structures and with that property that the convex envelope of concave function is linear on simplex, a linear programming relaxation problem is given to determine the lower bound of the global optimal value of the original problem. Thereby, a simplex branch and bound method for solving a class of multi-product problems is proposed and the convergence proof of the proposed method is given. Numerical examples show that the proposed method is feasible and effective.

关 键 词：全局优化 凹乘积规划 分支定界方法 凸包络 

分 类 号：O211.1[理学—概率论与数理统计]