Инструменты сайта


§

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

Раздел - в процессе разработки. Строительные работы: 14.01.2019 - ??.??.????.


Задача Вебера об оптимальном размещении производства

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

Задача. Пусть заданы координаты $ 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} \ . $$

В этом случае поставленная задача также называется задачей об оптимальном расположении (узловой) станции1), или — в случае $ L=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_{} $.

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

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

Рассмотрим простой случай производства, требующего трех материалов и для которого возможно технологическое разделение процесса производства на две стадии. На первой стадии два исходных материала возможно соединить в промежуточной заготовке5), а на второй же стадии эту заготовку совместить с оставшимся третьим исходным материалом — для получения окончательного продукта… Обозначим возможное размещение этих центров разделенной продукции через $ 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 $.

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

Общая постановка задачи Вебера

Обобщенная задача Вебера9) формулируется как поиск мест размещения определенного количества $ 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| \, . $$

Обозначение $ K $ для количества кластеров — традиционно используемое. Не следует путать метод $ K $ медиан с методом K средних: оба решают одну и ту же задачу кластеризации, но в разных минимизируемых (целевых) функциях.

Решение

Случай трех терминалов

Случай четырех терминалов

Влияние параметров на решение

Источники

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

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

1)
(нем.) Problem des Knotenpunktes [4].
2)
Launhardt Carl Wilhelm Friedrich (1832—1918), немецкий экономист; биография ЗДЕСЬ.
3)
Weber Alfred (1868-1958), немецкий экономист и социолог; брат известного социолога, историка и экономиста Макса Вебера. Среди его учеников был и писатель Франц Кафка. Биография ЗДЕСЬ
4)
Standort (нем.)
5)
(англ.) half-finished product
6)
terminal, demand point
7)
facility
8)
facility location problem или location theory (location analysis)
9)
Multifacility Weber problem
10)
Отождествить переводчика вот с этим человеком не удалось
algebra2/optimiz/distance/torri/weber.txt · Последние изменения: 2021/01/08 17:47 — au