Рамка Вариньона

Рама Вариньона , названная в честь Пьера Вариньона , представляет собой механическое устройство, которое можно использовать для определения оптимального местоположения склада для распределения товаров по множеству магазинов. Оптимальность означает, что сумма взвешенных расстояний магазинов до склада должна быть минимальной. Каркас состоит из доски с n отверстиями, соответствующими n магазинам на локациях. $\mathbf {x} _{1},...\mathbf {x} _{n}$ , n веревок связываются узлом на одном конце, свободные концы пропускаются по одному через отверстия и прикрепляются к гирям под доской (см. схему). Если пренебречь влиянием трения и другими шансами реального мира, узел примет положение равновесия. $\mathbf {v}$ . Можно показать (см. ниже), что точка $\mathbf {v}$ — оптимальное местоположение, которое минимизирует взвешенную сумму расстояний

(1):

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

.

Задача оптимизации называется проблемой Вебера . ^[1]

Механическая проблема – проблема оптимизации

В точку $\mathbf {v}$ сумма всех сил равна 0

Если отверстия имеют расположение $\mathbf {x} _{1},\dots ,\mathbf {x} _{n}$ а массы гирь $m_{1},...,m_{n}$ тогда сила, действующая на i-ю струну, имеет величину $m_{i}\cdot g$ ( $g=9.81{\text{m/sec}}$ : постоянная силы тяжести) и направление ${\tfrac {\mathbf {x} _{i}-\mathbf {v} }{\|\mathbf {x} _{i}-\mathbf {v} \|}}$ (юнитвектор). Суммирование всех сил и отмена общего термина $g$ получается уравнение

(2):

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

.

(В точке равновесия сумма всех сил равна нулю!)

Это нелинейная система координат точки $\mathbf {v}$ которое можно решить итеративно с помощью алгоритма Вейцфельда (см. ниже) ^[2]

Связь между уравнением (1) и уравнением (2) такова:

(3):

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

Следовательно, функция $D$ имеет в точку $\mathbf {v}$ локальный экстремум, а система Вариньона экспериментально обеспечивает оптимальное положение.

Пример

Для следующего примера точки

\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)

и веса

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

.

Координаты оптимального решения (красные): $(32.5,30.1)$ а оптимальная взвешенная сумма длин равна $L_{\text{op}}=1679$ . На втором рисунке показаны кривые уровня , состоящие из точек равных, но не оптимальных сумм. Кривые уровня можно использовать для выделения областей, где взвешенные суммы не превышают фиксированного уровня. Геометрически это неявные кривые с уравнениями

\;D(\mathbf {x} )-c=0,\;c>L_{\text{op}}\;

(см. уравнение (1) ).

Случай $n=2,m_{1}=m_{2}=1$ , кривые уровня представляют собой софокальные эллипсы

Особые случаи n=1 и n=2

В случае $n=1$ каждый получает $\mathbf {v} =\mathbf {x} _{1}$ .
В случае $n=2$ и $m_{2}>m_{1}$ каждый получает $\mathbf {v} =\mathbf {x} _{2}$ .
В случае $n=2$ и $m_{2}=m_{1}$ точка $\mathbf {v}$ может быть любая точка участка линии ${\overline {X_{1}X_{2}}}$ (см. схему). В этом случае кривые уровня (точки с одинаковой неоптимальной суммой) представляют собой софокусные эллипсы с точками $\mathbf {x} _{1},\mathbf {x} _{2}$ как общие очаги.

Алгоритм Вейцфельда и проблема с фиксированной точкой

Итерация как определение фиксированной точки для примера: начальная точка $\mathbf {v} _{0}=(25,15)$ (зеленый), отправная точка $\mathbf {v} _{m}$ (синий) — центр масс

Заменив в формуле (2) вектор $\mathbf {v}$ в номинаторе $\mathbf {v} _{k+1}$ и в знаменателе $\mathbf {v} _{k}$ и решая уравнение для $\mathbf {v} _{k+1}$ человек получает: ^[3]

(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}\|}}

который описывает итерацию. Подходящей отправной точкой является центр масс с массой $m_{i}$ в точку $\mathbf {x} _{i}$ :

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

.

Этот алгоритм называется алгоритмом Вейцфельда . ^[4]

Формулу (4) можно рассматривать как итерационную формулу определения неподвижной точки функции

(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} \|}}

с уравнением фиксированной точки

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

(см. фиксированную точку )

Замечание по численным задачам:
Описанный здесь итерационный алгоритм может иметь численные проблемы, если точка $\mathbf {v} _{k}$ находится близко к одной из точек $\mathbf {x} _{1},...\mathbf {x} _{n}$ .

См. также

Точка Ферма (случай $n=3,m_{1}=m_{2}=m_{3}=1$ )
Теорема Вариньона
геометрическая медиана

Внешние ссылки

Ссылки

^ З. Дрезнер, HW Hamacher: Местоположение объекта , Springer, 2004, ISBN 3-540-21345-7 , с. 7
^ Хорст В. Хамахер: Математические методы решения задач плоского местоположения , Vieweg + Teubner-Verlag, 2019, ISBN 978-3-663-01968-8 , с. 31
^ Карл-Вернер Хансманн: Промышленный менеджмент , De Gruyter Verlag, 2014, ISBN 9783486840827 , С. 115
^ см . Расположение объекта, с. 9

Уве Гётце: Управление рисками , Physica-Verlag HD, 2013, ISBN 978-3-642-57587-7 , стр. 268.
Эндрю Вуд, Сьюзан Робертс: экономическая география , Тейлор и Фрэнсис, 2012, ISBN 9781136899478 , с. 22
Х.А. Эйзелт, Карл-Луи Сандблом: Исследование операций , Springer Berlin Heidelberg, 2010 г., ISBN 9783642103261 , с. 239
Роберт Э. Куэнн: Экономика общего равновесия , Palgrave Macmillan UK, 1992, ISBN 9781349127528 , с. 226

[1] З. Дрезнер, HW Hamacher: Местоположение объекта , Springer, 2004, ISBN 3-540-21345-7 , с. 7

[2] Хорст В. Хамахер: Математические методы решения задач плоского местоположения , Vieweg + Teubner-Verlag, 2019, ISBN 978-3-663-01968-8 , с. 31

[3] Карл-Вернер Хансманн: Промышленный менеджмент , De Gruyter Verlag, 2014, ISBN 9783486840827 , С. 115

[4] см . Расположение объекта, с. 9

[1]

[2]

[3]

[4]