Como cualquier problema acotado de programación entera pura, tiene sólo un número finito de soluciones factibles, resulta natural considerar el uso de algun tipo de procedimiento de enumeración para encontrar una solución óptima. Desafortunadamente, como ya se dijo, este número finito puede ser, y casi siempre lo es, muy grande, por lo que es imperativo que cualquier procedimiento de enumeración de estructura con habilidad para que sólo sea necesario examinar una pequeña fracción de estas soluciones factibles. Por ejemplo, la programación dinámica (véase el capítulo) proporciona un procedimiento de este tipo para muchos problemas que tienen un número finito de soluciones factibles (aunque no es especialmente eficiente para la mayor parte delos problemas de PE) Otro enfoque de este tipo lo proporciona la técnica de ramificación y acotamiento. Esta técnica y algunas variaciones se han aplicado con cierto éxito a diversos problemas de investigación de operaciones, pero es más conocida por sus aplicaciones a los problemas de programación entera.
La idea básica en la que se apoya esta técnica se divide y vencerás. Como es demasiado complicado resolver directamente el problema original "grande", se divide en subproblemas cada vez más pequeños hasta que estos se puedan vencer. La división (ramificación) se hace mediante una partición del conjunto completo de soluciones factibles en subconjuntos más pequeños. La consulta (sondeo) se hace en parte acotando la mejor solución en el subconjunto y después descartando los subconjuntos cuya cota indique que no es posible que contenga una solución óptima.
Ahora se describirá cada uno de estos pasos básicos -ramificación, acotamiento y sondeo - y se ilustrarán aplicando un algoritmo de ramificación y acotamiento al ejemplo prototipo (el problema de California Manufacturing Co.) que se presentó en la sección 13.1.
No hay comentarios.:
Publicar un comentario