Wikipedia

Linear-fractional programming

This is an old revision of this page, as edited by Isheden (talk | contribs) at 10:56, 11 April 2011. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

In mathematical optimization, linear-fractional programming (LFP) is a generalization of linear programming (LP). Whereas the objective function in linear programs are linear functions, the objective function in a linear-fractional program is a ratio of two linear functions. A linear program can be regarded as a special case of a linear-fractional program in which the denominator is the constant function one.

Both linear programming and linear-fractional programming represent optimization problems using linear equations and linear inequalities, which for each problem-instance define a feasible set. Fractional linear programs have a richer set of objective functions. Informally, linear programming computes a policy delivering the best outcome, such as maximum profit or lowest cost. In contrast, a linear-fractional programming is used to achieve the highest ratio of outcome to cost, the ratio representing the highest efficiency.

For example, in the context of LP we maximize the objective function profit = income − cost and might obtain maximal profit of $100 (= $1100 of income − $1000 of cost). Thus, in LP we have an efficiency of $100/$1000 = 0.1. Using LFP we might obtain an efficiency of $10/$50 = 0.2 with a profit of only $10, which requires only $50 of investment however.

Formally, a linear-fractional program is defined as

Linear-fractional programs are quasiconvex minimization problems with a monotone property, pseudoconvexity, which is a stronger property than quasiconvexity. A linear-fractional objective function is both pseudoconvex and pseudoconcave; these properties allow FLP problems to be solved by a variant of the simplex algorithm (of George B. Dantzig).[1][2][3][4] FLP problems can also be solved by the criss-cross algorithm, which is a "purely combinatorial" basis-exchange algorithm.[5]

References

  1. ^ Chapter five: Craven, B. D. (1988). Fractional programming. Sigma Series in Applied Mathematics. Vol. 4. Berlin: Heldermann Verlag. p. 145. ISBN 3-88538-404-3. MR 0949209. {{cite book}}: Cite has empty unknown parameter: |1= (help)
  2. ^ Template:Cite article
  3. ^ Template:Cite article
  4. ^ Murty (1983, Chapter 3.20 (pp. 160–164) and pp. 168 and 179)
  5. ^ Illés, Tibor; Szirmai, Ákos; Terlaky, Tamás (1999). "The finite criss-cross method for hyperbolic programming". European Journal of Operational Research. 114 (1): 198–214. doi:10.1016/S0377-2217(98)00049-6. ISSN 0377-2217. {{cite journal}}: Invalid |ref=harv (help)
  • Bajalinov, E. B. (2003). Linear-Fractional Programming: Theory, Methods, Applications and Software. Boston: Kluwer Academic Publishers.
  • Barros, Ana Isabel (1998). Discrete and fractional programming techniques for ___location models. Combinatorial Optimization. Vol. 3. Dordrecht: Kluwer Academic Publishers. pp. xviii+178. ISBN 0-7923-5002-2. MR 1626973. {{cite book}}: Cite has empty unknown parameter: |1= (help)
  • Craven, B. D. (1988). Fractional programming. Sigma Series in Applied Mathematics. Vol. 4. Berlin: Heldermann Verlag. p. 145. ISBN 3-88538-404-3. MR 0949209. {{cite book}}: Cite has empty unknown parameter: |1= (help)
  • Martos, Béla (1975). Nonlinear programming: Theory and methods. Amsterdam-Oxford: North-Holland Publishing Co. p. 279. ISBN 0-7204-2817-3. MR 0496692. {{cite book}}: Cite has empty unknown parameter: |1= (help)
  • Schaible, S. (1995). "Fractional programming". In Reiner Horst and Panos M. Pardalos (ed.). Handbook of global optimization. Nonconvex optimization and its applications. Vol. 2. Dordrecht: Kluwer Academic Publishers. pp. 495–608. ISBN 0-7923-3120-6. MR 1377091.
  • Stancu-Minasian, I. M. (1997). Fractional programming: Theory, methods and applications. Mathematics and its applications. Vol. 409. Dordrecht: Kluwer Academic Publishers Group. pp. viii+418. ISBN 0-7923-4580-0. MR 1472981. {{cite book}}: Cite has empty unknown parameter: |2= (help); Text "Translated by Victor Giurgiutiu from the 1992 Romanian" ignored (help)

Software

  • WinGULF – educational interactive linear and linear-fractional programming solver with a lot of special options (pivoting, pricing, branching variables etc.).
Retrieved from "https://en.wikipedia.org/w/index.php?title=Linear-fractional_programming&oldid=423493244"