Content deleted Content added
Tom.Reding (talk | contribs) |
LucasBrown (talk | contribs) Changing short description from "Concept in mathematical opimization" to "Concept in mathematical optimization" |
||
| (24 intermediate revisions by 13 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
==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.▼
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 ⟶ 9:
\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
▲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
==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'''.<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–Cooper transformation uses the transformed variables <math>\mathbf{y} \in \mathbb{R}^n</math> and <math>t \ge 0 </math>:
:<math>\mathbf{y} = \frac{1}{\mathbf{d}^T \mathbf{x} + \beta} \cdot \mathbf{x}\;;\;\; t = \frac{1}{\mathbf{d}^T \mathbf{x} + \beta}</math>▼
:<math>
Line 30 ⟶ 28:
</math>
▲:<math>\mathbf{y} = \frac{1}{\mathbf{d}^T \mathbf{x} + \beta} \cdot \mathbf{x}\
Conversely, a solution for <math>\mathbf{y}</math> and <math>t </math> of the transformed linear program can be translated to a solution of the original linear-fractional program via
:<math>\mathbf{x}=\frac{1}{t}\mathbf{y}.</math>
==Duality==
Let the [[duality (optimization)|dual variables]] associated with the constraints <math>A\mathbf{y} - \mathbf{b} t \leq \mathbf{0}</math> and <math>\mathbf{d}^T \mathbf{y} + \beta t - 1 = 0</math> be denoted by <math>\mathbf{u}</math> and <math>\lambda</math>, respectively. Then the dual of the LFP above is <ref>{{cite journal|last1=Schaible |first1=Siegfried |title=Parameter-free Convex Equivalent and Dual Programs|journal=Zeitschrift für Operations Research |volume=18 |year=1974 |issue=5 |pages=187–196
:<math>
\begin{align}
Line 44 ⟶ 45:
\end{align}
</math>
which is an LP and which coincides with the dual of the equivalent linear program resulting from the
==Properties and algorithms==
The objective function in a linear-fractional problem is both quasiconcave and [[quasiconvex function|quasiconvex]] (hence quasilinear) with a [[monotonicity|monotone]] property, [[pseudoconvex function|pseudoconvexity]], which is a stronger property than [[quasiconvex function|quasiconvexity]]. A linear-fractional objective function is both pseudoconvex and pseudoconcave, hence [[pseudolinear function|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]]),<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=978-3-88538-404-5 |mr=949209
</ref><ref>{{cite journal | last1=Mathis|first1=Frank H.|last2=Mathis|first2=Lenora Jane|title=A nonlinear programming algorithm for hospital management |journal=[[SIAM Review]]|volume=37 |year=1995 |issue=2 |pages=230–234|mr=1343214|jstor=2132826|doi=10.1137/1037046|
</ref><ref>{{harvtxt|Murty|1983|loc=Chapter 3.20 (pp. 160–164) and pp. 168 and 179}}</ref> the [[criss-cross algorithm]],<ref>{{cite journal|title=The finite criss-cross method for hyperbolic programming|journal=European Journal of Operational Research|volume=114|issue=1|
pages=198–214|year=1999 <!-- issn=0377-2217 -->|doi=10.1016/S0377-2217(98)00049-6|first1=Tibor|last1=Illés|first2=Ákos|last2=Szirmai|first3=Tamás|last3=Terlaky
==Notes==
<references />
==
*{{cite book|last=Murty|first=Katta G.|author-link=Katta G. Murty|chapter=3.10 Fractional programming (pp. 160–164)|title=Linear programming|publisher=John Wiley & Sons, Inc.|___location=New York|year=1983|pages=xix+482|isbn=978-0-471-09725-9|mr=720547
▲*{{cite book|last=Murty|first=Katta G.|author-link=Katta G. Murty|chapter=3.10 Fractional programming (pp. 160–164)|title=Linear programming|publisher=John Wiley & Sons, Inc.|___location=New York|year=1983|pages=xix+482|isbn=978-0-471-09725-9|mr=720547|ref=harv}}
==Further reading==
Line 72 ⟶ 69:
*{{cite book | last=Stancu-Minasian | first=I. M.| title=Fractional programming: Theory, methods and applications | others=Translated by Victor Giurgiutiu from the 1992 Romanian | series=Mathematics and its applications|volume=409|publisher=Kluwer Academic Publishers Group | ___location=Dordrecht | year=1997 | pages=viii+418 | isbn=978-0-7923-4580-0 | mr=1472981 }}
{{DEFAULTSORT:Linear-Fractional Programming}}
| |||