计算数学
       首页 |  期刊介绍 |  编委会 |  投稿指南 |  期刊订阅 |  下载中心 |  留言板 |  联系我们 |  在线办公 | 
计算数学  2017, Vol. 39 Issue (3): 287-294    DOI:
论文 最新目录 | 下期目录 | 过刊浏览 | 高级检索 Previous Articles  |  Next Articles  
广义线性多乘积问题的完全多项式时间近似算法
申培萍1, 申子慧2
1. 河南师范大学数学与信息科学学院, 新乡 453007;
2. 商丘工学院基础教学部, 商丘 476000
A FULL POLYNOMIAL TIME APPROXIMATION ALGORITHM FOR GENERALIZED LINEAR MULTIPLICATIVE PROBLEMS
Shen Peiping1, Shen Zihui2
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
 全文: PDF (312 KB)   HTML (1 KB)   输出: BibTeX | EndNote (RIS)      背景资料
摘要 本文针对广义线性多乘积极小化问题,通过一系列的线性规划问题的解提出一种求其全局最优解的完全多项式时间近似算法,并给出该算法的计算复杂性,且数值算例验证该算法是可行的.
服务
把本文推荐给朋友
加入我的书架
加入引用管理器
E-mail Alert
RSS
作者相关文章
关键词线性多乘积   全局优化   近似算法   计算复杂性     
Abstract: 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.
Key wordsLinear multiplicative   Global optimization   Approximation algorithm   Computational complexity   
收稿日期: 2015-07-04;
基金资助:

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

引用本文:   
. 广义线性多乘积问题的完全多项式时间近似算法[J]. 计算数学, 2017, 39(3): 287-294.
. A FULL POLYNOMIAL TIME APPROXIMATION ALGORITHM FOR GENERALIZED LINEAR MULTIPLICATIVE PROBLEMS[J]. Mathematica Numerica Sinica, 2017, 39(3): 287-294.
 
[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]. 计算数学, 2017, 39(3): 321-327.
[2] 申培萍, 申子慧. 一类广义分式规划问题的完全多项式时间近似算法[J]. 计算数学, 2015, 37(2): 179-185.
[3] 申培萍, 张永俊, 梁彦超. 一类广义分式规划问题的ε-近似算法[J]. 计算数学, 2014, 36(3): 303-308.
[4] 李慧贤,李英华. 改进的进化算法解最短路问题[J]. 计算数学, 2007, 28(1): 47-55.
[5] 余胜生,文元桥,周敬利. 隧道算法的分布式并行计算模型[J]. 计算数学, 2006, 27(4): 299-306.
[6] 靳利霞,唐焕文,李斌,计明军,朱训芝. 一类连续函数模拟退火算法及其收敛性分析[J]. 计算数学, 2005, 27(1): 19-30.
[7] 马万,王兴华. 多元积分方程自适应解法的最优化[J]. 计算数学, 2004, 26(2): 161-168.
[8] 何尚录,徐成贤. 求解一类非单调线性互补问题的路径跟踪法及其计算复杂性[J]. 计算数学, 2001, 23(3): 299-306.

Copyright 2008 计算数学 版权所有
中国科学院数学与系统科学研究院 《计算数学》编辑部
北京2719信箱 (100190) Email: gxy@lsec.cc.ac.cn
本系统由北京玛格泰克科技发展有限公司设计开发
技术支持: 010-62662699 E-mail:support@magtech.com.cn
京ICP备05002806号-10