Lineare Programmierung für COMP331/557: Simplex-Verfahren verstehen – Eine Schritt-für-Schritt-Anleitung für den Klassentest

Lineare Programmierung meistern: Dein Leitfaden für den COMP331/557 Klassentest

Der COMP331/557 Klassentest fordert ein tiefes Verständnis der linearen Programmierung und des Simplex-Verfahrens. Ob du gerade erst mit dem Stoff beginnst oder dich auf die Prüfung vorbereitest – dieser Artikel hilft dir, die zentralen Konzepte zu durchdringen. Wir verzichten auf fertige Lösungen, aber du bekommst das Rüstzeug, um Aufgaben wie die aus dem Test selbstständig zu lösen. Stell dir vor, du optimierst die Produktion in einer Fabrik oder planst die Ressourcenverteilung für ein großes Event – genau das ist der Kern der linearen Programmierung.

Was ist lineare Programmierung? Ein aktuelles Beispiel

Lineare Programmierung hilft dir, unter gegebenen Beschränkungen ein Ziel zu maximieren oder zu minimieren. Stell dir vor, du organisierst im Mai 2026 ein großes Musikfestival: Du hast ein begrenztes Budget für Bühnen, Security und Catering. Mit linearer Programmierung könntest du berechnen, wie du die Besucherzahl maximierst oder die Kosten minimierst – ähnlich wie die Aufgaben im Klassentest. Die Methode ist überall einsetzbar: in der Logistik, im Finanzwesen oder sogar beim Trainieren von KI-Modellen.

Aufgabe 1: Das lineare Programm in Standardform aufstellen

In der ersten Aufgabe des Tests musst du aus einer Produktionsbeschreibung ein lineares Programm (LP) in Standardform ableiten. Die Standardform verlangt: Alle Variablen sind nichtnegativ, die Restriktionen sind ≤-Ungleichungen, und die Zielfunktion wird maximiert. Nehmen wir das Beispiel aus dem Test: Drei Maschinen X, Y, Z produzieren ein Produkt und verbrauchen unterschiedliche Ressourcen (Eisen, Kupfer, Nickel). Du hast 50 Tonnen von jedem Rohstoff. Dein Ziel: Produktionsmenge maximieren.

So gehst du vor: Definiere Entscheidungsvariablen, z. B. x = Anzahl der Durchläufe von Maschine X, y für Y, z für Z. Die Zielfunktion ist die Gesamtproduktion: 2,5x + 2y + 3z (in Tonnen). Die Restriktionen ergeben sich aus den Ressourcen: Eisen: 0,9x + 2y ≤ 50, Kupfer: 1,5x + 3z ≤ 50, Nickel: 0,5y + 0,1z ≤ 50. Alle Variablen ≥ 0. Das ist die Standardform. Vergiss nicht, die Einheiten konsistent zu halten – ein häufiger Fehler in linearen Programmen.

Schlupfvariablen und das initiale primal Dictionary

Um den Simplex-Algorithmus zu starten, führst du Schlupfvariablen ein. Sie wandeln Ungleichungen in Gleichungen um. Für jede ≤-Restriktion addierst du eine neue Variable: s1, s2, s3 ≥ 0. Aus 0,9x + 2y ≤ 50 wird 0,9x + 2y + s1 = 50. Das initiale Dictionary hat dann die Schlupfvariablen als Basisvariablen: s1 = 50 – 0,9x – 2y, s2 = 50 – 1,5x – 3z, s3 = 50 – 0,5y – 0,1z, und die Zielfunktion ζ = 2,5x + 2y + 3z. Die nicht-Basisvariablen sind x, y, z = 0. Das ist eine zulässige Basislösung. Den Simplex selbst musst du im Test nicht durchführen, aber das Dictionary vorzubereiten ist essenziell.

Aufgabe 2: Simplex geometrisch verstehen – Bland's Regel

Die zweite Aufgabe verlangt eine geometrische Interpretation des Simplex-Algorithmus. Du startest mit einer bestimmten Basis (z. B. (1,2,5,6)) und musst erklären, warum bestimmte Pivotschritte passieren. Stell dir den zulässigen Bereich als Polygon im Raum vor. Der Simplex wandert von Ecke zu Ecke, wobei die Zielfunktion verbessert wird. Bland's Regel verhindert Kreisläufe, indem sie die kleinste Indexnummer wählt. Geometrisch bedeutet das: Du bewegst dich entlang einer Kante, bis du eine neue Ecke erreichst. Wenn die Zielfunktion ζ = –x1 maximiert wird (also x1 minimiert), suchst du die linkeste Ecke. Jeder Pivot entspricht dem Verlassen einer Kante und dem Eintreten in eine neue – ähnlich wie bei einer KI-Optimierung, wo Algorithmen schrittweise bessere Lösungen finden.

Aufgabe 3: Einen Pivotschritt durchführen

Hier bekommst du ein Dictionary und musst einen Schritt des Simplex ausführen. Das Dictionary ist in der Form: ζ = 5 –4x1 +3x2 –6x3, x4 = 4 – x1 – x2, x5 = 6 – x2 – x3, x6 = 6 – x3. Die aktuelle Basislösung ist (0,0,0,4,6,6). Wähle eine eintretende Variable: Die mit dem positivsten Koeffizienten in ζ (da Maximierung). Hier ist das x2 (+3). Dann bestimmst du die verlassende Variable durch den kleinsten Quotienten: Für x4: 4/1 = 4, für x5: 6/1 = 6, für x6: – (keine Begrenzung, da x3 nicht in x6 vorkommt). Also verlässt x4 die Basis. Nach dem Pivot erhältst du eine neue Lösung: x2 = 4, x1 = 0, x3 = 0, x4 = 0, x5 = 2, x6 = 6. Der Zielfunktionswert steigt auf 17. Dieses Vorgehen ist typisch für Simplex-Aufgaben im Studium.

Aufgabe 4: Phase 1 der Zweiphasenmethode

Wenn das LP keine offensichtliche zulässige Basislösung hat (z. B. wegen negativer rechter Seite), brauchst du Phase 1. Die Aufgabe gibt ein LP mit ≤ -Ungleichungen, aber negativen rechten Seiten: x1 + x2 ≤ –4, x2 + x3 ≤ –6, x3 ≤ 6. Da die rechten Seiten nicht alle nichtnegativ sind, ist die Standard-Startlösung (x1=x2=x3=0) nicht zulässig. In Phase 1 führst du künstliche Variablen ein und minimierst deren Summe. Das LP für Phase 1 lautet: min w = a1 + a2, subject to x1 + x2 – a1 ≤ –4? Stopp: Eigentlich schreibst du die Restriktionen um, indem du Schlupfvariablen einführst und dann künstliche Variablen addierst, wo nötig. Die genaue Form findest du im Skript. Nach dem ersten Pivot erhältst du eine zulässige Basislösung für das ursprüngliche LP. Die Zweiphasenmethode ist besonders nützlich bei komplexen Optimierungsproblemen.

Aufgabe 5: Das duale Programm bestimmen

Jedes LP hat ein duales Gegenstück. Für das primal LP: max 12x1 –10x2 s.t. –4x1+3x2 ≤ 10, 4x1–3x2 ≤ 20, x1+4x2 ≤ 30, x1,x2 ≥ 0. Das duale LP wird aus den Koeffizienten gebildet: Jede primal Restriktion wird eine duale Variable (y1,y2,y3 ≥ 0). Die Zielfunktion wird min 10y1+20y2+30y3, und die Restriktionen ergeben sich aus den primalen Variablen: für x1: –4y1+4y2+1y3 ≥ 12, für x2: 3y1–3y2+4y3 ≥ –10. Die dualen Variablen sind nichtnegativ. Das Verständnis der Dualität ist entscheidend für Optimierung in der Wirtschaft und wird oft im Test abgefragt.

Tipps für den Test und darüber hinaus

Der COMP331/557 Klassentest verlangt saubere Erklärungen, keine Rechnungen mit Software. Übe, die Schritte logisch zu begründen. Verbinde die Theorie mit aktuellen Trends: Zum Beispiel nutzen KI-Apps lineare Programmierung zur Ressourcenallokation, und Finanzoptimierung verwendet Simplex für Portfolio-Management. Wenn du die Konzepte verstehst, wirst du nicht nur den Test bestehen, sondern auch reale Probleme lösen können. Viel Erfolg!