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 relació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 del 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 la máxima ganancia o el menor costo. Por el contrario, una programación lineal-fraccional se utiliza para lograr la mayor relación entre el resultado y el costo, la relación que representa la mayor eficiencia. Por ejemplo, en el contexto de PL maximizamos la función objetivo ganancia = ingreso − costo y podríamos obtener una ganancia máxima de $100 (= $1100 de ingreso − $1000 de costo). Por lo tanto, en PL 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 requiriendo solo $50 de inversión.

Transformación a un programa lineal

Cualquier programa lineal-fraccional puede transformarse en un programa lineal, suponiendo 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 requerir que el denominador de la función objetivo ( ) sea igual a 1. (Para entender 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 a través de 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

Sean las variables duales asociadas con las restricciones y denotadas 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 cuasiconcava y cuasiconvexa (por lo tanto cuasililineal) con una propiedad monótona , pseudoconvexidad , que es una propiedad más fuerte que la cuasiconvexidad . Una función objetivo lineal-fraccional es a la vez 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 criss-cross , ^[9] o métodos de punto interior .

Notas

1. Charnes, A.; Cooper, WW (1962). "Programación con funciones fraccionarias 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. Recuperado 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. 145. ISBN 978-3-88538-404-5.Sr .  0949209.
6. Kruk, Serge; Wolkowicz, Henry (1999). "Programación pseudolineal". SIAM Review . 41 (4): 795–805. 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 (pp. 160-164) y pp. 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 (pp. 160–164)". Programación lineal . Nueva York: John Wiley & Sons, Inc. pp. xix+482. ISBN 978-0-471-09725-9.Sr. 0720547  .

Lectura adicional

• Bajalinov, EB (2003). Programación lineal-fraccional: 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-6.Señor 1626973  .
• Martos, Béla (1975). Programación no lineal: teoría y métodos . Amsterdam-Oxford: North-Holland Publishing Co. p. 279. ISBN 978-0-7204-2817-9.Sr .  0496692.
• Schaible, S. (1995). "Programación fraccionaria". En Reiner Horst y Panos M. Pardalos (ed.). Manual de optimización global . Optimización no convexa y sus aplicaciones. Vol. 2. Dordrecht: Kluwer Academic Publishers. págs. 495–608. ISBN 978-0-7923-3120-9.Señor 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-0.Sr. 1472981  .