Linear-fractional programming: Difference between revisions

Revision as of 08:34, 13 December 2024

Latest revision as of 11:52, 20 August 2025

(2 intermediate revisions by 2 users not shown)

Line 1:

{{Short description|Concept in mathematical optimization}}

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 functional|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.

Line 14 ⟶ 15:

==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-CooperCharnes–Cooper transformation'''.<ref name="CC" /> The main idea is to introduce a new non-negative variable <math>t </math> to the program which will be used to rescale the constants involved in the program (<math>\alpha, \beta, \mathbf{b}</math>). This allows us to require that the denominator of the objective function (<math>\mathbf{d}^T \mathbf{x} + \beta</math>) equals 1. (To understand the transformation, it is instructive to consider the simpler special case with <math>\alpha = \beta = 0</math>.)

Formally, the linear program obtained via the Charnes-CooperCharnes–Cooper transformation uses the transformed variables <math>\mathbf{y} \in \mathbb{R}^n</math> and <math>t \ge 0 </math>:

:<math>

Line 44 ⟶ 45:

\end{align}

</math>

which is an LP and which coincides with the dual of the equivalent linear program resulting from the Charnes-CooperCharnes–Cooper transformation.

==Properties and algorithms==