Metodo de balas

Algoritmo aditivo de Balas
Otro algoritmo enumerativo importante es el algoritmo aditivo. Es debido originalmente a Egon Balas (1965). Se llama aditivo porque todas las operaciones matemáticas quese realizan consisten en sumar o restar.
El procedimiento consiste en generar una secuencia de soluciones parciales añadiendo en cada iteración una variable y considerando las solucionescomplementarias (resto de soluciones posibles). De esta forma, podemos por enumeración implícita, eliminar conjuntos de soluciones sin necesidad de evaluarlos exhaustivamente.
La selección de la variableañadida se hace en función de reducir al máximo la infactibilidad en la solución actual y eliminar la redundancia.

Este método es un procedimiento de enumeración que encuentra el óptimo en forma másrápida; en el método de Balas, la eficacia consiste en la evaluación solo de unas soluciones. El método empieza poniendo todas las variables iguales a cero y luego por medio de un procedimiento sistemáticode forma consecutiva se asigna a una por una de las variables el valor 1. Luego se reemplaza en cada una de las restricciones y se averigua la infactibilidad. Por esta razón el método es algunasveces llamado el algoritmo aditivo. Para describir el algoritmo, se considera la forma general siguiente de un problema de Programación Lineal con variables cero – uno: Paso 1. La función objetivo debeser del tipo minimización, con todos los coeficientes no negativos. Paso 2. Todas las restricciones deben ser del tipo £, con los lados derechos negativos de ser necesario. Luego, estas restricciones seconvierten a ecuaciones, usando las variables auxiliares en el lado izquierdo de las restricciones.

Ejemplo: MAX Z = 3 Y1 + 2 Y2– 5 Y3 – 2 Y4 + 3 Y5
MIN W = – 3 Y1 – 2 Y2 + 5 Y3 + 2 Y4– 3 Y5Con sus restricciones:
Reemplazamos: Y1 = 1 – X1; Y2 = 1 – X2; Y3 = X3; Y4 = X4; Y5 = 1 – X5
MIN W´ = 3 X1 + 2 X2 + 5 X3 + 2 X4 + 3 X5 – 8
Sujeta a:
Sustituimos W´ + 8 = W MIN W = 3 X1 +...