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

Будем говорить о наборе $$ \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} \ . $$

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

Частный случай задачи при $ 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.

Вебер предложил и следующее обобщение задачи:

Математически поставленная задача формулируется в виде: найти координаты точек $ 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 $.

Где расположить производство пельменей так, чтобы минимизировать транспортные расходы? Решение задачи будет зависеть от конфигурации весов $$ \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 веке эти задачи выделились в подраздел теории исследования операций. В современной литературе фиксированную точку $ P_j $ принято называть терминалом⁶⁾, а искомую точку $ W_{\ell} $ — производством⁷⁾; так что подраздел известен как задача об оптимальном размещении производств⁸⁾.

Обобщенная задача Вебера⁹⁾ формулируется как поиск мест размещения определенного количества $ 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 \} $ задача является естественным обобщением задачи о минимальном дереве Штейнера, имеющей целью построение на плоскости $ \mathbb R^2 $ сети минимальной длины, соединяющей заданные терминалы.

При всех весах $ \{\widetilde m_{ik}=0\} $ и $ \{ m_{ij}=1\} $ задача имеет связь с методом 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| \, . $$

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

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

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

[4]. Uteshev A.Yu., Semenova E.A. Geometry and Analytics of the Multifacility Weber Problem. 2019. arXiv:1912.12973

[5]. Uteshev A.Yu., Semenova E.A. Analytics of the multifacility Weber problem. LNCS, 2020, V.12251, pp. 395-411. .