Hallo zusammen,
hier ein schönes Beispiel für ein mathematisches Programm, bei dem der Gomory-Chvatal-Schnitt anders als der "offensichtliche" Schnitt, den wir durch eine Rundung (der rechten Seite der Ungleichung) erhalten würden, ist. Wir betrachten folgendes mathematisches Programm:
\( \begin{align}
\max \ 2x_1 + 3x_2 \\
s.d.\ x_1 + 2x_2 &\leq 3\\
4x_1 + 5x_2 &\leq 10\\
x_1, x_2 &\geq 0\\
x_1, x_2 &\in \mathbb{Z}
\end{align} \)
In Normalform:
\( \begin{align} \max \ 2x_1 + 3x_2 \\ s.d.\ x_1 + 2x_2 + y_1 &=3\\ 4x_1 + 5x_2 + y_2&=10\\ x_1, x_2, y_1, y_2 &\geq 0 \end{align} \)
Führen wir den Simplex-Algorithmus aus, kriegen wir folgende Tableaus:
Schauen wir uns nun die erste Zeile an, als Nebenbedingung wäre das:
\( x_2 + \frac{4}{3}y_1 - \frac{1}{3}y_3 = \frac{2}{3} \)
Der zugehörige Gomory-Chvatal-Schnitt ist:
\( (1- [1])x_2 + (\frac{4}{3} - [\frac{4}{3} ])y_1 + (-\frac{1}{3} - [-\frac{1}{3}]) \geq \frac{2}{3} \Leftrightarrow \frac{1}{3}y_1 + \frac{2}{3}y_2 \geq \frac{2}{3} \)
Bzw. in veränderter Basis dann:
\( 3x_1 + 4x_2 \leq 7\)
Der "offensichtliche" Schnitt dieser Nebenbedingung wäre \( x_2 \leq 0 \), was uns alle zulässigen Lösungen abgeschnitten hätte.
(Ein ausführliche Rechnung zu dem Beispiel findet ihr in diesem Vorlesungsskript der Uni Illinois).
Viele Grüße
Kendra Reiter