Marco Varignon

El marco de Varignon , que recibe su nombre de Pierre Varignon , es un dispositivo mecánico que se puede utilizar para determinar la ubicación óptima de un almacén para la distribución de mercancías a un conjunto de tiendas. Óptima significa que la suma de las distancias ponderadas de las tiendas al almacén debe ser mínima. El marco consta de un tablero con n agujeros que corresponden a las n tiendas en las ubicaciones${\displaystyle \mathbf {x} _{1},...\mathbf {x} _{n}}$Se atan n cuerdas con un nudo en un extremo; los extremos sueltos se pasan, uno a cada lado, por los agujeros y se sujetan a pesas situadas debajo del tablero (véase el diagrama). Si se ignora la influencia de la fricción y otras probabilidades del mundo real, las cuerdas son lo suficientemente largas como para evitar que las pesas se atasquen en sus agujeros, y ninguna pesa es tan pesada como para tirar del nudo a través del agujero y debajo de la mesa; en ese caso, el nudo alcanzará una posición de equilibrio.${\displaystyle \mathbf {v} }$Se puede demostrar (ver más abajo) que el punto${\displaystyle \mathbf {v} }$es la ubicación óptima que minimiza la suma ponderada de las distancias

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

El problema de optimización se llama problema de Weber . ^{[ 1 ]}

Si los agujeros tienen ubicaciones${\displaystyle \mathbf {x} _{1},\dots ,\mathbf {x} _{n}}$y las masas de los pesos son${\displaystyle m_{1},...,m_{n}}$entonces la fuerza que actúa en la i-ésima cuerda tiene la magnitud${\displaystyle m_{i}\cdot g}$(${\displaystyle g=9.81{\text{m/seg}}}$: constante de gravedad) y dirección${\displaystyle {\tfrac {\mathbf {x} _{i}-\mathbf {v} }{\|\mathbf {x} _{i}-\mathbf {v} \|}}}$(vector unitario). Sumando todas las fuerzas y cancelando el término común.${\displaystyle g}$uno obtiene la ecuación

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

(¡En el punto de equilibrio , la suma de todas las fuerzas es cero  !)

Este es un sistema no lineal para las coordenadas del punto${\displaystyle \mathbf {v} }$que se puede resolver iterativamente mediante el algoritmo de Weiszfeld (véase más abajo) ^{[ 2 ]}

La relación entre la ecuación (1) y la ecuación (2) es:

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

Por lo tanto, función${\displaystyle D}$tiene en el punto${\displaystyle \mathbf {v} }$Un extremo local y el marco de Varignon proporcionan la ubicación óptima experimentalmente.

Para el siguiente ejemplo, los puntos son

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

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

y los pesos

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

Las coordenadas de la solución óptima (en rojo) son${\displaystyle (32.5,30.1)}$y la suma ponderada óptima de longitudes es${\displaystyle L_{\text{op}}=1679}$La segunda imagen muestra curvas de nivel que consisten en puntos de sumas iguales pero no óptimas. Las curvas de nivel se pueden utilizar para asignar áreas, donde las sumas ponderadas no superan un nivel fijo. Geométricamente son curvas implícitas con ecuaciones.

${\displaystyle \;D(\mathbf {x} )-c=0,\;c>L_{\text{op}}\;}$(véase la ecuación (1) ).

• En caso de${\displaystyle n=1}$uno consigue${\displaystyle \mathbf {v} =\mathbf {x} _{1}}$.
• En caso de${\displaystyle n=2}$y${\displaystyle m_{2}>m_{1}}$uno consigue${\displaystyle \mathbf {v} =\mathbf {x} _{2}}$.
• En caso de${\displaystyle n=2}$y${\displaystyle m_{2}=m_{1}}$punto${\displaystyle \mathbf {v} }$puede ser cualquier punto de la sección de la línea${\displaystyle {\overline {X_{1}X_{2}}}}$(ver diagrama). En este caso, las curvas de nivel (puntos con la misma suma no óptima ) son elipses confocales con los puntos${\displaystyle \mathbf {x} _{1},\mathbf {x} _{2}}$como focos comunes.

Sustituyendo en la fórmula (2) vector${\displaystyle \mathbf {v} }$en el nominador por${\displaystyle \mathbf {v} _{k+1}}$y en el denominador por${\displaystyle \mathbf {v} _{k}}$y resolviendo la ecuación para${\displaystyle \mathbf {v} _{k+1}}$uno obtiene: ^{[ 3 ]}

(4):${\displaystyle \quad \mathbf {v} _{k+1}=\sum _{i=1}^{n}{\frac {m_{i}\mathbf {x} _{i}}{\|\mathbf {x} _{i}-\mathbf {v} _{k}\|}}\,{\Bigg /}\sum _{i=1}^{n}{\frac {m_{i}}{\|\mathbf {x} _{i}-\mathbf {v} _{k}\|}}}$

que describe una iteración. Un punto de partida adecuado es el centro de masa con masa${\displaystyle m_{i}}$en el punto${\displaystyle \mathbf {x} _ {i}}$:

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

Este algoritmo se llama algoritmo de Weiszfeld . ^{[ 4 ]}

La fórmula (4) puede verse como la fórmula de iteración para determinar el punto fijo de la función.

(5)${\displaystyle \quad \mathbf {G} (\mathbf {x} )=\sum _{i=1}^{n}{\frac {m_{i}\mathbf {x} _{i}}{\|\mathbf {x} _{i}-\mathbf {x} \|}}\,{\Bigg /}\sum _{i=1}^{n}{\frac {m_{i}}{\|\mathbf {x} _{i}-\mathbf {x} \|}}}$

con ecuación de punto fijo

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

(ver punto fijo )

Nota sobre problemas numéricos: El algoritmo de iteración descrito aquí puede tener problemas numéricos si el punto ${\displaystyle \mathbf {v} _{k}}$está cerca de uno de los puntos${\displaystyle \mathbf {x} _{1},...\mathbf {x} _{n}}$.

• Punto de Fermat (caso ${\displaystyle n=3,m_{1}=m_{2}=m_{3}=1}$)
• Teorema de Varignon
• mediana geométrica

• MathePrisma Uni Wuppertal: solución de problemas de clasificación con GeoGebra
• El marco de Varignon: Tratamiento matemático

• Uwe Götze: Gestión del riesgo , Physica-Verlag HD, 2013, ISBN 978-3-642-57587-7, pág. 268
• Andrew Wood, Susan Roberts  : Geografía económica , Taylor & Francis, 2012, ISBN 9781136899478pág.  22
• HA Eiselt, Carl-Louis Sandblom  : Investigación de operaciones , Springer Berlin Heidelberg, 2010, ISBN 9783642103261pág.  239
• Robert E. Kuenne: Economía del equilibrio general , Palgrave Macmillan UK, 1992, ISBN 9781349127528pág.  226