Page 133 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
P. 133
INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
Por lo tanto, X = 3 y Z = 3, siendo este el punto óptimo del sistema de ecuaciones (Bueno de Arjona,
1
1987). La programación del algoritmo de Tucker se desarrolló en el lenguaje de programación Java
y se localiza en el anexo A.
aNálISIS de coMplejIdad
Teniendo a
Max c x
T
Tal que Ax ≤ 0
X > 0
con n incógnitas y m inecuaciones, el algoritmo Simplex es iterativo; en este va recorriendo cada uno
de los vértices donde se logran satisfacer las m inecuaciones. Iniciemos computando el tiempo que
toma realizar una iteración suponiendo que el vértice actual es u. Por definición, es un punto donde
se satisfacen las m inecuaciones, por lo que u tiene por mucho n vecinos, como se muestra en la
figura 5.7, donde se tienen 3 ecuaciones y 2 incógnitas, por lo que el punto P contiene 6 puntos
vecinos.
Figura 5.6. Análisis de complejidad
127
