Задача. Пусть заданы координаты $ K_{} $ точек пространства $ \mathbb R^{n}_{} $ : $ \{P_j=(x_{j1},\dots,x_{jn})\}_{j=1}^K $. Определить координаты точки $ P_{\ast}=(x_{\ast 1},\dots,x_{\ast n}) $, решающей задачу оптимизации: $$ \min_{P\in \mathbb R^n} F(P) \qquad npu \qquad F(P)= \sum_{j=1}^Km_j |PP_j| \ . $$ Здесь $ | \cdot | $ означает евклидово расстояние: $ |P_1P_2|=\sqrt{(x_{11}-x_{21})^2+\dots+(x_{1n}-x_{2n})^2} $, а величины $ \{ m_j \}_{j=1}^K $ обычно (и практически везде в настоящем разделе) считаются положительными и называются весами.

Будем говорить о наборе $$ \left\{ \begin{array}{l|c|l} P_1 & \dots & P_K \\ m_1 & \dots & m_K \end{array} \right\} $$ как о конфигурации весов.

Рассмотрим сначала плоский вариант задачи: пусть $ n=2_{} $, $ \{P_j=(x_{j},y_j)\}_{j=1}^K $, $$ F(x,y)= \sum_{j=1}^{K} m_j \sqrt{(x-x_j)^2+(y-y_j)^2} \ . $$

Пример. В городах $ P_{1},P_2,P_3 $ расположены источники полезных ископаемых: железной руды, угля и воды соответственно. Известно, что для производства одной тонны стали необходимо иметь $ m_{1} $ тонн руды, $ m_2 $ тонн угля и $ m_3 $ тонн воды. В предположении, что стоимость перевозки одной тонны груза не зависит от его природы, где следует расположить сталелитейное производство так, чтобы минимизировать транспортные издержки?

С конца XIX века подобные задачи стали предметом изучения в экономической географии. Систематические исследования были начаты Вильгельмом Лаунхардтом²⁾[6] и позднее развиты Альфредом Вебером³⁾[1] . Последний ввел понятие штандорта⁴⁾ — оптимального места размещения производства, «склада».

В XX веке эти задачи выделились в подраздел теории исследования операций, известный в настоящее время как facility location problem или location theory (location analysis).

Частный случай задачи при $ n=2 , K=3 $ и $ m_1=m_2=m_3=1 $ известен как (классическая) задача Ферма-Торричелли: для трех неколлинеарных точек плоскости $ P_1=(x_1,y_1), P_2= (x_2,y_2) $ и $ P_3= (x_3,y_3) $ требуется определить $$ \min_{(x,y)} F(x,y) \quad npu \quad F(x,y)= \sum_{j=1}^3 \sqrt{(x-x_j)^2+(y-y_j)^2} \ . $$

Datis tribus punctis, quartum reperire, a quo si ducantur tres rectæ ad data puncta, summa trium harum rectarum sit minima quantitas

(лат.) Для трех заданных точек найти четвертую, такую что если от нее провести прямые линии до данных точек, сумма расстояний будет наименьшей) P. de Fermat, «Œuvres de Fermat», 1679, Livre I, Paris.

Рассмотрим теперь различные подходы к решению общей задачи. Для определения координат стационарной точки $ P_{\ast}=(x_{\ast},y_{\ast}) $ составим градиентную систему уравнений: $$ \left\{ \begin{array}{lll} \displaystyle \frac{\partial F}{\partial x} &= \displaystyle \frac{m_1(x-x_1)}{\sqrt{(x-x_1)^{2}+(y-y_1)^2}}+\dots+ \frac{m_K(x-x_K)}{\sqrt{(x-x_K)^2+(y-y_K)^2}} & = 0 \\ \displaystyle \frac{\partial F}{\partial y} &= \displaystyle \frac{m_1(y-y_1)}{\sqrt{(x-x_1)^2+(y-y_1)^2}}+\dots+ \frac{m_K(y-y_K)}{\sqrt{(x-x_K)^2+(y-y_K)^2}} & = 0 \end{array} \right. $$ Система эта нелинейная и даже неалгебраическая относительно $ x_{} $ и $ y_{} $, поэтому уже проблема установления существования (и количества) ее вещественных решений решается специально разработанными под нее методами.

Если обозначить $$ \frac{x-x_j}{\sqrt{(x-x_j)^{2}+(y-y_j)^2}} = \cos \gamma_j, \ \frac{y-y_j}{\sqrt{(x-x_j)^{2}+(y-y_1)^2}} = \sin \gamma_j , $$ где $ \gamma_j $ означает угол, образованный вектором $ \overrightarrow{PP_{j}} $ с осью абсцисс, то уравнения градиентной системы можно переписать в виде: $$ \left\{ \begin{array}{ll} m_1\cos \gamma_1 + m_2 \cos \gamma_2 + \dots + m_K\cos \gamma_K &=0,\\ m_1\sin \gamma_1 + m_2 \sin \gamma_2 + \dots + m_K \sin \gamma_K &=0 . \end{array} \right. $$ Если под $ m_{j} $ понимать величину силы, приложенной в точке $ P_{} $, и направленной к $ P_{j} $, то приведенные уравнения означают, что суммы проекций этих сил на координатные оси равны нулю, т.е. в точке $ P_{\ast} $ силы должны уравновешиваться. Это обстоятельство используют для экспериментального определения точки $ P_{\ast} $. На плоской доске, располагаемой горизонтально к поверхности Земли, рисуют многоугольник, подобный многоугольнику $ P_1 P_2 \ldots P_K $ и просверливают в его вершинах отверстия, через которые опускают нити, связанные одним узлом. Если к свободным концам этих нитей подвесить грузы массами, пропорциональными $ m_{j} $, то при равновесии этой системы общий узел нитей будет находиться в искомой точке $ P_{\ast} $.

Интуитивно понятно также, что если вес $ m_{i} $, приложенный сквозь отверстие $ P_{i} $, окажется много большим оставшихся весов, то узел затянется именно в это отверстие. Оказывается при возрастании $ m_{i} $ такое затягивание произойдет раньше выполнения условия $ m_i = \displaystyle \sum_{j\ne i} m_j $. См. ☟ НИЖЕ.

Известно для случая $ K=3 $ точек на плоскости для произвольных значений весов $ \{ m_j \} $ и для случая $ K=4 $ точек в случае одинаковых весов.

Исторически самое первое из известных решений задачи было предложено Торричелли в период до 1640 г.⁵⁾. для случая $ K=3 $ точек и одинаковых весов $ m_1=m_2=m_3=1 $ (классическая задача Ферма-Торричелли). Алгоритм предлагал нахождение точки $ P_{\ast} $ в идеологии классической геометрии: circinus et regula⁶⁾. На сторонах треугольника $ P_1P_2P_{3} $, как на основаниях, строятся новые треугольники — равносторонние; эти треугольники должны располагаться с внешней стороны треугольника $ P_1P_2P_{3} $. Для каждого треугольника строится описывающая его окружность. Пересечение этих трех окружностей и дает точку $ P_{\ast} $. На рисунке показано нахождение точки $ P_{\ast} $ для случая $ P_1=(1,1),P_2=(3,5),P_3=(7,2) $. С той поры было придумано много вариантов построения точки $ P_{\ast} $. Так, к примеру, в этой же точке $ P_{\ast} $ пересекаются прямые $ T_1 P_2 $ и $ T_2 P_1 $, и, вдобавок, $$ |T_1P_2|=|T_2P_1|=|P_{\ast} P_1|+|P_{\ast} P_2|+|P_{\ast} P_3| = \min_{P\in \mathbb R^2} \sum_{j=1}^3 |PP_j| \ . $$

Это решение обобщается в [2,6] на случай различных весов. Рассмотрим систему уравнений из предыдущего пункта: $$ \left\{ \begin{array}{ll} m_1\cos \gamma_1 + m_2 \cos \gamma_2 + m_3\cos \gamma_3 &=0,\\ m_1\sin \gamma_1 + m_2 \sin \gamma_2 + m_3 \sin \gamma_3&=0 . \end{array} \right. $$ Из этих уравнений выразим $ \cos \gamma_1 $ и $ \sin \gamma_1 $ и подставим в равенство $$ 1=\cos^2 \gamma_1+ \sin^2 \gamma_1 = $$ $$ =\left(\frac{m_2}{m_1} \cos \gamma_2 + \frac{m_3}{m_1} \cos \gamma_3 \right)^2+\left(\frac{m_2}{m_1} \sin \gamma_2 + \frac{m_3}{m_1} \sin \gamma_3 \right)^2 = $$ $$ = \frac{m_2^2}{m_1^2}+ \frac{m_3^2}{m_1^2} + 2\, \frac{m_2m_3}{m_1^2} \cos (\gamma_2-\gamma_3) \ . $$ Обратим внимание, что естественным ограничением на условие задачи оказывается $ |\cos (\gamma_2 -\gamma_3)| \le 1 $, что равносильно $ m_1\le m_2+m_{3} $ (сумма двух весов должна быть не меньше третьего; на самом деле условие того, что искомая точка $ P_{\ast} $ будет отличаться от вершин $ P_1,P_2,P_3 $ более жесткое — см. ☟ НИЖЕ). Далее, из последнего равенства следует: $$ \Rightarrow \sin^2 (\gamma_2 -\gamma_3) =\frac{-m_1^4-m_2^4-m_3^4+2\, m_1^2m_2^2+2\, m_1^2m_3^2+2\,m_2^2m_3^2}{4\,m_2^2m_3^2} \ . $$ Аналогичные равенства справедливы и для синусов оставшихся пар углов. Отсюда получаем условие, которое должно выполняться в искомой точке $ P_{\ast} $: $$ \frac{|\sin (\gamma_2 -\gamma_3)|}{m_1} =\frac{|\sin (\gamma_1 -\gamma_3)|}{m_2} = \frac{|\sin (\gamma_1 -\gamma_2)|}{m_3} \ . $$ Геометрический смысл разности $ \gamma_1 -\gamma_2 $ понятен из рисунка: это величина угла $ \widehat{P_1 P_{\ast}P_2} $. Можно образно сказать, что точки $ P_{1} $ и $ P_{2} $ «видно» из точки $ P_{\ast} $ под углом $ \gamma_2 -\gamma_1 $.

В случае $ m_1=m_2=m_3=1 $ последнее равенство характеризует точку треугольника, которая известна под названием точки Ферма-Торричелли: это такая точка, из которой все его вершины «видны» под углом $ 2\, \pi/3 $. Точка Ферма-Торричелли не всегда существует — она имеется только у треугольников, углы которых не превосходят той же величины $ 2\, \pi/3 $.

Теорема [3,4]. Точка Ферма-Торричелли существует только для треугольника $ P_{1}P_2P_3 $, у которого величина каждого угла меньше $ 2\pi/3 $. В этом случае она единственна и в ней достигается

$$ \min_{P\in \mathbb R^2} (|PP_1|+|PP_2|+|PP_3|) \, . $$ Если величина одного из углов треугольника $ \ge 2\pi/3 $, то минимум достигается при помещении точки $ P_{} $ в эту вершину.

Пример. Для точек $ P_1=(1,1), P_2=(3,5), P_3= (7,2) $ точка Ферма-Торричелли изображена на рисунке

Ее точные координаты приведены ☟ НИЖЕ . ♦

Вернемся к рассмотрению общего случая неравных весов. На стороне $ P_{2}P_3 $ треугольника $ P_{1}P_2P_3 $ строится треугольник $ P_2P_3Q $, в котором $$ |P_3Q|=\frac{m_2}{m_1}|P_2P_3|,\ |P_2Q|=\frac{m_3}{m_1}|P_2P_3| \ , $$ и который расположен по другую сторону от прямой $ P_2P_3 $ по отношению к треугольнику $ P_{1}P_2P_3 $. Построенный треугольник очевидно оказывается подобным так называемому весовому треугольнику, т.е. треугольнику с длинами сторон формально совпадающими с $ m_1,m_2,m_3 $.

Утверждается, что прямая $ QP_1 $ пересекает окружность, описанную вокруг треугольника $ P_2P_3Q $ в искомой точке $ P_{\ast} $. В самом деле (см. рисунок ниже), по теореме синусов для треугольника $ P_2P_3Q $ будет выполнено: $$ \frac{\sin \nu_1 }{|P_2P_3|} =\frac{\sin \nu_2 }{|P_3Q|} =\frac{\sin \nu_3 }{|P_2Q|} \quad \iff \quad \frac{\sin \nu_1 }{m_1}=\frac{\sin \nu_2 }{m_2}=\frac{\sin \nu_3 }{m_3} \ . $$ По построению точки $ P_{\ast} $ будут иметь место соотношения: $$ \mu_1+\nu_1=\mu_2+\nu_2= \mu_3+\nu_3= \pi \ , $$ и, следовательно, ограничения на углы $ \mu_1, \mu_2, \mu_3 $ оказываются такими же, как и на $ |\gamma_3-\gamma_2 |, |\gamma_3-\gamma_1 |, |\gamma_2-\gamma_1 | $.

Длина отрезка $ |P_1Q| $ позволяет определить величину минимального значения функции: $$ m_1 |P_1Q| = m_1 |P_{\ast} P_1|+m_2 |P_{\ast} P_2|+ m_3 |P_{\ast} P_3| = \min_{P\in \mathbb R^2} \sum_{j=1}^3 m_j|PP_j| \ . $$ В предыдущих рассуждениях предполагается, что точка $ P_{\ast} $ лежит внутри треугольника $ P_{1}P_2P_3 $. В противном случае, решением задачи будет одна из вершин треугольника.

Пример. Найти точку $ P_{\ast} $ для конфигурации

$$ \left\{ \begin{array}{c|c|c} P_{1}=(2,6) & P_{2}=(1,1) & P_{3}=(5,1) \\ m_{1}=2 & m_{2}=3 & m_{3}=4 \end{array} \right\} \ . $$

Решение. Здесь $ |P_2P_3|=4 $, следовательно $ |P_2Q|=4 \cdot 2 = 8, |P_3Q|=4 \cdot 3/2 = 6 $. Этими условиями определяем точку $ Q_{} $ — как одну из двух точек пересечения окружностей (радиуса $ 8_{} $ с центром в точке $ P_{2} $ и радиуса $ 6_{} $ с центром в $ P_3 $).

Её координаты: $ \approx (6.5,-4.8) $. Проводим окружность через точки $ P_2,P_3,Q $. Прямая $ QP_1 $ пересекает ее в искомой точке $ P_{\ast} \approx (3.9, 1.4) $ при минимальном значении для минимизируемой функции: $ F(x_{\ast},y_{\ast}) \approx 23.4 $.

Точные значения приведены ☟ НИЖЕ. ♦

Для $ K=4 $ точек на плоскости геометрическое решение известно только для случая одинаковых весов.

Теорема [Фаньяно]. Если точки $ P_{1},P_2,P_3, P_{4} $ образуют выпуклый четырехугольник, то

$$ \min_{P\in \mathbb R^2} \left(|PP_1|+|PP_2|+|PP_3|+|PP_{4}| \right)$$ достигается в точке $ P_{\ast} $, лежащей на пересечении диагоналей четырехугольника: $$ x_{\ast}=\frac{(x_1-x_3)(x_2y_4-y_2x_4)-(x_2-x_4)(y_3x_1-y_1x_3)}{(x_3-x_1)(y_2-y_4)-(x_2-x_4)(y_3-y_1)},\ $$ $$ y_{\ast}=\frac{(y_1-y_3)(x_2y_4-y_2x_4)-(y_2-y_4)(y_3x_1-y_1x_3)}{(x_3-x_1)(y_2-y_4)-(x_2-x_4)(y_3-y_1)} \, . $$ Если же точки $ P_{1},P_2,P_3, P_{4} $ не образуют выпуклый четырехугольник, и точка $ P_{i} $ лежит внутри треугольника, образованного тремя оставшимися точками, то минимум суммы расстояний достигается в точке $ P_{i} $.

Пусть $ \{P_j= (x_{j},y_j)\}_{j=1}^3 $. Обозначим $$ r_{j\ell}=\sqrt{(x_j-x_{\ell})^2+(y_j-y_{\ell})^2}=|P_jP_{\ell}| \quad npu \ \{j,\ell\} \subset \{1,2,3\} \ . $$

Теорема.[11] Пусть все углы треугольника $ P_{1}P_2P_3 $ меньше $ 2\pi /3 $, или, что то же, выполнены условия:

$$ r_{12}^2+r_{13}^2+r_{12}r_{13}-r_{23}^2>0,\ r_{23}^2+r_{12}^2+r_{12}r_{23}-r_{13}^2>0,\ r_{13}^2+r_{23}^2+r_{13}r_{23}-r_{12}^2>0 \ . $$ Точка $ P_{\ast} $ Ферма-Торричелли имеет координаты $$ x_{\ast}=\frac{\kappa_1\kappa_2\kappa_3}{2 \sqrt{3} |S| d} \left(\frac{x_1}{\kappa_1}+\frac{x_2}{\kappa_2}+\frac{x_3}{\kappa_3} \right), \ y_{\ast}=\frac{\kappa_1\kappa_2\kappa_3}{2 \sqrt{3} |S| d} \left(\frac{y_1}{\kappa_1}+\frac{y_2}{\kappa_2}+\frac{y_3}{\kappa_3} \right) $$ при $$ |P_1P_{\ast}|+|P_2P_{\ast}|+|P_3P_{\ast}|= \sqrt{d} \ . $$ Здесь $$ d=\frac{1}{\sqrt{3}}(\kappa_1+\kappa_2+\kappa_3)=\frac{r_{12}^2+r_{13}^2+r_{23}^2}{2}+ \sqrt{3}\, |S| \ , $$ $$ \left\{ \begin{array}{lcl} \kappa_1=\frac{\sqrt{3}}{2}(r_{12}^2+r_{13}^2-r_{23}^2)+|S| , \\ \kappa_2=\frac{\sqrt{3}}{2}(r_{23}^2+r_{12}^2-r_{13}^2)+|S| , \\ \kappa_3=\frac{\sqrt{3}}{2}(r_{13}^2+r_{23}^2-r_{12}^2)+|S| \ ; \end{array} \right. $$ и $$ S=x_1y_2+x_2y_3+x_3y_1-x_1y_3-x_3y_2-x_2y_1= $$ $$ =\left|\begin{array}{cc} x_2-x_1 & x_3-x_1 \\ y_2-y_1 & y_3-y_1 \end{array} \right|= \left| \begin{array}{ccc} 1 & 1 & 1 \\ x_1 & x_2 & x_3 \\ y_1 & y_2 & y_3 \end{array} \right| \ . $$

Если выписать символьные представления для $ x_{\ast} $ и $ y_{\ast} $ в виде функций от параметров $ \{x_j,y_j\}_{j=1}^3 $, то можно осуществить сокращение на общий множитель $ |S| $ числителей и знаменателей получившихся в теореме дробей ☟

Теорема.[5,11] Пусть все углы треугольника $ P_{1}P_2P_3 $ меньше $ 2\pi /3 $. Точка $ P_{\ast} $ Ферма-Торричелли имеет координаты

$$ x_{\ast}=\frac{X}{2\sqrt{3}d}, \ y_{\ast}= \frac{Y}{2\sqrt{3}d} $$ при $$ |P_1P_{\ast}|+|P_2P_{\ast}|+|P_3P_{\ast}|= \sqrt{d} \ . $$ Здесь $$ d=\frac{r_{12}^2+r_{13}^2+r_{23}^2}{2}+\sqrt{3} \cdot | S | \ ; $$ $$ X=\sqrt{3} [x_1r_{23}^2+x_2r_{13}^2+x_3r_{12}^2] +(x_1+x_2+x_3) \cdot |S|+ $$ $$ +3 \operatorname{sign} (S) [(y_2-y_1)(x_1x_2+y_1y_2)+(y_1-y_3)(x_1x_3+y_1y_3)+(y_3-y_2)(x_2x_3+y_2y_3)]; $$ $$ Y=\sqrt{3} [y_1r_{23}^2+y_2r_{13}^2+y_3r_{12}^2]+ (y_1+y_2+y_3) \cdot |S| - $$ $$ -3 \operatorname{sign} (S)[(x_2-x_1)(x_1x_2+y_1y_2)+(x_1-x_3)(x_1x_3+y_1y_3)+(x_3-x_2)(x_2x_3+y_2y_3)] \ ; $$ $$ S=x_1y_2+x_2y_3+x_3y_1-x_1y_3-x_3y_2-x_2y_1= $$ $$ =\left|\begin{array}{cc} x_2-x_1 & x_3-x_1 \\ y_2-y_1 & y_3-y_1 \end{array} \right|= \left| \begin{array}{ccc} 1 & 1 & 1 \\ x_1 & x_2 & x_3 \\ y_1 & y_2 & y_3 \end{array} \right| \ . $$

Пример. При $ P_1=(1,1),P_2=(3,5),P_3=(7,2) $ будет:

$$ x_{\ast}=\frac{2}{687} \left( 1029 + 79 \sqrt{3}\right) \approx 3.3939,\qquad y_{\ast}=\frac{1}{687} \left( 1053 + 647 \sqrt{3} \right) \approx 3.1639 , $$ $$ |P_{\ast}P_1|+|P_{\ast}P_2|+|P_{\ast}P_3| = \sqrt{41+22\sqrt{3}}\approx 8.8941 . $$ При $ P_1=(1,2),P_2=(3,3),P_3=(4,1) $ : $$ x_{\ast}=\frac{1}{6}(15+\sqrt{3}) \approx 2.7886,\qquad y_{\ast}=\frac{1}{2}(3+\sqrt{3}) \approx 2.3660 \ ; $$ $$ |P_{\ast}P_1|+|P_{\ast}P_2|+|P_{\ast}P_3| = \sqrt{5\,(2+\sqrt{3})}\approx 4.3197 \, . $$

Проверка равенства $$ \frac{(x_{\ast}-x_1)(x_{\ast}-x_2)+(y_{\ast}-y_1)(y_{\ast}-y_2)}{\sqrt{((x_{\ast}-x_1)^2+(y_{\ast}-y_1)^2)((x_{\ast}-x_2)^2+(y_{\ast}-y_2)^2)}}=-\frac{1}{2} $$ произведена.

Получено только для случая $ K=3 $.

Теорема.[11] Обозначим величину угла треугольника $ P_{1}P_2P_3 $ при вершине $ P_{j} $ через $ \alpha_j $. Если нарушено $ j $-е из трех условий

\begin{align*} m_2^2+m_3^2+2\, m_2m_3 \cos \alpha_1 & > m_1^2 , \\ m_1^2+m_3^2+2\, m_1m_3 \cos \alpha_2 & > m_2^2,\\ m_1^2+m_2^2+2\, m_1m_2 \cos \alpha_3 & > m_3^2, \end{align*} то минимум функции $$ F(x,y)=\sum_{j=1}^3 m_j \sqrt{(x-x_j)^2+(y-y_j)^2} $$ достигается в точке $ P_{j}=(x_j,y_j) $. Если все неравенства выполняются, то $ \min F(x,y) $ достигается в точке $ P_{\ast} $ с координатами: $$ x_{\ast}=\frac{K_1K_2K_3}{4 |S| \sigma d} \left(\frac{x_1}{K_1}+\frac{x_2}{K_2}+\frac{x_3}{K_3} \right), \ y_{\ast}=\frac{K_1K_2K_3}{4 |S| \sigma d} \left(\frac{y_1}{K_1}+\frac{y_2}{K_2}+\frac{y_3}{K_3} \right)\ . $$ при $$ F(x_{\ast},y_{\ast})=\min_{(x,y)} F(x,y)=\sqrt{d} \ . $$ Здесь $$ d= 2\, |S| \sigma + $$ $$ +\frac{1}{2}\left[m_1^2(r_{12}^2+r_{13}^2-r_{23}^2)+ m_2^2(r_{23}^2+r_{12}^2-r_{13}^2)+m_3^2(r_{13}^2+r_{23}^2-r_{12}^2) \right] \ ; $$ $$ r_{j\ell}=\sqrt{(x_j-x_{\ell})^2+(y_j-y_{\ell})^2}=|P_jP_{\ell}| \quad npu \ \{j,\ell\} \subset \{1,2,3\} \ ; $$ $$ S=x_1y_2+x_2y_3+x_3y_1-x_1y_3-x_3y_2-x_2y_1= $$ $$ =\left|\begin{array}{cc} x_2-x_1 & x_3-x_1 \\ y_2-y_1 & y_3-y_1 \end{array} \right|=\left| \begin{array}{ccc} 1 & 1 & 1 \\ x_1 & x_2 & x_3 \\ y_1 & y_2 & y_3 \end{array} \right| \ ; $$ $$ \sigma= \frac{1}{2} \sqrt{-m_1^4-m_2^4-m_3^4+2\,m_1^2m_2^2+2\,m_1^2m_3^2+2\,m_2^2m_3^2} \ ; $$ $$ \left\{ \begin{array}{ccc} K_1&=&(r_{12}^2+r_{13}^2-r_{23}^2)\sigma+(m_2^2+m_3^2-m_1^2) |S| , \\ K_2&=&(r_{23}^2+r_{12}^2-r_{13}^2)\sigma+(m_1^2+m_3^2-m_2^2) |S| , \\ K_3&=&(r_{13}^2+r_{23}^2-r_{12}^2)\sigma+(m_1^2+m_2^2-m_3^2) |S| . \end{array} \right. $$

Пример. Для конфигурации

$$ \left\{\begin{array}{c|c|c} P_{1}=(2,6) & P_{2}=(1,1) & P_{3}=(5,1) \\ m_{1}=2 & m_{2}=3 & m_{3}=4 \end{array} \right\} $$ точка $ P_{\ast} $ имеет координаты $$ x_{\ast}=\frac{4103+1833 \sqrt{15}}{2866}\approx 3.9086 , \ y_{\ast} =\frac{29523-4481 \sqrt{15}}{8598}\approx 1.4152 \, . $$ Минимальное значение для функции: $$ \min F(x,y)= m_1|P_{\ast}P_1|+m_2|P_{\ast}P_2|+m_3|P_{\ast}P_3|= 2\sqrt{79+15\sqrt{15}} \approx 23.4174 \, . $$ ♦

В случае $ K>3 $ точек аналитическое решение для обобщенной задачи Ферма-Торричелли вряд ли может быть получено. Тем не менее, можно попытаться продвинуться аналитикой возможно дальше, именно: свести поиск координаты точки $ P_{\ast} $ к решению системы полиномиальных (алгебраических) уравнений и попытаться применить к этой системе методы исключения переменных.

Пример. Выяснить динамику поведения точки $ P_{\ast} $ для конфигурации

$$ \left\{ \begin{array}{c|c|c|c} P_{1}=(1,1) & P_{2}=(3,5) & P_{3}=(7,2) & P_{4}=(6,6) \\ m_{1}=1 & m_{2}=1 & m_{3}=1 & m_{4}=m \end{array} \right\} $$ в зависимости от изменения параметра $ m_{} $.

Решение. При каждом конкретном значении параметра $ m_{} $ координаты стационарной точки $ P_{\ast} $ можно найти применением численных методов, но нас интересует хоть какое-то функциональное представление для $ P_{\ast} (m) $.

Градиентную систему уравнений $$ \left\{ \begin{array}{lll} \frac{ \partial F}{\partial x} &= \frac{(x-1)}{\sqrt{(x-1)^{2}+(y-1)^2}}+\frac{(x-3)}{\sqrt{(x-3)^{2}+(y-5)^2}}+\frac{(x-7)}{\sqrt{(x-7)^{2}+(y-2)^2}}+ \frac{m(x-6)}{\sqrt{(x-6)^2+(y-6)^2}} & = 0 \\ \frac{\partial F}{\partial y} &= \frac{(y-1)}{\sqrt{(x-1)^{2}+(y-1)^2}}+\frac{(y-5)}{\sqrt{(x-3)^{2}+(y-5)^2}}+\frac{(y-2)}{\sqrt{(x-7)^{2}+(y-2)^2}}+ \frac{m(y-6)}{\sqrt{(x-6)^2+(y-6)^2}} & = 0 \end{array} \right. $$ преобразуем к алгебраической. Это можно сделать различными методами и результат существенно зависит от организации процесса (т.е. алгебраическая система, включающая в себя множество решений исходной, определяется не единственным образом). Мы укажем пока только конечный результат (один из возможных): $$ F_1(x,y,m)=0,\ F_2(x,y,m)=0 \ ; $$ здесь $ F_{1} $ и $ F_{2} $ полиномы степени $ 6_{} $ по каждой переменной $ x_{} $ или $ y_{} $ и степени $ 12_{} $ по обеим переменным. Из этой системы, посредством вычисления результанта, можно исключить переменные $ x_{} $ или $ y_{} $ и получить алгебраические уравнения вида $$ \mathcal X(x,m)=0, \ \mathcal Y(y,m)=0, $$ которым удовлетворяют координаты стационарных точек при каждом фиксированном значении $ m_{} $. Оказывается, эти уравнения можно упростить (отбросить посторонние сомножители), сведя к уравнениям степени $ 12 $ по каждой из переменных $ x_{} $ или $ y_{} $. Их выражения ☞ ЗДЕСЬ.

Дальнейшее упрощение вряд ли возможно: уравнения неприводимы над $ \mathbb Q_{} $, и, скорее всего, неразрешимы в радикалах.

Можно пойти другим путем: исключать параметр $ m_{} $ с целью нахождения неявного представления кривой, на которой расположены стационарные точки при всех возможных значениях $ m_{} $. Результант $ \mathcal R_m(F_1,F_2) $ оказывается полиномом степени $ 96 $ по $ x_{} $ и $ y_{} $, и этот полином факторизуется в виде $$ 65536 (2x-y-1)^8(x^2-14x+53-4y+y^2)^8(x^2-12\,x+72-12y+y^2)^8 \Phi_0^2(x,y) \Phi^2(x,y) \ . $$ Собственно кривая стационарных точек задается одним множителем: $$ \Phi(x,y) = 0 $$ при $$ \Phi(x,y) =3\,y(-7\,y+10\,x)(8\,x-y)(2\,x-9\,y)(x^2+y^2)^4+ $$ $$ +8\,(160\,x^5-2594\,x^4y+10117\,x^3y^2+3152\,x^2y^3-6209\,xy^4+183\,y^5)(x^2+y^2)^3- $$ $$ -4\,(10144\,x^6-106368\,x^5y+344359\,x^4y^2+303368\,x^3y^3+32554\,x^2y^4-193808\,xy^5-16853\,y^6)(x^2+y^2)^2 $$ $$ +\dots -1152\, (2823793\,x^2-22813720\,xy-56866\,y^2)+4409856 (1491\,x+1234\,y)-2110116096 \ . $$ Полное выражение для функции $ \Phi $ и картина всей кривой $ \Phi=0 $ целиком достаточно сложны: см. ☞ ЗДЕСЬ. На рисунке выделена только ветвь, которая соответствует реальной динамике стационарной точки.

«Контрольные» точки на этой ветви:

x $ \left(\frac{2}{687}(1029 + 79\sqrt{3}),\frac{1}{687}(1053 + 647\sqrt{3}) \right) $ — точка Ферма-Торричелли треугольника $ P_1P_2P_{3} $, соответствует значению $ m=0 $;

x $ \left(\frac{29}{7},\frac{29}{7}\right) $ — точка пересечения диагоналей четырехугольника $ P_1P_2P_3P_4 $, соответствует значению $ m_{}=1 $ (см. ☞ теорему Фаньяно);

♦ $ (6,6) $ — вершина $ P_{4} $, соответствует значению $ m \approx 2.4436 $ (точное значение ☞ ЗДЕСЬ);

♦ $ (1,1) $ — вершина $ P_{1} $, соответствует значению $ m \approx -2.4184 $ (вообще говоря, в постановке задачи говорится только о положительных значениях весов, но почему бы не осуществить аналитическое продолжение? );

x $ (\frac{11}{3},\frac{11}{3}) $, соответствует $ m=1-\sqrt{2/5} \approx 0.3675 $.

Обращаемся к задаче в $ \mathbb R^{n}_{} $. Стационарные точки функции $$ F(P)=\sum_{j=1}^Km_j |PP_j| $$ являются решениями градиентной системы уравнений $$ \frac{\partial F}{\partial x_1}=0,\dots, \frac{\partial F}{\partial x_n}=0 \ , $$ которую можно записать в векторном виде $$ \sum_{j=1}^K m_j\frac{PP_j}{|PP_j|} = \mathbb O_{n\times 1} \ . $$ При этом следует иметь в виду, что, во-первых, при некоторых конфигурациях система может оказаться несовместной и, во-вторых, искомый минимум функции может достигаться в одной из точек $ \{P_j\} $ (которые последней системой не «отлавливаются»).

Теорема. Пусть точки $ \{P_j\}_{j=1}^K \subset \mathbb R^n $ все различны. Минимум функции $$ F(P)=\sum_{j=1}^K m_j |PP_j| $$ существует и единствен. При этом

1. если существует точка $ P_{i} $ такая, что выполняется условие $$ \left|\sum_{j=1 \atop j \ne i}^K m_j \frac{P_jP_i}{|P_jP_i|} \right| \le m_i \ , $$ то $ \min F(P) $ достигается в точке $ P_{i} $;

2. если для любого значения $ i \in \{1,\dots,K\} $ выполняется условие $$ \left|\sum_{j=1 \atop j \ne i}^K m_j \frac{P_jP_i}{|P_jP_i|} \right| > m_i \ , $$ то $ \min F(P) $ достигается в точке $ P_{\ast} $, удовлетворяющей градиентной системе уравнений $$ \sum_{j=1}^K m_j \frac{PP_j}{|PP_j|}=\mathbb O_{n\times 1}\, ; $$ и, в этом случае, $ P_{\ast} \not\in \{P_j\}_{j=1}^K $.

Доказательство ☞ ЗДЕСЬ

Пример. При каких значениях параметра $ m_{} $ в конфигурации

$$ \left\{ \begin{array}{c|c|c|c} P_{1}=(1,1) & P_{2}=(3,5) & P_{3}=(7,2) & P_{4}=(6,6) \\ m_{1}=1 & m_{2}=1 & m_{3}=1 & m_{4}=m \end{array} \right\} $$ $ \min \sum_{j=1}^4 m_j|PP_j| $ достигается в точке $ P_4 $?

Решение. Формируем условие $$ \left| m_1 \frac{(1,1)- (6,6)}{\sqrt{50}}+m_2\frac{(3,5)- (6,6)}{\sqrt{10}}+m_3 \frac{(7,2)- (6,6)}{\sqrt{17}} \right| \le m_4 \ . $$ Ответ. При $ m \ge \sqrt{3+4/\sqrt{5}+3\sqrt{2/17}+\sqrt{2/85}} \approx 2.4436 $.

В случае $ n=2, K=3 $ условия теоремы переформулируются в терминах углов $ \alpha_1,\alpha_2, \alpha_3 $ треугольника $ P_1P_2P_{3} $. Так, например, условие 2 эквивалентно

$$ \ m_2^2+m_3^2+2\, m_2m_3 \cos \alpha_1 > m_1^2 , \ \ m_1^2+m_3^2+2\, m_1m_3 \cos \alpha_2 > m_2^2,\ m_1^2+m_2^2+2\, m_1m_2 \cos \alpha_3 > m_3^2\, . $$ Если $ m_1=m_2=m_3 $, то эти условия означают, что все углы треугольника меньше $ 2\pi/3 $. В общем же случае (не обязательно равных весов) этим условиям можно придать следующую геометрическую интерпретацию. Их выполнение означает, что рассматривая величины весов $ m_1,m_2,m_3 $ в качестве длин отрезков, мы можем построить из этих отрезков треугольник — он так и называется: «весовой треугольник» [1].

Обозначим углы этого треугольника $ \beta_1, \beta_2, \beta_3 $ в соответствии с рисунком. Тогда, по теореме косинусов, получаем: $$ \cos \alpha_j+ \cos \beta_j > 0 \quad npu \quad j\in \{1,2,3\} \, . $$

Рассмотрим задачу в $ \mathbb R^{n}_{} $ сначала для случая одинаковых весов $ m_1=\dots=m_K=1 $. Перепишем градиентную систему уравнений $$ \frac{P-P_1}{|PP_1|}+\dots+\frac{P-P_K}{|PP_K|}= \mathbb O_{n\times 1}, $$ задающую стационарные точки функции $ F(P) $, в эквивалентном виде $$ P=\underbrace{\left(\frac{P_1}{|PP_1|}+\dots+\frac{P_K}{|PP_K|} \right) \bigg/ \left(\frac{1}{|PP_1|}+\dots+\frac{1}{|PP_K|} \right)}_{=\Phi(P)} \, . $$ Решать последнюю систему будем методом простой итерации. Возьмем в качестве начального приближения произвольную точку $ P^{(0)} \not\in \{P_j\}_{j=1}^K $ и строим последовательность по рекурсивной формуле $$ P^{(k)}=\Phi(P^{(k-1)}) \quad npu \quad k \in \mathbb N \ . $$ Утверждается, что эта последовательность сходится к точке $ P_{\ast} $, являющейся точкой минимума функции $ F(P)=\sum_{j=1}^K |PP_j| $.

Метод известен как алгоритм Вайсфельда [14].

Пример. Для $ P_1=(1,1), P_2=(3,5), P_3=(7,2) $ возьмем $ P^{(0)}=(2,2) $. Итерационная последовательность

$$ \left(\begin{array}{c} 2 \\ 2 \end{array} \right) \to \left(\begin{array}{c} 2.4979 \\ 2.1974 \end{array} \right) \to \left(\begin{array}{c} 2.8581 \\ 2.4862 \end{array} \right) \to \left(\begin{array}{c} 3.1122 \\ 2.7295 \end{array} \right) \to \dots \to P^{(7)} =\left(\begin{array}{c} 3.3_{\displaystyle 879} \\ 3.1_{\displaystyle 089} \end{array} \right) \to \dots $$ сходится к точке Ферма-Торричелли $ P_{\ast}\approx (3.3939, 3.1639 ) $. ♦

Пример. Для $ P_1=(1,1,0), P_2=(5,1,0), P_3=(2,6,0), P_4=(3,3,5) $ возьмем $ P^{(0)}=(1,1,1) $. Итерационная последовательность

$$ \left(\begin{array}{c} 1 \\ 1 \\ 1 \end{array} \right) \to \left(\begin{array}{c} 1.9583 \\ 1.8361 \\ 0.6226 \end{array} \right) \to \left(\begin{array}{c} 2.3007 \\ 2.1007 \\ 0.7319 \end{array} \right) \to \left(\begin{array}{c} 2.5077 \\ 2.2665 \\ 0.8386 \end{array} \right) \to \dots \to P^{(7)}= \left(\begin{array}{c} 2.6_{\displaystyle 781} \\ 2.42_{\displaystyle 28} \\ 0.9_{\displaystyle 552} \end{array} \right) \to \dots $$ сходится к точке $ P_{\ast} \approx (2.6823, 2.4298, 0.9607) $. ♦

Проблемы сходимости возникают в случае, когда искомая точка $ P_{\ast} $ близка к одной из $ \{P_j\}_{j=1}^K $.

Пример. Для

$$ P_1=(0,0), P_2=(1,0), P_3=(-4,7) $$ координаты точки Ферма-Торричелли: $ P_{\ast}\approx (0.0023,0.0039) $. Итерационная последовательность, стартующая из $ P^{(0)}=(0,1) $, не дает этой точности при $ 200 $ итерациях. ♦

Метод очевидным образом обобщается и на случай, когда веса в конфигурации не обязательно одинаковы: в рекурсивной формуле следует взять $$ \Phi(P)=\left(\frac{m_1P_1}{|PP_1|}+\dots+\frac{m_KP_K}{|PP_K|} \right) \bigg/ \left(\frac{m_1}{|PP_1|}+\dots+\frac{m_K}{|PP_K|} \right) \ . $$

Задача. Подобрать величины весов $ \{m_j\}_{j=1}^K $ так, чтобы минимум функции $ \displaystyle F(P)=\sum_{j=1}^K m_j |PP_j| $ находился в наперед заданной точке $ P_{\ast} \not\in \{P_j\}_{j=1}^K $.

В отличие от «прямой» задачи, обратная имеет довольно простое решение. Начнем рассмотрение со случая плоскости: $ n=2, K=3 $.

Теорема [11]. Пусть вершины треугольника $ P_{1}P_2P_3 $ пронумерованы против часовой стрелки. Тогда для значений

$$ m_1^{\ast} = |P_{\ast}P_1| \cdot \left| \begin{array}{ccc} 1 & 1 & 1 \\ x_{\ast} & x_2 & x_3 \\ y_{\ast} & y_2 & y_3 \end{array} \right|, \ m_2^{\ast} = |P_{\ast}P_2| \cdot \left| \begin{array}{ccc} 1 & 1 & 1 \\ x_1 & x_{\ast} & x_3 \\ y_1 & y_{\ast} & y_3 \end{array} \right|,\ m_3^{\ast} = |P_{\ast}P_3| \cdot \left| \begin{array}{ccc} 1 & 1 & 1 \\ x_1 & x_2 & x_{\ast} \\ y_1 & y_2 & y_{\ast} \end{array} \right| $$ функция $$ F(x,y) = \sum_{j=1}^3 m_{j}^{\ast} \sqrt{(x-x_j)^2+(y-y_j)^2} $$ имеет стационарную точкой точку $ P_{\ast}=(x_{\ast},y_{\ast}) $. Если последняя выбирается внутри треугольника $ P_{1}P_2P_3 $, то величины $ m_1^{\ast},m_2^{\ast},m_3^{\ast} $ все положительны и $$ F(x_{\ast},y_{\ast})=\min_{(x,y)\in \mathbb R^2} F(x,y)= \left| \begin{array}{cccc} 1 & 1 & 1 & 1\\ x_{\ast} & x_1 & x_2 & x_3 \\ y_{\ast} & y_1 & y_2 & y_3 \\ x_{\ast}^2+y_{\ast}^2 & x_1^2+y_1^2 & x_2^2+y_2^2 & x_3^2+y_3^2 \end{array} \right| \ . $$

Доказательство теоремы, а также геометрический смысл величин из ее формулировки ☞ ЗДЕСЬ.

Пример. Поместить в точках $ P_{1}=(2,6),P_{2}=(1,1), P_{3}=(5,1) $ соответствующие веса $ \{m_j^{\ast}\} $ так, чтобы точка минимума функции $ F(x,y) $ находилась бы в точке

$$ P_{\ast} = \left(\frac{ 4103+1833 \sqrt{15}}{2866} ,\ \frac{29523-4481 \sqrt{15}}{8598} \right) \ . $$

Решение. Формулы из теоремы дают: $$ \left\{\begin{array}{ccl} m_1^{\ast}&=& \displaystyle \frac{2(20925-4481\sqrt{15})}{18481401}\sqrt{316380606+35999826\sqrt{15}} \ ,\\ m_2^{\ast}&=& \displaystyle \frac{2(15105-2342\sqrt{15})}{6160467}\sqrt{75400161-9169767\sqrt{15}} \ , \\ m_3^{\ast}&=& \displaystyle \frac{8(-1185+15988\sqrt{15})}{18481401}\sqrt{8335761-2050623\sqrt{15}}\ , \end{array} \right. $$ при $$ F(x_{\ast},y_{\ast})=\frac{1}{4299}(-333980+193436\sqrt{15}) \ . $$ Сравним этот результат с полученным ☝ ВЫШЕ. В соответствии с замечанием, должно выполняться: $ m_1^{\ast} : m_2^{\ast} : m_3^{\ast} = 2 : 3 : 4 $. А проверьте! ♦

Обобщение результата в многомерный случай $ n>2 $ для числа точек $ K=n+1 $ ☞ ЗДЕСЬ.

Задача. Пусть заданы точки $ P_1,\dots,P_K $ на плоскости. Требуется построить связную систему $ \mathbf L_{} $ прямолинейных отрезков на той же плоскости, чтобы

1. любые две точки $ P_{j} $ и $ P_{\ell} $ могли быть связаны ломаной линией, звенья которой входили бы в состав системы $ \mathbf L_{} $;

2. общая длина всей системы $ \mathbf L_{} $ была наименьшей.

Такая система $ \mathbf L_{} $ называется минимальным деревом Штейнера, ее построение и применения см. в [3,4].

На первый взгляд кажется, что эта задача эквивалентна задаче Ферма-Торричелли в случае одинаковых весов и речь идет о поиске единственной точки $ P_{\ast} $ на плоскости. На самом деле, решение этой задачи для случая $ K \ge 4 $ предполагает построение нескольких вспомогательных точек.

Пример. Построить минимальное дерево Штейнера для точек $$ P_1=(0,3),\ P_2=(0,0),\ P_3=(4,0),\ P_4=(4,3) \, . $$

Решение. Будем пробовать варианты решения задачи, последовательно добавляя вспомогательные точки. Если не добавлять дополнительных точек вообще, то эта задача относится к классу задач построения минимального покрывающего дерева⁷⁾. В такой постановке решением рассматриваемого примера будет ломаная $ P_1P_2P_3P_4 $ длиной $ 3+4+3=10 $.

Если разрешено добавить одну дополнительную точку, то решением задачи, в соответствии с ☝ теорему Фаньяно, будет система из двух диагоналей прямоугольника:

Тем не менее, выигрыша в длине дерева не получим: $ 5+5=10 $. Но если разрешено добавлять две дополнительных точки, то расположив их в $ P_{\ast}=\left(\frac{\sqrt{3}}{2},\frac{3}{2} \right) $ и $ P_{\ast \ast}=\left(4-\frac{\sqrt{3}}{2},\frac{3}{2} \right) $

получим суммарную длину равной $ 4+ 3\sqrt{3} \approx 9.196152 $.

Можно ли улучшить этот результат добавлением еще большего количества дополнительных точек? Ответ отрицателен: оказывается, что для произвольной конфигурации системы $ \{P_j\}_{j=1}^4 $ количество дополнительных точек, необходимых для решения задачи о минимальном дереве, никогда не превысит двух. ♦

В рассмотренном примере точка $ P_{\ast} $ является точкой Ферма-Торричелли для треугольника $ P_1 P_2 P_{\ast \ast} $, а точка $ P_{\ast \ast} $ — точкой Ферма-Торричелли для треугольника $ P_3 P_4 P_{\ast } $. Это свойство оказывается принципиальным для решения общей задачи: для любой конфигурации точек $ \{ P_j \}_{j=1}^K \subset \mathbb R^2 $ минимальное дерево Штейнера является графом, соединяющим эти точки с дополнительными узлами графа, составляющими некоторое множество $ \{ S_{\ell} \}_{\ell=1}^M $. Мощность этого дополнительного множества находится в пределах $$ 0 \le M \le K-2 \, ,$$ и, при условии, что оно не пусто, любой его элемент является точкой Ферма-Торричелли для некоторой тройки точек из объединения $ \{ P_j \}_{j=1}^K \bigcup \{ S_{\ell} \}_{\ell=1}^M $. Степень каждой вершины $ \{ P_j \}_{j=1}^K $ графа равна либо $ 1_{} $ либо $ 2_{} $.

Задача о минимальном дереве Штейнера обсуждается ☞ ЗДЕСЬ.

Для случая $ n=2_{} $ рассмотрим задачу о линиях уровня функции $$ F(x,y)= \sum_{j=1}^{K} \sqrt{(x-x_j)^2+(y-y_j)^2} \ , $$ т.е. о кривых $ F(x,y)=c $ при различных значениях $ c_{} $. В случае $ K=2 $ решение задачи хорошо известно — это либо эллипс с фокусами в точках $ P_1=(x_1,y_1),P_2=(x_2,y_2) $, либо отрезок, соединяющий эти точки, либо пустое множество (мнимый эллипс). Что за кривые соответствуют случаям $ K \ge 3 $? Например, каково геометрическое место точек, сумма расстояний от которых до фиксированных точек $ P_1,P_2,P_3 $ является постоянной величиной? Этот вопрос был задан Декартом Ферма в 1638 г. (и именно отсюда возникла у Ферма постановка задачи о поиске минимума функции $ F_{} $).

Эти кривые называются мультифокусными (мультифокальными) эллипсами,полиэллипсами или обобщенными эллипсами. В немецком языке известны также под названием Tschirnhaus'sche Eikurve — яйцеобразные кривые Чирнгауза⁸⁾. Они могут считаться алгебраическими кривыми — последовательным возведением их уравнений в квадрат можно избавиться от радикалов.

Пример. Для $ P_1=(1,1),P_2=(3,5),P_3=(7,2) $ семейство трехфокусных эллипсов (алгебраических кривых порядка $ 8_{} $) выглядит так (числа на кривых — значения константы $ c_{} $):

Каким значениям $ c_{} $ соответствуют кривые, проходящие через точки $ P_1, P_2, P_3 $ ? ♦

В случае когда веса $ \{ m_j \} $ могут быть различными, линии уровня функции $$ F(x,y)= \sum_{j=1}^{K} m_j\sqrt{(x-x_j)^2+(y-y_j)^2} \ , $$ не имеют установившегося названия. В случае $ K=2 $ в литературе встречаются под названием овалы Декарта; сам Декарт называл их эллипсами второго рода. Если $ K\ge 3 $ и величины весов $ \{ m_j \} $ рационально соизмеримы, то этот случай может быть быть рассмотрен как предельный случай мультифокусного эллипса — когда некоторые из фокусов сливаются в один. Этими кривыми в середине XIX века интересовался (из любознательности) один шотландский ученый [7]. В случае $ K=3 $ кривые известны в экономической географии под названием изодапан⁹⁾; каждая такая кривая состоит из точек одинаковой суммарной стоимости транспортных перевозок до них из $ \{P_j\} $.

Анимация трехмерного аналога мультифокусного эллипса ☞ ЗДЕСЬ (470 Kb).

Задача 1. Построить максимальный равносторонний треугольник $ Q_1Q_2Q_3 $, описанный вокруг заданного треугольника $ P_{1}P_{2}P_3 $ (на каждой стороне треугольника $ Q_{1}Q_{2}Q_3 $ должна лежать одна вершина треугольника $ P_1P_2P_3 $).

Теорема. Пусть все углы треугольника $ P_{1}P_{2}P_3 $ меньше $ 2\pi/3 $. Высота искомого треугольника $ Q_1Q_2Q_3 $ равна $ |P_{\ast}P_1|+|P_{\ast}P_2|+|P_{\ast}P_3| $, где $ P_{\ast} $ — точка Ферма-Торричелли треугольника $ P_{1}P_{2}P_3 $. Стороны треугольника $ Q_1Q_2Q_3 $ перпендикулярны прямым $ P_{\ast}P_1, P_{\ast}P_2 $ и $ P_{\ast}P_3 $.

Задача 2. Построить минимальный равносторонний треугольник $ R_1R_2R_3 $, вписанный в заданный треугольник $ P_{1}P_{2}P_3 $ (на каждой стороне треугольника $ P_{1}P_{2}P_3 $ должна лежать одна вершина треугольника $ R_1R_2R_3 $).

На удивление, ссылок в интернете на решение задачи 2 я не нашел, за исключением ☞ ЭТОЙ. Задача похожа на задачу Фаньяно о построении произвольного треугольника минимального периметра, вписанного в данный остроугольный [4]; однако требование равносторонности треугольника в условии задачи существенно меняет ее решение.

Теорема. Пусть все углы треугольника $ P_{1}P_{2}P_3 $ меньше $ 2\pi/3 $. Стороны искомого треугольника $ R_1R_2R_3 $ параллельны сторонам треугольника $ Q_1Q_2Q_3 $, решающего предыдущую задачу. Имеет место соотношение между площадями трех треугольников — исходного, максимального описанного и минимального вписанного: $$ \frac{ S_{\triangle Q_1Q_2Q_3}}{ S_{\triangle P_1P_2P_3}}=\frac{ S_{\triangle P_1P_2P_3}}{S_{\triangle R_1R_2R_3}} \ . $$

Задача. Найти стационарные точки функции $$ F(P)= \sum_{j=1}^K m_j \left|PP_j \right|^L \ . $$ Здесь $ \{P,P_1,\dots,P_K\} \subset \mathbb R^n $, $ L_{} $ предполагается вещественным ненулевым числом, а величины $ \{ m_{j} \}_{j=1}^K $ — произвольными вещественными числами (не обязательно положительными).

В случае $ L=1 $ мы получаем обобщенную задачу Ферма-Торричелли, рассмотренную выше. В случае $ L=2 $ решением задачи является единственная точка $$ P_{\ast}= \frac{\sum_{j=1}^K m_jP_j}{ \sum_{j=1}^K m_j} $$ — точка глобального минимума функции $ F(P) $. В случае всех положительных $ \{m_j\}_{j=1}^K $ и $ n\in \{2,3\} $ точка $ P_{\ast} $ является центром масс (барицентром) системы материальных точек, расположенных в точках $ \{P_j\}_{j=1}^K $.

Нас интересует решение задачи для других показателей $ L_{} $. Поставленной задаче можно придать физический смысл. Пусть в пространстве имеется конфигурация $$ \left\{\begin{array}{c|c|c} P_1 & \dots & P_K \\ m_1 & \dots & m_K \end{array} \right\} $$ из $ K_{} $ фиксированных (неподвижных) точечных заряженных частиц, которые воздействуют на пробный точечный единичный заряд величины, помещенный в точку $ P_{} $; при этом сила воздействия $ j_{} $-го заряда прямо пропорциональна величине заряда $ m_{j} $ и пропорциональна некоторой степени $ L_{} $ расстояния от этого заряда до пробного. Требуется найти точку $ P_{\ast} \in \mathbb R^{n}_{} $, при помещении в которую пробного заряда, последний будет неподвижен (находиться в положении равновесия).

Особый интерес представляет частный случай поставленной задачи: $ L=-1 $. Этому случаю соответствует два физических потенциала — кулоновский (электростатический) и ньютоновский (гравитационный)¹⁰⁾.

Стационарные точки этого семейства потенциалов задаются градиентной системой уравнений $$ \left\{\frac{\partial F}{\partial x_{\ell}}= L \sum_{j=1}^{K} m_j |PP_j|^{L-1} \frac{(x_{\ell}-x_{j\ell})}{|PP_j|} = 0 \right\}_{\ell=1}^n \ , \quad npu \quad \begin{array}{c} \{P_j=(x_{j1},\dots,x_{jn})\}_{j=1}^K, \\ P=(x_1,\dots,x_n) \end{array} \ , $$ которая при четных значениях $ L_{} $ является алгебраической (или может быть немедленно приведена к алгебраической в случае отрицательных $ L_{} $); в остальных же случаях она будет содержать радикалы, от которых можно избавиться только последовательным возведением уравнений в квадрат. Уже для случая кулоновского потенциала $ L=-1, n=2, K=3 $ это приводит к алгебраическим уравнениям высокой степени с громоздкими коэффициентами.

Пример. Пусть $ P_1=(1,1), P_2=(5,1) , P_3=(2,6) $. Проанализировать поведение множества стационарных точек функции

$$ F(x,y)=\frac{1}{\sqrt{(x-1)^2+(y-1)^2}}+ \frac{m_2}{\sqrt{(x-5)^2+(y-1)^2}}+\frac{m_3}{\sqrt{(x-2)^2+(y-6)^2}} $$ в зависимости от значений $ m_2, m_3 $, рассматриваемых в качестве параметров.

Решение. Градиентная система уравнений $$ \begin{array}{rrr} \displaystyle \frac{x-1}{\sqrt{(x-1)^2+(y-1)^2}^3}& \displaystyle +\frac{m_2(x-5)}{\sqrt{(x-5)^2+(y-1)^2}^3}& \displaystyle +\frac{m_3(x-2)}{\sqrt{(x-2)^2+(y-6)^2}^3}=0\, , \\ \displaystyle \frac{y-1}{\sqrt{(x-1)^2+(y-1)^2}^3}& \displaystyle +\frac{m_2(y-1)}{\sqrt{(x-5)^2+(y-1)^2}^3}& \displaystyle +\frac{m_3(y-6)}{\sqrt{(x-2)^2+(y-6)^2}^3}=0 \, \end{array} $$ может быть преобразована в алгебраическую в ходе следующей процедуры. Обозначим $ A_1, A_2 $ и $ A_3 $ слагаемые в любом из этих уравнений. Последовательное возведение в степень по схеме $$ A_1+A_2+A_3=0 \quad \Rightarrow \quad (A_1+A_2)^2=A_3^2 \quad \Rightarrow \quad (2\, A_1A_2)^2 = (A_3^2-A_1^2 - A_2^2)^2 $$ приводит систему к алгебраической $$ F_1(x,y,m_2,m_3)=0,\ F_2(x,y,m_2,m_3)=0 \ . $$ Здесь $ F_{1} $ и $ F_{2} $ — полиномы степени $ 28 $ по переменным $ x_{} $ и $ y_{} $ с коэффициентами порядков до $ 10^{19} $. Нахождение всех решений этой системы — даже для конкретных (фиксированных) значений параметров $ m_2 $ и $ m_3 $ — становится вычислительно сложной задачей. А ведь требуется решить еще более сложную задачу: проследить динамику этого множества при изменении параметров!

Сложность поставленной задачи — по сравнению с обобщенной задачей Ферма-Торичелли — заключается еще и в том, что что число вещественных решений системы больше единицы; в зависимости от значений параметров, число стационарных точек — от $ 2_{} $ до $ 4_{} $. ♦

Гипотеза [Максвелл] [8,15]. Число стационарных точек кулоновского поля любой конфигурации $ K_{} $ стационарных зарядов в $ \mathbb R^3 $ не превосходит $ (K-1)^2 $. Не доказана¹¹⁾.

Что общего у поставленной в начале пункта задачи с обобщенной задачей Ферма-Торричелли? — То, что похожим образом решается обратная задача. Рассмотрим сначала плоский случай.

Теорема [12, 13]. Пусть точки $ P_{1}=(x_1,y_1),P_2=(x_2,y_2),P_3=(x_3,y_3) $ неколлинеарны. Тогда для значений

$$ m_1^{\ast} = |P_{\ast}P_1|^{2-L} \left| \begin{array}{ccc} 1 & 1 & 1 \\ x_{\ast} & x_2 & x_3 \\ y_{\ast} & y_2 & y_3 \end{array} \right|, \ m_2^{\ast} = |P_{\ast}P_2|^{2-L} \left| \begin{array}{ccc} 1 & 1 & 1 \\ x_1 & x_{\ast} & x_3 \\ y_1 & y_{\ast} & y_3 \end{array} \right|,\ m_3^{\ast} = |P_{\ast}P_3|^{2-L} \left| \begin{array}{ccc} 1 & 1 & 1 \\ x_1 & x_2 & x_{\ast} \\ y_1 & y_2 & y_{\ast} \end{array} \right| $$ функция $$ F(x,y) = \sum_{j=1}^3 m_{j}^{\ast} |PP_j|^L $$ имеет стационарную точку $ P_{\ast}=(x_{\ast},y_{\ast}) $. При этом $$ F(x_{\ast},y_{\ast})= \left| \begin{array}{cccc} 1 & 1 & 1 & 1\\ x_{\ast} & x_1 & x_2 & x_3 \\ y_{\ast} & y_1 & y_2 & y_3 \\ x_{\ast}^2+y_{\ast}^2 & x_1^2+y_1^2 & x_2^2+y_2^2 & x_3^2+y_3^2 \end{array} \right| \ . $$

Доказательство фактически повторяет приведенное ☞ ЗДЕСЬ.

Результат предыдущей теоремы позволяет существенно упростить решение «прямой» задачи.

Теорема [12, 13].Обозначим

$$ S_1(x,y)= \left| \begin{array}{ccc} 1 & 1 & 1 \\ x & x_2 & x_3 \\ y & y_2 & y_3 \end{array} \right|,\ S_2(x,y)= \left| \begin{array}{ccc} 1 & 1 & 1 \\ x_1 & x & x_3 \\ y_1 & y & y_3 \end{array} \right|,\ S_3(x,y)= \left| \begin{array}{ccc} 1 & 1 & 1 \\ x_1 & x_2 & x \\ y_1 & y_2 & y \end{array} \right| \, . $$ Любое решение системы $$ \partial F / \partial x = 0, \partial F / \partial y = 0 \ , $$ отличное от $ \{ P_j \} $, удовлетворяет соотношению $$ m_1:m_2:m_3=|PP_1|^{2-L} S_1(x,y):|PP_2|^{2-L} S_2(x,y):|PP_3|^{2-L} S_3(x,y) \ . $$ В случае, когда $ L_{} $ четно, вторая система ни чем не лучше первой: степени получающихся алгебраических уравнений одинаковы. Но вот в случае, когда $ L_{} $ — нечетно (как в случае кулоновского потенциала), преимущество второй системы становится очевидным: избавиться от радикалов можно однократным возведением в квадрат.

Для нечетных значений $ L\in \mathbb Z $ стационарные точки функции $ F_{} $ удовлетворяют системе алгебраических уравнений

$$ \left\{ \begin{array}{ll} m_2^2S_1^2(x,y) |PP_1|^{2(2-L)} - m_1^2S_2^2(x,y) |PP_2|^{2(2-L)} & =0, \\ m_2^2S_3^2(x,y) |PP_3|^{2(2-L)} - m_3^2S_2^2(x,y) |PP_2|^{2(2-L)} & =0. \end{array} \right. $$

Пример. В рассмотренном выше примере функции

$$ F(x,y)=\frac{1}{\sqrt{(x-1)^2+(y-1)^2}}+ \frac{m_2}{\sqrt{(x-5)^2+(y-1)^2}}+\frac{m_3}{\sqrt{(x-2)^2+(y-6)^2}} $$ предложенный алгоритм приводит к системе $$ \widetilde F_1(x,y,m_2,m_3)=0,\ \widetilde F_2(x,y,m_2,m_3)=0 \ , $$ при $$ \begin{array}{c} \widetilde F_1(x,y,m_2,m_3)= \\ =m_2^2\,(5\,x+3\,y-28)^2(x^2+y^2-2\,x-2\,y+2)^3 -(5\,x-y-4)^2(x^2+y^2-10\,x-2\,y+26)^3 , \\ \widetilde F_2(x,y,m_2,m_3)= \\ =m_2^2\,(4\,y-4)^2(x^2+y^2-4\,x-12\,y+40)^3 -m_3^2\,(5\,x-y-4)^2(x^2+y^2-10\,x-2\,y+26)^3. \end{array} $$ Здесь $ \deg \widetilde F_1 = \deg \widetilde F_2 =8 $ относительно переменных $ x_{} $ и $ y_{} $; это можно считать существенным успехом в сравнении с $ 28 $-й степенью уравнений, полученных в ходе первоначального решения.

Допустим, мы хотим исследовать динамику множества вещественных решений этой системы при различных фиксированных значениях $ m_2 $ и для произвольных значений $ m_3 $. Для получения неявного задания кривой $$ H(x,y,m_2) = 0 \ , $$ которая будет состоять из решений системы при всевозможных значениях $ m_3 $, мы должны исключить этот параметр из системы. Но он, фактически, уже исключен: первое уравнение от него не зависит! Иными словами, утверждается, что уравнение $$ m_2^2\,(5\,x+3\,y-28)^2(x^2+y^2-2\,x-2\,y+2)^3 -(5\,x-y-4)^2(x^2+y^2-10\,x-2\,y+26)^3=0 $$ при каждом фиксированном значении $ m_{2}=m_{2\ast} $ определяет на плоскости $ (x,y) $ кривую, целиком состоящую из стационарных точек семейства кулоновских потенциалов $$ \left\{ \frac{1}{\sqrt{(x-1)^2+(y-1)^2}}+ \frac{m_{2\ast}}{\sqrt{(x-5)^2+(y-1)^2}}+\frac{m_3}{\sqrt{(x-2)^2+(y-6)^2}} \right\}_{m_3 \in \mathbb R} \ . $$ Изобразим несколько таких кривых на рисунке (числа на кривых обозначают величины $ m_2 $; ветви одинакового цвета соответствуют одинаковым значениям этого заряда).

♦

Более подробное исследование этой задачи ☞ ЗДЕСЬ.

☞ ЗДЕСЬ.

.

При составлении настоящего раздела существенно использовалось содержание обзорной статьи

[*] . Martini H. Fermat-Torricelli problem. Encyclopedia of Mathematics. Supplement III. Kluwer Academic Publishers. 2001, C.149-151

[1]. Weber A. Über den Standort der Industrien. Teil I: Reine Theorie des Standorts. J.C.B.Mohr, 1909. Tübingen.
Вебер А. Теория размещения промышленности. М.-Л. «Книга». 1926. (На самом деле, последняя книга — не перевод оригинальной книги Вебера, а изложение ее содержания переводчиком Н.Морозовым¹²⁾).

[2]. Дингельдэй Фр. Сборникъ задачъ по приложенiю дифференцiальнаго и интегральнаго исчисленiй. С.-Петербург. 1912

[3]. Курант Р., Роббинс Г. Что такое математика? М.МЦНМО. 2004

[4]. Протасов В.Ю. Максимумы и минимумы в геометрии. М.МЦНМО. 2005

[5]. Уланов Е.А., Утешев А.Ю. Аналитическое решение обобщенной задачи Ферма-Торричелли-Штейнера./ / Процессы управления и устойчивость: Труды 42-й международной научной конференции аспирантов и студентов / Под ред. А. С. Ерёмина, Н. В. Смирнова. СПб.: Издат. Дом С.-Петерб. гос. ун-та, 2011. С. 201–206.

[6]. Launhardt W. Kommercielle Tracirung der Verkehrswege. Zeitschrift f. Architekten u.Ingenieur-Vereinis im Königreich Hannover. V. 18, pp. 516-534, 1872. Текст ☞ ЗДЕСЬ.

[7]. Maxwell J.C. Paper on the Description of Oval Curves. Observations on Circumscribed Figures Having a Plurality of Foci, and Radii of Various Proportions. 1846. «The Scientific Letters and Papers of James Clerk Maxwell: 1846-1862» Vol. 1, Cambridge University Press. 1990

[8]. Maxwell J.C. A Treatise on Electricity and Magnetism. Vol. 1. Dower, New York. 1954

[9]. Maxwell J.C. On Governors. Proc. Royal Soc. London. 1868, V.16: pp. 270–283.

[10]. Sturm R. Über die Punkte kleinster Entfernungssumme von gegebenen Punkten. J. Reine Angew. Math., V. 97, pp.49-61, 1884.

[11]. Uteshev A.Yu. Analytical Solution for the Generalized Fermat-Torricelli Problem. Amer.Math.Monthly. V. 121, N 4, pp.318-331, 2014. Текст ☞ ЗДЕСЬ (pdf).

[12]. Uteshev A.Yu., Yashina M.V. Stationary Points for the Family of Fermat-Torricelli-Coulomb-like potential functions. Proc. 15th Workshop CASC (Computer Algebra in Scientific Computing), Berlin 2013. Springer. Lecture Notes in Computer Science. V.8136 pp. 412-426, 2013.

[13]. Uteshev A.Yu., Yashina M.V. On Maxwell’s Conjecture for Coulomb Potential Generated by Point Charges. Springer. Transactions on Computational Sciences XXVII. Lecture Notes in Computer Science. V. 9570, pp. 68-80, 2016. Текст ☞ ЗДЕСЬ (pdf)

[14]. Weiszfeld E. Sur le point pour lequel la somme des distances de $ n_{} $ points donnés est minimum. Tohoku Math. Journal. V. 43, pp. 355–386, 1937.

[15]. Gabrielov A., Novikov D., Shapiro B. Mystery of Point Charges. Proc. London Math. Soc. Ser. 3. V. 95, pp. 443-472, 2007.