Solver für lineare Programmierung

Solver für lineare Programmierung

Der Solver für lineare Programmierung ist ein Online-Rechner, der das Maximum oder Minimum einer linearen Zielfunktion unter Berücksichtigung eines Systems linearer Ungleichungen oder Gleichungen findet. Er nutzt die Simplex-Methode (Big-M-Variante), sodass <=, >= und = Nebenbedingungen frei gemischt werden können. Bei Problemen mit 2 Variablen zeichnet er ein interaktives Diagramm des zulässigen Bereichs, in dem jeder Eckpunkt und das Optimum hervorgehoben sind.

Was ist lineare Programmierung?

Ein Problem der linearen Programmierung (LP) stellt folgende Aufgabe:

Die Menge der Punkte, die jede Nebenbedingung erfüllen, wird als zulässiger Bereich bezeichnet, ein konvexes Polyeder. Der Fundamentalsatz der linearen Programmierung besagt, dass wenn das LP ein endliches Optimum hat, dieses an einem Eckpunkt (Extrempunkt) dieses Polyeders erreicht wird. Deshalb ist die Simplex-Methode — die von Eckpunkt zu Eckpunkt wandert — so effektiv.

Wie die Simplex-Methode funktioniert

Ausgehend von einem zulässigen Eckpunkt verbessert die Simplex-Methode die Zielfunktion wiederholt durch Pivoting zu einem benachbarten Eckpunkt mit einem besseren Wert. Die Mechanik:

1. Standardform: Umwandlung des LP in max c^Tx unter Ax = b, x ≥ 0. Für <=-Bedingungen werden Schlupfvariablen hinzugefügt; für >= wird ein Überschuss subtrahiert und eine künstliche Variable mit einer großen Strafe −M hinzugefügt; für Gleichungen wird eine künstliche Variable hinzugefügt.
2. Initiales Tableau: Die Basis besteht aus Schlupf- und künstlichen Variablen, was einen offensichtlichen Start-Eckpunkt liefert.
3. Eintretende Variable: Wahl der Nicht-Basisvariable mit den größten positiven reduzierten Kosten \( c_j - z_j \). Wenn keine solche Variable existiert, ist die aktuelle Lösung optimal.
4. Austretende Variable: Aus der eintretenden Spalte wird der Quotiententest durchgeführt — dividieren Sie das RHS jeder Zeile durch seinen positiven Eintrag in der eintretenden Spalte und wählen Sie die Zeile mit dem kleinsten Verhältnis. Wenn kein positiver Eintrag existiert, ist das LP unbeschränkt.
5. Pivot: Anwendung des Gaußschen Eliminationsverfahrens, um die eintretende Spalte zu einem Einheitsvektor mit einer 1 in der austretenden Zeile zu machen.
6. Wiederholung, bis das Abbruchkriterium erfüllt ist.

Wenn bei Abschluss eine künstliche Variable mit einem positiven Wert in der Basis verbleibt, ist das ursprüngliche LP unzulässig.

Grafische Methode (für 2 Variablen)

Bei Problemen mit zwei Variablen ist der zulässige Bereich ein 2D-konvexes Polygon. Da das Optimum immer an einem Eckpunkt liegt, reicht es aus, jeden Eckpunkt aufzuzählen und die Zielfunktion dort auszuwerten. Dieser Rechner führt diese Aufzählung durch, indem er jedes Paar von Nebenbedingungsgrenzen schneidet, nur Schnittpunkte behält, die alle anderen Bedingungen erfüllen, und diese für die Visualisierung gegen den Uhrzeigersinn sortiert.

Eingabesyntax

Schreiben Sie die Zielfunktion in die erste Zeile, dann eine Nebenbedingung pro Zeile. Variablennamen können beliebige Bezeichner sein (x, y, x1, gewinn…). Operatoren sind <=, >= und =. Nichtnegativität kann als x, y >= 0 als Abkürzung geschrieben werden.

Leerzeilen und Kommentare, die mit # beginnen, werden ignoriert. Der Solver akzeptiert bis zu 8 Entscheidungsvariablen und 20 Nebenbedingungen.

Beispielaufgabe

Betrachten Sie eine Möbelwerkstatt, die Tische und Stühle baut. Jeder Tisch bringt 3 \$ Gewinn und benötigt 1 Einheit Holz und 2 Einheiten Arbeit. Jeder Stuhl bringt 5 \$ Gewinn und benötigt 1 Einheit Holz, 1 Einheit Arbeit und 3 Einheiten Lack. Verfügbar sind: 10 Holz, 16 Arbeit, 18 Lack. Mit x = Tische und y = Stühle lautet das LP:

Der zulässige Bereich ist ein Fünfeck. Auswertung von Z an jedem Eckpunkt:

Die Werkstatt sollte also 6 Tische und 4 Stühle für einen maximalen Gewinn von 38 \$ bauen. Die Holz- und Arbeitsbedingungen sind bindend (sie entsprechen im Optimum ihrem RHS); Lack hat einen Schlupf von 0 (in diesem Fall ebenfalls bindend), was bedeutet, dass alle drei Ressourcen erschöpft sind.

Häufige Fehlerquellen & was der Solver erkennt

Anwendungen

• Produktmix & Produktionsplanung — wie viele Einheiten jedes Produkts für maximalen Gewinn bei Ressourcenknappheit hergestellt werden sollen.
• Diät- & Mischungsprobleme — Minimierung der Kosten einer Ernährung oder eines Futtermittels, das dennoch Mindestanforderungen erfüllt.
• Transport & Zuweisung — Minimierung der Versandkosten, wenn Angebot und Nachfrage ausgeglichen sein müssen.
• Portfolio-Optimierung — Maximierung der erwarteten Rendite unter Risiko- oder Exposure-Nebenbedingungen (linearisiert).
• Netzwerkfluss — Max-Flow- und Min-Cost-Flow-Probleme lassen sich auf LPs mit total unimodularen Koeffizientenmatrizen reduzieren.
• Dienstplanung — Personaleinsatzplanung mit Schichtanforderungen und Grenzen für die Gesamtarbeitszeit.

So verwenden Sie diesen Rechner

1. Geben Sie Ihr LP in das Textfeld ein. Die erste Zeile muss mit Maximize oder Minimize beginnen. Jede folgende Zeile enthält eine Nebenbedingung.
2. Verwenden Sie das Kürzel x, y >= 0, um die Nichtnegativität für alle aufgeführten Variablen gleichzeitig zu deklarieren.
3. Klicken Sie auf LP-Problem lösen. Der Solver meldet den optimalen Wert Z, die optimalen Werte jeder Entscheidungsvariable, eine Liste bindender Nebenbedingungen und für 2-Variablen-LPs ein interaktives Diagramm des zulässigen Bereichs.
4. Fahren Sie über einen Eckpunkt im Diagramm, um seine Koordinaten und den Z-Wert zu sehen. Das Optimum ist mit einem Stern markiert.
5. Prüfen Sie die Simplex-Tableaus, um jeden Pivot zu sehen und zu verfolgen, wie die Methode Z verbessert. Die eintretende Spalte ist gelb markiert, die austretende Zeile rot.

Häufig gestellte Fragen

Was ist ein Problem der linearen Programmierung?

Ein Problem der linearen Programmierung (LP) sucht nach dem Maximum oder Minimum einer linearen Zielfunktion über einer Menge von Entscheidungsvariablen, die ein System linearer Ungleichungen oder Gleichungen erfüllen. Die zulässige Menge ist ein konvexes Polyeder, und das Optimum wird immer an einem seiner Eckpunkte erreicht — die zentrale Tatsache, die die Simplex-Methode ausnutzt.

Wie funktioniert die Simplex-Methode?

Die Simplex-Methode wandert entlang der Eckpunkte des zulässigen Polyeders. Jeder Schritt (ein "Pivot") tauscht eine Variable in der Basis gegen eine andere aus und bewegt sich zu einem benachbarten Eckpunkt mit einem strikt besseren Zielfunktionswert. Der Algorithmus stoppt, wenn kein Pivot Z mehr verbessern kann — der aktuelle Eckpunkt ist dann optimal. Dieses Tool verwendet die Big-M-Variante, sodass <=, >= und = Nebenbedingungen gemischt werden können.

Was ist der zulässige Bereich?

Der zulässige Bereich ist die Menge aller Variablenwerte, die alle Nebenbedingungen gleichzeitig erfüllen. Bei 2 Variablen ist es ein 2D-konvexes Polygon; bei n Variablen ist es ein n-dimensionales Polyeder. Ein leeres Polyeder bedeutet, dass das LP unzulässig ist; ein Polyeder, das sich unendlich in Verbesserungsrichtung erstreckt, bedeutet, dass das LP unbeschränkt ist.

Was bedeutet "unbeschränkt" in der linearen Programmierung?

Ein LP ist unbeschränkt, wenn der zulässige Bereich sich ins Unendliche in eine Richtung erstreckt, in der sich die Zielfunktion stetig verbessert. Zum Beispiel hat Maximize x unter der Bedingung x ≥ 0 kein endliches Maximum. LP-Probleme aus der Praxis, die unbeschränkt sind, weisen meist auf eine fehlende Nebenbedingung hin — oft eine obere Schranke für eine Ressource oder Variable.

Was bedeutet "alternative Optima"?

Alternative Optima treten auf, wenn mehr als ein Punkt denselben besten Zielfunktionswert erreicht. Geometrisch verläuft die Zielfunktion parallel zu einer bindenden Kante des Polygons, sodass jeder Punkt entlang dieser Kante — und jede Konvexkombination seiner Endpunkte — optimal ist. Der Solver markiert dies, wenn eine Nicht-Basisvariable am Ende reduzierte Kosten von Null aufweist.

Wie viele Variablen und Nebenbedingungen akzeptiert der Solver?

Bis zu 8 Entscheidungsvariablen und 20 Nebenbedingungen. Das interaktive Diagramm des zulässigen Bereichs wird nur für Probleme mit 2 Variablen gezeichnet; bei 3 oder mehr Variablen erhalten Sie weiterhin die vollständige numerische Simplex-Lösung, Schritt-für-Schritt-Tableaus und den Bericht über bindende Nebenbedingungen.

Weiterführende Literatur

• Lineare Optimierung — Wikipedia
• Simplex-Verfahren — Wikipedia
• Big-M-Methode — Wikipedia
• Dualität in der Optimierung — Wikipedia

Erweiterte Rechenoperationen:

• Antilogarithmus Rechner
• Betafunktion-Rechner
• Binomialkoeffizient-Rechner
• Binomialverteilungsrechner
• Binär-Rechner
• Zentraler Grenzwertsatz Rechner
• Kombinatorik-Rechner Empfohlen
• Rechner für komplementäre Fehlerfunktion
• Komplexe Zahlen Rechner
• Entropie-Rechner
• Fehlerfunktion berechnen
• Rechner für exponentiellen Zerfall
• Exponentielle Zunahme Rechner
• Exponentielles Integral Rechner
• exponenten-rechner-hohe-präzision
• Fakultätsrechner
• Gammafunktion-Rechner
• Goldener Schnitt Rechner
• Halbwertszeit berechnen
• Prozentuale Wachstumsrate Rechner Empfohlen
• permutationsrechner
• Poisson-Verteilungsrechner
• Polynom Wurzeln Rechner mit detaillierten Schritten
• Wahrscheinlichkeitsrechner
• Wahrscheinlichkeitsverteilung Rechner
• Anteil-Rechner
• Mitternachtsformel Rechner
• Wissenschaftlicher Taschenrechner
• Wissenschaftliche Schreibweise Rechner
• Signifikante Stellen Rechner Neu
• Summe von Kuben Rechner
• Summe von positiven Ganzzahlen Rechner
• Summe von Quadratzahlen Rechner
• Wahrheitstabellen-Generator
• Mengenlehre-Rechner
• Venn-Diagramm-Generator (3 Mengen)
• Chinesischer Restsatz Rechner
• Euler Totient Funktion Rechner
• Erweiterter Euklidischer Algorithmus Rechner Empfohlen
• Modularer Multiplikativer Inverser Rechner
• Kettenbruch-Rechner Empfohlen
• Dijkstra Kürzester Weg Rechner
• Minimaler Spannbaum Rechner
• Graph Gradfolgen-Validator
• Derangement Subfaktorielle Rechner
• Stirling-Zahlen-Rechner
• Schubfachprinzip-Rechner
• Markov-Ketten Stationäre Verteilung Rechner
• rundungsrechner Neu
• Negativer Binomialverteilungsrechner Neu
• Permutationen mit Wiederholung Rechner Neu
• Modulare Exponentiationsrechner Neu
• Primitivwurzel-Rechner
• Boolesche Algebra Vereinfacher Neu
• Karnaugh-Diagramm (K-Map) Löser Neu
• Graphfärbung Rechner Neu
• Topologische Sortierung Rechner Neu
• Adjazenzmatrix-Rechner Neu
• Inklusions-Exklusions-Rechner Neu
• Solver für lineare Programmierung Neu
• Traveling Salesman Solver (TSP) Neu
• Hamilton-Pfad-Prüfer Neu
• Planarer Graph Prüfer Neu
• Netzwerkfluss-Rechner (Maximaler Fluss) Neu
• Stable Marriage Problem Löser Neu
• Gruppentheorie-Ordnungsrechner Neu
• Ring und Körperrechner Neu