Ejemplo2 Ramificar y Acotar

Branch And Bound - Ramificar y Acotar


Resolver:


Max Z = 3X1 + 5X2
    Sujeto a:
            7X1 + 6X2    <= 100
            4X1 + 11X2  <= 80
CNN.
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 X1 (daría el mismo resultado pero con diferentes pasos si se ramificara por X2).  Salen dos nuevos problemas a uno se le agrega la restricción X1<= 11 (rama izquierda) y al otro se le agrega la restricción X1 >= 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 X2 no es entera. Toca ramificar por X2, 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 X2 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.

Rta: Z= 48, X1=11, X2=3
 

Contenido :

Social