Optimierung · Erklären & üben

Primaler Simplex

Der primale Simplex verbessert eine zulässige Basislösung schrittweise. Hier lernst du einen kleinen regulären Maximierungsfall mit einer unmittelbar zulässigen Schlupfvariablenbasis kennen.

Zu den Aufgaben

Erklärung 01

Modell und zulässiger Start

Unser kontinuierliches Modell maximiert $\mathsf{z=3x+2y}$ unter $\mathsf{x+y\leq4}$ , $\mathsf{x\leq2}$ , $\mathsf{y\leq3}$ sowie $\mathsf{x,y\geq0}$ . Die Variablen dürfen reelle Werte annehmen. Alle Nebenbedingungen haben die Form kleiner gleich und nichtnegative rechte Seiten. Ergänze nichtnegative Schlupfvariablen: $\mathsf{x+y+s_1=4}$ , $\mathsf{x+s_2=2}$ , $\mathsf{y+s_3=3}$ . Sie messen die ungenutzten Kapazitäten. Setzt du die Nichtbasisvariablen x und y auf null, erhältst du die zulässige Startbasis aus den drei Schlupfvariablen.

Schreibe jede Ungleichung als Gleichung mit Schlupfvariable
Setze die ursprünglichen Variablen auf null und lies die rechten Seiten ab.

Eine Startbasis muss die Gleichungen und die Nichtnegativität erfüllen.

So geht es am Beispiel

Bestimme die Startlösung des Modells.

$\mathsf{x=0}$

$\mathsf{y=0}$

$\mathsf{s_1=4}$

$\mathsf{s_2=2}$

$\mathsf{s_3=3}$

$\mathsf{z=3\cdot0+2\cdot0=0}$

Erklärung 02

Tableau und feste Vorzeichenkonvention

Die Spaltenfolge lautet $\mathsf{x,y,s_1,s_2,s_3,b}$ . Die rechte Spalte b enthält die rechten Seiten. Die Zielfunktionszeile wird als $\mathsf{z-3x-2y=0}$ geschrieben; die z-Spalte mit Koeffizient eins bleibt in der Tabelle weggelassen. Ein negativer Koeffizient in dieser Zeile zeigt hier eine verbessernde Eintrittsmöglichkeit an. Wir wählen den am stärksten negativen Koeffizienten. Die Spalten der Basisvariablen bilden in den Nebenbedingungszeilen die Einheitsmatrix.

Halte die Spaltenfolge fest
Übertrage die Koeffizienten einschließlich der Nullen.

Die Pivotregel gehört zu genau dieser Vorzeichenkonvention.

Spalten Basis, x, y, s eins, s zwei, s drei und rechte Seite b. Startbasis: s₁, s₂, s₃; Nichtbasis: x, y

So geht es am Beispiel

Lies die erste Nebenbedingungszeile und die Zielfunktionszeile ab.

$\mathsf{R_1=(1,1,1,0,0\mid4)}$

$\mathsf{R_z=(-3,-2,0,0,0\mid0)}$

Erklärung 03

Pivotspalte und Quotiententest

Im Starttableau wird x Eintrittsvariable, weil minus drei der kleinste Koeffizient der Zielfunktionszeile ist. Für den Quotiententest wird b nur durch positive Einträge der Pivotspalte geteilt. Einträge null oder negativ werden ausgelassen. Der kleinste zulässige Quotient bestimmt die austretende Basisvariable. Im regulären Beispiel sind die berücksichtigten Quotienten positiv und eindeutig verschieden. Allgemein darf ein Quotient auch null sein; solche entarteten Fälle werden hier nicht behandelt.

Wähle zuerst die Eintrittsspalte
Bilde dann nur bei positivem Spalteneintrag den Quotienten und wähle den kleinsten.

Positive Spalteneinträge sind die Voraussetzung für diesen Quotiententest.

So geht es am Beispiel

Bestimme den ersten Pivot des Starttableaus.

$\mathsf{4:1=4}$

$\mathsf{2:1=2}$

Erklärung 04

Erster Basiswechsel

Dividiere die Pivotzeile durch das Pivotelement, damit dort eine Eins steht. Eliminiere danach die übrigen Einträge der Pivotspalte durch Zeilenoperationen. Beim ersten Pivot ist das Element bereits eins. Die normierte zweite Zeile bleibt $\mathsf{x+s_2=2}$ . Danach wird sie von Zeile eins abgezogen und dreimal zur Zielfunktionszeile addiert. Zeile drei bleibt unverändert. Die neue Basis besteht aus s₁, x und s₃.

Normiere zuerst die Pivotzeile
Verwende anschließend diese normierte Zeile für alle übrigen Zeilenoperationen.

Ein Basiswechsel verändert die Darstellung, nicht das Gleichungssystem.

Spalten Basis, x, y, s eins, s zwei, s drei und rechte Seite b. Basis: s₁, x, s₃; Nichtbasis: y, s₂

So geht es am Beispiel

Führe den ersten Pivot aus. Die Reihenfolge der Spalten bleibt x, y, s₁, s₂, s₃, b.

$\mathsf{R_2\leftarrow R_2:1}$

$\mathsf{R_1\leftarrow R_1-R_2}$

$\mathsf{R_1=(0,1,1,-1,0\mid2)}$

$\mathsf{R_z\leftarrow R_z+3R_2}$

$\mathsf{R_z=(0,-2,0,3,0\mid6)}$

$\mathsf{R_3=(0,1,0,0,1\mid3)}$

Erklärung 05

Zweiter Pivot und Endlösung

Nun ist nur der y-Koeffizient in der Zielfunktionszeile negativ. Der Quotiententest liefert für Zeile eins zwei und für Zeile drei drei; Zeile zwei entfällt wegen ihres y-Koeffizienten null. Also tritt y ein und s₁ aus. Das Pivotelement in Zeile eins ist bereits eins. Nach der Elimination enthält die Zielfunktionszeile keine negativen Koeffizienten mehr. Es gilt $\mathsf{z+2s_1+s_2=10}$ . Weil beide Schlupfvariablen nichtnegativ sind, kann z höchstens zehn betragen; die gefundene Lösung erreicht diesen Wert.

Wiederhole Quotiententest und Pivotoperationen
Setze am Ende die Nichtbasisvariablen auf null und lies alle Basiswerte ab.

Die Endzeile liefert hier zugleich eine obere Schranke und den erreichten Optimalwert.

Spalten Basis, x, y, s eins, s zwei, s drei und rechte Seite b. Nichtbasis s₁ = s₂ = 0; x = 2, y = 2, s₃ = 1

So geht es am Beispiel

Führe den zweiten Pivot aus und lies das Ergebnis ab.

$\mathsf{2:1=2}$

$\mathsf{3:1=3}$

$\mathsf{R_1\leftarrow R_1:1}$

$\mathsf{R_3\leftarrow R_3-R_1}$

$\mathsf{R_3=(0,0,-1,1,1\mid1)}$

$\mathsf{R_z\leftarrow R_z+2R_1}$

$\mathsf{R_z=(0,0,2,1,0\mid10)}$

Erklärung 06

Probe, grafische Sicht und Grenzen

Prüfe die Endlösung in den ursprünglichen Ungleichungen, nicht nur im Tableau. Der zulässige Bereich hat die Eckpunkte $\mathsf{(0,0)}$ , $\mathsf{(2,0)}$ , $\mathsf{(2,2)}$ , $\mathsf{(1,3)}$ und $\mathsf{(0,3)}$ . Der Eckpunktvergleich bestätigt das Maximum. Andere Startlagen können zusätzliche Verfahren verlangen. Dualer Simplex und Big-M sind eigenständige weiterführende Methoden und werden hier nicht ausgeführt. Auch Entartung und Konvergenztheorie gehören nicht zu diesem Einstieg. Für die grafische Methode führt Lineare Optimierung weiter.

Prüfe jede Originalrestriktion und die Nichtnegativität
Setze die Werte zusätzlich in die ursprüngliche Zielfunktion ein.

Eine richtige Endlösung erfüllt das ursprüngliche Modell.

Gleiche Skalierung beider Achsen. Der schraffurfrei blau hinterlegte zulässige Bereich hat die Eckpunkte null null, zwei null, zwei zwei, eins drei und null drei. Die gestrichelte Zielfunktionsgerade drei x plus zwei y gleich zehn berührt den Bereich im optimalen Eckpunkt zwei zwei. Die Grenzgeraden x plus y gleich vier, x gleich zwei und y gleich drei sind eingezeichnet.

So geht es am Beispiel

Prüfe x = 2 und y = 2 und vergleiche die Zielfunktion an allen Eckpunkten.

$\mathsf{2+2=4\leq4}$

$\mathsf{2\leq2}$

$\mathsf{2\leq3}$

$\mathsf{2\geq0}$

$\mathsf{z=3\cdot2+2\cdot2=10}$

$\mathsf{z(0,0)=0}$

$\mathsf{z(2,0)=6}$

$\mathsf{z(2,2)=10}$

$\mathsf{z(1,3)=9}$

$\mathsf{z(0,3)=6}$

Jetzt bist du dran

Aufgaben & Lösungen

Rechne zuerst selbst. Nutze den Platz für deinen Rechenweg und vergleiche anschließend mit der Lösung.

01
Aufgabe 1Primaler Simplex · 1Verwende das Modell aus Abschnitt eins. Gib bei x = 0 und y = 0 die drei Schlupfwerte und den Zielfunktionswert getrennt an.Aufgabe öffnenAufgabe einklappen
Schlupf s₁
Schlupf s₂
Schlupf s₃
Zielfunktionswert z
Lösung & Rechenweg
Rechenweg
1. Schritt 1 · Erklärung
  $\mathsf{s_1=4-0-0=4}$
2. Schritt 2 · Erklärung
  $\mathsf{s_2=2-0=2}$
3. Schritt 3 · Erklärung
  $\mathsf{s_3=3-0=3}$
4. Schritt 4 · Erklärung
  $\mathsf{z=3\cdot0+2\cdot0=0}$
Ergebnisse & Teilantworten
1. Schlupf s₁4
2. Schlupf s₂2
3. Schlupf s₃3
4. Zielfunktionswert z0
02
Aufgabe 2Primaler Simplex · 1Schreibe die Zielfunktion z = 5x + 2y in unserer Tableaukonvention mit z auf der linken Seite. Welche Variable wird bei Wahl des stärksten negativen Koeffizienten zuerst Eintrittsvariable?Aufgabe öffnenAufgabe einklappen
Zielfunktionsgleichung
Eintrittsvariable
Lösung & Rechenweg
Rechenweg
1. Schritt 1 · Erklärung
  $\mathsf{z-5x-2y=0}$
2. Schritt 2 · Erklärung
  $\mathsf{-5<-2}$
Ergebnisse & Teilantworten
1. Zielfunktionsgleichung $\mathsf{z-5x-2y=0}$
2. Eintrittsvariablex
03
Aufgabe 3Primaler Simplex · 2Für eine Pivotspalte sind die Einträge von oben nach unten 2, 1, 0; die rechten Seiten lauten 8, 3, 7. Berechne die zwei zulässigen Quotienten, nenne die Pivotzeile und begründe das Auslassen der dritten Zeile.Aufgabe öffnenAufgabe einklappen
Quotient Zeile eins
Quotient Zeile zwei
Pivotzeile
Grund für Auslassen
Lösung & Rechenweg
Rechenweg
1. Schritt 1 · Erklärung
  $\mathsf{8:2=4}$
2. Schritt 2 · Erklärung
  $\mathsf{3:1=3}$
Ergebnisse & Teilantworten
1. Quotient Zeile eins4
2. Quotient Zeile zwei3
3. PivotzeileZeile zwei
4. Grund für AuslassenDer Pivotspalteneintrag null ist nicht positiv; durch null darf nicht geteilt werden.
04
Aufgabe 4Primaler Simplex · 2Die Pivotzeile lautet 2x + 4y + s₁ = 8; x soll Basisvariable werden. Normiere diese einzelne Zeile. Gib den x-Koeffizienten, den y-Koeffizienten, den s₁-Koeffizienten und die rechte Seite getrennt an.Aufgabe öffnenAufgabe einklappen
x-Koeffizient
y-Koeffizient
s₁-Koeffizient
Rechte Seite
Lösung & Rechenweg
Rechenweg
1. Schritt 1 · Erklärung
  $\mathsf{(2x+4y+s_1):2=8:2}$
2. Schritt 2 · Erklärung
  $\mathsf{x+2y+\tfrac12s_1=4}$
Ergebnisse & Teilantworten
1. x-Koeffizient1
2. y-Koeffizient2
3. s₁-Koeffizient $\mathsf{\tfrac12}$
4. Rechte Seite4
05
Aufgabe 5Primaler Simplex · 2Im Hauptbeispiel wird beim ersten Pivot R₂ von R₁ abgezogen. Ausgangszeilen: x + y + s₁ = 4 und x + s₂ = 2. Gib die neue Gleichung und die danach austretende sowie eintretende Basisvariable an.Aufgabe öffnenAufgabe einklappen
Neue Gleichung
Austretende Variable
Eintretende Variable
Lösung & Rechenweg
Rechenweg
1. Schritt 1 · Erklärung
  $\mathsf{(x+y+s_1)-(x+s_2)=4-2}$
2. Schritt 2 · Erklärung
  $\mathsf{y+s_1-s_2=2}$
Ergebnisse & Teilantworten
1. Neue Gleichung $\mathsf{y+s_1-s_2=2}$
2. Austretende Variables₂
3. Eintretende Variablex
06
Aufgabe 6Primaler Simplex · 2Nach dem ersten Pivot gelten y + s₁ − s₂ = 2, x + s₂ = 2 und y + s₃ = 3. Die Zielfunktionszeile ist z − 2y + 3s₂ = 6. Nenne die nächste Eintrittsvariable, die beiden zulässigen Quotienten, die Pivotzeile und die austretende Variable.Aufgabe öffnenAufgabe einklappen
Eintrittsvariable
Quotient Zeile eins
Quotient Zeile drei
Pivotzeile
Austretende Variable
Lösung & Rechenweg
Rechenweg
1. Schritt 1 · Erklärung
  $\mathsf{2:1=2}$
2. Schritt 2 · Erklärung
  $\mathsf{3:1=3}$
Ergebnisse & Teilantworten
1. Eintrittsvariabley
2. Quotient Zeile eins2
3. Quotient Zeile drei3
4. PivotzeileZeile eins
5. Austretende Variables₁
07
Aufgabe 7Primaler Simplex · 2Lies aus dem Endtableau des Hauptbeispiels x, y, alle drei Schlupfwerte und z ab. Welche Variablen sind Nichtbasisvariablen?Aufgabe öffnenAufgabe einklappen
x
y
s₁
s₂
s₃
z
Nichtbasisvariablen
Lösung & Rechenweg
Rechenweg
1. Schritt 1 · Erklärung
  $\mathsf{s_1=0}$
2. Schritt 2 · Erklärung
  $\mathsf{s_2=0}$
3. Schritt 3 · Erklärung
  $\mathsf{x=2}$
4. Schritt 4 · Erklärung
  $\mathsf{y=2}$
5. Schritt 5 · Erklärung
  $\mathsf{s_3=1}$
6. Schritt 6 · Erklärung
  $\mathsf{z=10}$
Ergebnisse & Teilantworten
1. x2
2. y2
3. s₁0
4. s₂0
5. s₃1
6. z10
7. Nichtbasisvariablens₁ und s₂
08
Aufgabe 8Primaler Simplex · 3Jemand schlägt x = 2 und y = 3 für das Hauptbeispiel vor. Berechne den Zielfunktionswert. Ist der Punkt zulässig? Begründe anhand der verletzten Originalrestriktion.Aufgabe öffnenAufgabe einklappen
Zielfunktionswert
Zulässig?
Begründung
Lösung & Rechenweg
Rechenweg
1. Schritt 1 · Erklärung
  $\mathsf{z=3\cdot2+2\cdot3=12}$
2. Schritt 2 · Erklärung
  $\mathsf{2+3=5>4}$
Ergebnisse & Teilantworten
1. Zielfunktionswert12
2. Zulässig?Nein
3. BegründungDie Restriktion x + y ≤ 4 ist verletzt, da die Summe fünf beträgt.
09
Aufgabe 9Primaler Simplex · 3Im Endtableau gilt z + 2s₁ + s₂ = 10. Erkläre, warum z höchstens zehn sein kann. Prüfe außerdem, ob der Ursprung beim veränderten Modell mit x + y ≥ 2 noch zulässig ist, und begründe getrennt.Aufgabe öffnenAufgabe einklappen
Begründung der oberen Schranke
Ursprung im veränderten Modell zulässig?
Begründung zur Startlage
Lösung & Rechenweg
Rechenweg
1. Schritt 1 · Erklärung
  $\mathsf{z=10-2s_1-s_2}$
2. Schritt 2 · Erklärung
  $\mathsf{s_1,s_2\geq0}$
3. Schritt 3 · Erklärung
  $\mathsf{z\leq10}$
4. Schritt 4 · Erklärung
  $\mathsf{0+0=0<2}$
Ergebnisse & Teilantworten
1. Begründung der oberen SchrankeVon zehn werden nur nichtnegative Größen abgezogen. Deshalb kann z zehn nicht überschreiten.
2. Ursprung im veränderten Modell zulässig?Nein
3. Begründung zur StartlageDer Ursprung verletzt x + y ≥ 2. Der hier verwendete unmittelbare Schlupfstart passt deshalb nicht.

Selbstcheck

Das kann ich jetzt

Ich nenne Ausgangs- und Zieleinheit.
Ich leite den passenden Faktor aus den Einheiten ab.
Ich schreibe Einheit und Zahlwert gemeinsam auf.

AT Academy · Version 2026-10-21