☞ **((:matricese/optimize/distancee/torri_e English version))** !!§!! Вспомогательная страница к разделу ((algebra2:optimiz:distance ВЫЧИСЛЕНИЕ РАССТОЯНИЙ МЕЖДУ ГЕОМЕТРИЧЕСКИМИ ОБЪЕКТАМИ)). Благодарю **Б.З.Тайбина** за обнаружение 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 $ обычно (и практически везде в настоящем разделе) считаются положительными и называются **весами**. Задача известна под различными названиями: //обобщенная задача Ферма-Торричелли//, //задача Ферма-Торричелли-Штейнера//, //задача Вебера//, задача о ((http://en.wikipedia.org/wiki/Geometric_median взвешенной геометрической медиане)). Будем говорить о наборе $$ \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} \ . $$ В этом случае поставленная задача называется //задачей об оптимальном расположении (узловой) станции//[[ (//нем.//) Problem des Knotenpunktes ((#источники [4])).]], или --- в случае $ K=3 $ --- //задачей о трёх заводах.// !!П!! **Пример.** В городах $ P_{1},P_2,P_3 $ расположены источники полезных ископаемых: железной руды, угля и воды соответственно. Известно, что для производства одной тонны стали необходимо иметь $ m_{1} $ тонн руды, $ m_2 $ тонн угля и $ m_3 $ тонн воды. В предположении, что стоимость перевозки одной тонны груза не зависит от его природы, где следует расположить сталелитейное производство так, чтобы минимизировать транспортные издержки? {{ algebra2:optimiz:distance:factory.png |}} С конца XIX века подобные задачи стали предметом изучения в экономической географии. Систематические исследования были начаты Вильгельмом **Лаунхардтом**[[**Launhardt** Carl Wilhelm Friedrich (1832—1918), немецкий экономист; биография ☞ ((https://ru.wikipedia.org/wiki/%D0%9B%D0%B0%D1%83%D0%BD%D1%85%D0%B0%D1%80%D0%B4%D1%82,_%D0%92%D0%B8%D0%BB%D1%8C%D0%B3%D0%B5%D0%BB%D1%8C%D0%BC ЗДЕСЬ)).]]((#источники [6])) и позднее развиты Альфредом **Вебером**[[**Weber** Alfred (1868-1958), немецкий экономист и социолог; брат известного социолога, историка и экономиста Макса Вебера. Среди его учеников был и писатель Франц Кафка. Биография ☞ ((https://ru.wikipedia.org/wiki/%D0%92%D0%B5%D0%B1%D0%B5%D1%80,_%D0%90%D0%BB%D1%8C%D1%84%D1%80%D0%B5%D0%B4 ЗДЕСЬ))]]((#источники [1])) . Последний ввел понятие **штандорта**[[Standort (//нем.//)]] --- оптимального места размещения производства, "склада". Каков должен быть первый общий подход к отысканию таких пунктов? С угловыми вершинами штандортной фигуры штандорт связан линиями --- их Вебер называет «компонентами»,--- по которым и происходит передвижение соответствующих тяжестей. Положим, что мы имеем перед собой производство, работающее с двумя локализованными материалами, причем на выработку $ 1_{} $ тонны продукта требуется $ 3/4 $ тонны одного материала и $ 1/2 $ тонны другого. В таком случае мы получаем штандортную фигуру, на «материаль­ных компонентах» которой передвигаются веса в $ 3/4 $ и $ 1/2 $, в то время как «потребительская компонента» отягощена $ 1_{} $. {{ matricese:optimize:distancee:weber_tree3.png |}} В XX веке эти задачи выделились в подраздел ((http://ru.wikipedia.org/wiki/%D0%98%D1%81%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%BE%D0%BF%D0%B5%D1%80%D0%B0%D1%86%D0%B8%D0%B9 теории исследования операций)), известный в настоящее время как ((http://en.wikipedia.org/wiki/Facility_location_problem 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. $$ Система эта нелинейная и даже ((:polynomialm#алгебраические_уравнения неалгебраическая)) относительно $ 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} $. {{ algebra2:optimiz:distance:torri:picture21.png |}} Интуитивно понятно также, что если вес $ m_{i} $, приложенный сквозь отверстие $ P_{i} $, окажется много большим оставшихся весов, то узел затянется именно в это отверстие. Оказывается при возрастании $ m_{i} $ такое затягивание произойдет __раньше__ выполнения условия $ m_i = \displaystyle \sum_{j\ne i} m_j $. См. ☟ ((#существование_и_единственность_решения НИЖЕ)). ====Геометрическое решение== {{algebra2:optimiz:distance:geometry_torri1.jpg |}} Известно для случая $ K=3 $ точек на плоскости для произвольных значений весов $ \{ m_j \} $ и для случая $ K=4 $ точек в случае одинаковых весов. Исторически самое первое из известных решений задачи было предложено Торричелли в период до 1640 г.[[Предполагается, что задача Ферма "пропутешествовала" в Италию с Мареном Мерсенном (Mersenne Marin, 1588-1648); роль последнего как организатора европейской науки Нового времени огромна, см. ☞ ((http://krotov.info/history/17/1670/elizarov.htm ЗДЕСЬ))]]. для случая $ 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} \ . $$ Аналогичные равенства справедливы и для синусов оставшихся пар углов. {{ algebra2:optimiz:distance:angles1.jpg|}} Отсюда получаем условие, которое должно выполняться в искомой точке $ 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) $ точка Ферма-Торричелли изображена на рисунке {{ algebra2:optimiz:distance:torri_point.jpg |}} Ее точные координаты приведены ☟ ((#analiticheskoe_resheniekoordinaty_tochki_ferma-torrichelli НИЖЕ)) . ♦ ---- Вернемся к рассмотрению общего случая неравных весов. На стороне $ P_{2}P_3 $ треугольника $ P_{1}P_2P_3 $ строится треугольник $ P_2P_3Q $, в котором {{ algebra2:optimiz:distance:weight_tri1.png|}} $$ |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} $. В самом деле (см. рисунок ниже), по ((http://ru.wikipedia.org/wiki/%D2%E5%EE%F0%E5%EC%E0_%F1%E8%ED%F3%F1%EE%E2 теореме синусов)) для треугольника $ 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 $). {{ algebra2:optimiz:distance:torri_point_gen.jpg |}} Её координаты: $ \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 $. Точные значения приведены ☟ ((#analiticheskoe_reshenie_obobschennoj_zadachi_ferma-torrichelli НИЖЕ)). ♦ ---- Для $ 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| \ . $$ $ |S|= 2 \times $ ((:dets:geometry#площади площадь треугольника)) $ 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 $-//е из трех условий// \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 \, . $$ ♦ Если выписать символьные представления для $ x_{\ast} $ и $ y_{\ast} $ в виде функций от параметров $ \{x_j,y_j,m_j\}_{j=1}^3 $, то можно осуществить сокращение на общий множитель $ |S| $ в числителе и в знаменателе получившихся в теореме дробей. Правда, результат такого сокращения выглядит довольно громоздко: см. ☞ ((:algebra2:optimiz:distance:torri:altern ЗДЕСЬ)). ====Аналитическое решение: исключение переменных== Для понимания материалов настоящего пункта крайне желательно ознакомиться с пунктом ((:dets:resultant#исключение_переменных_в_системе_полиномиальных_уравнений "Исключение переменных в системе полиномиальных уравнений")). В случае $ K>3 $ точек аналитическое решение для обобщенной задачи Ферма-Торричелли вряд ли может быть получено. Тем не менее, можно попытаться продвинуться аналитикой возможно дальше, именно: свести поиск координаты точки $ P_{\ast} $ к решению системы ((:polynomialm#алгебраические_уравнения полиномиальных (алгебраических) уравнений)) и попытаться применить к этой системе методы исключения переменных. !!П!! **Пример.** Выяснить динамику поведения точки $ 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_{} $ по обеим переменным. Из этой системы, посредством вычисления ((:dets:resultant результанта)), можно исключить переменные $ x_{} $ или $ y_{} $ и получить алгебраические уравнения вида $$ \mathcal X(x,m)=0, \ \mathcal Y(y,m)=0, $$ которым удовлетворяют координаты стационарных точек при каждом фиксированном значении $ m_{} $. Оказывается, эти уравнения можно упростить (отбросить посторонние сомножители), сведя к уравнениям степени $ 12 $ по каждой из переменных $ x_{} $ или $ y_{} $. Их выражения ☞ ((:algebra2:optimiz:distance:torri:vspom1 ЗДЕСЬ)). Дальнейшее упрощение вряд ли возможно: уравнения неприводимы над $ \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 $ целиком достаточно сложны: см. ☞ ((:algebra2:optimiz:distance:torri:vspom1 ЗДЕСЬ)). На рисунке выделена только ветвь, которая соответствует реальной динамике стационарной точки. {{ algebra2:optimiz:distance:4pointspl1.jpg |}} "Контрольные" точки на этой ветви: 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 $. **Доказательство** ☞ ((:algebra2:optimiz:distance:torri:exist ЗДЕСЬ)) !!П!! **Пример.** При каких значениях параметра $ 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 $. Заметим, что попадание точки $ 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])). {{ algebra2:optimiz:distance:fig1.jpg |}} Обозначим углы этого треугольника $ \beta_1, \beta_2, \beta_3 $ в соответствии с рисунком. Тогда, по ((http://ru.wikipedia.org/wiki/%D2%E5%EE%F0%E5%EC%E0_%EA%EE%F1%E8%ED%F3%F1%EE%E2 теореме косинусов)), получаем: $$ \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)} \, . $$ Решать последнюю систему будем ((http://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BF%D1%80%D0%BE%D1%81%D1%82%D0%BE%D0%B9_%D0%B8%D1%82%D0%B5%D1%80%D0%B0%D1%86%D0%B8%D0%B8 методом простой итерации)). Возьмем в качестве начального приближения произвольную точку $ 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| \ . $$ **Доказательство** теоремы, а также геометрический смысл величин из ее формулировки ☞ ((:algebra2:optimiz:distance:torri:inverse#плоский_случай ЗДЕСЬ)). Решение обратной задачи определяется с точностью до сомножителя, т.е. тройка решений $ (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 $ ☞ ((:algebra2:optimiz:distance:torri:inverse#пространственный_случай ЗДЕСЬ)). ==Смежные задачи== ===Дерево Штейнера== **Задача.** Пусть заданы точки $ 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) \, . $$ {{ algebra2:optimiz:distance:torri:steiner4-1.png |}} **Решение.** Будем пробовать варианты решения задачи, последовательно добавляя вспомогательные точки. Если не добавлять дополнительных точек вообще, то эта задача относится к классу задач ((https://en.wikipedia.org/wiki/Minimum_spanning_tree построения минимального покрывающего дерева))[[(англ.) Minimum spanning tree]]. В такой постановке решением рассматриваемого примера будет ломаная $ P_1P_2P_3P_4 $ длиной $ 3+4+3=10 $. {{ algebra2:optimiz:distance:torri:steiner4-2.png |}} Если разрешено добавить одну дополнительную точку, то решением задачи, в соответствии с ☝ ((#геометрическое_решение теорему Фаньяно)), будет система из двух диагоналей прямоугольника: {{ matricese:optimize:distancee:steiner4-3-1.png |}} Тем не менее, выигрыша в длине дерева не получим: $ 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) $ {{ matricese:optimize:distancee:steiner4-4-1.png |}} получим суммарную длину равной $ 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_{} $. !!§!! Задача о минимальном дереве Штейнера обсуждается ☞ ((:algebra2:optimiz:distance:torri:tree ЗДЕСЬ)). ===Мультифокусные эллипсы== Для случая $ 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** --- яйцеобразные кривые ((:biogr#чирнгауз Чирнгауза))[[Один из американских авторов остроумно перевел это выражение как //egglipse//; если аналогичным приемом переводить на русский получится //яйлипс// :-O...]]. Они могут считаться ((:polynomialm#случай_двух_переменных алгебраическими кривыми)) --- последовательным возведением их уравнений в квадрат можно избавиться от радикалов. !!П!! **Пример.** Для $ P_1=(1,1),P_2=(3,5),P_3=(7,2) $ семейство трехфокусных эллипсов (алгебраических кривых порядка $ 8_{} $) выглядит так (числа на кривых --- значения константы $ c_{} $): {{ algebra2:optimiz:distance:gen_ellipse3.jpg |}} Каким значениям $ 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 $ кривые известны в экономической географии под названием **изодапан**[[(//др.греч.//) $ \iota \sigma o \varsigma $ --- равный, $ \delta \breve{\alpha} \pi \acute{\alpha} \nu \alpha $ --- расходование, расход, трата; isodapane (//англ//.), термин введен А.Вебером.]]; каждая такая кривая состоит из точек одинаковой суммарной стоимости транспортных перевозок до них из $ \{P_j\} $. !!A!! Анимация трехмерного аналога мультифокусного эллипса ☞ ((:algebra2:optimiz:distance:torri:egglipse ЗДЕСЬ)) (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 я не нашел, за исключением ☞ ((http://mathafou.free.fr/pbg_en/sol143.html ЭТОЙ)). Задача похожа на задачу Фаньяно о построении __произвольного__ треугольника минимального периметра, вписанного в данный остроугольный ((#источники [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}_{} $, при помещении в которую пробного заряда, последний будет неподвижен (находиться в положении равновесия). {{ algebra2:optimiz:distance:coulomb_50.jpg |}} Особый интерес представляет частный случай поставленной задачи: $ L=-1 $. Этому случаю соответствует два физических потенциала --- кулоновский (электростатический) и ньютоновский (гравитационный)[[В последнем случае потенциал равен $ (-F(P)) $.]]. Стационарные точки этого семейства потенциалов задаются градиентной системой уравнений $$ \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_{} $ является ((:polynomialm#алгебраические_уравнения алгебраической)) (или может быть немедленно приведена к алгебраической в случае отрицательных $ 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 $. __Не доказана__[[По состоянию на 2017 г.]]. Что общего у поставленной в начале пункта задачи с обобщенной задачей Ферма-Торричелли? --- То, что похожим образом решается ((#обратная_задача обратная задача)). Рассмотрим сначала плоский случай. !!Т!! **Теорема** ((#источники [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| \ . $$ **Доказательство** фактически повторяет приведенное ☞ ((:algebra2:optimiz:distance:torri:inverse#плоский_случай ЗДЕСЬ)). Подчеркнем, что, фактически, этот результат решает задачу теории управления: подбором параметров системы удается обеспечить наперед заданное положение равновесия в кулоновском (ньютоновском) поле. Тут же возникает (традиционный для теории управления) вопрос об **устойчивости** полученного равновесия, т.е., иными словами, о том является ли полученная стационарная точка **точкой минимума** для потенциала. Пока отложим ответ на этот вопрос, заметив --- исключительно из соображений исторического сюрприза, что теория управления возникла из задачи, которую сформулировал в 1868 г. один ученый, фамилию которого наблюдательный читатель настоящего раздела легко угадает! Намек: Эдвард Раус (Edward John Routh) --- один из авторов ((:dets:resultant критерия Рауса-Гурвица)) --- был однокурсником этого ученого. Для случая $ 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 $. Для получения неявного задания кривой $$ 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 $; ветви одинакового цвета соответствуют одинаковым значениям этого заряда). {{ algebra2:optimiz:distance:torri:figure011.png |}} ♦ !!§!! ''Более подробное исследование этой задачи'' ☞ ((:algebra2:optimiz:distance:torri:coulomb ЗДЕСЬ)). ==Задачи== ☞ ((algebra2:optimiz:distance:torri:problems ЗДЕСЬ)). ((:algebra2:optimiz:distance:torri:weber .)) ==Источники == При составлении настоящего раздела существенно использовалось содержание обзорной статьи [*] . **Martini H.** //((http://www.encyclopediaofmath.org/index.php/Fermat-Torricelli_problem 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. (На самом деле, последняя книга --- не перевод оригинальной книги Вебера, а //изложение// ее содержания переводчиком Н.Морозовым[[Отождествить переводчика вот с этим ☞ ((https://ru.wikipedia.org/wiki/%CC%EE%F0%EE%E7%EE%E2,_%CD%E8%EA%EE%EB%E0%E9_%C0%EB%E5%EA%F1%E0%ED%E4%F0%EE%E2%E8%F7_%28%F0%E5%E2%EE%EB%FE%F6%E8%EE%ED%E5%F0%29 человеком)) не удалось]]). [2]. **Дингельдэй Фр.** //((:references#дингельдей Сборникъ задачъ по приложен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. Текст ☞ ((https://books.google.ru/books?id=NstBAQAAIAAJ&pg=PA515&redir_esc=y#v=onepage&q&f=false ЗДЕСЬ)). [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. Текст ☞ ((https://vmath.ru/vf5/_media/users/au/share/amer.math.monthly.121.04.318.pdf ЗДЕСЬ)) (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. Текст ☞ ((http://www.apmath.spbu.ru/ru/staff/uteshev/publ/publ11.pdf ЗДЕСЬ)) (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.