задача Вебера

В геометрии задача Вебера , названная в честь Альфреда Вебера , является одной из самых известных задач теории местоположения . Требуется найти точку на плоскости, которая минимизирует сумму транспортных расходов от этой точки до n пунктов назначения, где разные точки назначения связаны с разными затратами на единицу расстояния.

Задача Вебера обобщает геометрическую медиану , которая предполагает, что транспортные расходы на единицу расстояния одинаковы для всех пунктов назначения, и проблему вычисления точки Ферма , геометрической медианы трех точек. По этой причине ее иногда называют проблемой Ферма – Вебера, хотя то же название также использовалось для невзвешенной геометрической задачи о медиане. Проблема Вебера, в свою очередь, обобщается проблемой притяжения-отталкивания , которая позволяет некоторым из затрат быть отрицательными, так что чем больше расстояние от некоторых точек, тем лучше.

Определение и история задач Ферма, Вебера и проблем притяжения-отталкивания.

	Проблема Ферма	Проблема Вебера	Проблема притяжения-отталкивания
Впервые сформулированный	Ферма (до 1640 г.)	Симпсон (1750)	Телье (1985)
Геометрическое решение задачи треугольника	Торричелли (1645 г.)	Симпсон (1750)	Телье (2013)
Прямое численное решение задачи треугольника	Телье (1972)	Телье (1972)	Телье (1985)
Итерационное численное решение задачи	Э. Вайсфельд (1937), Кун и Куэнне (1962)	Э. Вайсфельд (1937), Кун и Куэнне (1962)	Чен, Хансен, Жомар и Туй (1992)

В случае треугольника задача Ферма состоит в расположении точки D относительно трех точек A, B, C таким образом, чтобы сумма расстояний между D и каждой из трех других точек была минимальной. Она была сформулирована знаменитым французским математиком Пьером де Ферма до 1640 года, и ее можно рассматривать как истинное начало как теории местоположения, так и космической экономики. Торричелли нашел геометрическое решение этой проблемы около 1645 года, но более 325 лет спустя она так и не нашла прямого численного решения. Э. Вайсфельд опубликовал в 1937 году статью с алгоритмом решения задачи Ферма-Вебера. Поскольку статья была опубликована в математическом журнале Tohoku, а Вайсфельд иммигрировал в США и сменил имя на Васзони, его работа не получила широкой известности. Кун и Куэнне независимо нашел аналогичное итерационное решение общей проблемы Ферма в 1962 году, а в 1972 году Телье нашел прямое численное решение задачи треугольника Ферма, которое является тригонометрическим. Решение Куна и Куэнне применимо к случаю многоугольников, имеющих более трех сторон, чего нельзя сказать о решении Телье по причинам, объясненным далее.

Задача Вебера в случае треугольника заключается в расположении точки D относительно трех точек A, B, C таким образом, чтобы сумма транспортных расходов между D и каждой из трех других точек была минимальной. Проблема Вебера является обобщением проблемы Ферма, поскольку она включает в себя как равные, так и неравные силы притяжения (см. ниже), тогда как проблема Ферма касается только равных сил притяжения. Впервые она была сформулирована и решена геометрически в случае треугольника Томасом Симпсоном в 1750 году. Позже он был популяризирован Альфредом Вебером в 1909 году. Итерационное решение Куна и Куэнне, найденное в 1962 году, и решение Телье, найденное в 1972 году, применимы как к проблеме треугольника Вебера, так и к задаче Ферма. Решение Куна и Куэнне применимо также к случаю многоугольников, имеющих более трех сторон.

простейшем варианте задача притяжения-отталкивания состоит в расположении точки D относительно трех точек A1 _, , A2 _R и В таким образом, чтобы силы притяжения, действующие со стороны точек и _, сила отталкивания _{A1, A2} оказываемая точкой R компенсируют друг друга, как это и должно происходить в оптимуме. Она представляет собой обобщение проблем Ферма и Вебера. Впервые она была сформулирована и решена в случае треугольника в 1985 году Люком-Норманом Телье . В 1992 году Чен, Хансен, Жомар и Туи нашли решение проблемы Телье для случая многоугольников, имеющих более трех сторон.

Геометрическое решение Торричелли задачи треугольника Ферма

Геометрическое решение Торричелли задачи треугольника Ферма.

Евангелистой Торричелли, Геометрическое решение проблемы треугольника Ферма, предложенное основано на двух наблюдениях:

1. Точка D находится в оптимальном положении, когда любое значительное перемещение из этого положения приводит к чистому увеличению общего расстояния до контрольных точек A, B, C. Это означает, что оптимальной точкой является единственная точка, в которой происходит бесконечно малое перемещение к одной из точек. три опорные точки вызывают сокращение расстояния до этой точки, равное сумме вызванных изменений расстояний до двух других точек; в самом деле, в задаче Ферма преимущество сокращения расстояния от А на один километр равно преимуществу сокращения расстояния от В на один километр или расстояния от С на ту же длину; другими словами, деятельность, которая должна быть расположена в D, в равной степени притягивается A, B, C ;
2. Согласно важной теореме евклидовой геометрии, в выпуклом четырехугольнике, вписанном в окружность, противоположные углы являются дополнительными (т. е. их сумма равна 180°); эта теорема может принять и следующий вид: если мы разрезаем окружность хордой AB , то получим две дуги окружности, скажем, AiB , AjB ; на дуге AiB любой угол ∠ AiB одинаков для любой выбранной точки i , а на дуге AjB все углы ∠ AjB также равны для любой выбранной точки j ; при этом углы ∠ AiB , ∠ AjB являются дополнительными.

Можно доказать, что из первого наблюдения следует, что в оптимуме углы между прямыми AD, BD, CD должны быть равны 360°/3 = 120°. Из этого заключения Торричелли сделал следующий вывод:

1. Если любой треугольник △ ABD , у которого равен угол ∠ADB 120°, порождает выпуклый четырехугольник ABDE, вписанный в окружность, то ∠ABE должен быть угол треугольника △ ABE равен (180° − 120°) = 60°;
2. Один из способов определить множество положений точки D , для которых угол ∠ ADB равен 120°, — это нарисовать равносторонний треугольник △ ABE (поскольку каждый угол равностороннего треугольника равен 60°), где E находится вне △ Треугольник ABC и нарисуйте круг вокруг этого треугольника; тогда все точки D' окружности этого круга, лежащие внутри круга △ ABC, таковы, что угол ∠ AD'B равен 120°;
3. Те же рассуждения можно провести и в отношении треугольников △ ACD , △ BCD ;
4. Это приводит к тому, чтобы нарисовать два других равносторонних треугольника △ ACF , △ BCG , где F, G расположены вне треугольника △ ABC , а также две другие окружности вокруг этих равносторонних треугольников и определить место пересечения трёх окружностей; в этом месте углы между прямыми AD, BD, CD обязательно равны 120°, что доказывает, что это оптимальное расположение.

Геометрическое решение Симпсоном задачи треугольника Вебера

Геометрическое решение Симпсоном задачи треугольника Вебера.

Геометрическое решение Симпсона так называемой «проблемы треугольника Вебера» (которая была впервые сформулирована Томасом Симпсоном в 1750 году) напрямую вытекает из решения Торричелли. Симпсон и Вебер подчеркнули тот факт, что в задаче общей минимизации перевозок преимущество приближения к каждой точке притяжения A, B или C зависит от того, что перевозится, и от стоимости его транспортировки. Следовательно, преимущество приближения на один километр к A, B или C варьируется, и углы ∠ ADB , ∠ ADC , ∠ BDC больше не обязательно должны быть равны 120°.

Симпсон продемонстрировал, что так же, как в случае задачи треугольника Ферма построенные треугольники △ ABE , △ ACF , △ BCG были равносторонними, поскольку три силы притяжения были равны, в случае задачи треугольника Вебера построенные треугольники △ ABE , △ ACF , △ BCG , где E, F, G расположены вне треугольника △ ABC , должны быть пропорциональны силам притяжения системы расположения.

Решение таково, что:

1. В построенном треугольнике △ ABE сторона AB пропорциональна силе притяжения w _C , направленной в сторону C , сторона AE пропорциональна силе притяжения w _B, направленной в сторону B , а сторона BE пропорциональна силе притяжения w _A , направленной в сторону B. в сторону А ;
2. В построенном треугольнике △ BCG сторона BC пропорциональна силе притяжения w _A , направленной в сторону A , сторона BG пропорциональна силе притяжения w _C, направленной в сторону B , а сторона CG пропорциональна силе притяжения w _{в сторону B.} B , направленной в сторону С ;
3. Оптимальная точка D расположена на пересечении двух окружностей, проведенных вокруг построенных треугольников △ ABE , △ BCG .

Третий треугольник сил △ ACF , где F находится вне треугольника △ ABC , можно нарисовать на основе стороны AC , а вокруг этого треугольника можно провести третью окружность. третья окружность пересекает две предыдущие в той же точке D. Эта

Геометрическое решение Телье задачи треугольника притяжения-отталкивания

Геометрическое решение Телье задачи треугольника притяжения-отталкивания.

Существует геометрическое решение задачи треугольника притяжения-отталкивания. Его открытие произошло сравнительно недавно. Данное геометрическое решение отличается от двух предыдущих тем, что в данном случае два построенных силовых треугольника перекрываются локационным треугольником △ A ₁ A ₂ R (где A ₁ и A ₂ — точки притяжения, а R — точка отталкивания), а , в предыдущих случаях они этого никогда не делали.

Это решение таково, что:

1. В построенном треугольнике △ RA ₂ H , который частично перекрывает локационный треугольник △ A ₁ A ₂ R , сторона RA ₂ пропорциональна силе притяжения w _{A 1} , направленной в сторону A ₁ , правая сторона пропорциональна силе притяжения w _{A 2} направлена ​​в сторону A ₂ , а сторона A ₂ H пропорциональна силе отталкивания w _{R ,} отталкивающей от точки R ;
2. В построенном треугольнике △ RA ₁ I , который частично перекрывает локационный треугольник △ A ₁ A ₂ R , сторона RA ₁ пропорциональна силе притяжения w _{A 2 ,} направленной в сторону A ₂ , сторона RI пропорциональна силе притяжения w _{A 1} направлена ​​в сторону A ₁ , а сторона A ₁ I пропорциональна силе отталкивания w _R, отталкивающей от точки R ;
3. Оптимальная точка D находится на пересечении двух окружностей, проведенных вокруг △ RA ₂ H и △ RA ₁ I. построенных треугольников

Это решение бесполезно, если одна из сил больше суммы двух других или если углы несовместимы. В некоторых случаях ни одна сила не превышает две другие, и углы несовместимы; тогда оптимальное местоположение находится в точке, которая оказывает большую силу притяжения.

Тригонометрическое решение Телье задач треугольника Ферма и Вебера

Углы задачи Вебера.

Случай несовпадения вершин углов α.

Более 332 лет отделяют первую постановку задачи треугольника Ферма и открытие ее неитерационного численного решения, тогда как геометрическое решение существовало почти весь этот период времени. Есть ли этому объяснение? Это объяснение заключается в возможности несовпадения начал трех векторов, ориентированных к трем точкам притяжения. Если эти начала совпадают и лежат в оптимальном месте P , векторы, ориентированные на A, B, C , и стороны треугольника местоположения △ ABC образуют шесть углов ∠1, ∠2, ∠3, ∠4, ∠5. , ∠6 и три вектора образуют ∠ α _A , ∠ α _B , ∠ α _C. углы Легко написать следующие шесть уравнений, связывающих шесть неизвестных (углы ∠1, ∠2, ∠3, ∠4, ∠5, ∠6 ) с шестью известными значениями (углы ∠ A , ∠ B , ∠ C , значения которых заданы и углы ∠ α _A , ∠ α _B , ∠ α _C , значения которых зависят только от относительной величины трех сил притяжения, направленных к точкам притяжения A, B, C ):

$${\begin{aligned}\angle 1+\angle 2&=\angle C;\\\angle 3+\angle 4&=\angle A;\\\angle 5+\angle 6&=\angle B;\\[4pt]\angle 1+\angle 6+\angle \alpha _{A}&=180^{\circ };\\\angle 2+\angle 3+\angle \alpha _{B}&=180^{\circ };\\\angle 4+\angle 5+\angle \alpha _{C}&=180^{\circ }.\end{aligned}}$$

К сожалению, эта система шести одновременных уравнений с шестью неизвестными не определена, и возможность несовпадения начал трех векторов, ориентированных к трем точкам притяжения, объясняет, почему. В случае несовпадения мы наблюдаем, что все шесть уравнений остаются в силе. Однако оптимальное расположение P исчезло из-за треугольного отверстия, существующего внутри треугольника. Фактически, как Телье (1972) показал, что треугольное отверстие имело точно такие же пропорции, как «треугольники сил», которые мы нарисовали в геометрическом решении Симпсона.

Чтобы решить проблему, мы должны добавить к шести одновременным уравнениям седьмое требование, которое гласит, что в середине локационного треугольника не должно быть треугольного отверстия. Другими словами, начала трех векторов должны совпадать.

Решение Телье задач треугольника Ферма и Вебера включает в себя три этапа:

1. Определите углы ∠ α _A , ∠ α _B , ∠ α _C так, чтобы три силы притяжения w _A , w _B , w _C компенсировали друг друга, чтобы обеспечить равновесие. Это делается с помощью следующих независимых уравнений: $${\begin{aligned}\cos \angle \alpha _{A}=-{\frac {w_{B}^{2}+w_{C}^{2}-w_{A}^{2}}{2\,w_{B}w_{C}}};\\\cos \angle \alpha _{B}=-{\frac {w_{A}^{2}+w_{C}^{2}-w_{B}^{2}}{2\,w_{A}w_{C}}};\\\cos \angle \alpha _{C}=-{\frac {w_{A}^{2}+w_{B}^{2}-w_{C}^{2}}{2\,w_{A}w_{B}}};\end{aligned}}$$
2. Определим значение угла ∠3 (это уравнение вытекает из требования точки D совпадения с точкой E ): $$\tan \angle 3={\frac {k\sin k'}{1+k\cos k'}};$$ где $${\begin{aligned}k&={\frac {\overline {CB}}{\overline {CA}}}\times {\frac {\sin \angle \alpha _{B}}{\sin \angle \alpha _{A}}},\\[4pt]k'&=(\angle A+\angle B+\angle \alpha _{C})-180^{\circ }.\end{aligned}}$$
3. Решите следующую систему одновременных уравнений, где ∠3 теперь известно: $${\begin{aligned}\angle 1+\angle 2&=\angle C;\\\angle 3+\angle 4&=\angle A;\\\angle 5+\angle 6&=\angle B;\\[4pt]\angle 1+\angle 6+\angle \alpha _{A}&=180^{\circ };\\\angle 2+\angle 3+\angle \alpha _{B}&=180^{\circ };\\\angle 4+\angle 5+\angle \alpha _{C}&=180^{\circ }.\end{aligned}}$$

Тригонометрическое решение Телье задачи притяжения-отталкивания треугольника

Углы задачи треугольника притяжения-отталкивания.

Случай несовпадения точек D, E .

Телье (1985) распространил проблему Ферма-Вебера на случай сил отталкивания. Рассмотрим случай треугольника, где действуют две силы притяжения w _{A 1} , w _{A 2} и одна сила отталкивания w _R . Здесь, как и в предыдущем случае, существует возможность несовпадения начал трех векторов. Поэтому решение должно требовать их совпадения. Тригонометрическое решение этой задачи Телье следующее:

1. Определить угол ∠ e : $$\cos \angle e=-{\frac {w_{A1}^{2}+w_{A2}^{2}-w_{R}^{2}}{2\,w_{A1}w_{A2}}};$$
2. Определить угол ∠ p : $$\cos \angle p=-{\frac {w_{A1}^{2}+w_{R}^{2}-w_{A2}^{2}}{2\,w_{A1}w_{R}}};$$
3. Определить угол ∠ c : $$\angle c=180^{\circ }-\angle p;$$
4. Определить угол ∠ d : $$\angle d=\angle e-\angle c;$$
5. Определим значение угла ∠3 (это уравнение вытекает из требования точки D совпадения с точкой E ): $$\tan \angle 3={\frac {x}{y}};$$ где $${\begin{aligned}x&=\sin \angle f-{\frac {\overline {RA_{1}}}{\overline {RA_{2}}}}\times {\frac {\sin \angle d\sin(\angle e-\angle b)}{\sin \angle c}};\\[4pt]y&={\frac {\overline {RA_{1}}}{\overline {RA_{2}}}}\times {\frac {\sin \angle d\cos(\angle e-\angle b)}{\sin \angle c}}-\cos \angle f;\end{aligned}}$$
6. Определить ∠1 : $$\angle 1=180^{\circ }-\angle e-\angle 3;$$
7. Определить ∠5 : $$\angle 5=180^{\circ }-\angle b-\angle c-\angle 1;$$
8. Определить ∠2 : $$\angle 2=\angle a-\angle 5.$$

Итеративные решения задач Ферма, Вебера и задач притяжения-отталкивания.

Когда количество сил превышает три, определить углы, разделяющие различные силы, без учета геометрии многоугольника расположения уже невозможно. Геометрические и тригонометрические методы тогда бессильны. В таких случаях используются итерационные методы оптимизации. Кун и Куэнне (1962) предложил алгоритм, основанный на итеративно перевзвешенном методе наименьших квадратов, обобщающий алгоритм Вайсфельда для невзвешенной задачи . Их метод справедлив для задач Ферма и Вебера, включающих множество сил, но не для задачи притяжения-отталкивания. В этом методе, чтобы найти приближение к точке y, минимизирующее взвешенную сумму расстояний $$\sum _{i=1}^{n}w_{i}\,\|x_{i}-y\|,$$ находится начальное приближение к решению y ₀ , а затем на каждом этапе алгоритма приближается к оптимальному решению, устанавливая y _{j + 1} как точку, минимизирующую сумму взвешенных квадратов расстояний $$\sum _{i=1}^{n}{\frac {w_{i}}{\|x_{i}-y_{j}\|}}\|x_{i}-y\|^{2}$$где начальные веса w _i входных точек делятся на расстояния от каждой точки до аппроксимации предыдущего этапа.В качестве единственного оптимального решения взвешенной задачи наименьших квадратов каждое последующее приближение может быть найдено как средневзвешенное значение: $$y_{j+1}={\frac {\displaystyle \sum _{i=1}^{n}{\frac {w_{i}x_{i}}{|x_{i}-y_{j}|}}}{\displaystyle \sum _{i=1}^{n}{\frac {w_{i}}{|x_{i}-y_{j}|}}}}$$

Система Вариньона обеспечивает экспериментальное решение проблемы Вебера.

Вместо этого для задачи притяжения-отталкивания приходится прибегнуть к алгоритму, предложенному Ченом, Хансеном, Жомаром и Туем (1992).

Интерпретация теории земельной ренты через призму проблемы притяжения-отталкивания

В мире пространственной экономики отталкивающие силы присутствуют везде. Стоимость земли является их главной иллюстрацией. Фактически существенную часть теории стоимости земли , как сельской, так и городской, можно резюмировать следующим образом.

В случае, когда всех привлекает одна точка притяжения (сельский рынок или центральный деловой район города), конкуренция между различными участниками торгов, которые все хотят разместиться в центре, приведет к созданию стоимости земли, которая изменит уникальную точку притяжения систему в точку отталкивания с точки зрения стоимости земли, и в равновесии каждый обитатель и деятельность будут расположены в точке, где силы притяжения и отталкивания, действующие на них со стороны центра, уравновесятся.

Проблема притяжения-отталкивания и новая экономическая география.

Проблема Телье предшествовала появлению Новой экономической географии . Это видят Оттавиано и Тисс (2005). как прелюдия к Новой экономической географии (НЭГ), которая была разработана в 1990-х годах и принесла Полу Кругману по Нобелевскую премию экономическим наукам в 2008 году. Концепция силы притяжения родственна концепции НЭГ агломерации или центростремительной силы, а Концепция отталкивающей силы сродни НЭГ-концепции рассеивающей или центробежной силы.

Ссылки

• Чен, Пей-Чун, Хансен, Пьер, Жомар, Бриджит и Хоанг Туй, 1992, «Проблема Вебера с притяжением и отталкиванием», Journal of Regional Science 32, 467–486.
• Кун, Гарольд В. и Роберт Э. Куэнн, 1962, «Эффективный алгоритм численного решения обобщенной задачи Вебера в пространственной экономике». Журнал региональной науки 4, 21–34.
• Оттавиано, Джанмарко и Жак-Франсуа Тисс, 2005 г., «Новая экономическая география: как насчет N? », Окружающая среда и планирование, А 37, 1707–1725.
• Симпсон, Томас, 1750 г., Доктрина и применение флюксий, Лондон.
• Телье, Люк-Норман и Борис Полански, 1989, «Проблема Вебера: частота различных типов решений и распространение на силы отталкивания и динамические процессы», Журнал региональной науки , том 29, вып. 3, с. 387–405.
• Телье, Люк-Норман, 1972, «Проблема Вебера: решение и интерпретация», Geographical Analysis , vol. 4, нет. 3, стр. 215–233.
• Телье, Люк-Норман, 1985, Пространственная экономика: экономическая рациональность обитаемого пространства , Шикутими, редактор Гаэтана Морена, 280 страниц.
• Телье, Люк-Норман, 2013 г., «Приложение 1: Геометрическое решение треугольного случая проблемы притяжения-отталкивания», приложение к статье Пьера Хансена, Кристофа Мейера и Люка-Нормана Телье «Географические топодинамические и новые экономические модели: совместимость, конвергенция и сравнительные преимущества», Марк-Урбен Пру (редактор), 2013, Территориальные науки II: методологии , Квебек, Presses de l’Université du Québec.
• Вебер, Альфред, 1909, О расположении промышленности , Тюбинген, Дж. С. Б. Мор) — английский перевод: Теория размещения промышленности , Чикаго, Chicago University Press, 1929, 256 страниц.
• Весоловский, Жорж, 1993, «Проблема Вебера: история и перспектива», Наука о местоположении , Vol. 1, с. 5–23.

Внешние ссылки

• «Задача Вебера» , Математическая энциклопедия , EMS Press , 2001 [1994]