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

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

(1):${\displaystyle \ \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

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

${\displaystyle \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 ${\displaystyle 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):${\displaystyle \ D(\mathbf {x} )=\sum _{i=1}^{n}m_{i}|\mathbf {x} _{i}-\mathbf {x} |}$

auffassen. Die Funktion ${\displaystyle D}$ wiederum beschreibt die Summe der mit ${\displaystyle m_{1},\dots ,m_{n}}$ gewichteten Abstände ${\displaystyle |\mathbf {x} _{1}-\mathbf {x} |,\dots ,|\mathbf {x} _{n}-\mathbf {x} |}$ der Punkte ${\displaystyle \mathbf {x} _{1},\dots ,\mathbf {x} _{n}}$ von dem Punkt ${\displaystyle \mathbf {x} }$. Da der Gradient der Funktion ${\displaystyle D}$ im Punkt ${\displaystyle \mathbf {v} }$ gleich Null ist, besitzt ${\displaystyle D}$ in ${\displaystyle \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

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

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

Die Koordinaten des optimalen Punktes (rot) sind ${\displaystyle (32{,}5;30{,}1)}$ und die optimale gewichtete Längensumme ist ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle \;D(\mathbf {x} )-c=0,\;c>L_{\text{op}}\;}$ (siehe Formel (2)).

Die Fälle n=1 und n=2

• Im Fall ${\displaystyle n=1}$ ist ${\displaystyle \mathbf {v} =\mathbf {x} _{1}}$.
• Im Fall ${\displaystyle n=2}$ und ${\displaystyle m_{2}>m_{1}}$ ist ${\displaystyle \mathbf {v} =\mathbf {x} _{2}}$.
• Im Fall ${\displaystyle n=2}$ und ${\displaystyle m_{2}=m_{1}}$ kann ${\displaystyle \mathbf {v} }$ jeder Punkt der Strecke ${\displaystyle {\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 ${\displaystyle \mathbf {x} _{1},\mathbf {x} _{2}}$ als gemeinsamen Brennpunkten.

Berechnung mit dem Newton-Verfahren (Extremalproblem)

Bezeichnungen: ${\displaystyle \ 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 ${\displaystyle D_{i}}$. Die Koeffizienten der für die Newton-Iteration benötigten Jacobi-Matrix ${\displaystyle J(\mathbf {x} )}$ sind dann:

${\displaystyle 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 ${\displaystyle \mathbf {v} _{0}}$ und löst für jeden Schritt das lineare Gleichungssystem (z. B. mit der Cramerschen Regel)

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

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

Berechnung mit dem Steiner-Weber-Ansatz (Fixpunktproblem)

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

${\displaystyle \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 ${\displaystyle \mathbf {x} _{i}}$ verwendet:

${\displaystyle \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)${\displaystyle \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

${\displaystyle \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 ${\displaystyle \mathbf {v} _{k}}$ in der Nähe eines der gegebenen Punkte ${\displaystyle \mathbf {x} _{1},...\mathbf {x} _{n}}$ liegt.

Siehe auch

• Fermat-Punkt (Fall ${\displaystyle n=3,m_{1}=m_{2}=m_{3}=1}$)
• Webersches Standortmodell
• Weber-Problem (engl.)

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

Einzelnachweise

1. ↑ S. Mamerow: Entscheiden und Wirtschaften: Eine Analyse des wirtschaftlichen Alltags unter anthropologischem Blickwinkel, Diplomica Verlag, 2012, ISBN 978-3-8428-8117-4, Seite 47
2. ↑ Horst W. Hamacher: Mathematische Lösungsverfahren für planare Standortprobleme, Vieweg+Teubner-Verlag, 2019, ISBN 978-3-663-01968-8, S. 31
3. ↑ Karl-Werner Hansmann :Industrielles Management, De Gruyter Verlag, 2014, ISBN 978-3-486-84082-7, 3486840827, S. 115