Branch And Bound - Ramificar y Acotar

Un Ejercicio de Optimización Ingeniería Civil Industrial

Ahora les presento mi nuevo compañero y amigo de las largas noches de estudio.... Ramificar y Acotar.
En esta oportunidad les explico la programación lineal entera usando el método de ramificar y acotar (branch and bound)

Branch And Bound - Ramificar y Acotar

Resolver:

Max Z = 3X₁ + 5X₂
    Sujeto a:
            7X₁ + 6X₂    <= 100
            4X₁ + 11X₂  <= 80

X1, X2 enteras.

Árbol de Solución:

 

Los círculos blancos representan los pasos.

1. Resolver el problema original continuo. Z = 50.18 ninguna de las variables es entera. Ramifiquemos por X₁ (daría el mismo resultado pero con diferentes pasos si se ramificara por X₂).  Salen dos nuevos problemas a uno se le agrega la restricción X₁<= 11 (rama izquierda) y al otro se le agrega la restricción X₁ >= 12 (rama derecha). Resolvamos primero la rama izquierda (la elección de la rama no importa).

2. En este nuevo problema Z vale 49.36 y X₂ no es entera. Toca ramificar por X₂, se agregan las restricciones como se ve en la gráfica. Resolvamos primero la rama izquierda.

3. Z = 48 y las variables son enteras. Ahora va ganando este Z.  Como las variables son enteras ya no se sigue ramificando por esta rama. A las restricciones que se traían en el segundo paso se le agrega la restricción X2>=4 y se sigue en el 4 paso.

 4. Z = 47 y todas las variables enteras. Como el Z es menor (y estamos maximizando) la ignoramos y esa rama queda agotada, no la seguimos ramificando. Toda la rama izquierda original queda agotada. Se sigue con la rama derecha del primer paso, agregándole a las restricciones del primer paso la restricción X1>=12.

5. Z= 49.33 y X₂ no es entera. Como el Z es mayor que 48 que es la mejor solución encontrada hasta ahora seguimos ramificando.

6. Al agregar la restricción X2 <=2, Z = 47.71 que es menor que 48  la mejor solución encontrada hasta ahora entonces no seguimos ramificando por ahí, esa rama queda agotada, y se pasa a la rama derecha del paso 5.

7. Al agregar la restricción X2>= 3 a las restricciones en el paso 5 la solución no es factible, por lo tanto esa rama queda agotada, mejor dicho todas las ramas quedaron agotadas, habiendo encontrado la mejor solución con Z = 48, X1= 11, X2 =3.

Como resultado tenemos que Z= 48, X1=11, X2=3