Ejemplo Del Algoritmo de Branch and Bound
Ejemplo Del Algoritmo de Branch and Bound
Ejemplo Del Algoritmo de Branch and Bound
(Ramificación y Acotamiento)
por GEO Tutoriales el 04/08/2011 en Programación Entera 0
Luego no sería del todo necesario seguir desarrollando el algoritmo dado que si
generamos cotas para la variable X2 del P2 en ningún caso podríamos obtener
una solución entera con valor óptimo superior a 20 (valor que reporta en la
función objetivo la actual solución entera de P1) y por tanto podríamos concluir
que X1=2y X2=2 es la solución óptima del problema entero. No obstante
el siguiente diagrama muestra los pasos adicionales en caso que quisiera
agregar cotas adicionales a partir del P2.
Un argumento similar al expuesto previamente en este caso explicaría la no
necesidad de seguir ramificando el P21. Se propone al lector verificar que se
obtiene la misma solución óptima si luego del P0 ramificamos a través de X2
agregando las restricciones X2<=1 y X2>=2.