线性分式规划的多项式算法
A Polynomial-Time Algorithm for Liner Fractional Programming
-
摘要: Charnes-Cooper提出了一种线性分式规划的算法。本文在此基础上证明了线性分式规划与一种特定的线性规划等价。将Karmarkar算法用于该线性规划,我们得到了线性分式规划的多项式算法。Abstract: A.Charnes and W.W.Cooper presented an algorithm for liner fractional programming.We prove that the liner fractional programming is an equivalent of a certain liner programming;then we use Karmarkar algorithm for the liner programming to get the polynomial-time algorithm for liner fractional programming.