$$ F(P) = m_1 |PP_1|+\dots+ m_K |PP_K| \to \min_{P\in \mathbb R^n} $$

$$ \{P_1,\dots,P_K\} \subset \mathbb R^n,\ \{m_1,\dots,m_K\} \subset \mathbb R_{+} $$

$$ | \cdot | - \mbox{ евклидово расстояние } $$

$$ F(x,y)= \sum_{j=1}^{3} \sqrt{(x-x_j)^2+(y-y_j)^2} \to \min_{(x,y)\in \mathbb R^2} $$

Декарт, 1638 => Ферма => (Мерсенн ?) => Торричелли, Фаньяно, Симпсон,...

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.

$$ F(x,y)= \sum_{j=1}^{3} m_j \sqrt{(x-x_j)^2+(y-y_j)^2} \to \min_{(x,y)\in \mathbb R^2} $$

Штейнер, Лаунхардт, Вебер,...

$$ F(P) = \frac{m_1}{|PP_1|}+\dots+ \frac{m_K}{|PP_K|} $$

$$ \{P_1,\dots,P_K\} \subset \mathbb R^n,\ \{m_1,\dots,m_K\} \subset \mathbb R $$

$$ | \cdot | - \mbox{ евклидово расстояние } $$

Кулоновский или ньютоновский потенциал

? Стационарные точки $ F(P) $ (положения равновесия) ?

$$ F(P) = m_1|PP_1|^L+\dots+ m_K|PP_K|^L $$

$$ 0\ne L \in \mathbb R $$

$$ \begin{array}{c} P_1 \\ m_1 \end{array} ; \dots ; \begin{array}{c} P_K \\ m_K \end{array} \qquad \qquad \mbox{ конфигурация весов } $$

$$ F(P) = m_1 |PP_1|+\dots+ m_K |PP_K| \to \min_{P\in \mathbb R^2} $$

Теория оптимального размещения (location theory, location analysis).

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

Для производства $ 1_{} $ тонны стали необходимо иметь $ m_{1} $ тонн руды, $ m_2 $ тонн угля и $ m_3 $ тонн воды.

Где расположить сталелитейное производство так, чтобы минимизировать транспортные издержки ?

Положим, мы имеем перед собой производство, работающее с двумя локализованными материалами, причем для выработки $ 1_{} $ т. продукта требуется $ 3/4 $ т. одного материала и $ 1/2 $ т. другого. В таком случае мы получаем штандортную фигуру, на «материаль­ных компонентах» (линиях, соединяющих штандорт с «материаль­ными складами») которого передвигаются веса в $ 3/4 $ и $ 1/2 $, в то время как «потребительская компонента» отягощена $ 1_{} $.
Альфред Вебер (1909)

Сети Штейнера

Только для плоского случая. Circinus et regula ((лат.) циркуль и линейка)

$ m_1=m_2=m_3=1 $, Торричелли , 1642

Точка Ферма - Торричелли

$ \{m_1,m_2,m_3\} \subset \mathbb R_{+} $, Лаунхардт , 1872

$ m_1=m_2=m_3=m_4=1 $, Штейнер , 1850

Точка пересечения диагоналей четырехугольника $ P_1P_2P_3P_4 $.

Только для плоского случая.

Минимум $$ F(P)=\sum_{j=1}^K m_j |PP_j| $$ существует и единствен.

1. Если $ \exists 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) = F(P_{i}) \ . $$

2. Если $ \forall 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) = F(P_{\ast}) , $$ где $ 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 $.

Вайсфельд , 1937 : $ \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}, $$ $$ \Updownarrow $$ $$ 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^{(k)}=\Phi(P^{(k-1)}) \to P_{\ast} $$

$$ F(x,y)= \sum_{j=1}^{K} m_j\sqrt{(x-x_j)^2+(y-y_j)^2} \ , $$

$$ F(x,y)=const \ . $$

$ K=2 $ — овалы Декарта.

$$ P_1=(1,1),P_2=(3,5),P_3=(7,2) $$

$$ K\ge 3, m_1:m_2:\dots:m_K= \mbox{ рациональное } \ : \ \mbox{ рациональное } \ : \dots \ : \ \mbox{ рациональное } $$

Чирнгауз, Максвелл...

$ K=3, m_1=m_2=m_3 $ — изодапаны((др.греч.) $ \iota \sigma o \varsigma $ — равный, $ \delta \breve{\alpha} \pi \acute{\alpha} \nu \alpha $ — расходование, расход, трата; isodapane (англ.), А.Вебер); кривая состоит из точек одинаковой суммарной стоимости транспортных перевозок до них из $ \{P_j\} $.

$$ \{P_1,\dots,P_K\} \subset \mathbb R^2 $$

Построить минимальное дерево Штейнера: связную систему $ \mathbf L_{} $ прямолинейных отрезков:

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

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

$$ P_1=(2,1) , P_2=(1,6) , P_3=(8,7) , P_4=(6,1) $$ решение задачи заключается в построении двух точек $ T_{1} $ и $ T_{2} $, таких, что они являются точками Ферма-Торричелли для, соответственно, треугольников $ P_1P_2T_2 $ и $ P_3P_4T_1 $. $$ T_1 \approx (2.91184,\ 2.49410) \ , T_2 \approx (5.21583,\ 2.43798) \ . $$ $$ |P_1P_3|+|P_2P_4|\approx 15.55634 \ ;\ $$ $$ | \mathbf{L} |= |P_1T_1|+|P_2T_2|+|P_3T_2|+|P_4T_2|+|T_1T_2| \approx 15.03073 \ . $$

$$ P_4=(6,4) $$

$$ F(x,y)=\sum_{j=1}^3 m_j \sqrt{(x-x_j)^2+(y-y_j)^2} $$

Обозначим величину угла треугольника $ P_{1}P_2P_3 $ при вершине $ P_{j} $ через $ \alpha_j $. Если нарушено $ j $-е из трех условий $$ \ m_2^2+m_3^3+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\, , $$ то $$ \min F(x,y) = F(x_j,y_j) \ . $$

Если все неравенства выполняются, то $$ \min F(x,y) = F(x_{\ast},y_{\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. $$

$$ F(P)=\sum_{j=1}^K m_j |PP_j| $$ Подобрать $ \{m_j\}_{j=1}^K $: $$ \min F(P)= F(P_{\ast}), \qquad P_{\ast} \not\in \{P_j\}_{j=1}^K . $$

$$ 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}) $. $$ 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| \ . $$

Найти стационарные точки функции $$ F(P)= \sum_{j=1}^K \frac{m_j}{\left|PP_j \right|} \ . $$

$$ \{P,P_1,\dots,P_K\} \subset \mathbb R^3 $$

Гипотеза Максвелла . Число стационарных точек $ \le (K-1)^2 $. Не доказана.

$$ P_1=(1,1), P_2=(5,1) , P_3=(2,6) . $$ Cтационарные точки функции $$ 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}} $$

$$ \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} $$ $$ \Updownarrow $$ Обозначим $ 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} $ — полиномы $ \deg F_j=28 $, коэффициенты ~ $ 10^{19} $.

Число стационарных точек — от $ 2_{} $ до $ 4_{} $, в зависимости от $ m_2,m_3 $.

$$ F(P) = m_1|PP_1|^L+\dots+ m_K|PP_K|^L $$

Задача управления: подобрать $ \{m_j\} $ так, чтобы $ F(P) $ имела стационарную точку в заданной точке $ P_{\ast} $.

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

$$ 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 \ , $$ $$ \Downarrow $$ $$ 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) \ . $$

Cтационарные точки функции $ 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}} $$ $$ \Downarrow $$ $$ \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} $$ $$ \Downarrow $$ Исключение переменной $ x_{} $ $$ \mathcal Y(y,m_2,m_3)=\mathcal R_{x}(\tilde F_1,\tilde F_2), \ \deg_y \mathcal Y = 34 $$

$$ m_2=2, m_3=2 \quad \Rightarrow \quad \mathfrak S_1 \approx (2.666216,\, 1.234430),\ \mathfrak S_2 \approx (2.744834,\, 3.244859) ; $$ $$ m_2=2, m_3=4 \quad \Rightarrow \quad \mathfrak S_1 \approx (1.941246,\, 2.552370) , \mathfrak S_2 \approx (2.655622,\, 1.638871) ,\ \mathfrak S_3 \approx (3.330794,\ 2.826444), $$ $$ \mathfrak N \approx (2.552939,\, 2.271691) \ . $$

Граница на плоскости $ (m_2,m_3) $ между двумя областями? $$ \Psi (m_2,m_3) = 0 $$ — ровно $ 3 $ стационарных точки (одна вырождена) $$ \Psi(m_2,m_3)= $$ $$ =3^{36}(64\,m_3^2+192\,m_2m_3+169\,m_2^2)^5(64\,m_3^2-192\,m_2m_3+169\,m_2^2)^5(28561\,m_2^4+19968\,m_2^2m_3^2+4096\,m_3^4)^7 $$ $$ + \dots + $$ $$ + 2^2\cdot 3^{31} \cdot 17^{40} (5545037166327\, m_2^4-161882110764644\,m_2^2m_3^2+1656772227072\,m_3^4) $$ $$ + 2^3\cdot 3^{36}\cdot 17^{44} (51827\,m_2^2+28112\,m_3^2)+ 3^{36}\cdot 17^{48} \ . $$