main

—Перегруженные регионы, в которых запрещено размещение предприятия, но транспортировка доступна и облагается пошлиной.

—Барьерные регионы, в которых запрещено размещение и не доступна транспортировка.

Katz и Cooper (1981) впервые изучили задачу Ферма–Вебера c одним круговым барьером. Для решения задачи они предположили, эвристический алгоритм, основанный на техники последовательной безусловной минимизации (SUMT). Klamroth (2004) в той же самой задаче разделила регион размещения на несколько выпуклых регионов, число выпуклых регионов ограничено числом ( 2), где —число источников сырья и рынков сбыта. Klamroth (2001b) рассмотрела задачу Ферма–Вебера на плоскости с линейными барьерами с конечным числом проходов. Она доказала, что время затрачиваемое на решение задачи экспоненциально растет с ростом числа проходов.

McGarvey и Cavalier (2003) разработали метод (BSSS) которые находил приблизительный глобальный оптимум для задачи Ферма–Вебера с выпуклыми многогранными забытыми регионами. Учитывая, как произвольной формы барьеров и выпуклые запрещено регионов, Батта и соавторы (1989) обобщил результаты Ларсон и Садик (1983).

Wang и соавторы (2002) сформулировал математическую модель решения задачи, где источники сырья и рынки сбыта имеют конечный размер и барьеры представлены в виде прямоугольников. Для линейных барьеров с различными функциями расстояния Klamroth и Wiecek (2002), предлагают алгоритм многокритериальной задачи размещения. Canbolat и Wesolowsky (2010) представили решение задачи Вебера с прямолинейной функцией расстояния с вероятностными линейными барьерами.

Данную задачу можно отнести к задачам нелинейной оптимизации, а именно к задаче Ферма–Вебера с линейными барьерами и евклидовой функцией расстояния. Данные задачи очень актуальны в современном мире, при транспортировке грузов всегда встречают на своем пути такие линейные преграды как: реки, автомагистрали, железные дороги, горные гряды и т.д.

11

2. Содержательная и формальная постановка

задачи

2.1. Содержательная постановка задачи

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

2.2. Формальная постановка задачи

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

2.2.1. Задача без ограничений

Формально модель можно описать следующим образом. Предприятие производит один продукт и использует источников сырья для его производства. Продукт и сырье продаётся и покупается на заданном числе

= { 1, . . . , } 2 рынков сбыта продукции и источников сырья. Точка

12

может быть одновременно как и рынком сбыта, так и/или источником одного или нескольких видов сырья. Количество потребляемой продукции и производимого сырья для точки дано и определено с помощью:( ), 1( ), . . . , ( ) (некоторые, но не все величины ( ), . . . , ( ) могут быть равны нулю). Транспортный тариф на транспортировку сырья и готовой продукции постоянен и определён как: , 1, . . . , . Наконец, расстояние между любыми двумя точками задаётся некоторым функционалом [2].

Определим идеальный вес, который равен общим суммарным транспорт-

ным издержкам, которые предприятие тратит на доставку готовой продукции

Данный идеальный вес, есть сила с которой точка притягивает к себе предприятие [2].

Задача Ферма–Вебера состоит в нахождении точки 2 в которой функция транспортных затрат ( ) достигает своего минимума, и где функция транспортных затрат равна:

Пусть точки распределены на плоскости. Тогда функция транспортных затрат примет вид:

√

Где ‖ − ‖ = ( 1 − 1)2 + ( − 2)2 есть евклидово расстояние между точками и . Так как точки не коллинеарны, то целевая функция ( )

может быть представлена в виде строго выпуклой функции, таким образом задача Ферма–Вебера с евклидовой функцией расстояния, имеет единственное решение [2].

Выпуклую оболочку множества назовем Полигоном Размещения, для простоты будем называть его просто ПР [2].

13

Для задачи Ферма–Вебера с евклидовым расстоянием Кун [3] показал, что пункт оптимального размещения принадлежит ПР, и этот результат нельзя улучшить. Для того чтобы показать это, достаточно показать частный случай множества для которого любая точка лежащая в ПР, есть точка оптимального размещения, которая соответствует условиям задачи Ферма– Вебера .

Рассмотрим задачу локационного треугольника. Из книги Куна [3], мы знаем, что любая внутренняя точка ¯ треугольника, получается путем решения многофакторной задачи минимизации: ‖ 1 − ‖ ‖ 2 − ‖ и ‖ 3 − ‖. Следовательно, существуют такие веса ≥ 0 для = 1, 2, 3, что:

Очевидно, что по крайней мере один вес положителен, скажем, что 1

строго положителен. Предположим тогда, что два других равны нулю. В этом случае, точка ¯ должна быть лежать в точке 1, что приводит нас к противоречию. Пусть только один вес равен нулю, предположим, что

3 = 0. Тогда, точка ¯ должна принадлежать отрезку [ 1, 2], что приводит

в очередной раз к противоречию. Следовательно все три веса должны

3

∑

быть строго положительны. Так как · ‖ − ‖ строго выпукла, то точка

=1

¯ будет единственной точкой минимума функции ( ), которая зависит от весовых соотношений 1, 2 и 3 [2].

Из сказанного выше следует, задача Ферма–Вебера с евклидовой функцией расстояния, непрерывна, и следовательно, из формулы (2), каждую точку можно рассматривать как источник силы которая притягивает предприятие к себе и сила притяжения точки растет, с ростом идеального веса

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

14

2.2.2. Численное решение задачи без ограничений

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

2

которое означает, что сила притяжения точки , больше или равна сумме сил притяжения всех остальных источников в этой точке. Или когда задача имеет симметричных характер [5].

Итерационное решение задачи. Оптимальное решение задачи удовлетворяет первому условию существования минимума функции ( ):

Другими словами, сумма сил в точке оптимума равна нулю [2].

Из формулы (5) следует, что не существует простого аналитического решения. Следовательно, для определения оптимального местоположения, требуется метод последовательных приближений. Принципиальная схема была разработана Weiszfeld (1936), но она была заново открыта несколькими независимыми авторами. Weiszfeld отметил, что условие (5) можно переформулировать так:

15

Тогда начав наши вычисления в некоторой точке начального приближения 1 (которая может являться точкой оптимума нашей задачи), и вычислив

‖ − 1‖ для каждой точки из множества и из формулы (6) получив новую точку 2, заменив выражение ‖ − 1‖ выражением ‖ − 2‖, мы в конечном итоге, проведя −1 итерацию, получим точку −1, вычислив значение

‖ − −1‖, можно легко аналогично получить -ую точку . Эта процедура продолжается до тех пор, пока значение ( ) не будет достаточно близко к значению ( −1). Этот алгоритм может быть переписан в рекурсивном виде:

где grad ( −1),есть градиент ( ) в точке −1. Было показано, что точка

стремится к точке равновесия при условии, что не одна из точек приближения

, = 1, . . . , не совпадает с точкой [3]. Причина этого ограничения в том, что градиент ( ) не существует в точке = .

Ostresh предложил заменить формулу (7) следующей формулой:

когда −1 = , и показал, что алгоритм (7)–(8) всегда стремиться к точке оптимального размещения.

Данный алгоритм применяется тогда, когда любая точка Полигона Размещения, может быть потенциальной точкой оптимального размещения.

2.2.3. Формальное введение барьеров

Линейные барьеры в задаче Ферма–Вебера могут быть смоделирована следующим образом: Пусть = {( , ) 2 : = + } линия, и пусть

{ : = {1, . . . , }} будет множество точек лежащих на линии . Тогда

будет называть линией барьера c проходами, или просто линия барьера [11].

16

Район возможных размещений определен, как объединение двух замкнутых полуплоскостей 1 и 2, которые являются множествами лежащими с обеих сторон линии . Здесь объединение 1 2 = 2, так как линия

= + принадлежит обоим полуплоскостям 1 и 2. Результат легко переносится на случай, когда линия барьера имеет конечную ширину, но для упрощения модели мы будем использовать это определение, конечно размещение предприятия на линии запрещено [11].

Кроме того, конечное число источников сырья и/или рынков сбыта продукции: , = {1, . . . , } задается в каждой полуплоскости , = 1, 2, и представлены точками из множества 2. Положительное

значение = ( ) + связано с каждой точкой и обозначает вес

точки [11].

Основное различие между моделью с барьерами и без заключается в

функции расстояния. Функция расстояния , для задачи Ферма–Вебера с барьерами, определяется как длина кратчайшего пути, который не пересекает

линию барьера. Таким образом, определяется

— это проход в барьере, через который проходит кратчайший путь между двумя точками и , которые расположены в противоположных полуплоскостях. Заметим, что для функции , неравенство треугольника по-прежнему выполняется, но при этом функция не является однородной. Как следствие целевая функциия задачи размещения с барьерами, не выпукла [11].

Основная идея решения задачи Ферма–Вебера с барьерами можно представить в следующем виде: Предположим, что оптимальное решение проблемы находится в полуплоскости 1. Тогда проходы в барьере можно представить как исскуственные источники сырья и/или рынков сбыта. Решение задачи может быть получено с помощью задачи Ферма–Вебера без барьеров в полуплоскости 1. Поиск соответствующих подмножеств и исскуственных весов, есть комбинаторная задача [11].

17

Можно воспользоваться формулой (10) и переписать целевую функцию для точки .

Лемма 1. Пусть есть расстояние полученное с помощью евклидовой нормы, и , {1, 2}, ̸= . Тогда существуют проходы 1 , . . . , такие, что

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

Лемма 2. Рассмотрим задачу Ферма–Вебера с барьерами и пусть будет евклидовым расстоянием таким, что если условие:

18

Теорема 1. В условиях леммы 2 (15,16), каждое оптимальное решение

* * задачи Ферма–Вебера с линейным барьером является также

оптимальным решением соответствующей подзадачи Ферма–Вебера без барьеров, которая получена с помощью источников сырья и/или рынков

сбыта: ( , . . . , , 1, . . . , ) для ( {1, 2}) и целевой функции * .

1

В случае выполнения условия Леммы 2 (17,18), из Теоремы 1 можно получить следующее следствие:

Следствие 1. В предположении выполнения Леммы 2 (17,18), существу-

ет по крайней мере одно оптимальное решение * * задачи Вебера с

барьерами, которое также есть оптимальное решения соответствующей задачи Ферма–Вебера без барьеров с источниками сырья и/или рынков сбыта:

( 1, . . . , , 1, . . . , ) для ( {1, 2}) и целевой функции * .

Данные теоремы, предоставленные в работе [11] показывают, что задачу Ферма–Вебера с барьерами, можно свести к решению конечного числа задач Ферма–Вебера без ограничений.

19

3. Алгоритм решения

Случай когда существует только один проход в барьере тривиален. Пусть и , {1, 2}, ̸= . Любой путь из существующих точек размещения в точку проходит через проход . Следовательно целевая функция для точки может быть записана в виде:

Так как вес точки есть сумма весов всех фиксированных точек полу-

равны, то точка находится в . в этом случае, задача Ферма–Вебера без барьеров, должна быть решена не больше двух раз (для каждой из полуплоскостей). Это может быть сделано с сложность ( ), где ( ) — сложность полиноминальных алгоритмов.

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

Линейный барьер с двумя проходами. Для = 1, 2 определим дистанцию между существующими точками размещения и двумя проходами

1 и 2

и без потери общности допустим, что точки размещения упорядочены по возрастанию (1) ≤ · · · ≤ ( ). Кроме того, пусть {1, 2} c ̸= . Кратчайший путь КП из существующей точки в точку

проходит через один из проходов 1 и 2, зависить от следующих условий:

20