Algoritmo Aditivo De Balas

Algoritmo Aditivo De Balas

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ón solo 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 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 considera 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 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 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ón objetivo 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; Infactibilidad 12

o X1 = 0; X2 = 0; X3 = 0; X4 = 0; X5 = 0

0 2; 0 – 2; 0 5; Infactibilidad 2

o X1 = 0; X2 = 0; X3 = 0; X4 = 0; X5 = 0

0 0; 0 – 5; 0 – 1; Infactibilidad 6

o X1 = 0; X2 = 0; X3 = 0; X4 = 0; X5 = 0

0 – 1; 0 2; 0 2; Infactibilidad 1

o X1 = 0; X2 = 0; X3 = 0; X4 = 0; X5 = 0

0 2; 0 1; 0 2; Infactibilidad 0

Solución Optima Unica:

X*1 = 0; X*2 = 0; X*3 = 0; X*4 = 0; X*5 = 1; W* = 3

Solución Optima Unica para el problema original:

Y*1 = 1; Y*2 = 1; Y*3 = 0; Y*4 = 0; Y*5 = 0; Z* = 5

Algunos autores emplean el algoritmo de Balas modificado, el cual consiste en introducirle al modelo una restricción denominada de filtro, la cual no es otra que la función objetivo con una cota inferior del valor óptimo. Históricamente es muy importante, ya que ha demostrado que algoritmos eficaces de programación en números enteros podrían emplear la enumeración implícita


Mis sitios nuevos:
Emprendedores
Politica de Privacidad