2. Lineare Optimierung

Man schaut auf die Werte der Schlupfvariablen. Eine Maschine $i$ ist genau dann voll ausgelastet, wenn die zugehörige Schlupfvariable $y_i = 0$ ist – das heißt, die Restriktion $\sum a_{ij}x_j + y_i = b_i$ ist mit Gleichheit erfüllt.

Im Beispiel: $y_1 = 0$ und $y_3 = 0$ → Maschinen A und C voll ausgelastet. $y_2 = 30$ und $y_4 = 130$ → Maschinen B und D haben noch freie Kapazität (30 bzw. 130 Zeiteinheiten).

Die Schattenpreise stehen in der Zielzeile (bzw. der reduzierten Kostenzeile) unter den Schlupfvariablen $y_i$. Für eine Maximierungs-Standardform sind sie im Optimum ≥ 0.

Beispiel: Steht in der Zielzeile unter $y_1$ die Zahl 100, so bedeutet das: eine zusätzliche Stunde Kapazität auf Maschine A bringt 100 GE zusätzlichen Gewinn – innerhalb des zulässigen Sensitivitätsbereichs.

Falsch (auf Basis des Endtableaus im Skript). Der Schattenpreis von Maschine C ist $\pi_C = 66\tfrac{2}{3}$ GE/h. Eine zusätzliche Stunde Kapazität bringt daher rund 66,67 GE Mehrgewinn – nicht 0,5 GE.

Merkregel: Ist die Restriktion aktiv (Schlupf $y_C = 0$), gilt $\Delta G = \pi_C \cdot \Delta b_C$. Der Schattenpreis wird direkt aus dem Endtableau abgelesen; Angaben, die davon abweichen, sind zu widerlegen.

Schlupfvariablen messen die ungenutzte Restkapazität einer Restriktion:

• $y_1 = 0$: Restriktion 1 (Maschine A) ist voll ausgelastet, es bleibt keine freie Kapazität. Die Maschine ist ein Engpass.
• $y_2 = 30$: Restriktion 2 (Maschine B) hat noch 30 Kapazitätseinheiten frei; sie ist inaktiv. Zusätzliche Stunden auf Maschine B würden den Gewinn nicht erhöhen (Schattenpreis = 0).

Wenn die Isogewinngerade parallel zu einer aktiven Restriktion verläuft. Grafisch: das Optimum wird auf einer ganzen Kante (nicht nur in einer Ecke) angenommen.

Im Simplex-Endtableau erkennt man das daran, dass eine Nichtbasisvariable in der Zielzeile den reduzierten Kostenkoeffizienten 0 hat. Ein alternativer Basistausch wäre möglich, ohne den Zielwert zu ändern.

Keine Lösung (unzulässig): Die Restriktionen widersprechen sich – der zulässige Bereich ist leer. Im Simplex äußert sich das in Phase I: das Hilfsproblem hat ein Optimum > 0.

Unbeschränkt: Der zulässige Bereich erlaubt beliebig hohe Zielwerte ($G \to \infty$ bei Maximierung). Im Simplex findet man keine begrenzende Pivotzeile, weil alle Koeffizienten in der Pivotspalte $\le 0$ sind.

Zwei $\le$-Restriktionen → zwei duale Variablen $w_1, w_2 \ge 0$. Zwei $\ge 0$-primale Variablen → zwei duale $\ge$-Restriktionen.

Die dualen Variablen $w_i$ entsprechen den Schattenpreisen der primalen Restriktionen.

Die Zielfunktion $G = c_1 x_1 + c_2 x_2$ definiert eine Isogewinngerade mit Steigung $-c_1/c_2$. Ändern sich $c_1$ oder $c_2$, ändert sich die Steigung dieser Geraden.

Solange die Steigung zwischen den Steigungen der beiden aktiven Restriktionen in der Optimalecke liegt, bleibt diese Ecke optimal – nur der Zielwert verändert sich. Verlässt die Steigung dieses Intervall, springt das Optimum auf eine benachbarte Ecke.

Man vergleicht also die Steigung der Isogewinngeraden mit den Steigungen der aktiven Restriktionsgeraden.

Der zulässige Bereich eines LP ist ein konvexes Polyeder. Eine lineare Zielfunktion nimmt ihr Maximum (bzw. Minimum) über einer konvexen Menge immer in einem Extrempunkt (= Ecke) an.

Deshalb genügt es, die endlich vielen Ecken zu prüfen. Der Simplex-Algorithmus wandert genau dieses Eckengerüst systematisch ab und wählt jeweils Nachbarecken mit besserem Zielwert aus – bis kein Verbessern mehr möglich ist. Das ist deutlich effizienter als das komplette Innere zu durchsuchen.

Für jedes zulässige $x$ (primal) und $w$ (dual) gilt $f_P(x) \le f_D(w)$ (schwache Dualität). Findet man ein Paar $(x^*, w^*)$ mit $f_P(x^*) = f_D(w^*)$, so sind beide bereits optimal (starke Dualität).

Nutzen: Man kann eine zulässige duale Lösung als Schranke nutzen und dadurch Optimalitätszertifikate ausstellen, ohne den Simplex zu Ende zu rechnen. Ist das PP unbeschränkt, ist das DP unzulässig – und umgekehrt.

Schattenpreis = 0 bedeutet, dass die zugehörige Restriktion nicht bindend (inaktiv) ist – es ist noch Kapazität vorhanden ($y_i > 0$). Eine zusätzliche Kapazitätseinheit auf dieser Maschine wäre nutzlos: sie würde nur den Schlupf erhöhen, aber den Zielwert nicht verändern.

Umgekehrt gilt: ein Schattenpreis > 0 zeigt einen echten Engpass an, der sich zu lockern lohnt (Investition in mehr Kapazität rechnet sich bis zum Wert des Schattenpreises).

Nein – solange $\Delta b_i$ innerhalb des vorhandenen Schlupfs bleibt. Da $y_i > 0$, ist die Restriktion nicht bindend; eine Verschiebung ändert nichts an der Optimalecke und auch nichts am Zielwert ($\pi_i = 0$).

Anders bei einer aktiven Restriktion: Dort gilt $\Delta G = \pi_i \cdot \Delta b_i$ innerhalb des Sensitivitätsintervalls. Verlässt $\Delta b_i$ dieses Intervall, ändert sich der Basissatz und die Analyse muss neu gerechnet werden.

Eine Restriktion $\sum a_{ij} x_j \le b_i$ heißt im Optimum

• aktiv (bindend): Gleichheit gilt, $\sum a_{ij} x_j^* = b_i$, Schlupf $y_i^* = 0$. Sie bestimmt die Optimalecke mit.
• inaktiv: Ungleichheit ist strikt, $\sum a_{ij} x_j^* < b_i$, Schlupf $y_i^* > 0$. Sie schränkt die aktuelle Lösung nicht ein.

Nur an aktiven Restriktionen greifen Schattenpreise; Änderungen an inaktiven Restriktionen sind (in Grenzen) folgenlos.

Schlupfvariablen $y_i \ge 0$ dienen dazu, Ungleichungen in Gleichungen zu überführen: $\sum a_{ij} x_j + y_i = b_i$. Nur mit Gleichungen kann der Simplex-Algorithmus (Pivotieren via Gauß-Schritten) sinnvoll arbeiten.

In der Zielfunktion tauchen sie mit Koeffizient $0$ auf ($c_{y_i} = 0$) – sie repräsentieren ja keinen Gewinn oder Verlust, sondern bloß ungenutzte Kapazität. In der optimalen Zielzeile allerdings erscheinen unter den Schlupfvariablen die Schattenpreise, was ihre ökonomische Interpretation liefert.