Direkt zum Inhalt

Lexikon der Mathematik: Fourier-Motzkin, Verfahren von

Methode zum Auffinden einer Lösung eines Systems

\begin{eqnarray}\begin{equation} a_{i}^{T}\cdot x\leq b_{i},i=1\ldots,s \end{equation}\end{eqnarray}

linearer Ungleichungen.

Dabei werden die einzelnen Variablen schrittweise eliminiert. Um beispielsweise x1 zu eliminieren, werden in allen Ungleichungen der jeweilige Koeffizient von x1 zu 0, −1 oder 1 normiert (durch Multiplikation der entsprechenden Ungleichung mit einer geeigneten positiven Zahl). Das so entstehende System laute

\begin{eqnarray}\begin{align} &\max\{\tilde{a}^{T}_{j}\cdot(x_{2},\ldots,x_{n})-\tilde{b_{j}};m_{1}+1\leq j \leq m_{2}\}\\ &\leq x_{1}\leq \min\{-\tilde{a}^{T}_{i}\cdot (x_{2},\ldots,x_{n})+\tilde{b}_{i};1\leq t\leq m_{1}\}. \end{align}\end{eqnarray}

Hier wird x1 beseitigt, indem man nurmehr die Ungleichungen

\begin{eqnarray}\begin{equation} \tilde{a}^{T}_{i}\cdot(x_{2},\ldots,x_{n})-\tilde{b}_{j}\leq -\tilde{a}^{T}_{i}\cdot(x_{2},\ldots,x_{n})+\tilde{b}_{i} \end{equation}\end{eqnarray}

für i = m2 + 1,…, m3 betrachtet.

Analog verfährt man mit den restlichen Variablen weiter. Geometrisch entspricht dieses Vorgehen einer Projektion. Das Verfahren ist im worst case-Verhalten nicht effizient, da bei jedem Eliminationsschritt die Anzahl der Ungleichungen auf m1 · m2 + m3 anwächst, was sich auf eine exponentielle Anzahl auswachsen kann.

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