Direkt zum Inhalt

Lexikon der Mathematik: Gomory, Schnittverfahren von

ein im folgenden näher beschriebenes Schnittebenenverfahren zur Behandlung ganzzahliger linearer Optimierungsprobleme.

Man betrachte das Problem min cT · x unter den Nebenbedingungen \begin{eqnarray}A\,\cdot \,x=b,\,\,x\,\ge \,0.\end{eqnarray}

Dabei seien alle Dateneinträge in A, b und c ganzzahlig (oder rational). Das Optimum wird bezüglich ganzzahliger Vektoren x ∈ ℤn gesucht. Zunächst löst man mit der Simplexmethode das Optimierungsproblem ohne Berücksichtigung der Forde-rung nach Ganzzahligkeit der Lösung. I. allg. wird eine Lösung \(\bar{x}\) die Ganzzahligkeit nicht erfüllen. Deswegen wird eine weitere Nebenbedingung, ein sogenannter Gomory-Schnitt, hinzugefügt.

Sei B die zugehörige Matrix einer zulässigen Basis für \(\bar{x}\). Jede Basisvariable xi, iI, läßt sich (nach Multiplikation von A·x = b mit B−1) als Funktion in den Nicht-Basisvariablen xj, jJ, schreiben, etwa \begin{eqnarray}{x}_{i}=\frac{{s}_{i}}{D}\,+\,\frac{1}{D}\,\cdot \,\displaystyle \sum _{j\in J}{t}_{ij}\,\cdot \,{x}_{j}\,.\end{eqnarray}

Dabei sind D := | det(B)| und die si, tij ganzzahlig. Die Basislösung entsteht durch Wahl xj := 0 gemäß \({x}_{i}=\frac{{s}_{i}}{D}\). Nach Voraussetzung ist hier ein xi nicht ganzzahlig (sonst wäre das gesamte Problem gelöst).

Es wird nun nach einem zulässigen Punkt gesucht, bei dem die Komponente xi ganzzahlig wird. Die obige funktionale Abhängigkeit liefert zunächst \begin{eqnarray}{s}_{i}=\displaystyle \sum {t}_{ij}\,\cdot \,{x}_{j}\,\,\mathrm{mod}\,D\,.\end{eqnarray}

Definiert man zu λ ∈ ℤ den Wert |λ|D als Repräsentant modulo D von λ in {0, 1,…,D − 1}, so folgt die Lösbarkeit der Gleichung \begin{eqnarray}\displaystyle \sum _{j\in J}{|{t}_{ij}|}_{D}\,\cdot \,{x}_{j}={|{s}_{i}|}_{D}\,+\,k\,\cdot \,D\end{eqnarray} mit k ∈ ℕ0 (da x ≥ 0 und |si|D + k · D ≥ 0 gelten muß). Man fügt nun als Nebenbedingung die Ungleichung \begin{eqnarray}\displaystyle \sum _{j\in J}{|{t}_{ij}|}_{D}\,\cdot \,{x}_{j}\,\ge \,{|{s}_{i}|}_{D}\end{eqnarray} hinzu, und wiederholt das Vorgehen für das neue System. Geeignete Variationen des Verfahrens garantieren die Endlichkeit.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos