Linear-fractional programming

In <a href="/facts/Mathematical_optimization/oRn8Iv5I">mathematical optimization</a>, linear-fractional programming (LFP) is a generalization of <a href="/facts/Linear_programming/GduXFQxT">linear programming</a> (LP). Whereas the objective function in a linear program is a <a href="/facts/Linear_functional/oGh7Asrz">linear function</a>, 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 <a href="/facts/Affine_function/BD7yDr10">affine functions</a> over a <a href="/facts/Polyhedron/UC0p9FTF">polyhedron</a>,

maximize
                
                
              
              
                
                  
                    
                      
                        
                          c
                        
                        
                          T
                        
                      
                      
                        x
                      
                      +
                      α
                    
                    
                      
                        
                          d
                        
                        
                          T
                        
                      
                      
                        x
                      
                      +
                      β
                    
                  
                
              
            
            
              
                
                  subject to
                
                
              
              
                A
                
                  x
                
                ≤
                
                  b
                
                ,
              
            
          
        
      
    
    {\displaystyle {\begin{aligned}{\text{maximize}}\quad &{\frac {\mathbf {c} ^{T}\mathbf {x} +\alpha }{\mathbf {d} ^{T}\mathbf {x} +\beta }}\\{\text{subject to}}\quad &A\mathbf {x} \leq \mathbf {b} ,\end{aligned}}}

where 
 
 
 
 
 x
 
 ∈
 
 
 R
 
 
 n
 
 
 
 
 {\displaystyle \mathbf {x} \in \mathbb {R} ^{n}}
 
 represents the vector of variables to be determined, 
 
 
 
 
 c
 
 ,
 
 d
 
 ∈
 
 
 R
 
 
 n
 
 
 
 
 {\displaystyle \mathbf {c} ,\mathbf {d} \in \mathbb {R} ^{n}}
 
 and 
 
 
 
 
 b
 
 ∈
 
 
 R
 
 
 m
 
 
 
 
 {\displaystyle \mathbf {b} \in \mathbb {R} ^{m}}
 
 are vectors of (known) coefficients, 
 
 
 
 A
 ∈
 
 
 R
 
 
 m
 ×
 n
 
 
 
 
 {\displaystyle A\in \mathbb {R} ^{m\times n}}
 
 is a (known) matrix of coefficients and 
 
 
 
 α
 ,
 β
 ∈
 
 R
 
 
 
 {\displaystyle \alpha ,\beta \in \mathbb {R} }
 
 are constants. The constraints have to restrict the <a href="/facts/Feasible_region/cJUKNCmM">feasible region</a> to 
 
 
 
 {
 
 x
 
 
 |
 
 
 
 d
 
 
 T
 
 
 
 x
 
 +
 β
 >
 0
 }
 
 
 {\displaystyle \{\mathbf {x} |\mathbf {d} ^{T}\mathbf {x} +\beta >0\}}
 
, 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.

Linear-fractional programming open-in-new

Linear-fractional programming