Paradoja De Aumento Programación Lineal

27Congreso Nacional de Estadística e Investigación Operativa Lleida, 8-11 de Abril de 2003

PROGRAMACIÓN LINEAL 2002: EL ALGORITMO TREVISO Y LA PARADOJA DEL AUMENTO
Albino Moino
Departamento de Estadística Universidad de Oriente, Núcleo Nueva Esparta, Guatamare, N.E., Venezuela E-mail: moino@ne.udo.edu.ve

RESUMEN
Introducción. El Algoritmo Treviso que consiste en señalar el elementopivote que permite aumentar la solución óptima original. Herramienta del análisis de sensibilidad. Los pasos del Algoritmo del Treviso. Primer ejemplo ilustrativo dónde el Algoritmo de Treviso, versión cambio de signo, se aplica a la Paradoja del Aumento. Segundo ejemplo ilustrativo del Algoritmo Treviso aplicado a la Paradoja del Aumento, versión formato tradicional, es decir, con la introducción deun nuevo vector columna o una nueva variable de decisión. Conclusiones. Palabras Claves: PL2002, Paradoja, Aumento, Análisis Sensibilidad Clasificación AMS: 90C05 y 90C31

1. Introducción.
Después de la presentación, el 10 de julio de 2001, de la Paradoja del Aumento en la Universidad de Oriente uno de los presente comentó. “La Paradoja del Aumento es interesante pero importante sería hallar sualgoritmo”. En la mañana siguiente desperté y comenté a mi esposa que había soñado con la Paradoja del Aumento y que había encontrado el algoritmo que la define. Media hora después de despertarme ya no podía recordar el algoritmo que sentía haber soñado. Pasaron tres días infructuosos para recordarlo. Finalmente deje de presionar la mente, plantee un problema en la computadora y poco a poco todose convirtió en lógico y natural. El Algoritmo Treviso, bautizado así en honor a mi difunto padre que había nacido en esta bella ciudad del Veneto, Italia, comenzó a surgir del caos.

2. El Algoritmo Treviso versión 1.1
El Algoritmo Treviso consiste en: 1.- Resolver el problema de Programación Lineal y hallar los valores de las variables de decisión y los valores duales.

2.- Como todos losvalores duales son positivos es necesario asignarles valores positivos o valores negativos. Si pertenecen a restricciones con relación de orden del tipo menor o igual, (≤), se le asignará un signo positivo. En cambio, si el valor dual pertenece a una restricción con la relación de orden del tipo igualdad, (=), o mayor o igual, (≥), se le asigna el signo negativo. 3.- Se asigna ordenadamente cadavalor dual a cada restricción. Luego el valor dual y1 corresponde a la primera restricción, y2 a la segunda restricción y así sucesivamente. 4.- Hallar si el elemento pivote que resulta ser la intersección de la variable de decisión básica y la correspondiente restricción dada por el valor dual indicado con valor distinto de cero, (yk≠0). 5.- Si el valor dual es positivo se procede solamente acambiar de signo al elemento pivote. En cambio si el valor dual es negativo se procede a sumar el valor absoluto del valor dual, Abs(yk), al elemento pivote. 6.- Resolver el problema modificado con el Método Simplex y obtener la solución óptima correspondiente. 7. Si se desea hallar una nueva solución se repiten los pasos 1 al 5 hasta obtener el aumento o disminución deseado. De existir elinconveniente de una solución acotada simplemente se agrega la cota deseada añadiendo una nueva restricción al problema original. Cada vez que se aplica el Algoritmo Treviso en un análisis de sensibilidad se provocará un aumento en la función objetivo si el objetivo del problema es maximizar. Ejemplo ilustrativo 1 Aplicación del Algoritmo Treviso en forma tradicional, o sea, cambiando signos o sumandoelementos en los pivotes. Problema Original Resultados usado LINDO
Maximizar 3x1 + 5x2 + x3 Sujeto a: -x1 + 2x2 + 2x3 ≤ 20 x2 + 2x3 ≤ 30 ≤ 40 2x1 + x2 x1 + 3x2 + x3 ≤ 100 ≤ 30 3x1 + x2 x1, x2, x3 ≥ 0 Cambiar signo a intersecciones x1/y5=a51 y x2/y1=a12 Max 3x1 + 5x2 + x3 Sujeto a: -x1 - 2x2 + 2x3 ≤ 20 x2 + 2x3 ≤ 30 ≤ 40 2x1 + x2 x1 + 3x2 + x3 ≤ 100 -3x1 + x2 ≤ 30 x1, x2, x3 ≥ 0
Función Objetivo:...