Para terminar, debe hacerse notar que más que encontrar una solución óptima, la técnica de ramificación y acotamiento se puede usar también para encontrar una solución cercana a la óptima, en general, con mucho menos esfuerzo computacional. En algunas aplicaciones, una solución es "bastante buena" si su Z está lo "suficientemente cerca' del valor de Z en la solución óptima (llámese Z**). "Suficientemente cerca" se puede definir como
Z ≥ Z** - K o como Z ≥ (1 - α)Z**
para una constante (positiva) específica K o α. Por ejemplo, si α=0.05, entonces se requiere que la solución se encuentre a un 5% de la óptima. Para encontrar una solución "suficientemente cerca" a la óptima sólo se necesita un cambio en el procedimiento usual de ramificación y acotamiento. ESte cambio consiste en reemplazar la prueba de sondeo 1 para un subproblema,
Cota ≤ Z*?
ya sea por Cota - K ≤ Z*?
o bien por (1 - α) cota ≤ Z*?
No hay comentarios.:
Publicar un comentario