Se describirá un algoritmo básico de ramificación y acotamiento para resolver este problema que, un poco más elaborado, ha proporcionado el enfoque estándar a PEM. La estructura de este algoritmo fue desarrollada por R.J. Dakin basándose en un algoritmo anterior que se debera a A.H. Land y A.G. Doig.
ESte algoritmo es bastante parecido en estructura al algoritmo de PEB que se presentó en la sección anterior. De nuevo la solución de una soltura de PL proporciona la base tanto para la ramificación como para el acotamiento. De hecho sólo se necesitan cuatro cambios al algoritmo de PEB para manejar la generalización de variables enteras binarias a generales y de PE pura a PE mixta.
Un cambio involucra la elección de la variable de ramificación. Antes se elegía de manera automática la siguiente variable en el ordenador natural (x1,x2,.......xn). Ahora, las únicas variables que se toman en cuenta son las variables con restricción de enteras que tienen un valor no entero en la solución óptima de la soltura de PL para el subproblema actual. La regla para elegir estas variables será la primera de la lista en el orden natural. (Los paquetes de producción casi siempre utilizan una regla más complicada.)
No hay comentarios.:
Publicar un comentario