Проблема Вебера

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

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

Определение и история проблем Ферма, Вебера и притяжения-отталкивания [ править ]

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

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

В своей простейшей версии задача притяжения-отталкивания состоит в размещении точки D по отношению к трем точкам A ₁ , A ₂ и R таким образом, чтобы силы притяжения, создаваемые точками A ₁ и A ₂ , и сила отталкивания оказывались точкой R компенсируют друг друга, как это должно происходить при оптимуме. Он представляет собой обобщение как проблемы Ферма, так и проблемы Вебера. Впервые она была сформулирована и решена в случае треугольника в 1985 году Люком-Норманом Телье . ^[5] В 1992 году Чен, Хансен, Жомард и Туй нашли решение проблемы Телье для случая многоугольников, имеющих более трех сторон.

Геометрическое решение Торричелли проблемы треугольника Ферма [ править ]

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

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

1 - точка D находится в своем оптимальном месте, когда любое значительное перемещение из этого местоположения вызывает чистое увеличение общего расстояния до контрольных точек A, B и C, что означает, что оптимальная точка - единственная точка, в которой бесконечно малое движение в сторону одна из трех контрольных точек вызывает уменьшение расстояния до этой точки, которое равно сумме индуцированных изменений расстояний до двух других точек; фактически, в задаче Ферма преимущество уменьшения расстояния от 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 пропорциональна силе притяжения _C w, направленной в сторону C, сторона AE пропорциональна силе притяжения _B w, направленной в сторону B, а сторона BE пропорциональна силе притяжения _A w указывая на A;

2– в построенном треугольнике BCG сторона BC пропорциональна силе притяжения _A w, направленной к A, сторона BG пропорциональна силе притяжения _B w, направленной к B, а сторона CG пропорциональна силе притяжения _C w указывая на C;

3– оптимальная точка D расположена на пересечении двух окружностей, проведенных вокруг построенных треугольников ABE и BCG.

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

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

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

Существует геометрическое решение проблемы треугольника притяжения-отталкивания. Его открытие произошло сравнительно недавно. ^[6] Это геометрическое решение отличается от двух предыдущих, поскольку в этом случае два построенных силовых треугольника перекрывают треугольник расположения A ₁ A ₂ R (где A ₁ и A ₂ - точки притяжения, а R - точки отталкивания). , тогда как в предыдущих случаях они никогда не делали этого.

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

1– в построенном треугольнике RA ₂ H, который частично перекрывает локационный треугольник A ₁ A ₂ R, сторона RA ₂ пропорциональна силе притяжения _A1 w, направленной в сторону A ₁ , правая сторона пропорциональна силе притяжения _A2 w указывает на A ₂ , и сторона A ₂ H пропорциональна силе отталкивания _R w, отталкивающей от точки R;

2– в построенном треугольнике RA ₁ I, который частично перекрывает локационный треугольник A ₁ A ₂ R, сторона RA ₁ пропорциональна силе притяжения _A2 w, направленной в сторону A ₂ , сторона RI пропорциональна силе притяжения _A1 w направлен в сторону A ₁ , и сторона A ₁ I пропорциональна силе отталкивания _R w, отталкивающей от точки 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):

∠1 + ∠2 = ∠C;

∠3 + ∠4 = ∠A;

∠5 + ∠6 = ∠B;

∠1 + ∠6 + ∠α _A = 180 °;

∠2 + ∠3 + ∠α _B = 180 °;

∠4 + ∠5 + ∠α _C = 180 °.

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

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

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

1– Определите углы ∠α _A , ∠α _B и ∠α _C , которые таковы, что три силы притяжения _A w, _B w и _C w компенсируют друг друга для обеспечения равновесия. Это делается с помощью следующих независимых уравнений:

cos ∠α _A = - ( _B w ² + _C w ² - _A w ² ) / (2 _B w _C w);

cos ∠α _B = - ( _A w ² + _C w ² - _B w ² ) / (2 _A w _C w);

cos ∠α _C = - ( _A w ² + _B w ² - _C w ² ) / (2 _A w _B w);

2– Определите значение угла ∠3 (это уравнение вытекает из требования, чтобы точка D совпадала с точкой E):

tan ∠3 = (k sin k ') / (1 + k cos k');

где k = (CB / CA) (sin ∠α _B / sin ∠α _A ), а k '= (∠A + ∠B + ∠α _C ) - 180 °;

3– Решите следующую систему одновременных уравнений, в которой теперь известно ∠3:

∠1 + ∠2 = ∠C;

∠3 + ∠4 = ∠A;

∠5 + ∠6 = ∠B;

∠1 + ∠6 + ∠α _A = 180 °;

∠2 + ∠3 + ∠α _B = 180 °;

∠4 + ∠5 + ∠α _C = 180 °.

Тригонометрическое решение Телье проблемы притяжения-отталкивания треугольника [ править ]

Телье (1985) ^[8] распространил задачу Ферма – Вебера на случай сил отталкивания. Рассмотрим случай треугольника, в котором есть две силы притяжения _A1 w и _A2 w и одна сила отталкивания _R w. Здесь, как и в предыдущем случае, существует вероятность того, что начала трех векторов не совпадают. Значит, решение должно требовать их совпадения. Тригонометрическое решение этой проблемы Теллье следующее:

1– Определите угол ∠e:

cos ∠e = - ( _A1 w ² + _A2 w ² - _R w ² ) / (2 _A1 w _A2 w);

2– Определите угол ∠p:

cos ∠p = - ( _A1 w ² + _R w ² - _A2 w ² ) / (2 _A1 w _R w);

3– Определите угол ∠c:

∠c = 180 ° - ∠p;

4– Определите угол ∠d:

∠d = ∠e - ∠c;

5– Определите значение угла ∠3 (это уравнение вытекает из требования, чтобы точка D совпадала с точкой E):

загар ∠3 = х / у;

где x = sin ∠f - (RA ₁ / RA ₂ ) (sin ∠d sin [∠e - ∠b] / sin ∠c); и y = (RA ₁ / RA ₂ ) (sin ∠d cos [∠e - ∠b] / sin ∠c) - cos ∠f;

6– Определите ∠1:

∠1 = 180 ° - ∠e - ∠3;

7– Определите ∠5:

∠5 = 180 ° - ∠b - ∠c - ∠1;

8– Определите ∠2:

∠2 = ∠a - ∠5.

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

Когда количество сил больше трех, больше невозможно определить углы, разделяющие различные силы, без учета геометрии многоугольника местоположения. Тут бессильны геометрические и тригонометрические методы. В таких случаях используются итерационные методы оптимизации. Кун и Куэнне (1962) ^[9] предложили алгоритм, основанный на итеративно взвешенных наименьших квадратах, обобщающий алгоритм Вайсфельда для невзвешенной задачи . Их метод применим для задач Ферма и Вебера с участием многих сил, но не для проблемы притяжения-отталкивания. В этом методе, чтобы найти приближение к точке y, минимизируя взвешенную сумму расстояний

${\ displaystyle \ sum _ {i = 1} ^ {n} w_ {i} \, \ | x_ {i} -y \ |,}$

находится начальное приближение к решению y ₀ , а затем на каждом этапе алгоритма приближается к оптимальному решению, устанавливая y _{j  + 1} как точку, минимизирующую сумму взвешенных квадратов расстояний

${\ displaystyle \ sum _ {i = 1} ^ {n} {\ frac {w_ {i}} {\ | x_ {i} -y_ {j} \ |}} \ | x_ {i} -y \ | ^ {2}}$

где начальные веса w _i входных точек делятся на расстояния от каждой точки до приближения из предыдущего этапа. В качестве единственного оптимального решения взвешенной задачи наименьших квадратов каждое последующее приближение может быть найдено как средневзвешенное:

${\ Displaystyle \ left.y_ {j + 1} = \ left (\ sum _ {i = 1} ^ {n} {\ frac {w_ {i} x_ {i}} {\ | x_ {i} -y_ {j} \ |}} \ right) \ right / \ left (\ sum _ {i = 1} ^ {n} {\ frac {w_ {i}} {\ | x_ {i} -y_ {j} \ |}} \ right).}$

Для решения проблемы притяжения-отталкивания вместо этого следует прибегнуть к алгоритму, предложенному Ченом, Хансеном, Жомардом и Таем (1992). ^[10]

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

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

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

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

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

Заметки [ править ]

Ссылки [ править ]

• Чен, Пей-Чун, Хансен, Пьер, Жомар, Бриджит и Хоанг Туй, 1992, «Проблема Вебера с притяжением и отталкиванием», Journal of Regional Science 32, 467–486.
• Кун, Гарольд В. и Роберт Э. Куенн, 1962, "Эффективный алгоритм численного решения обобщенной проблемы Вебера в пространственной экономике". Журнал региональной науки 4, 21–34.
• Оттавиано, Джанмарко и Жак-Франсуа Тисс, 2005, «Новая экономическая география: а как насчет N? », Окружающая среда и планирование A 37, 1707–1725.
• Симпсон, Томас, 1750 г., Доктрина и применение флюксий, Лондон.
• Телье, Люк-Норманд и Борис Полански, 1989, «Проблема Вебера: частота различных типов решений и распространение на силы отталкивания и динамические процессы», Journal of Regional Science , vol. 29, no. 3, стр. 387–405.
• Телье, Люк-Норманд, 1972, «Проблема Вебера: решение и интерпретация», Географический анализ , т. 4, вып. 3. С. 215–233.
• Телье, Люк-Норманд, 1985, Пространственная экономика: рациональное экономическое пространство , Шикутими, Гаэтан Морин Эдитур, 280 страниц.
• Телье, Люк-Норманд, 2013 г., «Приложение 1: Геометрическое решение проблемы притяжения – отталкивания», приложение к статье Пьера Хансена, Кристофа Мейера и Люка-Нормана Телье «Топодинамические модели и новая экономика. géographique: совместимость, конвергенция и сравнение преимуществ », в Marc-Urbain Proulx (ed.), 2013, Sciences du Territoire II: méthodologies , Québec, Presses de l'Université du Québec.
• Weber, Alfred, 1909, Über den Standort der Industrien , Tübingen, JCB Mohr) - английский перевод: Theory of Location of Industries , Chicago, Chicago University Press, 1929, 256 страниц.
• Весоловски, Джордж, 1993, «Проблема Вебера: история и перспектива», Геолокация , Vol. 1, стр. 5–23.

Внешние ссылки [ править ]

• "Проблема Вебера" , Энциклопедия математики , EMS Press , 2001 [1994]