线性分式规划的多项式时间算法

Polynomial Time Algorithms for Linear Fractional Programming

线性规划（ＬＰ）各种形式的多项式时间算法的研究和成果已相当成熟，但对线性分式规划（ＬＦＰ）的研究甚少．在理论上，ＬＦＰ可转换为ＬＰ，但ＬＰ的多项式时间算法求得的多半为近似解，且ＬＦＰ转换为ＬＰ是通过一个非线性分式映射实现的．因此研究和分析ＬＰ的各种多项式时间算法对ＬＦＰ的稳定性具有理论和实际意义．本文首先系统地分析了从ＬＦＰ到ＬＰ的转换及各种性质．然后，将ＬＰ的一些多项式时间算法推广到ＬＦＰ，最后证明它们仍可在多项式时间内求得满足精度的近似解．

The research and achievement about different kinds of polynomial time algorithms for linear programming (LP) have been more mature. but there is little of study about linear fractional programming (LFP). Theoretically LFP can be translated into LP. but the solutions generated by polynomial time algorithm for LP almost are approximate, moreover. the translation from LFP to LP is made by a nonlin early frational map. So it has theorical and practical sense to study and analyse the stability about LFP of Polynomial time algorithms for LP. This paper first analyses systematically the translation from LFP to LP and its various properties. Then it extends some polynomial time algorithms for LP to LFP, and shows that the extension algorithms still obtains an approximate solutions satisfying precision for LFP in polynomial time.