Come determinare la complessità del tempo simplex (ad esempio flusso massimo)

Question

L'algoritmo simplex si dice che abbia una complessità temporale esponenziale nel caso peggiore. Eppure è ancora spesso usato nella pratica. Come si può determinare la complessità temporale media per un determinato problema (risolvibile con simplex).

Ad esempio, qual è la complessità temporale media del problema di flusso massimo da risolvere con l'algoritmo simplex. (Wiki ha complessità temporale per tutti gli altri algoritmi)

Grazie per il vostro tempo.

Answer 1

La complessità del caso medio è piuttosto difficile da analizzare e dipende dalla distribuzione del programma lineare. Credo che sia stato risolto per essere polinomiale sotto alcune distribuzioni comuni. Al momento non riesco a trovare la carta però.

EDIT: Sì, qui sono le fonti:

Nocedal, J. e Wright, S. J. Ottimizzazione Numerica. New York: Springer-Verlag, 1999.

Forsgren, A .; Gill, P. E .; e Wright, M. H. "Metodi interni per l'ottimizzazione non lineare". SIAM Rev. 44, 525-597, 2002.

L'ho letto nel primo libro e apparentemente è stato dimostrato in un documento a parte (Forsgren). Potresti trovarlo in una biblioteca universitaria.

Answer 2

Se è ancora interessante. La complessità temporale di simplex è O ((n + m) * n).

n - numero di variabili.

m - limiti di disuguaglianza.

Perché? Perché il numero di iterazioni potrebbe essere non più di n + m nel caso di n che è un limite superiore sul numero di vertici.

Ma questo limite superiore è esponenziale in n.