Проблема Вебера - Weber problem

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

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

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

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

В случае треугольника задача Ферма состоит в том, чтобы определить положение точки 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₁, А₂ и R таким образом, чтобы силы притяжения, действующие со стороны точек 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 пропорциональна силе притяжения _Cw, направленный в сторону C, сторона AE пропорциональна силе притяжения _Bw указывает на B, а сторона BE пропорциональна силе притяжения _Аw указывает на A;

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

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

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

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

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

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

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

1– в построенном треугольнике RA₂H, который частично перекрывает A₁А₂Треугольник расположения R, RA₂ сторона пропорциональна силе притяжения _A1w указывает на A₁, правая сторона пропорциональна силе притяжения _A2w указывает на A₂, а буква A₂Сторона H пропорциональна силе отталкивания _рw отталкивание от точки R;

2– в построенном треугольнике RA₁I, который частично перекрывает A₁А₂Треугольник расположения R, RA₁ сторона пропорциональна силе притяжения _A2w указывает на A₂, сторона ПП пропорциональна силе притяжения _A1w указывает на A₁, а буква A₁Сторона I пропорциональна силе отталкивания _рw отталкивание от точки R;

3– оптимальная точка D расположена на пересечении двух окружностей, проведенных вокруг прямого восхождения.₂H и RA₁Я построил треугольники. Это решение бесполезно, если одна из сил больше суммы двух других или если углы несовместимы. В некоторых случаях никакая сила не превышает двух других, и углы несовместимы; тогда оптимальное местоположение находится в точке, которая проявляет большую силу притяжения.

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

Углы проблемы Вебера.

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

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

∠1 + ∠2 = ∠C;

∠3 + ∠4 = ∠A;

∠5 + ∠6 = ∠B;

∠1 + ∠6 + ∠α_А = 180° ;

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

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

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

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

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

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

cos ∠α_А = −( _Bш² + _Cш² − _Аш²) / (2 _Bш _Cw);

cos ∠α_B = −( _Аш² + _Cш² − _Bш²) / (2 _Аш _Cw);

cos ∠α_C = −( _Аш² + _Bш² − _Cш²) / (2 _Аш _Bw);

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

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

где k = (CB / CA) (sin ∠α_B / sin ∠α_А) и k ’= (∠A + ∠B + ∠α_C) − 180° ;

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

∠1 + ∠2 = ∠C;

∠3 + ∠4 = ∠A;

∠5 + ∠6 = ∠B;

∠1 + ∠6 + ∠α_А = 180° ;

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

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

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

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

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

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

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

cos ∠e = - ( _A1ш² + _A2ш² − _рш²) / (2 _A1ш _A2w);

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

cos ∠p = - ( _A1ш² + _рш² − _A2ш²) / (2 _A1ш _р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] предложил алгоритм, основанный на методом наименьших квадратов с повторным взвешиванием обобщающий Алгоритм Вайсфельда для невзвешенная проблема. Их метод применим для задач Ферма и Вебера с участием многих сил, но не для задачи притяжения-отталкивания. В этом методе, чтобы найти приближение к точке у минимизация взвешенной суммы расстояний

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

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

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

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

${\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]

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

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

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

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

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

Примечания

1. Кун, Гарольд В. и Роберт Э. Куэнн, 1962, «Эффективный алгоритм для численного решения обобщенной проблемы Вебера в пространственной экономике». Журнал региональной науки 4, 21–34.
2. Телье, Люк-Норманд, 1972, «Проблема Вебера: решение и интерпретация», Географический анализ, т. 4, вып. 3. С. 215–233.
3. Симпсон, Томас, 1750 г., Доктрина и применение флюксий, Лондон.
4. Вебер, Альфред, 1909 г., Über den Standort der Industrien, Тюбинген, J.C.B. Mohr) - английский перевод: Теория размещения отраслей, Чикаго, Издательство Чикагского университета, 1929, 256 страниц.
5. Телье, Люк-Норманд, 1985, Пространственная экономия: рациональная экономическая жизнь, Chicoutimi, Gaëtan Morin éditeur, 280 страниц.
6. Телье, Люк-Норманд, 2013 г., «Приложение 1: Геометрическое решение проблемы притяжения-отталкивания», приложение к докладу Пьера Хансена, Кристофа Мейера и Люка-Нормана Телье «Топодинамические модели и новая экономика. géographique: совместимость, конвергенция и сравнение преимуществ », в Marc-Urbain Proulx (ed.), 2013, Sciences du Territoire II: методологии, Квебек, Press de l’Université du Québec.
7. Телье, Люк-Норманд, 1972, «Проблема Вебера: решение и интерпретация», Географический анализ, т. 4, вып. 3. С. 215–233.
8. Телье, Люк-Норманд, 1985, Пространственная экономия: рациональная экономическая жизнь, Chicoutimi, Gaëtan Morin éditeur, 280 страниц.
9. Кун, Гарольд В. и Роберт Э. Куэнн, 1962, «Эффективный алгоритм для численного решения обобщенной проблемы Вебера в пространственной экономике». Журнал региональной науки 4, 21–34.
10. Чен, Пей-Чун, Хансен, Пьер, Жомар, Бриджит и Хоанг Туй, 1992, «Проблема Вебера с притяжением и отталкиванием». Журнал региональной науки 32, 467–486.
11. Оттавиано, Джанмарко и Жак-Франсуа Тисс, 2005, «Новая экономическая география: как насчет N? », Окружающая среда и планирование A 37, 1707–1725.

Рекомендации

• Чен, Пей-Чун, Хансен, Пьер, Жомар, Бриджит и Хоанг Туй, 1992, «Проблема Вебера с притяжением и отталкиванием». Журнал региональной науки 32, 467–486.
• Кун, Гарольд В. и Роберт Э. Куенн, 1962, "Эффективный алгоритм численного решения обобщенной проблемы Вебера в пространственной экономике". Журнал региональной науки 4, 21–34.
• Оттавиано, Джанмарко и Жак-Франсуа Тисс, 2005, «Новая экономическая география: как насчет N? », Окружающая среда и планирование A 37, 1707–1725.
• Симпсон, Томас, 1750 г., Доктрина и применение флюксий, Лондон.
• Телье, Люк-Норманд и Борис Полански, 1989, «Проблема Вебера: частота различных типов решений и распространение на силы отталкивания и динамические процессы», Журнал региональной науки, том 29, вып. 3, стр. 387–405.
• Телье, Люк-Норманд, 1972, «Проблема Вебера: решение и интерпретация», Географический анализ, т. 4, вып. 3. С. 215–233.
• Телье, Люк-Норманд, 1985, Пространственная экономия: рациональная экономическая жизнь, Chicoutimi, Gaëtan Morin éditeur, 280 страниц.
• Телье, Люк-Норманд, 2013 г., «Приложение 1: Геометрическое решение проблемы притяжения – репульсии», приложение к статье Пьера Хансена, Кристофа Мейера и Люка-Нормана Телье «Топодинамические модели и новая экономика. géographique: совместимость, конвергенция и сравнение преимуществ », в Marc-Urbain Proulx (ed.), 2013, Sciences du Territoire II: методологии, Квебек, Press de l’Université du Québec.
• Вебер, Альфред, 1909 г., Über den Standort der Industrien, Тюбинген, J.C.B. Mohr) - английский перевод: Теория размещения отраслей, Чикаго, Издательство Чикагского университета, 1929, 256 страниц.
• Весоловски, Джордж, 1993, «Проблема Вебера: история и перспективы», Геолокация, Vol. 1, стр. 5–23.

внешняя ссылка

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

• Математический портал
• Деловой и экономический портал