Simplex-Verfahren und Dualität: Aufgaben mit Lösungen

Hier übst du die Schritte des Simplex-Verfahrens an kleinen Beispielen. Wähle oben eine Aufgabenart oder lass sie gemischt. Mit „Neue Aufgaben“ entsteht ein neues Blatt.

Das brauchst du

• Ecken: Das Optimum liegt in einer Ecke des zulässigen Bereichs. Setze die beiden Ungleichungen gleich und löse das Gleichungssystem.
• Schlupf: Aus a x + b y ≤ r wird a x + b y + s = r mit s ≥ 0. Im Punkt (x, y) ist s = r − a x − b y.
• Pivotspalte: die Spalte mit dem größten Zielfunktionskoeffizienten (im Tableau der kleinste Eintrag der Zielzeile).
• Pivotzeile: die Zeile mit dem kleinsten Quotienten aus rechter Seite und positivem Spaltenwert.
• Dualität: Zum Problem „max c·x, A x ≤ r“ gehört „min r·u, A^T u ≥ c, u ≥ 0“. Beide haben denselben Optimalwert. Sind beide x-Werte positiv, sind beide dualen Ungleichungen scharf.

Alles steht auf der Seite Lineare Optimierung beim Eckenprinzip, beim Simplex-Verfahren und bei der Dualität.