Deja un comentario

Dantzig y Karmakar

El método del simplex

El método del simplex fue desarrollado en los años 50 por el matemático americano George Dantzig.

La idea sobre la que se asienta puede entenderse fácilmente con la siguiente comparación: Imagínate que sobre tu mesa tienes el esqueleto, formado por las aristas, de un complicado poliedro convexo como el de la figura.

A una hormiga que deambula por la mesa se le antoja subir, escalando por las aristas del poliedro, al vértice situado a altura máxima. ¿Qué camino tomará para subir cuanto antes?

Comienza a subir por una arista hasta llegar al vértice final de ella. Desde ese vértice tiene varias otras aristas que podría recorrer para seguir escalando. ¿Cuál debe escoger? Parece razonable elegir la que suba más rápidamente, es decir, la de mayor pendiente, hasta llegar al próximo vértice. Y desde ese vértice escogerá de nuevo la arista de mayor pendiente hasta llegar a un vértice desde el que no pueda ascender más. Habrá llegado a la cima.

 Método del simplex y algoritmo de Karmarkar

El método del simplex es un algoritmo que indica, paso a paso, un procedimiento para resolver el problema que se propone en la programación lineal. Si bien es cierto que se pueden construir ejemplos en los que el método del simplex resulta ser un algoritmo muy lento (es fácil imaginar un poliedro en el que las aristas de mayor pendiente, por las que la hormiga del ejemplo escoge subir, sean muy cortas y muchas), en la práctica sucede, normalmente, que el método del simplex funciona muy eficientemente y conduce muy rápidamente a la solución.

El algoritmo de Karmarkar

En 1984, Narendra Karmarkar, un matemático indio establecido en Estados Unidos, diseñó una importante modificación del método del simplex. Puestos nuevamente, como ejemplo, la hormiga y tu poliedro, alcanzar la cima del poliedro aplicando esta modificación supondría que la hormiga podría ascender por el interior del poliedro abandonando las aristas por las que, según el método del simplex, debía subir. Con ello, escogiendo las rutas de ascenso adecuadamente, se podría colocar más rápidamente en la cima.

Al principio, el método de Karmarkar fue acogido con cierto escepticismo. Unos años antes, el matemático soviético L. G. Khachian había desarrollado un método, basado en otro llamado del elipsoide, que, si bien teóricamente parecía superior al del simplex, resultó ser menos eficiente desde el punto de vista práctico.

Pero el algoritmo de Karmarkar ha demostrado una eficacia bastante mayor, sobre todo cuando se trabaja con sistemas de un número de variables y de inecuaciones verdaderamente grande. Un cierto problema reciente de programación lineal con 800 000 variables fue resuelto con el algoritmo de Karmarkar tras 10 horas de trabajo de ordenador. Se cree que el problema hubiera necesitado semanas enteras de trabajo de ordenador mediante el método del simplex.

Sin embargo, el tratamiento de sistemas moderadamente grandes, el método del simplex parece, todavía, preferible.

El problema del viajante

Un viajante desea hacer una gira con su avioneta por unas cuantas ciudades y volver al punto de partida. Por cuestiones obvias de tiempo y de dinero, quiere planificar su itinerario de modo que este resulte, en kilómetros, lo más corto posible.

Este es uno de los ejemplos del famoso problema del viajante, de indudable interés práctico y económico.

Hay otras muchas situaciones en la que se presentan variantes del mismo problema. Por ejemplo:

• Un operario, cuyo trabajo consiste en recoger las monedas de las 100 cabinas telefónicas que tiene asignadas, desea hacerse un itinerario lo más corto posible.

• Una compañía eléctrica que tiene que enviar a un agente para leer los contadores de una zona a la que sirve, desea hacerlo de modo que se minimice el tiempo y los gastos de desplazamiento.

• Un robot que hace los agujeros en una de las placas metálicas de la fabricación en serie de un automóvil, ahorrará un montón de dinero si es programado de forma que minimice el tiempo de su trabajo en cada placa.

Lo que se busca al resolver el problema del viajante es un algoritmo: un procedimiento automáti co que, partiendo de los datos, conduzca, paso a paso, a la mejor solución posible, es decir, a la determinación del itinerario óptimo. Se puede pensar en diversos procedimientos que parezcan razonables. Por ejemplo:

Procedimiento A

• Se hacen todos los itinerarios posibles.

• Se computa el kilometraje de cada uno.

• Se escoge el de mínimo kilometraje.

Se dice pronto, pero es fácil ver que este procedimiento es inviable cuando el número de ciudades es razonablemente grande. Pongamos que son 25. Para 25 ciudades hay 24!/2 itinerarios posibles que no repiten ciudades dos veces, es decir, aproximadamente, 3 í 1023. Un ordenador que construyese un millón de itinerarios en un segundo, tardaría más de diez mil millones de años en construirlos todos. Una espera un poco larga para el viajante.

Procedimiento B

• Saliendo de una ciudad, el viajante se dirige a la cuidad más cercana.

• Luego, a la más cercana no recorrida aún.

• Y así hasta que las recorra todas.

• Finalmente, vuelve a su ciudad de origen.

Es fácil ver, con ejemplos sencillos, que este algoritmo, “el algoritmo del tacaño”, no conduce necesariamente a la solución óptima. Es más, se pueden dar situaciones en las que este algoritmo conduce a soluciones pésimas.

Actualmente se sospecha que no existe un algoritmo eficiente que conduzca en tiempo razonable a la solución óptima del problema del viajante. “Lo mejor es enemigo de lo bueno”, dice el refrán.

Por eso, los expertos se contentan con procesos heurísticos que proporcionen soluciones suficientemente buenas, Hoy día existen algoritmos que conducen eficazmente a soluciones que, con seguridad, no sobrepasan, en kilometraje, una vez y media el kilometraje de la solución óptima; es decir, con seguridad son, a lo sumo, una vez y media peores que la solución óptima.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: