| 线性比式和优化问题的完全多项式时间近似算法 |
| |
| 引用本文： | 申子慧,申培萍.线性比式和优化问题的完全多项式时间近似算法[J].应用数学,2019,32(1):176-182. |
| |
| 作者姓名： | 申子慧 申培萍 |
| |
| 作者单位： | 商丘工学院基础教学部;河南师范大学数学与信息科学学院 |
| |
| 基金项目： | 国家自然科学基金(11671122);商丘工学院青年课题(2018XKQ02) |
| |
| 摘 要： | 本文针对线性比式和优化问题提出一个完全多项式时间近似算法,该算法主要利用原问题的等价问题及网格结点参数获得有限个与结点参数相关的线性规划问题,通过求解这些线性规划问题获得原问题的近似最优解.最终证明算法的收敛性,并给出了算法的计算复杂度,通过计算结果呈现算法的有效性与可行性.
|
| 关 键 词： | 比式和 全局优化 近似算法 计算复杂性 |
| 收稿时间： | 2018/3/20 0:00:00 |
A Fully Polynomial Time Approximation Algorithm for Linear Sum-of-Ratios Optimization Problems |
| |
| SHEN Zihui,SHEN Peiping.A Fully Polynomial Time Approximation Algorithm for Linear Sum-of-Ratios Optimization Problems[J].Mathematica Applicata,2019,32(1):176-182. |
| |
| Authors: | SHEN Zihui SHEN Peiping |
| |
| Institution: | (Department of Basic Education,Shangqiu Institute of Technology,Shangqiu 476000,China;College of Mathematics and Information Science,Henan Normal University,Xinxiang 453007,China) |
| |
| Abstract: | In this paper, we present a fully polynomial time approximation scheme for a class of linear sum-of-ratios optimization problems. The algorithm we develop mainly exploits the original problem’s equivalent one and grid node parameters to acquire a finite number of linear programming subproblems,by solving which an optimal solution of the original problem can be obtained. In the end, we prove the algorithm’s convergence, and give the computational complexity. And computational results show the algorithm is effective and feasible. |
| |
| Keywords: | Sum-of-ratios Global optimization Approximation scheme Computational complexity |
| 本文献已被 CNKI 维普 等数据库收录！ |
| 点击此处可从《应用数学》浏览原始摘要信息 |
| 点击此处可从《应用数学》下载免费的PDF全文 |
|
