El método de ramificación y acotamiento, también conocido como Branch and Bound, es un algoritmo utilizado para resolver modelos de Programación Entera. Este algoritmo funciona generando de manera recursiva cotas o restricciones adicionales que ayudan en la obtención de valores enteros para las variables de decisión.
Modelos de programación entera
Los modelos de programación entera son una extensión de los modelos lineales donde algunas variables toman valores enteros. Estos modelos pueden clasificarse en:
- Enteros puros: son aquellos en que todas las variables únicamente pueden tomar valores enteros.
- Mixtos: son aquellos en los que hay al mismo tiempo variables continuas y variables que sólo pueden tomar valores enteros.
- Binarios: las variables sólo pueden tomar los valores cero o uno.
El método de Gomory
El método de Gomory es otra técnica utilizada para resolver programación entera. Este método utiliza las desigualdades de corte de Gomory para generar restricciones adicionales que eliminan soluciones fraccionarias.
Corte de Benders
Además del método de ramificación y acotamiento y del método de Gomory, existe otra técnica llamada Corte de Benders. Este procedimiento utiliza inecuaciones similares a las que se ocupan en el método propuesto por J.F.
¿Cómo funciona el método de ramificación y acotamiento?
El método comienza con una solución inicial del modelo de programación entera, la cual puede ser encontrada a través del método de Gomory o de otro método similar. Luego, se toma una subproblema de la solución, es decir, se selecciona una variable que se encuentra en una fracción en la solución óptima. Se crea una nueva solución que fija una cota inferior (floor) para la variable seleccionada, y se extiende la solución anterior añadiendo la restricción creada.
Si la nueva solución aún no es entera, se divide en dos subproblemas: uno en el que se fija la variable seleccionada en su cota inferior y otro en el que se fija en la cota superior (ceiling). El proceso se repite para ambos subproblemas hasta que se obtiene una solución entera. En cada iteración se genera una nueva cota superior basada en la media de la cota inferior y superior.
Preguntas frecuentes
¿Cuál es la diferencia entre programación lineal y programación entera?
La programación lineal busca maximizar o minimizar una función lineal sujeta a un conjunto de restricciones lineales. Por otro lado, la programación entera tiene la misma función objetivo, pero algunas de las variables de decisión deben ser enteras. Esto hace que la programación entera sea más difícil de resolver computacionalmente.
¿Cuál es la ventaja del método de ramificación y acotamiento frente al método de Gomory?
Ambos métodos son útiles y necesarios para resolver modelos de programación entera. La principal ventaja del método de ramificación y acotamiento es su eficiencia en términos de tiempo y memoria. Mientras que el método de Gomory crea una gran cantidad de restricciones adicionales que pueden complicar el proceso de solución, el método de ramificación y acotamiento utiliza menos restricciones y es menos demandante en términos computacionales.
¿Qué aplicaciones tiene el método de ramificación y acotamiento?
El método de ramificación y acotamiento se utiliza en una gran variedad de aplicaciones donde es necesario optimizar la asignación de recursos. Algunos ejemplos incluyen el diseño de rutas de transporte, la planificación de producción, la gestión de inventarios, entre otros.