Varignon’scher Apparat

Varignon'scher Apparat

Der Varignon'sche Apparat, benannt nach dem französischen Mathematiker und Physiker Pierre de Varignon, ist eine einfache Anordnung, um ein Standort-Optimierungsproblem experimentell zu lösen: Auf einer Tischplatte werden mehrere Standorte maßstabsgetreu eingezeichnet. An diesen Standorten werden Löcher gebohrt, durch welche Fäden gezogen werden. Die Enden aller Fäden werden auf der Tischoberseite zusammengeknotet. Unterhalb der Tischplatte werden der Beteiligten entsprechende Gewichte an die Fäden gehängt. Als Gewicht nimmt man beispielsweise eine Personenanzahl oder Einwohneranzahl, um die Gewichtung des Standorts auszudrücken. Die Kräfte, die nun wirken, ziehen den Knotenpunkt auf der Oberfläche der Platte zum optimalen Standort.

Mechanisches Problem

Im Punkt $\mathbf {v}$ ist die Summe aller Kräfte =0

Sind die Löcher in der ebenen Platte an den Stellen $\mathbf {x} _{1}=(x_{1},y_{1}),\dots ,\mathbf {x} _{n}=(x_{n},y_{n})$ angebracht und hängen an den Fäden die Massen $m_{1},\dots ,m_{n}$ , so muss der Gleichgewichtspunkt $\mathbf {v} =(x,y)$ die Gleichgewichtsbedingung (Summe aller Kräfte im Punkt $\mathbf {v}$ ist Null) erfüllen. Der Betrag der im i-ten Faden angreifenden Kraft $\mathbf {f} _{i}$ ist $m_{i}g$ ($g$ ist die Erdbeschleunigung) und hat die Richtung ${\tfrac {\mathbf {x} _{i}-\mathbf {v} }{|\mathbf {x} _{i}-\mathbf {v} |}}$ (Einheitsvektor). Summiert man diese Kräfte auf und kürzt den gemeinsamen Faktor $g$ heraus, erhält man die Gleichung

(1):$\ \mathbf {F} (\mathbf {v} )=\sum _{i=1}^{n}m_{i}{\frac {\mathbf {x} _{i}-\mathbf {v} }{|\mathbf {x} _{i}-\mathbf {v} |}}=\mathbf {0}$.

In Komponenten bedeutet diese Vektorgleichung

$\sum _{i=1}^{n}m_{i}{\frac {x_{i}-x}{|\mathbf {x} _{i}-\mathbf {v} |}}=0$

$\sum _{i=1}^{n}m_{i}{\frac {y_{i}-y}{|\mathbf {x} _{i}-\mathbf {v} |}}=0$.

Dies ist ein nichtlineares Gleichungssystem für die Unbekannten $x,y$ und kann mit dem 2-dimensionalen Newton-Verfahren oder dem Weiszfeldverfahren gelöst werden.

Standort-Problem

Die linke Seite der Gleichung (1) lässt sich auch als Gradient der Funktion

(2):$\ D(\mathbf {x} )=\sum _{i=1}^{n}m_{i}|\mathbf {x} _{i}-\mathbf {x} |$

Varignon-Apparat: Beispiel

Beispiel mit Niveau-Kurven

auffassen. Die Funktion $D$ wiederum beschreibt die Summe der mit $m_{1},\dots ,m_{n}$ gewichteten Abstände $|\mathbf {x} _{1}-\mathbf {x} |,\dots ,|\mathbf {x} _{n}-\mathbf {x} |$ der Punkte $\mathbf {x} _{1},\dots ,\mathbf {x} _{n}$ von dem Punkt $\mathbf {x}$. Da der Gradient der Funktion $D$ im Punkt $\mathbf {v}$ gleich Null ist, besitzt $D$ in $\mathbf {v}$ ein relatives Extremum. Das heißt, der Varignon'sche Apparat liefert eine einfache Möglichkeit, das Standort-Problem (Optimierung) experimentell zu lösen und Newton- und Weiszfeld-Verfahren liefern rechnerische Lösungen.

Beispiel

Für das Beispiel (siehe Bilder) sind die Punkte

$X_{1}=(0,0),X_{2}=(40,0),X_{3}=(50,40),$

$X_{4}=(10,50),X_{5}=(-10,30)$ und die Gewichte :$m_{1}=10,m_{2}=10,m_{3}=20,m_{4}=10,m_{5}=5$.

Die Koordinaten des optimalen Punktes (rot) sind $(32{,}5;30{,}1)$ und die optimale gewichtete Längensumme ist $L_{\text{op}}=1679$. Das zweite Bild zu diesem Beispiel zeigt Niveau-Kurven nicht-optimaler Punkte mit derselben gewichteten Längensumme (gLS). Von innen nach außen sind die (größeren) gLS $1680,1710,1760,1820,1900$.
Niveau-Kurven kann man dazu benutzen, um Bereiche zu beschreiben, in denen die Kosten die dem Niveau zugehörigen Kosten nicht überschreiten. Geometrisch sind sie implizite Kurven mit Gleichungen $\;D(\mathbf {x} )-c=0,\;c>L_{\text{op}}\;$ (siehe Formel (2)).

Fall $n=2,m_{1}=m_{2}=1$, die Niveau-Kurven sind konfokale Ellipsen

Die Fälle n=1 und n=2

• Im Fall $n=1$ ist $\mathbf {v} =\mathbf {x} _{1}$.
• Im Fall $n=2$ und $m_{2}>m_{1}$ ist $\mathbf {v} =\mathbf {x} _{2}$.
• Im Fall $n=2$ und $m_{2}=m_{1}$ kann $\mathbf {v}$ jeder Punkt der Strecke ${\overline {X_{1}X_{2}}}$ sein (siehe Bild). In diesem Fall sind die Niveau-Kurven (Punkte mit derselben nicht-optimalen Längensumme) konfokale Ellipsen mit den Punkten $\mathbf {x} _{1},\mathbf {x} _{2}$ als gemeinsamen Brennpunkten.

Berechnung mit dem Newton-Verfahren (Extremalproblem)

Bezeichnungen: $\ D_{i}=|\mathbf {x} _{i}-\mathbf {x} |\ ,\ D(\mathbf {x} )=\sum _{i=1}^{n}m_{i}D_{i}$

Für die Jacobi-Matrix des Newton-Verfahrens berechnet man die zweiten partiellen Ableitungen der Funktionen $D_{i}$. Die Koeffizienten der für die Newton-Iteration benötigten Jacobi-Matrix $J(\mathbf {x} )$ sind dann:

$J_{xx}=\sum _{i=1}^{n}m_{i}D_{ixx},\quad J_{xy}=\sum _{i=1}^{n}m_{i}D_{ixy},\quad J_{xx}=\sum _{i=1}^{n}m_{i}D_{ixx}$

Iteration: Man wählt einen Startpunkt $\mathbf {v} _{0}$ und löst für jeden Schritt das lineare Gleichungssystem (z. B. mit der Cramerschen Regel)

$J(\mathbf {v} _{k})\;\Delta \mathbf {v} _{k}=-\mathbf {F} (\mathbf {v} _{k})$ .

Danach erhält man $\ \mathbf {v} _{k+1}=\mathbf {v} _{k}+\Delta \mathbf {v} _{k}.$

Berechnung mit dem Steiner-Weber-Ansatz (Fixpunktproblem)

Iteration mit dem Fixpunkt-Verfahren für das Beispiel: Startpunkt $\mathbf {v} _{0}=(25,15)$ (grün), Startpunkt $\mathbf {v} _{m}$ (blau) ist der Massenmittelpunkt (Masse $m_{i}$ im Punkt $\mathbf {x} _{i}$)

Der folgende auf Jakob Steiner zurückgehende Algorithmus basiert auf der Idee, in Gleichung (1) im Zähler die Näherung $\mathbf {v} _{k+1}$ und im Nenner die Näherung $\mathbf {v} _{k}$ einzusetzen und diese Gleichung dann nach $\mathbf {v} _{k+1}$ aufzulösen:

$\mathbf {v} _{k+1}=\sum _{i=1}^{n}{\frac {m_{i}\mathbf {x} _{i}}{|\mathbf {x} _{i}-\mathbf {v} _{k}|}}{\big /}\sum _{i=1}^{n}{\frac {m_{i}}{|\mathbf {x} _{i}-\mathbf {v} _{k}|}}$

Als Startpunkt wird der Massenmittelpunkt der Anordnung mit den Massen in den Punkten $\mathbf {x} _{i}$ verwendet:

$\mathbf {v} _{0}={\frac {\sum _{i=1}^{n}m_{i}\mathbf {x} _{i}}{\sum _{i=1}^{n}m_{i}}}$.

Der Weiszfeld-Algorithmus benutzt diese Iterationformel.

Die Iterationsformel kann als Iteration zur Bestimmung des Fixpunktes der Funktion

(3)$\quad G(\mathbf {x} )=\sum _{i=1}^{n}{\frac {m_{i}\mathbf {x} _{i}}{|\mathbf {x} _{i}-\mathbf {x} |}}{\big /}\sum _{i=1}^{n}{\frac {m_{i}}{|\mathbf {x} _{i}-\mathbf {x} |}}$

mit der Fixpunktgleichung

$\quad \mathbf {x} =G(\mathbf {x} )$

angesehen werden (Siehe hierzu Fixpunktsatz von Banach.)

Bemerkung zu numerischen Problemen:
Beide Iterationsverfahren in der hier beschriebenen Form haben numerische Probleme, falls ein Iterationspunkt $\mathbf {v} _{k}$ in der Nähe eines der gegebenen Punkte $\mathbf {x} _{1},...\mathbf {x} _{n}$ liegt.

Siehe auch

• Fermat-Punkt (Fall $n=3,m_{1}=m_{2}=m_{3}=1$)
• Webersches Standortmodell

Weblinks

• MathePrisma Uni Wuppertal: Lösung eines Standort-Problems mit GeoGebra

Literatur

• Uwe Götze: Risikomanagement, Physica-Verlag HD, 2013, ISBN 978-3-642-57587-7, S. 268