线性分式多乘积规划问题的多项式时间近似算法  

A Fully Polynomial Time Approximation Algorithm for Linear Fractional Multiplicative Programs

作　　者：申培萍[1] 黄冰迪 SHEN Peiping;HUANG Bingdi(College of Mathematics and Information Science,Henan Normal University,Xinxiang 453007,China)

机构地区：[1]河南师范大学数学与信息科学学院,河南新乡453007

出　　处：《应用数学》2018年第4期927-932,共6页Mathematica Applicata

基　　金：国家自然科学基金(11671122);河南省高等学校重点科研项目(17A110006)

摘　　要：本文首先将一般形式的线性分式多乘积规划问题(MP),转化为特殊形式的子问题.再根据子问题提出一种求解(MP)的完全多项式时间近似算法,并从理论上证明该算法的收敛性和计算复杂性,数值算例也说明了算法是可行的.In this article, we present a fully polynomial time approximation algorithm for solving a class of general linear fractional multiplicative programming（MP） problems. For solving the problem（MP）, we first convert the original problem（MP） into several subproblems where both the numerator and denominator of each ratio function are positive affine functions in the objective function. The proposed approximation algorithm can then find an ε-approximation solution for each subproblem. Thus, by using the subproblem solutions we can obtain an ε-approximation global optimization solution for problem（MP）, since the number of subproblem is finite. The convergence of the algorithm is proved, and an approximation fully polynomial time is given by analyzing the computational complexity of the algorithm.As the term p of fractional multiplicatives is fixed, there is a polynomial time dependency of the algorithm with respect to the inverse of the required precision, while there is an exponential time dependency with respect to p. Finally, the numerical examples show that the algorithm is feasible.

关 键 词：线性分式多乘积规划 全局优化 完全多项式时间近似算法 计算复杂性 

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