!!§!! Вспомогательная страница к разделу ☞ ((algebra2:optimiz:distance ВЫЧИСЛЕНИЕ РАССТОЯНИЙ МЕЖДУ ГЕОМЕТРИЧЕСКИМИ ОБЪЕКТАМИ)). !!⊗!! Раздел - в процессе разработки. Строительные работы: 14.01.2019 - ??.??.????. ---- ==Задача Вебера об оптимальном размещении производства== ~~TOC~~ ===Обобщенная задача Ферма-Торричелли== **Задача**. Пусть заданы координаты $ L_{} $ точек пространства $ \mathbb R^{n}_{} $ : $ \{P_j=(x_{j1},\dots,x_{jn})\}_{j=1}^L $. Определить координаты точки $ W_{\ast}=(x_{\ast 1},\dots,x_{\ast n}) $, решающей задачу оптимизации: $$ \min_{W\in \mathbb R^n} F(W) \qquad npu \qquad F(W)= \sum_{j=1}^L m_j |WP_j| \ . $$ Здесь $ | \cdot | $ означает евклидово расстояние: $ |P_1P_2|=\sqrt{(x_{11}-x_{21})^2+\dots+(x_{1n}-x_{2n})^2} $, а величины $ \{ m_j \}_{j=1}^L $ обычно считаются положительными и называются **весами**. Задача известна под различными названиями: //обобщенная задача Ферма-Торричелли//, //задача Ферма-Торричелли-Штейнера//, //задача Вебера//, задача о ((http://en.wikipedia.org/wiki/Geometric_median взвешенной геометрической медиане)). Будем говорить о наборе $$ \left\{ \begin{array}{c|c|c} P_1 & \dots & P_L \\ m_1 & \dots & m_L \end{array} \right\} $$ как о **конфигурации весов**. ===Плоский случай== Рассмотрим сначала плоский вариант задачи: пусть $ n=2_{} $, $ \{P_j=(x_{j},y_j)\}_{j=1}^L $, $$ F(x,y)= \sum_{j=1}^{L} m_j \sqrt{(x-x_j)^2+(y-y_j)^2} \ . $$ В этом случае поставленная задача также называется //задачей об оптимальном расположении (узловой) станции//[[ (//нем.//) Problem des Knotenpunktes ((#источники [4])).]], или --- в случае $ L=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 |}} Частный случай задачи при $ n=2 , L=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. Вебер предложил и следующее обобщение задачи: Рассмотрим простой случай производства, требующего трех материалов и для которого возможно технологическое разделение процесса производства на две стадии. На первой стадии два исходных материала возможно соединить в промежуточной заготовке[[(англ.) half-finished product]], а на второй же стадии эту заготовку совместить с оставшимся третьим исходным материалом --- для получения окончательного продукта... Обозначим возможное размещение этих центров разделенной продукции через $ W_1 $ и $ W_2 $; а именно $ W_1 $ --- для первой стадии, и $ W_2 $ --- для второй. Что будет результатом такого разделения? Математически поставленная задача формулируется в виде: найти координаты точек $ W_1 $ и $ W_2 $, обеспечивающих $$ \min_{\{W_1,W_2\} \subset \mathbb R^2} F(W_1,W_2) $$ для $$ F(W_1,W_2)= m_1|W_1P_1|+m_2|W_1P_2| +m_3|W_2P_3|+m_4|W_2P_4|+ m |W_1W_2| \, . $$ Здесь числа $ \{ m_j\}_{j=1}^4 $ и $ m $ предполагаются положительными. !!П!! **Пример.** В магазин, расположенный в точке $ P_4 $ ежедневно должно поступать $ m_4 $ килограммов пельменей. Для производства этого количества требуется $ m_3 $ кг мяса и $ m $ кг теста. Мясо поступает из мясокомбината $ P_3 $. Для производства требуемого количества теста необходимо $ m_1 $ кг воды, источник которой --- в точке $ P_1 $, и $ m_2 $ кг муки, производимой на мукомольном комбинате, расположенном в $ P_2 $. {{ algebra2:optimiz:distance:torri:pelmen.png |}} Где расположить производство пельменей так, чтобы минимизировать транспортные расходы? Решение задачи будет зависеть от конфигурации весов $$ \left\{ \begin{array}{c|c|c|c|} P_1 & P_2 & P_3 & P_4 \\ m_1 & m_2 & m_3 & m_4 \end{array} m \right\} $$ Возможно, придется организовать производство прямо в магазине, стянув туда все компоненты. Однако, возможно и организовать производство в точке, отличной от $ P_4 $, в которую впоследствии везти конечный продукт. И эта задача относится к рассмотренной выше. Но можно, наконец, разбить производство на два этапа. На первом этапе --- в некоторой точке $ W_1 $ (поближе к источникам сырья) --- организовать производство теста, а потом отвезти его в точку $ W_2 $, где соединить его с мясом. Осталось только выяснить возможно ли подобрать такие точки $ W_1 $ и $ W_2 $, чтобы транспортные расходы были минимальными, ну или, хотя бы, меньшими тех, что обеспечивается решением задачи Вебера при одном, неразделяемом географически, месте производства? ♦ В 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 теории исследования операций)). В современной литературе фиксированную точку $ P_j $ принято называть **терминалом**[[terminal, demand point]], а искомую точку $ W_{\ell} $ --- производством[[facility]]; так что подраздел известен как ((http://en.wikipedia.org/wiki/Facility_location_problem задача об оптимальном размещении производств))[[facility location problem или location theory (location analysis)]]. ===Общая постановка задачи Вебера== Обобщенная задача Вебера[[Multifacility Weber problem]] формулируется как поиск мест размещения определенного количества $ K \ge 2 $ производств $ \{W_{i}\}_{i=1}^{K} $ в пространстве $ \mathbb R^n $, соединенных с терминалами $ \{ P_j\}_{j=1}^L \subset \mathbb R^n $ прямолинейными путями и обеспечивающих решение задачи $$ \min_{\{W_{1},\dots, W_{K}\}\subset \mathbb R^n} \left\{ \sum_{j=1}^L \sum_{i=1}^{K} m_{ij} |W_iP_j| + \sum_{k=1}^{K} \sum_{i=k+1}^{K} \widetilde m_{ik} |W_iW_k| \right\} \, ; $$ здесь некоторые из весов $ m_{ij} $ или $ \widetilde m_{ik} $ могут быть нулевыми. В случае разрешимости задачи, будем называть значение минимума **минимальной стоимостью сети**. При всех весах $ \{ m_{ij}=1\} $ и $ \{\widetilde m_{ik}\} \subset \{0,1 \} $ задача является естественным обобщением задачи о ((:algebra2:optimiz:distance:torri:tree минимальном дереве Штейнера)), имеющей целью построение на плоскости $ \mathbb R^2 $ сети минимальной длины, соединяющей заданные терминалы. При всех весах $ \{\widetilde m_{ik}=0\} $ и $ \{ m_{ij}=1\} $ задача имеет связь с ((https://en.wikipedia.org/wiki/K-medians_clustering методом K медиан)) решения задачи кластеризации точечного множества $ \{P_j\}_{j=1}^L $. Последняя заключется в нахождении такого разбиения множества на $ K $ непересекающихся подмножеств $ \mathbb S_1,\dots, \mathbb S_K $, чтобы минимизировалась сумма расстояний от геометрических медиан $ W_1,\dots, W_K $ подмножеств до точек соответствующих подмножеств: $$ \min_{\mathbb S_1,\dots, \mathbb S_K} \sum_{i=1}^K \sum_{P_r\in \mathbb S_i} |W_iP_r| \, . $$ {{ algebra2:optimiz:distance:torri:point_set_12.png |}} Обозначение $ K $ для количества кластеров --- традиционно используемое. Не следует путать метод $ K $ медиан с ((https://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_k-%D1%81%D1%80%D0%B5%D0%B4%D0%BD%D0%B8%D1%85 методом K средних)): оба решают одну и ту же задачу кластеризации, но в разных минимизируемых (целевых) функциях. ===Решение== ====Случай трех терминалов== ====Случай четырех терминалов== {{ :algebra2:optimiz:distance:torri:weight-2.png?600 |}} ====Влияние параметров на решение== ==Источники == [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]. **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 ЗДЕСЬ)). [4]. **Uteshev A.Yu., Semenova E.A.** //Geometry and Analytics of the Multifacility Weber Problem.// 2019. ((https://arxiv.org/pdf/1912.12973.pdf arXiv:1912.12973)) [5]. **Uteshev A.Yu., Semenova E.A.** //Analytics of the multifacility Weber problem.// LNCS, 2020, V.**12251**, pp. 395-411. ((http://vmath.ru/vf5/_media/users/au/pvt/uteshev-semenova2020_chapter_analyticsofthemultifacilityweb.pdf .))