Eckpunkt-Rechner

Der Eckpunkt-Rechner beantwortet den letzten Schritt jeder Aufgabe zur linearen Optimierung: Welcher Punkt maximiert bei gegebenen Zielfunktionskoeffizienten und Eckpunkten des zulässigen Bereichs die Zielfunktion, und welchen Wert erreicht sie? Eine lineare Zielfunktion über einem konvexen Polytop erreicht ihr Optimum stets in einem Eckpunkt; die Auswertung an jedem Eckpunkt ist daher keine Näherung, sondern die exakte Lösung. Sie senden den Koeffizientenvektor und die Punktliste; der Endpunkt wertet das Skalarprodukt an jedem Punkt aus, wendet eine deterministische Regel bei Gleichstand an und liefert den Gewinnerpunkt, seinen Zielwert und seine Position in Ihrer Liste. Er läuft in Millisekunden, speichert nichts, und derselbe Code läuft kostenlos in Ihrem Browser auf dieser Seite.

Warum das Optimum stets ein Eckpunkt ist

Der Hauptsatz der linearen Optimierung besagt: Hat ein lineares Programm eine optimale Lösung und besitzt sein zulässiger Bereich mindestens einen Eckpunkt, dann ist ein Eckpunkt optimal. Eine lineare Zielfunktion verschiebt sich in parallelen Niveaumengen; schiebt man diese in Richtung der Verbesserung, werden sie schließlich gegen einen Extrempunkt des zulässigen Polytops gedrückt. Deshalb arbeiten die klassischen Methoden — die grafische Lösung mit zwei Variablen, die Simplex-Methode in höheren Dimensionen — ausschließlich mit Eckpunkten.

Haben Sie die Eckpunkte Ihres zulässigen Bereichs bereits aufgezählt, ist die verbleibende Arbeit reine Arithmetik: Berechnen Sie c·x an jedem Punkt und wählen Sie den größten Wert. Genau das tut dieser Endpunkt, mit strenger Validierung, damit ein fehlerhafter Punkt oder ein Dimensionskonflikt laut scheitert statt Ihr Ergebnis still zu verfälschen. Da er jeden Punkt auswertet, nennt er Ihnen auch die Zahl der verglichenen Kandidaten — nützlich, wenn Sie eine Lösung prüfen oder die Methode Schritt für Schritt vermitteln.

Eckpunkte aus Ihren Nebenbedingungen aufbereiten

Die Eingabe ist bewusst einfach: ein Zielarray und ein Array von Eckpunkten, wobei jeder Punkt ein Array von Zahlen mit derselben Länge wie das Zielarray ist. Das Ermitteln dieser Punkte ist Ihre Aufgabe — üblicherweise durch Schnitt von Nebenbedingungsgeraden in zwei Dimensionen oder durch ein Vertex-Enumerationsverfahren in höheren Dimensionen. Jeder gesendete Punkt muss zulässig sein; der Endpunkt vertraut Ihrer Liste und prüft Nebenbedingungen nicht nach, weil er sie nie zu sehen bekommt.

Gleichstand ist deterministisch: Erreichen zwei Punkte denselben Maximalwert, gewinnt der zuerst in Ihrer Liste stehende — wiederholte Aufrufe mit derselben Eingabe liefern also immer Byte für Byte dieselbe Antwort.

Das Ergebnis lesen und automatisieren

Der index ist in der Praxis wichtig, weil Punkte in Ihrem Modell meist Bezeichnungen tragen — Maschinenmix A, Portfolio B — und die Position die Rückabbildung ohne fehleranfälligen Koordinatenvergleich erlaubt. Typische Automatisierungen sind die Bewertung von Studierendenabgaben gegen eine Referenzlösung, die Verifikation, dass das von einem Solver gemeldete Optimum zu einer unabhängigen Eckpunktaufzählung passt, sowie die Bewertung kleiner Planungs- oder Mischungsmodelle, bei denen das Aufzählen der Eckpunkte günstiger ist als der Einsatz eines vollwertigen LP-Solvers.