Método Branch and Bound

Luis Enrique Muñoz Delgado Administración de Empresas
Método branch and bound Grupo: 7001

Fecha: 07/10/17
Método Branch and Bound
El método de diseño de algoritmos Ramificación y poda (también llamado Ramificación y

Acotación) es una variante del Backtracking mejorado sustancialmente.
Se aplica mayoritariamente para resolver cuestiones o problemas de optimización.
Su operatoria consiste en resolver éste como si fuese un modelo de programación lineal y luego
generar cotas en caso que al menos una variable de decisión adopte un valor fraccionario.
El algoritmo genera en forma recursiva cotas (o restricciones adicionales) que favorecen la

obtención de valores enteros para las variables de decisión.
En este contexto resolver el modelo lineal asociado a un modelo de programación entera se

conoce frecuentemente como resolver la relajación continua del modelo entero.
La técnica de Ramificación y poda se suele interpretar como un árbol de soluciones, donde cada
rama nos lleva a una posible solución posterior a la actual.
La característica de esta técnica con respecto a otras anteriores (y a la que debe su nombre) es
que el algoritmo se encarga de detectar en qué ramificación las soluciones dadas ya no están
siendo óptimas, para «podar» esa rama del árbol y no continuar malgastando recursos y
procesos en casos que se alejan de la solución óptima.
Ejemplo: (Branch and Bound):
El paso inicial consiste en resolver este problema como si fuese un modelo de Programación
Lineal (relajación continua).
Si la solución de dicho problema llegara a respetar las condiciones de integralidad para las
variables de decisión, ésta ya sería la solución óptima del problema entero.
Si bien este procedimiento se puede extender a problemas de mayor dimensión, utilizamos un

modelo en 2 variables para poder representar los pasos del algoritmo gráficamente. El gráfico a
continuación muestra dicha resolución:
1
Luis Enrique Muñoz Delgado Administración de Empresas
Método branch and bound Grupo: 7001
Fecha: 07/10/17
La relajación continua (Problema P0) nos da como solución óptima X1=20/9 y X2=14/9 con valor
óptimo V(P0)=319,1. Dado que al menos una variable de decisión toma valor fraccionario se
debe buscar una aproximación a valor entero. En este caso en particular con 2 soluciones
fraccionarias como criterio se puede seleccionar aquella con un mayor impacto (coeficiente) en
la función objetivo, sin embargo, no importando cuál de ellas se seleccione en un inicio los
resultados serán los mismos.
En consecuencia, seleccionaremos X1 y aproximaremos los resultados (20/9=2,222) al entero

superior e inferior más cercano. Esto genera 2 subproblemas que llamaremos P1 y P2
respectivamente. El problema P1 es similar a P0 pero considera como restricción adicional
X1<=2. Al resolver dicho problema se obtiene X1=2 y X2=7/4 con V(P1)=380. El problema P2 es
similar a P0 pero adicionalmente tiene la restricción X1>=3, con solución óptima X1=3 y X2=0 y
V(P2)=360. Este nodo (P2) se agota y sólo el P1 puede generar nuevos nodos.
Cabe destacar que un nodo o subproblema se agota en las siguientes situaciones: 1) Se alcanza
una solución entera, 2) El problema es infactible, 3) Se obtiene una solución fraccionaria pero
no es necesario continuar dado que ésta no es mejor (en términos de valor de la función
objetivo) que una solución entera que se ha alcanzado previamente.
Continuando con el procedimiento el P1 genera 2 nuevos nodos. P11 (similar a P1 con la

restricción adicional X2<=1) con solución X1=2 y X2=1 y V(P11)=320. El problema P12 (similar a
P1 con la restricción adicional X2>=2) con solución X1=12/7 y X2=2 y V(P12)=365,7.
Sólo P12 genera nuevos nodos: P121 (similar a P12 con la restricción adicional X1<=1) con
solución X1=1 y X2=21/8 y V(P121)=330. Adicionalmente el problema P122 (similar a P12 con la
restricción adicional X1>=2) resulta ser infactible al no existir solución.
Finalmente, si bien se puede continuar ramificando (generando nodos) a contar del problema
P121 esto no es necesario dado que el valor óptimo sólo podrá ir disminuyendo (dado que cada
vez se resuelve un problema sobre un dominio de soluciones factibles menor) y por tanto en
ningún caso se podrá obtener una solución entera mejor que la que ya se dispone (P2). Por tanto
X1=3 y X2=0 es solución óptima del problema entero con valor óptimo V(PE)=360. Se
recomienda verificar que se obtienen los mismos resultados ramificando inicialmente por X2 en
vez de X1.

Método Branch and Bound

Cargado por

Copyright:

Formatos disponibles

Método Branch and Bound

Cargado por

Información del documento

Descripción original:

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Método Branch and Bound

Cargado por

Copyright:

Formatos disponibles

Luis Enrique Muñoz Delgado Administración de Empresas

Método branch and bound Grupo: 7001

Método Branch and Bound

El método de diseño de algoritmos Ramificación y poda (también llamado Ramificación y

Se aplica mayoritariamente para resolver cuestiones o problemas de optimización.

El algoritmo genera en forma recursiva cotas (o restricciones adicionales) que favorecen la

En este contexto resolver el modelo lineal asociado a un modelo de programación entera se

Ejemplo: (Branch and Bound):

Si bien este procedimiento se puede extender a problemas de mayor dimensión, utilizamos un

En consecuencia, seleccionaremos X1 y aproximaremos los resultados (20/9=2,222) al entero

Continuando con el procedimiento el P1 genera 2 nuevos nodos. P11 (similar a P1 con la

También podría gustarte