En optimización matemática , la programación lineal-fraccionaria ( 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-fraccionario es una relación de dos funciones lineales. Un programa lineal puede considerarse como un caso especial de un programa lineal-fraccionario en el que el denominador es la función constante uno.
Relación con la programación lineal
Tanto la programación lineal como la programación lineal-fraccionaria 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 fraccionales tienen un conjunto más rico de funciones objetivas. 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, se utiliza una programación lineal-fraccional para lograr la relación más alta de resultado a costo, la relación que representa la mayor eficiencia. Por ejemplo, en el contexto de LP 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 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.
Definición
Formalmente, un programa lineal-fraccional se define como el problema de maximizar (o minimizar) una relación de funciones afines sobre un poliedro ,
dónde 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.
Transformación a un programa lineal
Bajo el supuesto de que la región factible no está vacía y está limitada, la transformación de Charnes-Cooper [1]
traduce el programa lineal-fraccional anterior al programa lineal equivalente:
Entonces la solución para y produce la solución del problema original como
Dualidad
Deje que las variables duales asociadas con las restricciones y ser denotado por y , respectivamente. Entonces el dual del LFP anterior es [3] [4]
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 tanto cuasicóncava como 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 tanto pseudoconvexa como pseudoconcava, por lo tanto, pseudolineal . Dado que un LFP se puede transformar en un LP, se puede resolver utilizando cualquier método de solución LP, como el algoritmo simplex (de George B. Dantzig ), [5] [6] [7] [8] el algoritmo entrecruzado , [9] o métodos de punto interior .
Notas
- ^ a b Charnes, A .; Cooper, WW (1962). "Programación con Funcionales Lineales Fraccionales". Trimestral de Logística de Investigación Naval . 9 (3-4): 181-186. doi : 10.1002 / nav.3800090303 . Señor 0152370 .
- ^ 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 .
- ^ 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 .
- ^ 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 .
- ^ Capítulo cinco: Craven, BD (1988). Programación fraccionada . Serie Sigma en Matemática Aplicada. 4 . Berlín: Heldermann Verlag. pag. 145. ISBN 978-3-88538-404-5. Señor 0949209 .
- ^ 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 .
- ^ 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 .
- ^ Murty (1983 , Capítulo 3.20 (págs. 160-164) y págs. 168 y 179)
- ^ 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 .
Referencias
- Craven, BD (1988). Programación fraccionada . Serie Sigma en Matemática Aplicada. 4 . Berlín: Heldermann Verlag. pag. 145. ISBN 978-3-88538-404-5. Señor 0949209 .
- 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 .
- Kruk, Serge; Wolkowicz, Henry (1999). "Programación pseudolineal" . Revisión SIAM . 41 (4): 795–805. doi : 10.1137 / S0036144598335259 . JSTOR 2653207 . Señor 1723002 .
- 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 .
- Murty, Katta G. (1983). "3.10 Programación fraccionada (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 ubicación . Optimización combinatoria. 3 . Dordrecht: Kluwer Academic Publishers. 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 . Amsterdam-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. 2 . Dordrecht: Kluwer Academic Publishers. 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. 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. MR 1472981 .
Software
- WinGULF : solucionador educativo interactivo de programación lineal y lineal-fraccional con muchas opciones especiales (pivotantes, precios, variables de ramificación, etc.)
- JOptimizer - biblioteca de optimización convexa de Java (código abierto)