Linear-fractional programming: Difference between revisions

Content deleted Content added
Citation bot (talk | contribs)
Added bibcode. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Optimization algorithms and methods | #UCB_Category 127/168
formatting
Line 14:
 
==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:
\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==