线性比式和优化问题的完全多项式时间近似算法  

A Fully Polynomial Time Approximation Algorithm for Linear Sum-of-Ratios Optimization Problems

作　　者：申子慧 申培萍 SHEN Zihui;SHEN Peiping(Department of Basic Education,Shangqiu Institute of Technology,Shangqiu 476000,China;College of Mathematics and Information Science,Henan Normal University,Xinxiang 453007,China)

机构地区：[1]商丘工学院基础教学部,河南商丘476000 [2]河南师范大学数学与信息科学学院,河南新乡453007

出　　处：《应用数学》2019年第1期176-182,共7页Mathematica Applicata

基　　金：国家自然科学基金(11671122);商丘工学院青年课题(2018XKQ02)

摘　　要：本文针对线性比式和优化问题提出一个完全多项式时间近似算法,该算法主要利用原问题的等价问题及网格结点参数获得有限个与结点参数相关的线性规划问题,通过求解这些线性规划问题获得原问题的近似最优解.最终证明算法的收敛性,并给出了算法的计算复杂度,通过计算结果呈现算法的有效性与可行性.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.

关 键 词：比式和 全局优化 近似算法 计算复杂性 

分 类 号：O221.2[理学—运筹学与控制论]