Cómo determinar la complejidad del tiempo simplex (es decir, flujo máximo)

Question

Se dice que el algoritmo simplex tiene una complejidad de tiempo de caso exponencial más desfavorable. Sin embargo, todavía se usa a menudo en la práctica. ¿Cómo se puede determinar la complejidad del tiempo promedio para un cierto problema (que se resuelve con simplex).

Por ejemplo, ¿cuál es la complejidad de tiempo promedio del problema de flujo máxima ser resuelto con el algoritmo simplex. (Wiki tiene complejidad de tiempo para todos los otros algoritmos)

Gracias por su tiempo.

Answer 1

La complejidad del caso promedio es bastante difícil de analizar y que depende de la distribución de su programa lineal. Creo que se resolvió que era tiempo polinomial bajo algunas distribuciones comunes. Actualmente no puedo encontrar el papel.

EDITAR: Sí, aquí están las fuentes:

Nocedal, J. y Wright, S. J. Optimización Numérica. Nueva York: Springer-Verlag, 1999.

Forsgren, A .; Gill, P. E .; y Wright, M. H. "Métodos interiores para la optimización no lineal". SIAM Rev. 44, 525-597, 2002.

lo leí en el primer libro y al parecer se comprobó en un documento separado (Forsgren). Puedes encontrarlos en una biblioteca universitaria.

Answer 2

Si todavía es interesante. La complejidad de tiempo de simplex es O ((n + m) * n).

n - número de variables.

m - restricciones de desigualdad.

¿Por qué? Debido a que el número de iteraciones no puede ser mayor que n + m en el caso de n que es un límite superior en el número de vértices.

Pero este límite superior es exponencial en n.