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

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

Una forma ingenua para realizar una iteración sería revisar cada vecino potencial para observar
si es realmente un vértice del poliedro de restricciones y determinar su costo. Calcular el costo es
sencillo: simplemente se realiza un producto punto, pero revisar si es un vértice que cumpla con las
restricciones representa resolver un sistema de n ecuaciones y n incógnitas por el método de Gauss,
teniendo una complejidad de O(n ) (con la suposición de que se tienen n inecuaciones), lo que da un
3
tiempo aproximado de ejecución del O(m.n ) por iteración.
4
Afortunadamente, existe un mejor camino, y el factor m.n se puede mejorar a m.n, lo que hace del
4
Simplex un algoritmo práctico. El algoritmo Simplex, estando en un punto factible (la fase II), permite
mejorar el valor de la función objetivo de manera acelerada, ya que no existe una búsqueda a ciegas
del nuevo punto factible. Para seleccionar el mejor vecino, la función objetivo es de la forma “max c
u
+ c .y”, donde cu es el valor de la función objetivo en el punto u. Esto, de forma directa, identifica un

sentido prometedor hacia donde moverse: en este caso se busca cualquier punto tal que c > 0 (si
no existe alguno, entonces el punto u es óptimo y el algoritmo se detiene).

Por ende, se puede observar que el tiempo por iteración del Simplex es O(nm). Pero ¿cuántas
iteraciones se pueden realizar? Por supuesto, no pueden ser más de , cota superior indicada
por el número de vértices. Esta cota superior es exponencial en n.
De hecho, existen ejemplos de programación lineal en los cuales el método Simplex requiere un
número exponencial de iteraciones. Por ello, el método Simplex es un algoritmo de grado exponen-
cial. Sin embargo, esto no sucede en la práctica, lo cual en realidad hace que el algoritmo sea tan
valorado y ampliamente usado.

Por supuesto que Simplex no es un algoritmo de tiempo polinomial. Ciertamente, pocos problemas
causan que el algoritmo vaya de una esquina factible a una esquina factible mejor hasta encontrar el
óptimo en un tiempo exponencial. Por ello, por un largo tiempo la programación lineal se ha con-
siderado una paradoja: ¡un problema que se puede resolver en tiempo polinomial en práctica,
pero no en teoría!

Entonces, en 1979, un joven matemático soviético llamado Leonid Khachiyan presentó el algoritmo
del elipsoide (el cual es totalmente diferente al Simplex). Este nuevo algoritmo es extremadamente
simple en su concepción (pero sofisticado en su prueba) y puede resolver cualquier problema de pro-
gramación lineal en tiempo polinomial en lugar de moverse de una esquina a otra del poliedro. El al-
goritmo de Khachiyan confina a un elipsoide cada vez más pequeño hasta localizar el punto óptimo.

Cuando este algoritmo fue anunciado, se convirtió en un Sputnik matemático. Incluso Estados Uni-
dos se preocupó bastante de la posible superioridad científica de la Unión Soviética, ya que la de-
mostración se publicó en la parte más tensa de la guerra fría. El algoritmo del elipsoide fue un avance
teórico importante, aunque en la práctica no ha podido competir con el método Simplex. En este
caso, la paradoja de programación lineal es la siguiente: un problema con dos algoritmos (uno
que es eficiente en teoría y uno que es eficiente en la práctica).

Unos años después Narendra Karmarkar, un estudiante graduado de UC Berkeley, desarrolló un
algoritmo completamente diferente para ejecutar en un tiempo polinomial. El algoritmo de Karmarkar

128