METODO DE RAMIFICACIÓN Y BIFURCACIÓN

METODO DE RAMIFICACIÓN Y BIFURCACIÓN

1. Resolver el problema mediante PL. Si la respuesta es entera es válida la respuesta, si no es así este valor proporciona un límite superior inicial.
2. Encontrar cualquier solución factible que satisfaga las restricciones de enteros que se utilizara como límite inferior, casi siempre el redondeo hacia abajo lograra este resultado.
3. Convertir en una rama una variable del paso 1 que no tenga valor entero. Dividir el problema en dos subproblemas con base en valores enteros que estén inmediatamente arriba o abajo del valor no entero.
4. Crear nodos en la parte superior de estas nuevas ramas para solucionar los problemas nuevos
5. A. Si una rama da una solución del problema de PL que no es factible termina la rama

B. Si una rama de una solución del problema de PL es factible, pero la solución no es entera siga al paso 6

c. Si la rama da una solución entera factible, examinar el valor de la F.O si este valor es igual límite superior se llega una solución óptima. Si no es igual l límite superior, pero sobrepasa el inferior fijarlo como nuevo límite inferior y seguir al paso 6 . Por último, si es menor que el límite inferior se termina esta rama

6.  Examinar de nuevos las ramas y fijar el limite superior igual al valor máximo de la F.O en todos los nodos finales . Si el límite inferior es igual inferior detenerse e ir de nuevo al paso 3

Ejemplo

MaxZ = 7X1+6X2

s.a

2X1+3X2<=12

6X1+5X2<=30

X1, X2 son enteros

...