计算数学
       首页 |  期刊介绍 |  编委会 |  投稿指南 |  期刊订阅 |  下载中心 |  留言板 |  联系我们 |  重点论文 |  在线办公 | 
计算数学  2019, Vol. 41 Issue (2): 212-218    DOI:
论文 最新目录 | 下期目录 | 过刊浏览 | 高级检索 Previous Articles  |  Next Articles  
线性分式多乘积规划问题的完全多项式时间近似算法
申子慧1,2, 申培萍1,2
1. 商丘工学院基础教学部, 商丘 476000;
2. 河南师范大学数学与信息科学学院, 新乡 453007
A FULLY POLYNOMIAL TIME APPROXIMATION ALGORITHM FOR LINEAR FRACTIONAL MULTIPLICATIVE PROGRAMMING PROBLEMS
Shen Zihui1,2, Shen Peiping1,2
1. Department of Basic Education, Shangqiu Institute of Technology, Shangqiu 476000, China;
2. College of Mathematics and Information Science, Henan Normal University, Xinxiang 453007, China
 全文: PDF (283 KB)   HTML (1 KB)   输出: BibTeX | EndNote (RIS)      背景资料
摘要 本文针对线性分式多乘积规划问题,通过Charnes-Cooper转化将原问题转化为一个等价问题,借助此等价问题提出一个获得原问题全局近似最优解的算法,最终证明了算法的收敛性,且提供了算法运算时间的理论分析.
服务
把本文推荐给朋友
加入我的书架
加入引用管理器
E-mail Alert
RSS
作者相关文章
关键词线性分式多乘积   全局优化   近似算法   计算复杂性     
Abstract: In this article, an approximation algorithm is developed for a class of linear fractional multiplicative programming problems. The key to the method is converting the original problem to an equivalent problem by introducing the Charnes-Cooper transformation, based on which this algorithm is discussed. It turns out that this algorithm is convergent. Moreover, we provide the theoretical computational time of the algorithm.
Key wordslinear fractional multiplicative   global optimization   approximation algorithm   computational complexity   
收稿日期: 2018-02-04; 出版日期: 2019-05-18
基金资助:

国家自然科学基金(11671122).

通讯作者: 申培萍,E-mail:shenpeiping@163.com     E-mail: shenpeiping@163.com
引用本文:   
. 线性分式多乘积规划问题的完全多项式时间近似算法[J]. 计算数学, 2019, 41(2): 212-218.
. A FULLY POLYNOMIAL TIME APPROXIMATION ALGORITHM FOR LINEAR FRACTIONAL MULTIPLICATIVE PROGRAMMING PROBLEMS[J]. Mathematica Numerica Sinica, 2019, 41(2): 212-218.
 
[1] Pardalos P M, Phillips A T. Global optimization of fractional programs[J]. Journal of Global Optimization, 1991, 1:173-182.
[2] Benson H P, Boger G M. Outcome-space cutting-plane algorithm for linear multiplicative programming[J]. Journal of Optimization Theory and Applications, 2000, 104:301-332.
[3] Liu X J, Umegaki T, Yamamoto Y. Heuristic methods for linear multiplicative programming[J]. Journal of Global Optimization, 1999, 15:433-447.
[4] Kuno T. A Finite Branch-and-Bound Algorithm for Linear Multiplicative Programming[J]. Computational Optimization and Applications, 2001, 20:119-136.
[5] Benson H P. An outcome space branch and bound-outer approximation algorithm for convex multiplicative programming[J]. Journal of Global Optimization, 1999, 15:315-342.
[6] Konno H, Kuno T. Linear multiplicative programming[J]. Mathematical Programming, 1992, 56:51-64.
[7] Depetrini D, Locatelli M. Approximation of linear fractional-multiplicative problems[J]. Mathematical Programming, 2011, 128:437-443.
[1] 刘群锋, 陈景周, 徐钦桂. 多水平直接搜索全局优化方法[J]. 计算数学, 2017, 38(4): 297-311.
[2] 申培萍, 申子慧. 广义线性多乘积问题的完全多项式时间近似算法[J]. 计算数学, 2017, 39(3): 287-294.
[3] 高岳林, 吴佩佩. 非线性整数规划的一个新的无参数填充函数算法[J]. 计算数学, 2017, 39(3): 321-327.
[4] 申培萍, 申子慧. 一类广义分式规划问题的完全多项式时间近似算法[J]. 计算数学, 2015, 37(2): 179-185.
[5] 申培萍, 张永俊, 梁彦超. 一类广义分式规划问题的ε-近似算法[J]. 计算数学, 2014, 36(3): 303-308.
[6] 李慧贤,李英华. 改进的进化算法解最短路问题[J]. 计算数学, 2007, 28(1): 47-55.
[7] 余胜生,文元桥,周敬利. 隧道算法的分布式并行计算模型[J]. 计算数学, 2006, 27(4): 299-306.
[8] 靳利霞,唐焕文,李斌,计明军,朱训芝. 一类连续函数模拟退火算法及其收敛性分析[J]. 计算数学, 2005, 27(1): 19-30.
[9] 马万,王兴华. 多元积分方程自适应解法的最优化[J]. 计算数学, 2004, 26(2): 161-168.
[10] 何尚录,徐成贤. 求解一类非单调线性互补问题的路径跟踪法及其计算复杂性[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