Das lineare Komplementaritätsproblem: Eine Einführung by Uwe Schäfer

By Uwe Schäfer

Wer Querverbindungen bzw. Querbezüge in der Mathematik magazine, ist beim linearen Komplementaritätsproblem genau richtig. Denn viele mathematische Problemstellungen, die auf den ersten Blick nichts miteinander zu tun haben, lassen sich in ein lineares Komplementaritätsproblem überführen. Das vorliegende Buch stellt ausführlich viele dieser Problemstellungen vor und beschreibt, wie sie letztendlich auf ein lineares Komplementaritätsproblem führen. Zur Lösung werden sowohl direkte als auch iterative Verfahren betrachtet, wobei auch ein Augenmerk darauf geworfen wird, welche Besonderheiten auftreten können, wenn die Algorithmen auf einem desktop umgesetzt werden. Ausgearbeitete Lösungen zu den in den einzelnen Kapiteln gestellten Aufgaben runden das Buch ab.

Show description

Read or Download Das lineare Komplementaritätsproblem: Eine Einführung PDF

Best linear programming books

Classes of linear operators

This publication provides a landscape of operator conception. It treats various sessions of linear operators which illustrate the richness of the speculation, either in its theoretical advancements and its purposes. for every of the periods numerous differential and necessary operators encourage or illustrate the most effects.

Basic Classes of Linear Operators

A comprehensive graduate textbook that introduces functional research with an emphasis at the thought of linear operators and its software to differential equations, vital equations, endless platforms of linear equations, approximation thought, and numerical research. As a textbook designed for senior undergraduate and graduate scholars, it starts with the geometry of Hilbert areas and proceeds to the speculation of linear operators on those areas together with Banach areas.

Time Continuity in Discrete Time Models: New Approaches for Production Planning in Process Industries (Lecture Notes in Economics and Mathematical Systems)

Creation making plans difficulties containing particular features from technique industries are addressed during this ebook. the most topic is the improvement of mathematical programming versions that permit to version construction plans which aren't disrupted via discretization of time. besides the fact that, discrete time versions are used as a foundation and are for that reason better to incorporate points of time continuity.

Additional resources for Das lineare Komplementaritätsproblem: Eine Einführung

Sample text

Das lexikographische Minimum von 1 1 1100 , 0010 V := 1 1 ist der zweite Zeilenvektor. Daher ist i0 = 2. Nach einem Gauß–Jordan-Schritt (1) mit Pivotelement a2 4 erh¨alt man . BVF2 w1 w2 w3 z1 z2 z3 z0 (q (2) .. (B (2) )−1 ) . z0 0 –1 0 0 1 2 1 1 .. 1 –1 0 z1 –1 1 0 1 1 –2 0 . 0 .. 0 1 0 w3 –2 1 1 0 3 –3 0 . 0 .. 0 1 1 28 2 Der Lemke-Algorithmus w2 hat das Basisvariablenfeld verlassen. Daher ist j0 = 3 + 2 = 5 der neue Pivotspaltenindex. Das lexikographische Minimum von V := 1 1 1 1 1 -1 0 , 0010 , 0011 1 1 3 ist der dritte Zeilenvektor.

Es stammt von K. G. Murty aus dem Jahre 1978, und wir werden es in diesem Abschnitt vorstellen. Dieses Beispiel ist allerdings sehr speziell konstruiert, und wir wollen betonen, dass (analog zum Simplexverfahren) das durchschnittliche Laufzeitverhalten des lexikographischen Lemke-Algorithmus durch einen Ausdruck beschr¨ankt ist, der polynomial in n ist. Wir verweisen diesbez¨ uglich auf die Arbeit [116] von M. J. Todd. F¨ ur n ≥ 2 betrachten wir LCP (q(n), M (n)) mit ⎞ ⎛ 1 2 ... ⎟ ⎜ 0 1 . . ⎟ ⎟ ∈ Rn×n M = M (n) = ⎜ ⎟ ⎜.

N ⎜ ⎜ ⎟ ⎜− j ⎟ . 2 ⎟ ∈ Rn . q = q(n) = ⎜ ⎟=⎜ ⎜ −2n − 2n−1 − 2n−2 ⎟ ⎜ j=i ⎟ ⎟ ⎜ ⎟ ⎜ ⎟ .. ⎝ −2n − 2n−1 ⎠ ⎜ ⎟ . 25) j=n Jeder Hauptminor von M hat den Wert 1. Somit ist M eine P-Matrix und LCP (q, M ) hat genau eine L¨ osung. Wir werden zeigen, dass der lexikographische Lemke-Algorithmus f¨ ur dieses Beispiel genau 2n Pivotschritte durchf¨ uhrt bis er die L¨ osung findet. Dazu werden wir zun¨ achst im folgenden Satz eine Halbgerade betrachten, die das Innere aller 2n durch M definierten komplement¨aren Kegel durchquert.

Download PDF sample

Rated 4.11 of 5 – based on 33 votes