The Varignon frame, named after
Pierre Varignon
Pierre Varignon (1654 – 23 December 1722) was a French mathematician. He was educated at the Jesuit College and the University of Caen, where he received his M.A. in 1682. He took Holy Orders the following year.
Varignon gained his first ex ...
, 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 of 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
, 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
. It can be shown (see below), that point
is the optimal location which minimizes the weighted sum of distances
:(1):
.
The optimization problem is called
Weber problem
In geometry, the Weber problem, named after Alfred Weber, is one of the most famous problems in location theory. It requires finding a point in the plane that minimizes the sum of the transportation costs from this point to ''n'' destination point ...
.
Mechanical Problem - Optimization Problem
If the holes have locations
and the masses of the weights are
then the force acting at the i-th string has the magnitude
(
: constant of gravity) and direction
(unitvector). Summing up all forces and cancelling the common term
one gets the equation
:(2):
.
(At the point of ''equilibrium'' the sum of all forces is zero !)
This is a
non-linear system
In mathematics and science, a nonlinear system is a system in which the change of the output is not proportional to the change of the input. Nonlinear problems are of interest to engineers, biologists, physicists, mathematicians, and many other ...
for the coordinates of point
which can be solved iteratively by the ''Weiszfeld-algorithm'' (see below)
The connection between equation (1) and equation (2) is:
:(3):
Hence Function
has at point
a local extremum and the Varignon frame provides the optimal location experimentally.
Example
For the following example the points are
:
:
and the weights
:
.
The coordinates of the optimal solution (red) are
and the optimal weighted sum of lengths is
. 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 weighted sums do not exceed a fixed level. Geometrically they are
implicit curve
In mathematics, an implicit curve is a plane curve defined by an implicit equation relating two coordinate variables, commonly ''x'' and ''y''. For example, the unit circle is defined by the implicit equation x^2+y^2=1. In general, every implic ...
s with equations
:
(see equation (1)).
Special cases n=1 und n=2
* In case of
one gets
.
* In case of
and
one gets
.
* In case of
and
point
can be any point of the line section
(see diagram). In this case the level curves (points with the same ''not-optimal'' sum) are
confocal ellipses with the points
as common foci.
Weiszfeld-algorithm and a fixpoint problem
Replacing in formula (2) vector
in the nominator by
and in the denominator by
and solving the equation for
one gets:
:(4):
which describes an iteration. A suitable starting point is the center of mass with mass
in point
:
:
.
This algorithm is called
Weiszfeld-algorithm.
[see ''Facility location, p. 9]
Formula (4) can be seen as the iteration formula for determining the fixed point of function
:(5)
with fixpoint equation
:
(see
fixed point)
Remark on numerical problems:
The iteration algorithm described here may have numerical problems if point
is close to one of the points
.
See also
*
Fermat point
In Euclidean geometry, the Fermat point of a triangle, also called the Torricelli point or Fermat–Torricelli point, is a point such that the sum of the three distances from each of the three vertices of the triangle to the point is the smallest ...
(case
)
*
Varignon's theorem
Varignon's theorem is a statement in Euclidean geometry, that deals with the construction of a particular parallelogram, the Varignon parallelogram, from an arbitrary quadrilateral (quadrangle). It is named after Pierre Varignon, whose proof was ...
*
geometric median
In geometry, the geometric median of a discrete set of sample points in a Euclidean space is the point minimizing the sum of distances to the sample points. This generalizes the median, which has the property of minimizing the sum of distances ...
External links
MathePrisma Uni Wuppertal: Lösung eines Standort-Problems mit GeoGebraThe Frame of Varignon: Mathematical Treatment
References
* Uwe Götze: ''Risikomanagement'', Physica-Verlag HD, 2013, , S. 268
* Andrew Wood, Susan Roberts : ''Economic Geography'', Taylor & Francis, 2012, , p. 22
* H. A. Eiselt, Carl-Louis Sandblom :''Operations Research'', Springer Berlin Heidelberg, 2010, , p. 239
* Robert E. Kuenne: ''General Equilibrium Economics'', Palgrave Macmillan UK, 1992, {{ISBN, 9781349127528, p. 226
Cartography