Eine interessante Frage ist, ob der Simplexalgorithmus auch wirklich das Optimum findet.

Ohne weitere Begründung:
Ja, aufgrund der speziellen Problemstruktur von Lineare Optimierungsproblemen ist ein lokales Optimum auch ein globales Optimum.

Ein lokales Optimum ist ein Punkt, an dem sich der Zielwert in alle Richtungen verschlechtert. Demgegenüber ist das Optimum, zur Verdeutlichung auch globales Optimum genannt, ein Punkt, an dem der beste Zielwert des Problems erreicht wird.

Bei der Linearen Optimierung ist es so, dass wenn ein Punkt gefunden wurde, an dem sich der Zielwert in alle Richtungen verschlechtert, nicht nur ein lokales Optimum gefunden wurde, sondern immer auch das Optimum. Man sagt das „lokale Optimum ist das globale Optimum“.

In der Abbildung sind zwei fiktive Zielfunktionen eingetragen. Bei der Linken ist es wie bei Linearen Optimierungsproblemen, das lokale Optimum ist das Optimum.

In der anderen Abbildung gibt es drei Punkte, die zwar in ihrer Umgebung den höchsten Zielwert haben, also lokale Optima sind. Aber nur ein Punkt ist das globale Optimum. Ist ein Punkt gefunden, an dem sich der Zielwert in alle Richtungen verschlechtert, kann es trotzdem lohnend sein, noch weiter zu suchen, ob es Punkte mit höherem Zielwert gibt. An dieser Stelle sei nochmals versichert, dass derartiges bei Linearen Optimierungsproblemen nicht der Fall ist.