Page 109 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

Ahora, imagínese que una hormiga que deambula por la mesa intenta subir escalando por las aristas
del poliedro al vértice situado en la 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.

El método Simplex es un algoritmo que indica, paso a paso, un procedimiento para resolver el pro-
blema que se propone en la programación lineal. Si bien es cierto que se pueden construir ejemplos
en los que el método 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 Simplex funciona muy eficien-
temente y conduce de forma rápida a la solución.

Pero en 1984, Narendra Karmarkar, un matemático de origen indio establecido en Estados Unidos,
logró un algoritmo que supera por mucho, en eficiencia, al algoritmo Simplex para el tratamiento de
problemas con un gran número de variables y de restricciones. Puestos nuevamente como ejemplo
el caso de la hormiga y el poliedro, alcanzar la cima del poliedro aplicando esta modificación supon-
dría que la hormiga podría ascender por el interior del poliedro abandonando las aristas por las que,
según el método 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 elipsoide, que si bien teóricamente parecía superior al 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
problema reciente de programación lineal con 800 000 variables fue resuelto con el algoritmo de Kar-
markar tras 10 horas de trabajo del ordenador. Se cree que el problema hubiera necesitado semanas
enteras de trabajo de ordenador mediante el método Simplex. Sin embargo, en el tratamiento de sis-
temas moderadamente grandes, el método Simplex parece, todavía, preferible (Docentes Educación
Navarra, 29 de diciembre de 2018).

Método SIMplex

Las metodologías empleadas dentro de la investigación de operaciones están fundamentadas en
álgebra lineal, donde los primeros problemas de resolución de sistemas lineales de inecuaciones se
remontan a Joseph Fourier (en el año 1826), quien más adelante desarrolló el método de eliminación
de Fourier-Motzkin.

103