Hispanopedia Wiki
Articulo de referencia

Programación lineal fraccionaria

En optimización matemática , la programación lineal fraccionaria ( PLF ) es una generalización de la programación lineal (PL). Mientras que la función objetivo en un programa li...

Hispanopedia WikiContenido en espanolLectura gratuita

En optimización matemática , la programación lineal fraccionaria ( PLF ) es una generalización de la programación lineal (PL). Mientras que la función objetivo en un programa lineal es una función lineal , la función objetivo en un programa lineal fraccionario es una razón entre dos funciones lineales. Un programa lineal puede considerarse un caso especial de un programa lineal fraccionario en el que el denominador es la función constante 1.

Formalmente, un programa lineal-fraccional se define como el problema de maximizar (o minimizar) una razón de funciones afines sobre un poliedro ,

maximizardoTincógnita+αdTincógnita+βsujeto aAincógnita≤b,{\displaystyle {\begin{aligned}{\text{maximizar}}\quad &{\frac {\mathbf {c} ^{T}\mathbf {x} +\alpha }{\mathbf {d} ^{T}\mathbf {x} +\beta }}\\{\text{sujeto a}}\quad &A\mathbf {x} \leq \mathbf {b} ,\end{aligned}}}

dóndeincógnita∈Rnorte{\displaystyle \mathbf {x} \in \mathbb {R} ^{n}}representa el vector de variables a determinar,do,d∈Rnorte{\displaystyle \mathbf {c} ,\mathbf {d} \in \mathbb {R} ^{n}}yb∈Rmetro{\displaystyle \mathbf {b} \in \mathbb {R} ^{m}}son vectores de coeficientes (conocidos),A∈Rmetro×norte{\displaystyle A\in \mathbb {R} ^{m\times n}}es una matriz (conocida) de coeficientes yα,β∈R{\displaystyle \alpha ,\beta \in \mathbb {R} }son constantes. Las restricciones deben limitar la región factible a{incógnita|dTincógnita+β>0}{\displaystyle \{\mathbf {x} |\mathbf {d} ^{T}\mathbf {x} +\beta >0\}}, es decir, la región en la que el denominador es positivo. [ 1 ] [ 2 ] Alternativamente, el denominador de la función objetivo debe ser estrictamente negativo en toda la región factible.

Motivación mediante comparación con la programación lineal.

Tanto la programación lineal como la programación lineal fraccionaria representan problemas de optimización mediante ecuaciones e inecuaciones lineales , que definen un conjunto factible para cada instancia del problema . Los programas lineales fraccionarios cuentan con un conjunto más amplio de funciones objetivo. De manera informal, la programación lineal calcula una política que ofrece el mejor resultado, como el máximo beneficio o el menor coste. En cambio, la programación lineal fraccionaria se utiliza para lograr la mayor relación entre el resultado y el coste, la cual representa la mayor eficiencia. Por ejemplo, en el contexto de la programación lineal, maximizamos la función objetivo beneficio  =  ingresos − costes   y podríamos obtener un beneficio máximo de 100 $ (=  1100 $  de  ingresos − 1000 $ de costes). Por lo tanto, en la programación lineal, tenemos una eficiencia de 100 $/1000 $ = 0,1. Utilizando la programación lineal fraccionaria, podríamos obtener una eficiencia de 10 $/50 $ = 0,2 con un beneficio de tan solo 10 $, pero requiriendo únicamente una inversión de 50 $.      

Transformación en un programa lineal

Cualquier programa lineal-fraccional puede transformarse en un programa lineal, suponiendo que la región factible no es vacía y está acotada, utilizando la transformación de Charnes-Cooper . [ 1 ] La idea principal es introducir una nueva variable no negativa.t{\displaystyle t}al programa que se utilizará para reescalar las constantes involucradas en el programa (α,β,b{\displaystyle \alpha ,\beta ,\mathbf {b} }). Esto nos permite exigir que el denominador de la función objetivo (dTincógnita+β{\displaystyle \mathbf {d} ^{T}\mathbf {x} +\beta }) es igual a 1. (Para comprender la transformación, es instructivo considerar el caso especial más simple conα=β=0{\displaystyle \alpha =\beta =0}.)

Formalmente, el programa lineal obtenido mediante la transformación de Charnes-Cooper utiliza las variables transformadas.y∈Rnorte{\displaystyle \mathbf {y} \in \mathbb {R} ^{n}}yt≥0{\displaystyle t\geq 0}:

maximizardoTy+αtsujeto aAy≤btdTy+βt=1t≥0.{\displaystyle {\begin{alineado}{\text{maximizar}}\quad &\mathbf {c} ^{T}\mathbf {y} +\alpha t\\{\text{sujeto a}}\quad &A\mathbf {y} \leq \mathbf {b} t\\&\mathbf {d} ^{T}\mathbf {y} +\beta t=1\\&t\geq 0.\end{aligned}}}

Una soluciónincógnita{\displaystyle \mathbf {x} }El programa lineal-fraccional original se puede traducir a una solución del programa lineal transformado mediante las igualdades.

y=1dTincógnita+β⋅incógnitayt=1dTincógnita+β.{\displaystyle \mathbf {y} ={\frac {1}{\mathbf {d} ^{T}\mathbf {x} +\beta }}\cdot \mathbf {x} \quad {\text{y}}\quad t={\frac {1}{\mathbf {d} ^{T}\mathbf {x} +\beta }}.}

Por el contrario, una solución paray{\displaystyle \mathbf {y} }yt{\displaystyle t}del programa lineal transformado se puede traducir a una solución del programa lineal fraccionario original mediante

incógnita=1ty.{\displaystyle \mathbf {x} ={\frac {1}{t}}\mathbf {y} .}

Dualidad

Sean las variables duales asociadas con las restriccionesAy−bt≤0{\displaystyle A\mathbf {y} -\mathbf {b} t\leq \mathbf {0} }ydTy+βt−1=0{\displaystyle \mathbf {d} ^{T}\mathbf {y} +\beta t-1=0}ser denotado portú{\displaystyle \mathbf {u} }yλ{\displaystyle \lambda }, respectivamente. Entonces el dual del LFP anterior es [ 3 ] [ 4 ]

minimizarλsujeto aATtú+λd=do−bTtú+λβ≥αtú∈R+metro,λ∈R,{\displaystyle {\begin{aligned}{\text{minimize}}\quad &\lambda \\{\text{subject to}}\quad &A^{T}\mathbf {u} +\lambda \mathbf {d} =\mathbf {c} \\&-\mathbf {b} ^{T}\mathbf {u} +\lambda \beta \geq \alpha \\&\mathbf {u} \in \mathbb {R} _{+}^{m},\lambda \in \mathbb {R} ,\end{aligned}}}

que es un LP y que coincide con el dual del programa lineal equivalente resultante de la transformación de Charnes-Cooper.

Propiedades y algoritmos

La función objetivo en un problema lineal-fraccional es a la vez cuasicóncava y cuasicónvexa (por lo tanto cuasilineal) con una propiedad monótona , pseudoconvexidad , que es una propiedad más fuerte que la cuasicónvexidad . Una función objetivo lineal-fraccional es a la vez pseudocóncava y pseudoconvexa, por lo tanto pseudolineal . Dado que un LFP puede transformarse en un LP, puede resolverse utilizando cualquier método de solución de LP, como el algoritmo simplex (de George B. Dantzig ), [ 5 ] [ 6 ] [ 7 ] [ 8 ] el algoritmo de cruce , [ 9 ] o métodos de punto interior .

Notas

  1. 1 2 Charnes, A.; Cooper, WW (1962). "Programación con funcionales fraccionarios lineales". Naval Research Logistics Quarterly . 9 ( 3– 4): 181– 186. doi : 10.1002/nav.3800090303 . MR 0152370 . 
  2. ↑ Boyd, Stephen P.; Vandenberghe, Lieven (2004). Optimización convexa (PDF) . Cambridge University Press. pág. 151. ISBN  978-0-521-83378-3. Consultado el 15 de octubre de 2011 .
  3. ^ Schaible, Siegfried (1974). "Programas duales y equivalentes convexos sin parámetros". Zeitschrift für Investigación de operaciones . 18 (5): 187– 196. doi : 10.1007/BF02026600 . SEÑOR 0351464 . S2CID 28885670 .  
  4. ↑ Schaible, Siegfried (1976). "Programación fraccionaria I : Dualidad". Management Science . 22 (8): 858– 867. doi : 10.1287/mnsc.22.8.858 . JSTOR 2630017. MR 0421679 .   
  5. ↑ Capítulo cinco: Craven, BD (1988). Programación fraccionaria . Serie Sigma en Matemáticas Aplicadas. Vol. 4. Berlín: Heldermann Verlag. pág. 145. ISBN   978-3-88538-404-5. SR 0949209 . 
  6. ↑ Kruk, Serge; Wolkowicz, Henry (1999). "Programación pseudolineal". SIAM Review . 41 (4): 795– 805. Bibcode : 1999SIAMR..41..795K . CiteSeerX 10.1.1.53.7355 . doi : 10.1137/S0036144598335259 . JSTOR 2653207 . MR 1723002 .   
  7. ↑ Mathis, Frank H.; Mathis, Lenora Jane (1995). "Un algoritmo de programación no lineal para la gestión hospitalaria". SIAM Review . 37 (2): 230– 234. doi : 10.1137/1037046 . JSTOR 2132826 . MR 1343214 . S2CID 120626738 .   
  8. ↑ Murty (1983 , Capítulo 3.20 (págs. 160–164) y págs. 168 y 179)    
  9. ↑ Illés, Tibor; Szirmai, Ákos; Terlaky, Tamás (1999). "El método entrecruzado finito para la programación hiperbólica". Revista europea de investigación operativa . 114 (1): 198– 214. CiteSeerX 10.1.1.36.7090 . doi : 10.1016/S0377-2217(98)00049-6 . Zbl 0953.90055 . Preimpresión posdata .  

Fuentes

  • Murty, Katta  G. (1983). "3.10 Programación fraccionaria (págs. 160–164)". Programación lineal . Nueva York: John Wiley & Sons, Inc. págs.  xix+482. ISBN 978-0-471-09725-9MR 0720547 .​ 

Lecturas adicionales

  • Bajalinov, EB (2003). Programación lineal fraccionaria: teoría, métodos, aplicaciones y software . Boston: Kluwer Academic Publishers.
  • Barros, Ana Isabel (1998). Técnicas de programación discreta y fraccionaria para modelos de localización . Optimización combinatoria. Vol.  3. Dordrecht: Kluwer Academic Publishers. pp.  xviii+178. ISBN 978-0-7923-5002-6MR 1626973 .​ 
  • Martos, Béla (1975). Programación no lineal: Teoría y métodos . Ámsterdam-Oxford: North-Holland Publishing Co. pág.  279. ISBN 978-0-7204-2817-9. MR 0496692 . 
  • Schaible, S. (1995). «Programación fraccionaria». En Reiner Horst y Panos M. Pardalos (eds.). Manual de optimización global . Optimización no convexa y sus aplicaciones. Vol.  2. Dordrecht: Kluwer Academic Publishers. pp. 495–608 . ISBN  978-0-7923-3120-9. MR 1377091 . 
  • Stancu-Minasian, IM (1997). Programación fraccionaria: Teoría, métodos y aplicaciones . Matemáticas y sus aplicaciones. Vol.  409. Traducido por Victor Giurgiutiu del rumano de 1992. Dordrecht: Kluwer Academic Publishers Group. pp.  viii+418. ISBN 978-0-7923-4580-0MR 1472981 .​