• 论文 • 上一篇    下一篇

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

申培萍1, 申子慧2   

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

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

申培萍, 申子慧. 广义线性多乘积问题的完全多项式时间近似算法[J]. 计算数学, 2017, 39(3): 287-294.

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.
阅读次数
全文


摘要