Algoritmo Aditivo De Balas

5.5 ALGORITMO ADITIVO DE BALAS
Este método es un procedimiento de enumeración que encuentra el óptimo en forma más rápida; en el método de Balas, la eficacia consiste en la evaluación solo de unassoluciones. El método empieza poniendo todas las variables iguales a cero y luego por medio de un procedimiento sistemático de 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 algunas veces llamado el algoritmo aditivo.
Para describir el algoritmo, se considerala forma general siguiente de un problema de Programación Lineal con variables cero – uno:
Paso 1. La función objetivo debe ser del tipo minimización, con todos los coeficientes no negativos.Paso 2. Todas las restricciones deben ser del tipo £, con los lados derechosnegativosde ser necesario. Luego, estas restricciones se convierten a ecuaciones, usando las variables auxiliares en el ladoizquierdo de las restricciones. Ejemplo:
MAX Z = 3 Y1 + 2 Y2– 5 Y3 – 2 Y4 + 3 Y5
Sujeta a:
MIN W = – 3 Y1 – 2 Y2 + 5 Y3 + 2 Y4– 3 Y5
Con 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 + 2 X2 + 5 X3 + 2 X4 + 3 X5
Con sus restricciones:
Siempreel problema nuevo a resolver consiste en la minimización de la función objetivo, teniendo en cuenta la medida de la no factibilidad de la holgura. Cuando la infactibilidad da el menor valor,continuamos con el siguiente paso; en el caso de una infactibilidad cero, ésta corresponde a la solución óptima; si encontramos varias infactibilidades iguales a cero, reemplazamos en la función objetivo yla respuesta será la que haga esta función mínima.
o X1 = 0; X2 = 0; X3 = 0; X4 = 0; X5 = 0
0 1; 0 – 2; 0 – 1; Infactibilidad 3
o X1 = 0; X2 = 0; X3 = 0; X4 = 0; X5 = 0
0 2; 0 5; 0 – 12;...