viernes, 21 de agosto de 2015

Programación Entera Desarrollos recientes (VI)

Hacerlo tiene la ventaja importante de estrechar la soltura de PL (lo que elimina algunas de sus soluciones factibles) sin eliminar ninguna solución factible del problema de PEB. Otra técnica es preparar un "gatillo" que va a fijar el valor de una o más variables, después que se ha dado cierto valor a otra variable durante el desarrollo del algoritmo. Por ejemplo, para el grupo de variables que representan un conjunto de alternativas mutuamente excluyentes, en cuanto una de las variables se iguala a 1, el resto se puede fijar 0. Un gatillo de este tipo se puede preparar también para las restricciones que representan decisiones continuas y para otras restricciones con forma similar.

Se ha comprobado que el uso de la computadora para llevar a cabo estas ideas y otras parecidas en forma automática es de gran ayuda para acelerar un algoritmo. Sin embargo, una técnica todavía más importante es la generación de planos cortantes. Una cortadura para un problema de PE es una nueva restricción que elimina algunas soluciones factibles de la soltura de PL original, incluso su solución óptima. El propósito de agregar una nueva restricción con esta propiedad es estrechar la soltura de PL, estrechando con esto la cota obtenida en el paso de acotamiento de la técnica de ramificación y acotamiento. Al estrechar la soltura de PL se incrementa la posiblidad de que su solución óptima sea factible (y por lo tanto óptima) para el problema de PE, con lo que e mejoraría la prueba de sondeo 3.

No hay comentarios.:

Publicar un comentario