Русская Википедия:Задача Вебера
Задача Вебера — одна из наиболее известных задач размещения производства. Названна в честь немецкого экономиста Альфреда Вебера. В задаче требуется найти точку на плоскости, которая минимизирует сумму цен перевозок из этой точки в n точек потребления, где для разных точек потребления назначается своя цена перевозки на единицу расстояния.
Задача Вебера обобщает поиск Шаблон:Не переведено 5, для которой цены перевозок полагаются равными для всех точек потребления, и задачу нахождения точки Ферма, геометрической медианы трёх точек. По этой причине задачу иногда называют задачей Ферма – Вебера, хотя то же самое имя используется и для задачи нахождения невзвешенной геометрической медианы. Задача Вебера, в свою очередь, обобщается задачей притяжения – отталкивания, которая позволяет отрицательные цены, так что для некоторых точек большее расстояние предпочтительнее.
Определение и история задач Ферма, Вебера и притяжения – отталкивания
| Задача Ферма | Задача Вебера | Задача притяжения – отталкивания | |
|---|---|---|---|
| Сформулирована | Ферма (до 1640) | Симпсон (1750) | Телье (1985) |
| Геометрическое решение задачи треугольника |
Торричелли (1645) | Симпсон (1750) | Телье (2013) |
| Прямое численное решение задачи треугольника |
Телье (1972) | Телье (1972) | Телье (1985) |
| Итеративное численное решение задачи |
Кун и Куэн (1962) | Кун и Куэн (1962) | Чен, Хансен, Жомар и Туй (1992) |
В случае треугольника задача Ферма заключается в нахождении такой точки D по отношению к трём точкам A, B и C, что сумма расстояний от D до каждой из этих трёх точек была минимальна. Задачу сформулировал знаменитый французский математик Пьер Ферма до 1640. Задачу можно рассматривать как истинное начало задачи размещения производства. Торричелли нашёл геометрическое решение задачи около 1645 года, но прямого численного решения не было ещё более 325 лет. Кун и КуэнШаблон:Sfn нашли итеративное решение общей задачи Ферма в 1962, а в 1972 Шаблон:Не переведено 5Шаблон:Sfn нашёл прямое численное (тригонометрическое) решение треугольной задачи Ферма. Решение Куна и Куэна пригодно для многоугольников с более чем тремя сторонами, что неверно для случая решения Телье по причинам, объяснённым далее.
Задача Вебера заключается в случае треугольника в нахождении такой точки D по отношению к трём точкам A, B и C, что сумма стоимости перевозки от пункта D до трёх остальных точек была минимальна. Задача Вебера является обобщением задачи Ферма, поскольку использует равные и неравные силы притяжения (см. ниже), в то время как в задаче Ферма силы одинаковы. Задача была впервые сформулирована и решена для случая треугольника Томасом Симпсоном в 1750Шаблон:SfnШаблон:Sfn. Кун и Куэн нашли итеративное решение в 1962, а решение Телье, найденное в 1972, применимо как к задаче Вебера, так и к задаче Ферма. Решение Куна и Куэна применимо к случаю многоугольника с более чем тремя сторонами.
В простейшем случае задача притяжения-отталкивания заключается в нахождении такой точки D по отношению к трём точкам A1, A2 и R, что приложенные силы притяжения точек A1 и A2 приложенная и сила отталкивания точки R компенсируют друг друга [1]. Задача обобщает как задачу Ферма, так и задачу Вебера. Задачу сформулировал и решил для треугольника в 1985 Шаблон:Не переведено 5Шаблон:Sfn. В 1992 Чен, Хансен, Жомар и Туй нашли решение задачи Телье для многоугольников с более чем тремя сторонами.
Геометрическое решение Торричелли задачи Ферма для треугольника
Геометрическое решение Эванджелиста Торричелли задачи Ферма для треугольника опирается на два наблюдения:
1. Точка D имеет оптимальное положение, если любой сдвиг с этой точки приводит к увеличению суммарного расстояния до точек A, B и C, что означает, что оптимальная точка — это только та точка, в которой бесконечно малый сдвиг в направлении к одной из трёх точек равен сумме изменений до двух других точек. Другими словами, точка D одинаково притягивается точками A, B и C.
2. В выпуклом четырёхугольнике, вписанном в окружность, противоположные углы в сумме дают 180°. Можно это сформулировать следующим образом: если мы рассечём окружность хордой AB, мы получим дуги окружности, скажем, AiB и AjB. Любой опирающийся на дугу AiB угол ∠AiB один и тот же для любой точки i, а опирающийся на дугу AjB угол ∠AjB один и тот же для любой точки j. Более того, углы ∠AiB и ∠AjB в сумме дают 180°.
Можно доказать, что из первого наблюдения следует, что в точке оптимума углы, в вершинах треугольников, опирающихся на отрезки AD, BD и CD, должны быть равны 360° / 3 = 120°. Из этого Торричелли пришёл к выводу, что:
1. Если из треугольника ABD, угол ∠ADB которого равен 120°, образован вписанный в окружность выпуклый четырёхугольник ABDE, угол ∠AEB треугольника ABE должен быть равен (180° − 120°)= 60°;
2. Один из способов получения точки D, для которой угол ∠ADB равен 120° — построить равносторонний треугольник ABE (поскольку все углы равностороннего треугольника равны 60°), где точка E расположена вне треугольника ABC, и построить окружность, вокруг этого треугольника. Тогда для всех точек D’ описанной вокруг треугольника окружности, лежащих внутри треугольника, угол ∠AD’B равен 120°;
3. То же самое можно сделать для треугольников ACD и BCD;
4. Это приводит к построению равносторонних треугольников ACF и BCG, где F и G лежат вне треугольника ABC, а также к построению двух других окружностей вокруг этих равносторонних треугольников. Все три окружности пересекаются в одной точке D и углы, опирающиеся на отрезки AD, BD и CD будут равны 120°, что доказывает оптимальное положение точки.
Геометрическое решение Симпсона задачи Вебера для треугольника
Геометрическое решение Симпсона так называемой «задачи Вебера для треугольника» (которая была сформулирована Томасом Симпсоном в 1750) напрямую вытекает из решения Торричелли. Симпсон и Вебер подчёркивают факт, что в задаче минимизации перевозок выгода от приближения к точкам потребления A, B или C зависит от того, что везётся и за какую цену. Следовательно, выгода от приближения на некоторое расстояние меняется и углы ∠ADB, ∠ADC и ∠BDC больше не должны быть равны 120°.
Симпсон показал, что треугольники ABE, ACF и BCG, строящиеся аналогично решению Торричелли, где E, F и G расположены вне треугольника ABC, должны быть пропорциональны силам притяжения. В случае задачи Ферма треугольники были равносторонними, поскольку силы притяжения одинаковы
Решение таково:
1. В строящемся треугольнике ABE сторона AB пропорциональна силе притяжения Cw в направлении к C, сторона AE пропорциональна силе притяжения Bw в направлении к B, а сторона BE пропорциональна силе притяжения Aw в направлении к A.
2. В строящемся треугольнике BCG сторона BC пропорциональна силе притяжения Aw в направлении к A, сторона BG пропорциональна силе притяжения Bw в направлении к B, а сторона CG пропорциональна силе притяжения Cw в направлении к C;
3. Оптимальная точка D расположена на пересечении двух окружностей вокруг построенных треугольников ABE и BCG.
Третий треугольник ACF, где F находится вне треугольника ABC, может быть построена на стороне AC и можно построить третью окружность вокруг этого треугольника. Эта третья окружность пересекает две другие окружности в той же точке D.
Геометрическое решение Телье задачи притяжения — отталкивания
Для задачи притяжения — отталкивания в случае треугольника существует геометрическое решение. Оно было открыто относительно недавноШаблон:Sfn. Это геометрическое решение отличается от двух предыдущих, поскольку в этом случае строящиеся треугольники сил накладываются на треугольник размещения точек A1A2R (здесь A1 и A2 — точки притяжения, а R — точка отталкивания).
Решение таково:
1. В строящемся треугольнике RA2H, который накладывается частично на треугольник размещения точек A1A2R, сторона RA2 пропорциональна силе притяжения A1w в направлении к A1, сторона RH пропорциональна силе притяжения A2w в направлении к A2, а сторона A2H пропорциональна силе отталкивания Rw в направлении от R.
2. В строящемся треугольнике RA1I, который накладывается частично на треугольник размещения точек A1A2R, сторона RA1 пропорциональна силе притяжения A2w в направлении к A2, сторона RI пропорциональна силе притяжения A1w в направлении к A1, а сторона A1I пропорциональна силе отталкивания Rw в направлении от R;
3. Оптимальная точка D располагается на пересечении двух описанных вокруг построенных треугольников RA2H и RA1I окружностей. Решение не получается, если одна из сил больше суммы двух других или если углы не сравнимы. В некоторых случаях нет вышеупомянутых нарушений (никакая сила не больше суммы двух других и углы сравнимы), но оптимальное решение находится в точке с большей силой притяжения.
Тригонометрическое решение Телье задач Ферма и Вебера
Более 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)Шаблон:Sfn, эта треугольная «дыра» имеет в точности те же пропорции, что и «треугольники сил», которые мы строили в геометрическом решении Симпсона.
Чтобы решить задачу, нам следует добавить к указанным шести уравнениям седьмое, которое должно предотвратить появление треугольной «дыры» в центре треугольника точек притяжения. Другими словами, начала векторов должны совпадать.
Решение Телье задач Ферма и Вебера для треугольника осуществляется за три шага:
1. Определяем углы ∠αA, ∠αB и ∠αC, при которых три силы притяжения Aw, Bw и Cw уравновешивают друг друга, обеспечивая равновесие. Для этого используем следующие равенства:
- cos ∠αA = −( Bw2 + Cw2 − Aw2) / (2 Bw Cw) ;
- cos ∠αB = −( Aw2 + Cw2 − Bw2) / (2 Aw Cw) ;
- cos ∠αC = −( Aw2 + Bw2 − Cw2) / (2 Aw Bw) ;
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)Шаблон:Sfn расширил задачу Ферма – Вебера на случай отталкивающих сил. Рассмотрим случай для треугольника, в котором действуют две силы притяжения A1w и A2w и одна сила отталкивания Rw. Здесь, как и в предыдущем случае, возможен случай несовпадения начал трёх векторов. Таким образом, решение должно требовать их совпадения. Тригонометрическое решение Телье этой задачи следующее:
1. Определяем угол ∠e:
- cos ∠e = -( A1w2 + A2w2 − Rw2) / (2 A1w A2w) ;
2. Определяем угол ∠p:
- cos ∠p = -( A1w2 + Rw2 − A2w2) / (2 A1w Rw) ;
3. Определяем угол ∠c:
- ∠c = 180° − ∠p ;
4. Определяем угол ∠d:
- ∠d = ∠e − ∠c ;
5. Определяем значение угла ∠3 (это уравнение требует совпадения точек D и E):
- tan ∠3 = x / y ;
где x = sin ∠f – (RA1/RA2)(sin ∠d sin [∠e − ∠b] / sin ∠c) ; и y = (RA1/RA2)(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)Шаблон:Sfn предложили алгоритм, основанный на Шаблон:Не переведено 5 обобщающий Шаблон:Не переведено 5 для Шаблон:Не переведено 5. Их метод работает для задач Ферма и Вебера, в которых есть много сил, но не для задачи притяжения-отталкивания. В этом методе для нахождения приближения к точке y, минимизирующей взвешенную сумму расстояний
- <math>\sum_{i=1}^n w_i\, \|x_i-y\|,</math>
берётся начальное решение y0 и на каждом шаге алгоритм приближается к оптимальному решению путём выбора yj + 1, минимизирующего взвешенную сумму расстояний
- <math>\sum_{i=1}^n \frac{w_i}{\|x_i-y_j\|} \|x_i-y\|^2</math>,
где начальные веса wi делятся на расстояние от точки до приближения предыдущего шага. Каждая последующая аппроксимация может быть получена как взвешенное среднее единственного оптимального решения взвешенного метода наименьших квадратов:
- <math>\left. y_{j+1}=\left( \sum_{i=1}^n \frac{w_ix_i}{\| x_i - y_j \|} \right) \right/ \left( \sum_{i=1}^n \frac{w_i}{\| x_i - y_j \|} \right).</math>
Для задачи притяжения — отталкивания можно обратиться к помощи алгоритма, который предложили Чен, Хансен, Жомар и Туй (1992)Шаблон:Sfn.
Интерпретация теории стоимости земли в свете задачи притяжения — отталкивания
В мире экономической теории использования пространства отталкивающие силы вездесущи. Стоимость земли является их главной иллюстрацией. Фактически существенная часть теория стоимости земли, как сельской, так и городской, может быть подытожена следующим образом.
В случае, когда всех привлекает единственная точка притяжения (сельский рынок или центральный деловой район города), соревнование различных участников торгов, желающих разместиться в центре, образует цену земли, которая преобразует точку притяжения системы в точку отталкивания, определяемую высокой стоимостью земли, и каждый житель и деловая активность размещается в точке, где силы притяжения и отталкивания компенсируются.
Задача притяжения — отталкивания и новая экономическая география
Оттавино и Тисс (2005)Шаблон:Sfn рассматривают задачу Телье как прелюдию «новой экономической географии» (НЭГ), разработанной в 1990-х годах, за которую Пол Кругман получил Нобелевскую премию по экономике в 2008 г. Концепция сил притяжения родственна концепции агломерации или центростремительных сил НЭГ, а концепция отталкивающих сил родственна концепции рассредоточения или центробежных сил.
Примечания
Литература
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга. Английский перевод
Ссылки
- ↑ Здесь не имеются в виду силы, аналогичные гравитационным или электрическим, поскольку эти силы не зависят от расстояния.
