PROGRAMACIÓN ENTERA SUBTEMA: RAMIFICACIÓN , ACOTAMIENTO Y SONDEO

TEMA: PROGRAMACIÓN ENTERA

SUBTEMA: RAMIFICACIÓN , ACOTAMIENTO Y SONDEO

Este método se creó en 1960 por A.H: Land y A. Doig, siendo el más popular para resolver los problemas de programación entera. Como su nombre lo indica, consiste en partir el problema original, el cual se irá dividiendo en ramas, cada una de las cuales va acortando la región factible de solución, conservando las soluciones enteras hasta que se encuentre la solución óptima.

El procedimiento del método consiste de los siguientes pasos:

1. Se resuelve el problema original relajándolo a programación lineal, es decir sin limitarse a una solución entera. Si por azar se obtiene una solución entera el problema se ha terminado. Si cuando menos una de las variables de decisión es fraccionaria, se continua con el paso siguiente.

1. De las variables de decisión que hayan quedado fraccionarias, se toma una de ellas y se hace una RAMIFICACIÓN del problema en dos modelos. El primer modelo que corresponde a la rama “A”, además de las restricciones originales deberá llevar la restricción de  X1 ≤ k1 (donde k1 es el entero inmediato inferior a la solución fraccionaria de X1) y el segundo modelo que es el correspondiente a la rama “B” llevará, además de las restricciones originales, la restricción X1 ≥ k2; (donde k2 es el entero inmediato superior a la solución fraccionaria de X1). Ejemplo si la solución de relajación de PL dio como resultado X1=1.35, la restricción a añadir a las originales sería X1≤ l que sería el modelo de la rama “A” y para la rama “B” el modelo tendría las restricciones originales más X1 ≥ 2.

1. Resolver cada rama del paso anterior con relajación de PL. Aquí nos podemos encontrar con tres opciones:

1. Que la solución encontrada no sea factible. en cuyo caso esta rama ya no se investiga más
2. Que la solución hallada sea entera, en cuyo caso el valor de la función objetivo es un ACOTAMIENTO  que será inferior para problemas de maximización y superior para problemas de minimización. Esto viene siendo el proceso de acotación. En esta rama ya no se prosigue la búsqueda de nuevas opciones.
3. Que la solución encontrada sea fraccionaria, lo cual da origen a una posible nueva ramificación. Si después de haber efectuado la relajación de PL en las dos nuevas ramas el valor de la función objetivo es mejor al de la cota previamente calculada en las ramas anteriormente analizadas, se toma este valor como nueva cota. En cambio si el valor no es mejor al de la cota, entonces se dice que esta rama esta “sondeada”  o sea que esta rama la debemos de dejar de lado porque no nos va a llevar al valor óptimo de la función objetivo, en cuyo caso se continúa con la siguiente rama. A este proceso de le llama SONDEO que es sinónimo de descarte.

...