Linear-fractional programming: Difference between revisions

Revision as of 17:22, 16 April 2023

Revision as of 13:11, 17 April 2023

Line 1:

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.

==Relation 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 = income − cost''' and might obtain maximum 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, but only requiring $50 of investment.

==Definition==

Formally, a linear-fractional program is defined as the problem of maximizing (or minimizing) a ratio of [[affine function]]s over a [[polyhedron]],

:<math>

Line 12 ⟶ 8:

\end{align}

</math>

where <math>\mathbf{x} \in \mathbb{R}^n</math> represents the vector of variables to be determined, <math>\mathbf{c}, \mathbf{d} \in \mathbb{R}^n</math> and <math>\mathbf{b} \in \mathbb{R}^m</math> are vectors of (known) coefficients, <math>A \in \mathbb{R}^{m \times n}</math> is a (known) matrix of coefficients and <math>\alpha, \beta \in \mathbb{R}</math> are constants. The constraints have to restrict the [[feasible region]] to <math>\{\mathbf{x} | \mathbf{d}^T\mathbf{x} + \beta > 0\}</math>, i.e. the region on which the denominator is positive.<ref name="CC">{{cite journal |last1=Charnes |first1=A. |last2=Cooper |first2=W. W. |author2-link=William W. Cooper |year=1962 |title=Programming with Linear Fractional Functionals |journal=Naval Research Logistics Quarterly |volume=9 |issue=3–4 |year=1962 |pages=181–186|mr=152370 |doi=10.1002/nav.3800090303 |mr=152370}}</ref><ref name="BV">{{cite book |titlelast1=ConvexBoyd Optimization|first1=Stephen P. |last1url=Boydhttps://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf |first2title=LievenConvex Optimization |last2=Vandenberghe |yearfirst2=2004Lieven |publisher=Cambridge University Press |year=2004 |isbn=978-0-521-83378-3 |urlpage=https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf151 |access-date=October 15, 2011|page=151}}</ref> Alternatively, the denominator of the objective function has to be strictly negative in the entire feasible region.

==RelationMotivation 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&nbsp;=&nbsp;income&nbsp;&minus;&nbsp;cost''' and might obtain maximum profit of $100 (=&nbsp;$1100&nbsp;of&nbsp;income&nbsp;&minus;&nbsp;$1000 of cost). Thus, in LP we have an efficiency of $100/$1000&nbsp;=&nbsp;0.1. Using LFP we might obtain an efficiency of $10/$50&nbsp;=&nbsp;0.2 with a profit of only $10, but only requiring $50 of investment.

==Transformation to a linear program==