Direkt zum Inhalt

Lexikon der Mathematik: Lemke, Verfahren von

eine Methode zur Lösung linearer Komplemetaritätsprobleme der Form

\begin{eqnarray}\begin{array}{ll}w-M\cdot z=q, & \\ w\ge 0,z\ge 0, & {w}^{T}\cdot z=0.\end{array}\end{eqnarray}

Unter der Annahme, daß q ≥ 0 nicht gilt (ansonsten ist z:= 0, w := q eine Lösung), führt man eine weitere Variable t ≥ 0 ein, und verändert das Ausgangsproblem zu

\begin{eqnarray}\begin{array}{l}w=M\cdot z={e}^{T}\cdot t+q,\\ w\ge 0, z\ge 0, t\ge 0,\end{array}\end{eqnarray}

und e := (1, …, 1)T. Mit qi0 := min{qj, j} und der Wahl t := −qi0, wk := qkqi0 für ki0, sowie wi0 = 0, z:= 0, gewinnt man eine Ecke des zugehörigen Polyeders. Für diese sind wi0 und alle zk Nichtbasisvariablen. Jetzt werden wie im Simplexverfahren – allerdings ohne das Vorhandensein einer Zielfunktion – Austauschschritte durchgeführt, wobei zi0 die erste Pivotspalte festlegt. Ziel ist es, die Variable t aus der Basis zu entfernen. Im Falle einer positiv definiten Matrix M ist dann das Problem gelöst.

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

Partnerinhalte