stringtranslate.com

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 ,

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.

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 ).

Formalmente, el programa lineal obtenido mediante la transformación de Charnes-Cooper utiliza las variables transformadas y :

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

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

Dualidad

Sean las variables duales asociadas con las restricciones y denotadas por y , respectivamente. Entonces el dual de la 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 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. ^ ab 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

Lectura adicional