• 论文 •

### 广义线性多乘积问题的完全多项式时间近似算法

1. 1. 河南师范大学数学与信息科学学院, 新乡 453007;
2. 商丘工学院基础教学部, 商丘 476000
• 收稿日期:2015-07-04 出版日期:2017-08-15 发布日期:2017-08-04
• 基金资助:

国家自然科学基金（11671122）；河南省高等学校重点科研项目基础研究计划

Shen Peiping, Shen Zihui. A FULL POLYNOMIAL TIME APPROXIMATION ALGORITHM FOR GENERALIZED LINEAR MULTIPLICATIVE PROBLEMS[J]. Mathematica Numerica Sinica, 2017, 39(3): 287-294.

### A FULL POLYNOMIAL TIME APPROXIMATION ALGORITHM FOR GENERALIZED LINEAR MULTIPLICATIVE PROBLEMS

Shen Peiping1, Shen Zihui2

1. 1. College of Mathematics and Information Science, Henan Normal University, Xinxiang 453007, China;
2. Department of Basic Education, Shangqiu Institute of Technology, Shangqiu 476000, China
• Received:2015-07-04 Online:2017-08-15 Published:2017-08-04

In this article we consider the problem of minimizing a class of generalized linear multiplicative function over a polytope and present a fully polynomial time approximation algorithm for globally solving this problem. The computational complexity result of the algorithm is derived, and the numerical examples show that the algorithm is feasible.

MR(2010)主题分类:

()
 [1] Bennett K P. Global tree optimization:A non-greedy decision tree algorithm[J]. Computing Sciences and Statistics, 1994, 26:156-160.[2] Depetrini D, Locatelli M. Approximation algorithm for linear fractional multiplicative problems[J]. Mathematical Programming, 2011, 128:437-443.[3] 申培萍, 赵小科. 线性分式规划问题的多项式时间近似算法[J]. Mathematica Applicata, 2013, 26:355-359.[4] Goyal V, Ravi R. An FPTAS for minimizing a class of low-rank quasi-concave functions over convex set[J]. Operations Research Letters, 2013, 41:191-196.[5] Henderson J M, Quandt R E. Microeconomics, McGraw-Hill, New York, 1971.[6] Konno H, Kuno T. Generalized linear multiplicative and fractional programming[J]. Annals of Operations Research, 1990, 25:147-162.[7] Konno H, Shirakawa H, Yamazaki H. A mean-absolute deviation-skewness protfolio optimazation model[J]. Annals of Operations Research, 1993, 45:205-220.[8] Konno H, Yajima Y, Kuno T. An outer approximation method for minimizing the product of several convex functions on a convex set[J]. Journal of Global Optimization, 1993, 3:325-335.[9] Maranas C D, Androulakis I P, Floudas C A, Berger A J, Mulvey J M. Solving long-term financial planning problems via global optimization[J]. Journal of Economic Dynamics Control, 1997, 21:1405-1425.[10] Schaible S, Sodini C. Finite algorithm for generalized linear multiplicative programming[J]. Journal of Optimization Theory and Applications, 1995, 87:441-455.[11] Wang, C F, Shen P P. A global optimization algorithm for linear fractional programming[J]. Applied Mathematics and Computation, 2008, 204:281-287.
 [1] 申子慧, 申培萍. 线性分式多乘积规划问题的完全多项式时间近似算法[J]. 计算数学, 2019, 41(2): 212-218. [2] 高岳林, 吴佩佩. 非线性整数规划的一个新的无参数填充函数算法[J]. 计算数学, 2017, 39(3): 321-327. [3] 申培萍, 申子慧. 一类广义分式规划问题的完全多项式时间近似算法[J]. 计算数学, 2015, 37(2): 179-185. [4] 申培萍, 张永俊, 梁彦超. 一类广义分式规划问题的ε-近似算法[J]. 计算数学, 2014, 36(3): 303-308. [5] 靳利霞,唐焕文,李斌,计明军,朱训芝. 一类连续函数模拟退火算法及其收敛性分析[J]. 计算数学, 2005, 27(1): 19-30. [6] 马万,王兴华. 多元积分方程自适应解法的最优化[J]. 计算数学, 2004, 26(2): 161-168. [7] 何尚录,徐成贤. 求解一类非单调线性互补问题的路径跟踪法及其计算复杂性[J]. 计算数学, 2001, 23(3): 299-306.