线性分式多乘积问题的ε-近似算法  

An ε-Approximation Algorithm for Linear Fractional Multiplicative Problems

作　　者：申子慧 陈玉松 申培萍 SHEN Zihui;CHEN Yusong;SHEN Peiping(Department of Basic Education,Shangqiu Institute of Technology,Shangqiu 476000,China;School of Mathematics and Statistics,North China University of Water Resources and Electric Power,Zhengzhou 450000,China)

机构地区：[1]商丘工学院基础教学部,河南商丘476000 [2]华北水利水电大学数学与统计学院,河南郑州450000

出　　处：《应用数学》2021年第4期877-884,共8页Mathematica Applicata

摘　　要：本文针对线性分式多乘积问题提出一个近似算法;该算法主要通过非均匀搜索网格结点,将等价问题转化为多项式个与结点参量相关的线性子问题,通过求解这些子问题获得原问题的全局近似最优解.本文不仅从理论上证明了算法的收敛性,且通过算例验证算法的可行性与有效性,最终给出算法的计算复杂度.In this paper, we present an approximation scheme for globally solving a class of linear fractional multiplicative problems. To solve the problems, we decompose the original problem into a polynomial number of linear minimization subproblems associated with grid points from nonuniform search.And a global approximation solution is obtained by solving these subproblems. Finally, we also show convergence and computational complexity of the algorithm. The results of two examples imply feasibility and effectiveness of the scheme.

关 键 词：分式多乘积 全局优化 近似算法 计算复杂度 

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