Branch and Bound

UNIDAD III:MÉTODO BRANCH AND BOUND

INSTITUTO TECNOLÓGICO DE CULIACÁN

Cntextualiza tu tema con un subtítulo

Para encontrar la solución entera, es necesario encontrar la solución relajada, es decir una solución no entera para posteriormente aplicar el método de ramificar y acotar, que llevará a la solución entera.

Método Branch and Bound

Ejemplo Max Z= 5X1 + 4X2 X1 + X2. ≤ 5 10X1 + 6X2 ≤ 45 X1, X2 ≥ 0, entero

01

La solución relajada muesra a x1 y x2 con valores no enteros, por lo que es necesario integrar restricciones que permitan encontrar una solución entera. Exploramos la trayectoria de x1<=3 para desarrollar esa rama.

01

Exploramos ahora x1>=4 para construir su trayectoria

Contextualiza tu tema con un subtítulo

Árbol Branch and Bound

La solución se encuentra en el PL1, ya que es la que otroga el mayor valor en la función ofjetivo y cumple con las varibles enteras:X1=3, X2=2 Y Z=23

01