En la sección 4.9 se presentó un importante desarrollo nuevo en programación que se debe a Narendra Karmarkar de AT&T Laboratories. Se trata de un poderoso algoritmo para resolver problemas muy grandes de programación lineal. SE introducirá aquí la naturaleza del enfoque de Karmarkar con la descripción de una variante relativamente sencilla (la variante "afin" o de "escala afin") de este algoritmo.
En esta sección se centrará la atención sobre las principales ideas de Karmarkar a un nivel intuitivo evitando los detalles matemáticos. En particular, se pasarán por alto ciertos detalles que se necesitan para la aplicación completa del algoritmo (por ejemplo, cómo encontrar una solución factible inicial de prueba) pero que no son esenciales para la comprensión de los conceptos básicos. Las ideas se pueden resumir como sigue:
Concepto 1: Obtener, del interior de la región factible, una solución factible que lleve a la solución óptima.
Concepto 2: Moverse en la dirección que mejore el valor de la función objetivo lo más rápido posible.
Concepto 3: Transformar la región factible para colocar la solución prueba actual cerca del centro permitiendo así una mejora grande cuando se lleve a cabo el concepto 2.
No hay comentarios.:
Publicar un comentario