In mathematical optimization, linear-fractional programming (LFP) is a generalization of linear programming (LP). Whereas the objective function in a linear program is a linear function, 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 1.

Formally, a linear-fractional program is defined as the problem of maximizing (or minimizing) a ratio of affine functions over a polyhedron, are constants. The constraints have to restrict the feasible region, i.e. the region on which the denominator is positive. Alternatively, the denominator of the objective function has to be strictly negative in the entire feasible region.

Motivation by comparison to linear programming

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=incomecost and might obtain maximum profit of $100 (=$1100ofincome$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, but only requiring $50 of investment.

Transformation to a linear program

Any linear-fractional program can be transformed into a linear program, assuming that the feasible region is non-empty and bounded, using the Charnes–Cooper transformation..)

:

to the original linear-fractional program can be translated to a solution of the transformed linear program via the equalities

of the transformed linear program can be translated to a solution of the original linear-fractional program via

Duality

Let the dual variables, respectively. Then the dual of the LFP above is which is an LP and which coincides with the dual of the equivalent linear program resulting from the Charnes–Cooper transformation.

Properties and algorithms

The objective function in a linear-fractional problem is both quasiconcave and quasiconvex (hence quasilinear) with a monotone property, pseudoconvexity, which is a stronger property than quasiconvexity. A linear-fractional objective function is both pseudoconvex and pseudoconcave, hence pseudolinear. Since an LFP can be transformed to an LP, it can be solved using any LP solution method, such as the simplex algorithm (of George B. Dantzig), the criss-cross algorithm, or interior-point methods.

Notes

Sources

Further reading