УказательРазделыОбозначенияАвторО проектеEnglish version


Вспомогательная страница к разделу ВЫЧИСЛЕНИЕ РАССТОЯНИЙ МЕЖДУ ГЕОМЕТРИЧЕСКИМИ ОБЪЕКТАМИ.


Благодарю Б.З.Тайбина за обнаружение 03.06.10 ошибки на настоящей странице и информирование о ней.


Задача Ферма-Торричелли и ее развитие

Обобщенная задача Ферма-Торричелли

Задача. Пусть заданы координаты 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 обычно считаются положительными и называются весами.

§

Задача известна под различными названиями: обобщенная задача Ферма-Торричелли, задача Ферма-Торричелли-Штейнера, задача Вебера, задача о взвешенной геометрической медиане.

Будем говорить о наборе

\begin{array}{c} P_1 \\ m_1 \end{array} ; \dots ; \begin{array}{c} P_K \\ m_K \end{array}

как о конфигурации весов.

Плоский случай

Рассмотрим сначала плоский вариант задачи: пусть 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} \ .
§

В этом случае поставленная задача называется задачей об оптимальном расположении (узловой) станции1), или — в случае K=3задачей о трёх заводах.

П

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

§

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

Каков должен быть первый общий подход к отысканию таких пунктов? С угловыми вершинами штандортной фигуры штандорт связан линиями — их Вебер называет «компонентами»,— по которым и происходит передвижение соответствующих тяжестей. Положим, что мы имеем перед собой производство, работающее с двумя локализованными материалами, причем на выработку 1_{} тонны продукта требуется 3/4 тонны одного материала и 1/2 тонны другого. В таком случае мы получаем штандортную фигуру, на «материаль­ных компонентах» которой передвигаются веса в 3/4 и 1/2, в то время как «потребительская компонента» отягощена 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 ... 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 г.5). для случая K=3 точек и одинаковых весов m_1=m_2=m_3=1 (классическая задача Ферма-Торричелли). Алгоритм предлагал нахождение точки P_{\ast} в идеологии классической геометрии: circinus et regula6). На сторонах треугольника 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} \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 (|PP_1|+|PP_2|+|PP_3|). Если величина одного из углов треугольника больше или равна 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} \sum_{j=1}^3 m_j|PP_j| \ .

В предыдущих рассуждениях предполагается, что точка P_{\ast} лежит внутри треугольника P_{1}P_2P_3. В противном случае, решением задачи будет одна из вершин треугольника.

П

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

\begin{array}{c} P_{1}=(2,6) \\ m_{1}=2 \end{array}\ ; \ \begin{array}{c} P_{2}=(1,1) \\ m_{2}=3 \end{array} \ ; \ \begin{array}{c} P_{3}=(5,1) \\ m_{3}=4 \end{array} \ .

Решение. Здесь |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} образуют выпуклый четырехугольник, то минимум суммы расстояний

|PP_1|+|PP_2|+|PP_3|+|PP_{4}|

достигается в точке P_{\ast}, лежащей на пересечении диагоналей четырехугольника. Если же точки 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| \ .

§

|S|= 2 \times площадь треугольника P_{1}P_2P_3.

П

Пример. При 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-е из трех условий

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

то минимум функции

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.

П

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

\begin{array}{c} P_{1}=(2,6) \\ m_{1}=2 \end{array}\ ; \ \begin{array}{c} P_{2}=(1,1) \\ m_{2}=3 \end{array} \ ; \ \begin{array}{c} P_{3}=(5,1) \\ m_{3}=4 \end{array} \ .

точка P_{\ast} имеет координаты

x_{\ast}=\frac{1}{2866} \left( 4103+1833 \sqrt{15} \right)\approx 3.9086 , \ y_{\ast} =\frac{1}{8598} \left( 29523-4481 \sqrt{15} \right)\approx 1.4152 \quad .

Минимальное значение для функции:

\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 \, .

§

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

Аналитическое решение: исключение переменных

§

Для понимания материалов этого пункта существенно потребуется материалы пункта "Исключение переменных в системе полиномиальных уравнений".

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

П

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

\begin{array}{c} P_{1}=(1,1) \\ m_{1}=1 \end{array}\ ; \ \begin{array}{c} P_{2}=(3,5) \\ m_{2}=1 \end{array} \ ; \ \begin{array}{c} P_{3}=(7,2) \\ m_{3}=1 \end{array} \ ; \ \begin{array}{c} P_{4}=(6,6) \\ m_{4}=m \end{array}

в зависимости от изменения параметра m_{}.

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

Градиентную систему уравнений

\left\{ \begin{array}{lll} \displaystyle \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 \\ \displaystyle \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{P-P_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_j-P_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_j-P_i}{|P_jP_i|} \right| > m_i \ ,

то \min F(P) достигается в точке P_{\ast}, удовлетворяющей градиентной системе уравнений

\sum_{j=1}^K m_j \frac{P-P_j}{|PP_j|}=\mathbb O_{n\times 1}\, ;

и, в этом случае, P_{\ast} \not\in \{P_j\}_{j=1}^K.

П

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

\begin{array}{c} P_{1}=(1,1) \\ m_{1}=1 \end{array}\ ; \ \begin{array}{c} P_{2}=(3,5) \\ m_{2}=1 \end{array} \ ; \ \begin{array}{c} P_{3}=(7,2) \\ m_{3}=1 \end{array} \ ; \ \begin{array}{c} P_{4}=(6,6) \\ m_{4}=m \end{array}

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

§

Заметим, что попадание точки P_{\ast} в вершину P_{i} происходит при значениях m_{i} меньших, чем сумма оставшихся весов.

=>

В случае 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| \ .

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

§

Решение обратной задачи определяется с точностью до сомножителя, т.е. тройка решений (m_1,m_2,m_3) определяется отношением m_1:m_2:m_3. С учетом этого обстоятельства, решение обратной задачи единственно.

П

Пример. Поместить в точках 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 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 — яйцеобразные кривые Чирнгауза7). Они могут считаться алгебраическими кривыми — последовательным возведением их уравнений в квадрат можно избавиться от радикалов.

П

Пример. Для 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 кривые известны в экономической географии под названием изодапан8); каждая такая кривая состоит из точек одинаковой суммарной стоимости транспортных перевозок до них из \{P_j\}.

A

Анимация трехмерного аналога мультифокусного эллипса ЗДЕСЬ (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_{}. Поставленной задаче можно придать физический смысл. Пусть в пространстве имеется конфигурация

\begin{array}{c} P_1 \\ m_1 \end{array} ; \dots ; \begin{array}{c} P_K \\ m_K \end{array}

из K_{} фиксированных (неподвижных) точечных заряженных частиц, которые воздействуют на пробный точечный единичный заряд величины, помещенный в точку P_{}; при этом сила воздействия j_{}-го заряда прямо пропорциональна величине заряда m_{j} и пропорциональна некоторой степени L_{} расстояния от этого заряда до пробного. Требуется найти точку P_{\ast} \in \mathbb R^{n}_{}, при помещении в которую пробного заряда, последний будет неподвижен (находиться в положении равновесия).

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

Стационарные точки этого семейства потенциалов задаются градиентной системой уравнений

\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]. Число стационарных точек кулоновского поля любой конфигурации K_{} стационарных зарядов в \mathbb R^3 не превосходит (K-1)^2. Не доказана10).

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

Т

Теорема [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| \ .

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

§

Подчеркнем, что, фактически, этот результат решает задачу теории управления: подбором параметров системы удается обеспечить наперед заданное положение равновесия в кулоновском (ньютоновском) поле. Тут же возникает (традиционный для теории управления) вопрос об устойчивости полученного равновесия, т.е., иными словами, о том является ли полученная стационарная точка точкой минимума для потенциала. Пока отложим ответ на этот вопрос, заметив — исключительно из соображений исторического сюрприза, что теория управления возникла из задачи, которую сформулировал в 1868 г. один ученый, фамилию которого наблюдательный читатель настоящего раздела легко угадает! Намек: Эдвард Раус (Edward John Routh) — один из авторов критерия Рауса-Гурвица — был однокурсником этого ученого.

§

Для случая L=1 стационарная точка потенциала (Ферма-Торричелли) единственна для каждого фиксированного набора значений весов. Решение обратной задачи тоже было единственным — с точностью до домножения вектора весов (m_1^{\ast},m_2^{\ast},m_3^{\ast} ) на сомножитель. Для других показателей L_{} стационарных точек у соответствующих потенциалов может быть несколько. Примером может являться случай кулоновского потенциала L=-1. Наряду с точкой P_{\ast}, гарантированной условием теоремы, будет существовать еще, по крайней мере, одна «посторонняя» стационарная точка \tilde P_{\ast}. Следовательно, решение обратной задачи определяется не единственным образом: существует набор весов (\widetilde{m}_1^{\ast},\widetilde{m}_2^{\ast},\widetilde{m}_3^{\ast}), обеспечивающий стационарность точки \tilde P_{\ast} и непропорциональный набору (m_1^{\ast},m_2^{\ast},m_3^{\ast}).

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

Т

Теорема [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. Для получения неявного задания кривой

\Eta (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 Industrie. Teil I: Reine Theorie des Standorts. J.C.B.Mohr, 1909. Tübingen.
Вебер А. Теория размещения промышленности. М.-Л. «Книга». 1926. (На самом деле, последняя книга — не перевод оригинальной книги Вебера, а изложение ее содержания переводчиком Н.Морозовым11)).

[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. Препринт arXiv:1208.3324v1 (220 Kb)

[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.

[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.

1) (нем.) Problem des Knotenpunktes [4].
2) Launhardt Carl Wilhelm Friedrich (1832—1918), немецкий экономист; биография ЗДЕСЬ.
3) Weber Alfred (1868-1958), немецкий экономист и социолог; брат известного социолога, историка и экономиста Макса Вебера. Среди его учеников был и писатель Франц Кафка.
4) Standort (нем.)
5) Предполагается, что задача Ферма «пропутешествовала» в Италию с Мареном Мерсенном (Mersenne Marin, 1588-1648); роль последнего как организатора европейской науки Нового времени огромна, см. ЗДЕСЬ
6) (лат.) Циркуль и линейка.
7) Один из американских авторов остроумно перевел это выражение как egglipse; если аналогичным приемом переводить на русский получится яйлипс :-O
8) (др.греч.) \iota \sigma o \varsigma — равный, \delta \breve{\alpha} \pi \acute{\alpha} \nu \alpha — расходование, расход, трата; isodapane (англ.), термин введен А.Вебером.
9) В последнем случае потенциал равен (-F(P)).
10) По состоянию на 2014 г.
11) Отождествить переводчика вот с этим человеком не удалось

2016/09/07 10:58 редактировал au