Programación lineal-fraccional

En optimización matemática , la programación lineal-fraccional ( LFP ) es una generalización de la programación lineal (LP). Mientras que la función objetivo en un programa lineal es una función lineal , la función objetivo en un programa lineal-fraccional es una relación de dos funciones lineales. Un programa lineal puede considerarse como un caso especial de un programa lineal-fraccional 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 proporción de funciones afines sobre un poliedro ,

${\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}}}$

donde representa el vector de variables a determinar, y son vectores de coeficientes (conocidos), es una matriz (conocida) de coeficientes y son constantes. Las restricciones tienen que restringir la región factible a , es decir, la región en la que el denominador es positivo. ^{[1] [2]} Alternativamente, el denominador de la función objetivo tiene que ser estrictamente negativo en toda la región factible. ${\displaystyle \mathbf {x} \in \mathbb {R} ^{n}}$ ${\displaystyle \mathbf {c} ,\mathbf {d} \in \mathbb {R} ^{n}}$ ${\displaystyle \mathbf {b} \in \mathbb {R} ^{m}}$ ${\displaystyle A\in \mathbb {R} ^{m\times n}}$ ${\displaystyle \alpha ,\beta \in \mathbb {R} }$ ${\displaystyle \{\mathbf {x} |\mathbf {d} ^{T}\mathbf {x} +\beta >0\}}$

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

Tanto la programación lineal como la programación lineal-fraccional representan problemas de optimización que utilizan ecuaciones lineales y desigualdades lineales, que para cada instancia de problema definen un conjunto factible . Los programas lineales fraccionarios tienen un conjunto más rico 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. Por el contrario, se utiliza una programación lineal-fraccional para lograr la mayor relación entre resultado y costo, relación que representa la mayor eficiencia. Por ejemplo, en el contexto de PL maximizamos la función objetivo beneficio = ingreso − costo y podríamos obtener un beneficio máximo de $100 (= $1100 de ingreso − $1000 de costo). Así, en LP tenemos una eficiencia de $100/$1000 = 0,1. Usando LFP podríamos obtener una eficiencia de $10/$50 = 0,2 con una ganancia de solo $10, pero solo requiriendo $50 de inversión.

Transformación a un programa lineal.

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

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

${\displaystyle {\begin{aligned}{\text{maximize}}\quad &\mathbf {c} ^{T}\mathbf {y} +\alpha t\\{\text{subject to}}\quad &A\mathbf {y} \leq \mathbf {b} t\\&\mathbf {d} ^{T}\mathbf {y} +\beta t=1\\&t\geq 0.\end{aligned}}}$

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

${\displaystyle \mathbf {y} ={\frac {1}{\mathbf {d} ^{T}\mathbf {x} +\beta }}\cdot \mathbf {x} \quad {\text{and}}\quad t={\frac {1}{\mathbf {d} ^{T}\mathbf {x} +\beta }}.}$

Por el contrario, una solución para y del programa lineal transformado se puede traducir a una solución del programa lineal-fraccional original mediante ${\displaystyle \mathbf {y} }$ ${\displaystyle t}$

${\displaystyle \mathbf {x} ={\frac {1}{t}}\mathbf {y} .}$

Dualidad

Denotemos las variables duales asociadas con las restricciones y por y , respectivamente. Entonces el dual de la LFP anterior es ^{[3] [4]} ${\displaystyle A\mathbf {y} -\mathbf {b} t\leq \mathbf {0} }$ ${\displaystyle \mathbf {d} ^{T}\mathbf {y} +\beta t-1=0}$ ${\displaystyle \mathbf {u} }$ ${\displaystyle \lambda }$

${\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 cuasiconvexa (por lo tanto, cuasilineal) con una propiedad monótona , pseudoconvexidad , que es una propiedad más fuerte que la cuasiconvexidad . Una función objetivo lineal-fraccional es pseudoconvexa y pseudocóncava, por lo tanto, pseudolineal . Dado que un LFP se puede transformar en un LP, se puede resolver utilizando cualquier método de solución de LP, como el algoritmo simplex (de George B. Dantzig ), ^{[5] [6] [7] [8]} el algoritmo entrecruzado , ^[9] o métodos de punto interior .

Notas

1. Charnes, A.; Cooper, WW (1962). "Programación con funcionales lineales fraccionarios". Logística de investigación naval trimestral . 9 (3–4): 181–186. doi : 10.1002/nav.3800090303. SEÑOR  0152370.
2. Boyd, Stephen P.; Vandenberghe, Lieven (2004). Optimización convexa (PDF) . Prensa de la Universidad de Cambridge. pag. 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 fraccionada I: Dualidad". Ciencias de la gestión . 22 (8): 858–867. doi :10.1287/mnsc.22.8.858. JSTOR  2630017. SEÑOR  0421679.
5. Capítulo cinco: Craven, BD (1988). Programación fraccionada . Serie Sigma en Matemática Aplicada. vol. 4. Berlín: Heldermann Verlag. pag. 145.ISBN​ 978-3-88538-404-5. SEÑOR  0949209.
6. Kruk, Serge; Wolkowicz, Henry (1999). "Programación pseudolineal". Revisión SIAM . 41 (4): 795–805. CiteSeerX 10.1.1.53.7355 . doi :10.1137/S0036144598335259. JSTOR  2653207. SEÑOR  1723002. 
7. Mathis, Frank H.; Mathis, Lenora Jane (1995). "Un algoritmo de programación no lineal para la gestión hospitalaria". Revisión SIAM . 37 (2): 230–234. doi :10.1137/1037046. JSTOR  2132826. SEÑOR  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-9. SEÑOR  0720547.

Otras lecturas

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