Jak określić złożoność czasową simplex (tj. Przepływ maksymalny)

Question

Mówi się, że algorytm Simplex ma skomplikowaną złożoność czasową w najgorszym przypadku. Jednak wciąż jest często stosowany w praktyce. W jaki sposób można określić średni czas złożoności dla określonego problemu (rozwiązany przy pomocy simplex).

Na przykład, jaka jest średnia czasowa złożoności problemu z maksymalnym przepływem rozwiązywanego za pomocą algorytmu simplex. (Wiki ma złożoność czasową dla wszystkich innych algorytmów)

Dziękuję za poświęcony czas.

Answer 1

Średnia złożoność przypadku jest dość trudna do analizy i zależy od rozkładu programu liniowego. Uważam, że został opracowany jako czas wielomianowy w ramach niektórych wspólnych dystrybucji. Obecnie jednak nie mogę znaleźć papieru.

EDIT: Tak, tutaj są źródła:

Nocedal J., Wright, S. J. Numeryczna optymalizacja. New York: Springer-Verlag, 1999.

Forsgren, A .; Gill, P.E .; i Wright, M. H. "Wewnętrzne metody nieliniowej optymalizacji." SIAM Rev. 44, 525-597, 2002.

Przeczytałem to w pierwszej książce i najwyraźniej zostało to udowodnione w osobnej gazecie (Forsgren). Możesz znaleźć albo w bibliotece uniwersyteckiej.

Answer 2

Jeśli nadal jest interesująca. Złożoność czasowa simplex to O ((n + m) * n).

n - liczba zmiennych.

m - ograniczenia nierówności.

Dlaczego? Ponieważ liczba iteracji nie może być większa niż n + m w przypadku n , która jest górną granicą liczby wierzchołków.

Ale ta górna granica jest wykładnicza w n.