Metodo ramificar y cortar

METODO ADITIVO (ENUMERACION) DE EGON 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ónsolo de unas soluciones. 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 elvalor 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, seconsidera la 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 nonegativos.
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 enel lado izquierdo 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:Siempre el 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ónobjetivo y la 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;...