algoritmo de ramificacion

Algoritmo de ramificación y acotamiento ( Branch and Bound)

El primer algoritmo de ramificación y acotamiento fue desarrollado en 1960 por A Landy y G Doig para el problema general de PLE1 combinada o pura. Más adelante, en 1965, E. Balas desarrolló el algoritmo aditivo para resolver PLEs con variables binarias puras(cero o uno). Los cálculos del algoritmo aditivo eran tansimples(principalmente sumas y restas) que en un inicio fue aclamado como un posible gran avance en la solución de la PLE. Por desgracia, no produjo las ventajas computacionales deseadas.
Además se demostró que el algoritmo, que inicialmente no parecía estar relacionado con la técnica de ramificación y acotamiento, era simplemente un caso especial del algoritmo general de Land y Doig.

Cada problema deProgramación Lineal Entera para su solución se divide en dos subproblemas; para cada subproblema puede ocurrir lo siguiente:

1. Cuando el problema es no factible se da por terminado.
2. La solución es entera mejor que cualquier solución entera conocida, es candidata a solución; en este caso no se busca más.
3. Es fraccionario mejor que la solución entera conocida más adecuada, se parte en dos esteproblema.
4. Es peor que la mejor entera conocida; no se investiga más.


Ejemplo usando simplex:

MAX Z = 3 X1+ 5 X2
Con sus restricciones:

Solución Analítica:
Estandarización:


TABLERO 1 SIMPLEX
 
0
Cj
3
5
0
CB
VB
b
X1
X2
S1
0
S1
20
6
8
1
0
Z
0
-3
-5
0


TABLERO 2 SIMPLEX
CB
VB
b
X1
X2
S1
0
X2
5/2
3/4
1
1/8
0
Z
25/2
3/4
0
5/8

SoluciónÓptima Única de Programación Lineal: X*1 = 0; X*2 = 5/2; S*1 = 0; Z* = 25/2, más no de Programación Lineal Entera.

Solución Óptima al problema de Programación Lineal Entera:
X*1 = 2; X*2 = 1; Z* = 11

Ejemplo usando un análisis geométrico :

La compañía TELFA fabrica mesa y sillas. Una mesa requiere 1 hora de trabajo y 9 pies de tabla de madera, y una silla requiere 1 hora de trabajo y 5pies de tabla de madera. Actualmente la compañía dispone de 6 horas de trabajo y 45 pies de madera. Cada tabla contribuye con 8 dólares de utilidad y cada silla con 5 dólares. Formule y resuelva un modelo lineal entero (PLE o PE) para maximizar la utilidad de TELFA

Variables de Decisión:

x1 = número de mesas a fabricar y
x2 = número de sillas a fabricar.

Objetivo: Maximizar la utilidad:Max z = 8 x1 + 5 x2

Restricciones:

x1 + x2 6 (Horas de trabajo)
9 x1 + 5 x2 45 (Madera)
x1; x2 0
x1; x2 enteros.

El Problema Lineal que se obtiene de omitir todas las restricciones enteras o del tipo 0-1 para todas las variables de un modelo de Programación Lineal Entera PLE se llama relajación PL del PLE.
La región factible de la relajación PL de un PLE contiene la región factibledel PLE. Esto se deduce por que cada restricción que se quita (en este caso la restricción de que las variables sean enteras) hace que la región factible en el peor caso quede igual: Quitar restricciones no puede hacer más pequeña la región factible. Por lo tanto: Si la región factible para la relajación PL es vacía, entonces la región factible para el PLE también es vacía.
El valor óptimo de zpara la relajación PL el valor óptimo de z para el PLE. Esto se deduce por la contención de las regiones factibles: El PL relajado tiene un espacio adicional de búsqueda que el PL y no puede empeorar. Por lo tanto, Si el optimo de z para la relajación PL está en la región factible del PLE, entonces tal punto es el optimo del PLE.

Geometría del Problema

La región en amarillo corresponde a laregión factible del problema relajado. Los puntos en verde corresponde a la región factible del problema con x1 y x2 enteros. El punto en rojo corresponde al óptimo del problema relajado:
z = 41:25; x1 = 3:75; x2 = 2:25.
C



Nuestro problema consiste en encontrar el punto de región factible del PLE que tenga la mejor evaluación. No uno donde aproximadamente se obtenga el mejor. En general,...