Wikipedia

Linear-fractional programming

This is an old revision of this page, as edited by Kiefer.Wolfowitz (talk | contribs) at 00:47, 22 March 2011 (removed Category:Nonlinear programming using HotCat). 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). Where the objective function of linear programs are linear functions, the objective function of a linear-fractional program is a ratio of two linear functions. In other words, a linear program is a fractional-linear program in which the denominator is the constant function having the value one everywhere.

Informally, if linear programming determines the way to achieve the best outcome (such as maximum profit or lowest cost) in a given mathematical model and given some list of requirements represented as linear equations, in linear-fractional programming model we can achieve the best (highest) ratio of outcome to cost, i.e. highest efficiency.

For example, if in the frame of LP we maximize profit = income − cost and obtain maximal profit of 100 units (= $1100 of income − 1000$ of cost), then using LFP we can obtain only $10 of profit which requires only $50 of investment. Thus, in LP we have efficiency $100/$1000 = 0.1, at the same time LFP provides efficiency equal to $10/$50 = 0.2.

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

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. ^ 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=420066694"