Linear-fractional programming: Difference between revisions

Revision as of 00:56, 27 March 2011

Revision as of 16:34, 8 April 2011

Line 1:

In [[mathematical optimization]], '''linear-fractional programming (LFP)''' is a generalization of [[linear programming]] (LP). WhereWhereas the objective function ofin linear programs are [[linear functional|linear functions]], the objective function ofin a linear-fractional program is a ratio of two linear functions. In other words, a linear program is a fractional-linear-fractional 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 a linear-fractional programming model we can achieve the best (highest) ratio of outcome to cost, i.e. the highest efficiency.

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

FractionalLinear-linearfractional programs are [[quasiconvex function|quasiconvex]] [[convex minimization|minimization]] problems with a [[monotonicity|monotone]] property, "[[pseudoconvex function|pseudoconvexity]]", which is a stronger property than [[quasiconvex function|quasiconvexity]]. A fractional-linear-fractional objective function hasis both "pseudoconvexity"pseudoconvex and "pseudoconcavity",pseudoconcave; these properties allowingallow FLP problems to be solved by a variant of the [[simplex algorithm]] (of [[George B. Dantzig]]).<ref>

Chapter five: {{cite book| last=Craven|first=B. D.|title=Fractional programming|series=Sigma Series in Applied Mathematics|volume=4|publisher=Heldermann Verlag|___location=Berlin|year=1988|pages=145|isbn=3-88538-404-3 |id={{MR|949209}}| }}</ref><ref> {{cite article | last1=Kruk | first1=Serge|last2=Wolkowicz|first2=Henry|title=Pseudolinear programming | url=http://www.jstor.org/stable/2653207 |journal=[[SIAM Review]]|volume=41 |year=1999 |number=4 |pages=795-805 |id={{MR|1723002}}.{{jstor|2653207}}.{{doi|DOI:10.1137/S0036144598335259}}| }}

</ref><ref> {{cite article | last1=Mathis|first1=Frank H.|last2=Mathis|first2=Lenora Jane|title=A nonlinear programming algorithm for hospital management |url=http://www.jstor.org/stable/2132826|journal=[[SIAM Review]]|volume=37 |year=1995 |number=2 |pages=230-234|id={{MR|1343214}}.{{jstor|2132826}}.{{doi|DOI:10.1137/1037046}}|}}