Simplex-Rechner für lineare Optimierung
Gib eine Zielfunktion und Nebenbedingungen in einfacher Schreibweise ein, etwa 3x + 5y und 2x + y ≤ 18. Der Rechner findet das exakte Optimum mit dem Zwei-Phasen-Simplex-Verfahren, zeigt jedes Tableau mit hervorgehobenem Pivotelement und zeichnet bei zwei Variablen den zulässigen Bereich mit seinen Eckpunkten.
Zuletzt aktualisiert:
Schreibe Terme wie 3x, -0.5y, 2/3 x1. Variablen können beliebige Namen haben (x, y, x1, stuehle). Schreibe x >= 0-Zeilen selbst, wenn du die Nichtnegativität deaktivierst.
Zulässiger Bereich
Schritte der Simplex-Tableaus
Anleitung: Simplex-Rechner für lineare Optimierung
- Wähle Maximieren oder Minimieren und gib die Zielfunktion ein, zum Beispiel
3x + 5y. - Gib die Nebenbedingungen ein, eine pro Zeile, etwa
3x + 2y <= 18oderx + y >= 4. - Lass „Alle Variablen ≥ 0“ aktiviert für die üblichen Nichtnegativitätsbedingungen oder deaktiviere es für freie Variablen.
- Klicke auf „Lösen“, um den optimalen Wert, die Variablenwerte und die bindenden Nebenbedingungen zu sehen.
- Lies die Tableau-Schritte darunter und prüfe bei zwei Variablen den Graphen und die Eckpunkttabelle.
Standardform und Simplex-Tableau
Ein lineares Programm hat in diesem Tool die Form maximiere (oder minimiere) z = c₁x₁ + c₂x₂ + … + cₙxₙ unter den Nebenbedingungen aᵢ₁x₁ + … + aᵢₙxₙ (≤, ≥ oder =) bᵢ, meist mit allen xⱼ ≥ 0. Zum Start des Simplex-Verfahrens wird jede Nebenbedingung zu einer Gleichung:
| Art der Nebenbedingung | Wird zu | Start-Basisvariable |
|---|---|---|
| 3x + 2y ≤ 18 | 3x + 2y + s₁ = 18 | Schlupf s₁ = 18 |
| x + y ≥ 4 | x + y − e₂ + a₂ = 4 | künstlich a₂ = 4 (in Phase 1 entfernt) |
| x + y = 10 | x + y + a₃ = 10 | künstlich a₃ = 10 (in Phase 1 entfernt) |
| negative rechte Seite, z. B. x − y ≥ −2 | mit −1 multiplizieren: −x + y ≤ 2 | Schlupf |
Die Zielfunktionszeile des Tableaus enthält z − c·x = 0, daher beginnen ihre Einträge als Negative der Zielfunktionskoeffizienten. Jeder Pivotschritt teilt die Pivotzeile durch das Pivotelement und eliminiert den Rest der Pivotspalte, genau wie beim Gauß-Jordan-Verfahren.
Rechenbeispiel
Maximiere z = 3x + 5y unter x ≤ 4, 2y ≤ 12 und 3x + 2y ≤ 18 mit x, y ≥ 0 (das Standardproblem oben).
- Der negativste Eintrag in der Zielfunktionszeile ist −5, also tritt y ein. Quotienten: Zeile 2 ergibt 12 ÷ 2 = 6, Zeile 3 ergibt 18 ÷ 2 = 9, also tritt s₂ aus.
- Nach dem Pivotschritt hat x −3 in der Zielfunktionszeile, also tritt x ein. Quotienten: Zeile 1 ergibt 4, Zeile 3 ergibt 6 ÷ 3 = 2, also tritt s₃ aus.
- Es bleiben keine negativen Einträge: Das Optimum ist x = 2, y = 6, z = 36. Die Nebenbedingungen 2 und 3 sind bindend; Nebenbedingung 1 hat den Schlupf 2.
Der Graph bestätigt es: Die Eckpunkte sind (0, 0), (4, 0), (4, 3), (2, 6) und (0, 6) mit den z-Werten 0, 12, 27, 36 und 30.
Tipps zum Aufstellen von Textaufgaben
- Lege zuerst die Variablen fest: "x = Anzahl Stühle, y = Anzahl Tische". Du kannst sogar die Namen eintippen (
stuehle,tische). - Eine Ressource, eine Nebenbedingung: Arbeitsstunden, Kilogramm Material, Budget. Die Koeffizienten geben an, wie viel der Ressource jede Einheit verbraucht.
- „Mindestens“ bedeutet ≥, „höchstens“ oder „nicht mehr als“ bedeutet ≤.
- Prüfe die Einheiten: Jeder Term einer Nebenbedingung muss dieselbe Einheit wie ihre rechte Seite haben.
Häufige Fragen
Was ist lineare Optimierung?
Lineare Optimierung (lineare Programmierung) findet den besten Wert (größter Gewinn, kleinste Kosten) einer linearen Zielfunktion wie z = 3x + 5y, wenn die Variablen lineare Nebenbedingungen wie 3x + 2y ≤ 18 erfüllen müssen. Die Menge der Punkte, die alle Nebenbedingungen erfüllen, ist der zulässige Bereich, und das Optimum liegt, falls es existiert, in einer Ecke dieses Bereichs.
Wie funktioniert das Simplex-Verfahren?
Es startet in einer Ecke des zulässigen Bereichs und wechselt wiederholt zu einer benachbarten Ecke, die die Zielfunktion verbessert. Im Tableau ist die eintretende Variable diejenige mit dem negativsten Eintrag in der Zielfunktionszeile, und die austretende Variable wird über den Engpasstest (rechte Seite ÷ positiver Spalteneintrag) bestimmt. Wenn keine negativen Einträge mehr übrig sind, ist die aktuelle Ecke optimal.
Was sind Schlupf-, Überschuss- und künstliche Variablen?
Eine Schlupfvariable macht aus einer ≤-Nebenbedingung eine Gleichung (3x + 2y + s = 18) und misst ungenutzte Kapazität. Eine Überschussvariable wird von einer ≥-Nebenbedingung abgezogen. Künstliche Variablen sind vorübergehende Hilfsvariablen für ≥- und =-Zeilen, damit der Simplex einen Startpunkt hat; Phase 1 entfernt sie, und wenn das nicht gelingt, ist das Problem unzulässig.
Wie wird ein Minimierungsproblem gelöst?
z zu minimieren ist dasselbe wie −z zu maximieren. Der Rechner negiert also die Zielfunktion, führt dieselben Simplex-Schritte aus und gibt das Minimum als Negativ des Endwerts aus. Die Tableau-Hinweise zeigen an, wann diese Umwandlung verwendet wird.
Was bedeutet unbeschränkt oder unzulässig?
Unzulässig bedeutet, dass kein Punkt alle Nebenbedingungen gleichzeitig erfüllt, zum Beispiel x + y ≤ 4 und x + y ≥ 6. Unbeschränkt bedeutet, dass sich die Zielfunktion endlos verbessern lässt, weil der zulässige Bereich in diese Richtung offen ist; in einem realen Modell fehlt dann meist eine Nebenbedingung.
Wann wird die grafische Methode angezeigt?
Der zulässige Bereich wird gezeichnet, sobald das Problem genau zwei Variablen hat. Die erste Variable liegt auf der waagerechten Achse. Die Eckpunkttabelle listet jede Ecke des Bereichs mit ihrem Zielfunktionswert auf, also die klassische grafische Methode, die neben dem Simplex-Verfahren gelehrt wird.
Kann ich mehr als zwei Variablen verwenden?
Ja. Der Simplex-Rechner verarbeitet bis zu 12 Variablen und 20 Nebenbedingungen mit exakten Brüchen. Nur der Graph ist auf zwei Variablen beschränkt; die Tableau-Schritte funktionieren für jede Größe.
Werden alle Tools auf FreeToolCabin auf Qualität und Genauigkeit getestet?
Ja. Jedes Tool auf der Website durchläuft automatische Tests in echten Browsern, die prüfen, ob das Ergebnis stimmt und keine Fehler auftreten. Wenn du einen Fehler findest oder einen Vorschlag hast, schreib uns an [email protected] – wir sehen es uns an.