Punkt auf der Kante
Voraussetzung: Mehrere Optima
Bei mehreren optimalen Lösungen gibt es nicht nur die beiden Ecken. Die ganze Kante dazwischen ist optimal. Jeder optimale Punkt liegt auf der Verbindung der optimalen Ecken: Er ist ein Gemisch aus ihnen mit Gewichten, die nicht negativ sind und sich zu eins addieren. Hier lernst du, wie du einen Punkt dieser Kante aus den beiden Ecken ausrechnest und warum sein Zielwert derselbe ist. Voraussetzung ist der Sonderfall „Mehrere Optima“.
Sind \(P\) und \(Q\) zwei optimale Ecken, ist jeder Punkt
\[ R=\lambda P+(1-\lambda)Q\qquad\text{mit }0\le\lambda\le 1 \]
optimal. Du rechnest Koordinate für Koordinate.
- Die Gewichte \(\lambda\) und \(1-\lambda\) sind nicht negativ und ergeben zusammen \(1\).
- \(\lambda=1\) gibt die Ecke \(P\), \(\lambda=0\) die Ecke \(Q\). Dazwischen wandert \(R\) auf der Kante.
- Jede Koordinate von \(R\) ist \(\lambda\) mal die Koordinate von \(P\) plus \(1-\lambda\) mal die von \(Q\).
Warum der Zielwert gleich bleibt: \(Z\) ist linear, \(Z(\lambda P+(1-\lambda)Q)=\lambda Z(P)+(1-\lambda)Z(Q)\). Haben beide Ecken denselben Wert \(w\), ist das \(\lambda w+(1-\lambda)w=w\). Jeder Punkt der Kante hat also den optimalen Wert. Zulässig bleibt \(R\) auch: Der Bereich enthält die ganze Verbindungsstrecke zweier seiner Punkte.
Mit \(\lambda=\frac{1}{2}\) ist \(R=\left(\frac{1}{2}\cdot 9+\frac{1}{2}\cdot 0,\ \frac{1}{2}\cdot 0+\frac{1}{2}\cdot 3\right)=\left(\frac{9}{2},\frac{3}{2}\right)\). Dort ist \(Z=2\cdot\frac{9}{2}+6\cdot\frac{3}{2}=9+9=18\). Der Wert ist derselbe wie an den Ecken. Zur Probe: \(\frac{9}{2}+3\cdot\frac{3}{2}=\frac{9}{2}+\frac{9}{2}=9\), der Punkt liegt auf der Grenze \(x_1+3x_2=9\).
Ein zweites Beispiel, andere Gewichte
Mit \(\lambda=\frac{1}{3}\) ist \(R=\frac{1}{3}P+\frac{2}{3}Q=\left(\frac{1}{3}\cdot 9,\ \frac{2}{3}\cdot 3\right)=(3,2)\). Dort ist \(Z=2\cdot 3+6\cdot 2=6+12=18\), wieder derselbe Wert. Ein Punkt wie \((3,0)\) liegt dagegen nicht auf der Kante, hier ist \(Z=6\).
Mehr als zwei optimale Ecken
Bei drei oder mehr optimalen Ecken sind alle Mischungen mit nichtnegativen Gewichten optimal, die zusammen \(1\) ergeben. Bei zwei Variablen ist es der Streckenzug zwischen den optimalen Ecken, also eine Kante.