Bei einem Algorithmus ist ein wichtiges Merkmal, wie sich der Rechenaufwand mit steigender Problemgröße verhält. Dabei ist zwischen dem ungünstigsten Fall und dem durchschnittlichen Verhalten zu unterscheiden.

Wenn man den ungünstigsten Fall zugrunde legt, muss der Simplexalgorithmus leider als für größere Probleme ungeeignet eingestuft werden. Der Rechenaufwand wächst mit steigender Problemgröße exponentiell. Man nennt Algorithmen dieser Art auch „nichteffizient“.

Die Wissenschaftler Victor Klee und George J. Minty konstruierten ein Problem mit d Variablen, d Neben­bedingungen und d Nicht­negativitäts­bedingungen. Dabei ist d eine beliebige natürliche Zahl.

Dieses spezielle Problem hat 2·d zulässige Basis­lösungen und die Zielfunktion ist auch so konstruiert, dass jede Ecke abgesucht wird. D.h. der Simplex­algorithmus benötigt 2·d-1 Iterationen, um zum Optimum zu gelangen.

Der durchschnittliche Fall ist dramatisch günstiger. Es gibt hierzu verschiedene Untersuchungen, die zu ähnlichen Ergebnissen kommen. Häufig wird berichtet, dass die Anzahl der Iterationen linear mit der Problemgröße steigt. Relativ über­einstimmend wird berichtet, dass vor allem die Anzahl der Nebenbedingungen Einfluss auf die Zahl der Iterationen hat. Linear steigend heißt, dass zum Beispiel pro zusätzlicher Neben­bedingungen drei Iterationen hinzukommen.

Wenn man die Zahl der Iterationen für den konstruierten und den durch­schnittlichen Fall in eine Tabelle einträgt, wird der Unterschied klar:

Die Schlussfolgerung ist:

Der Simplexalgorithmus ist zum Lösen von großen Problemen sehr gut geeignet.