User:Ag2gaeh/sandbox

Varignon frame

The Varignon frame, named after Pierre Varignon, is a mechanical device which can be used to determine an optimal location of a warehouse for the destribution of goods to a set of shops. Optimal means that the sum the weighted distances of the shops to the warehouse should be minimal. The frame consists of a board with n holes corresponding to the n shops at the locations $\mathbf {x} _{1},...\mathbf {x} _{n}$, n strings are tied together in a knot at one end, the loose ends are passed, one each, through the holes and are attached to weights below the board (see diagram). If the influence of friction and other odds of the real world are neglected, the knot will take a position of equilibrium $\mathbf {v}$. It can be shown (see below), that point $\mathbf {v}$ is the optimal location which minimizes the weighted sum of distances

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

The optimization problem is called Weber problem.

Mechanical Problem - Optimization Problem

At point $\mathbf {v}$ the sum of all forces is 0

If the holes have locations $\mathbf {x} _{1},\dots ,\mathbf {x} _{n}$ and the masses of the weights are $m_{1},...,m_{n}$ then the force acting at the i-th string has the magnitude $m_{i}\cdot g$ ($g=9.81{\text{m/sec}}$: constant of gravity) and direction ${\tfrac {\mathbf {x} _{i}-\mathbf {v} }{|\mathbf {x} _{i}-\mathbf {v} |}}$ (unitvector). Summing up all forces and cancelling the common term $g$ one gets the equation

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

(At the point of equilibrium the sum of all forces is zero !)

This is a non-linear system for the coordinates of point $\mathbf {v}$ which can be solved iteratively by the Weiszfeld-algorithm (see below)

The connection between equation (1) and equation (2) is:

(3): $\ \mathbf {F} (\mathbf {x} )=\nabla D(\mathbf {x} )={\begin{bmatrix}{\frac {\partial D}{\partial x}}\\{\frac {\partial D}{\partial y}}\end{bmatrix}}.$

Hence Function $D$ has at point $\mathbf {v}$ a local extremum and the Varignon frame provides the optimal location experimentally.

Varignon frame: example

Level curves

Example

For the following example the points are

$\mathbf {x} _{1}=(0,0),\ \mathbf {x} _{2}=(40,0),\ \mathbf {x} _{3}=(50,40),$

$\mathbf {x} _{4}=(10,50),\ \mathbf {x} _{5}=(-10,30)$

and the weights

$m_{1}=10,\;m_{2}=10,\;m_{3}=20,\;m_{4}=10,\;m_{5}=5$.

The coordinates of the optimal solution (red) are $(32.5,30.1)$ and the optimal weighted sum of lenghts is $L_{\text{op}}=1679$. The second picture shows level curves which consist of points of equal but not optimal sums. Level curves can be used for assigning areas, where the wheighted sums do not exceed a fixed level. Geometrically they are implicit curves with equations

$\;D(\mathbf {x} )-c=0,\;c>L_{\text{op}}\;$ (see equation (1)).

Case $n=2,m_{1}=m_{2}=1$, the level curves are confocal ellipses

Special cases n=1 und n=2

• In case of $n=1$ one gets $\mathbf {v} =\mathbf {x} _{1}$.
• In case of $n=2$ and $m_{2}>m_{1}$ one gets $\mathbf {v} =\mathbf {x} _{2}$.
• In case of $n=2$ and $m_{2}=m_{1}$ point $\mathbf {v}$ can be any point of the line section ${\overline {X_{1}X_{2}}}$ (see diagram). In this case the level curves (points with the same not-optimal sum) are confocal ellipses with the points $\mathbf {x} _{1},\mathbf {x} _{2}$ as common foci.

Weiszfeld-algorithm and a fixpoint problem

Iteration as fixpoint determination for the example: starting point $\mathbf {v} _{0}=(25,15)$ (green), starting point $\mathbf {v} _{m}$ (blue) is the center of mass

Replacing in formula (2) vector $\mathbf {v}$ in the nominator by $\mathbf {v} _{k+1}$ and in the denominator by $\mathbf {v} _{k}$ and solving the equation for $\mathbf {v} _{k+1}$ one gets :

(4):$\quad \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}|}}$

which describes an iteration. As starting point is chosen the center of mass with mass $m_{i}$ in point $\mathbf {x} _{i}$:

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

This algorithm is called Weiszfeld-algorithm.

Formula (4) can be seen as the iteration formula for determining the fixed point of function

(5)$\quad \mathbf {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} |}}$

with fixpoint equation

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

(see fixed point)

Remark on numerical problems:
The iteration algorithm described here may have numerical problems if point $\mathbf {v} _{k}$ is near of one of the points $\mathbf {x} _{1},...\mathbf {x} _{n}$.

See also

• Fermat point (case $n=3,m_{1}=m_{2}=m_{3}=1$)

External links

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

References

• Uwe Götze: Risikomanagement, Physica-Verlag HD, 2013, ISBN 978-3-642-57587-7, S. 268
• Andrew Wood, Susan Roberts : Economic Geography, Taylor & Francis, 2012, ISBN: 9781136899478, 1136899472, p. 22
• H. A. Eiselt, Carl-Louis Sandblom :Operations Research, Springer Berlin Heidelberg, 2010, ISBN: 9783642103261, 364210326X, p. 239
• Robert E. Kuenne: General Equilibrium Economics, Palgrave Macmillan UK, 1992, ISBN: 9781349127528, 1349127523, p.226