Оптимальное размещение сервисных центров с наибольшей степенью живучести на нечетких графах

Размещено на http://www.allbest.ru/

Технологический институт Южного Федерального университета в г. Таганроге

Научно-технический центр «Информационные технологии» Южного Федерального университета

Оптимальное размещение сервисных центров с наибольшей степенью живучести на нечетких графах

д.т.н., профессор Берштейн Л.С.

д.т.н., доцент Боженюк А.В.

д.т.н. Розенберг И.Н.

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

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

При размещении центров обслуживания на нечетком графе естественно рассмотреть задачу нахождения их «оптимального» расположения в том смысле, чтобы все (оставшиеся) вершины нечеткого графа обслуживались с наибольшей степенью живучести. Будем рассматривать случай, когда центры обслуживания размещаются только на вершинах нечеткого графа. Для рассмотрения этой задачи введем следующие понятия.

Основные понятия и определения. Пусть - нечеткий ориентированный граф [3] с числом вершин |X|=n. Пусть имеется k центров обслуживания (k<n), размещенных в вершинах подмножества Y, |Y|=k, Y X. Пусть, - степень достижимости вершины x_j из вершины x_i.

Величина

(1)

называется степенью живучести нечеткого графа [4] при его обслуживании k центрами из множества вершин Y.

Значение определяет минимаксную величину сильной связности между каждой вершиной из множества X\Y и одним из центров, расположенных в Y.

Иными словами, можно «выйти» из некоторой вершины подмножества Y, достичь любой вершину графа, «обслужить ее», «вернуться» обратно в исходную вершину и при этом конъюнктивная прочность такого пути будет не меньше величины .

Ясно, что величина зависит как от числа центров k, так и от расположения центров на вершинах графа (т.е. от выбора множества Y).

Таким образом, задача размещения k центров обслуживания (k<n) для конкретного нечеткого графа сводится к нахождению такого подмножества вершин YX, для которого значение степени живучести достигает наибольшего значения, т.е. величины

(2)

Нечеткое множество

задаваемое на множестве вершин n, называется нечетким множеством живучести нечеткого графа .

Нечеткое множество живучести определяет наибольшие степени живучести графа при его обслуживании 1,2,…,n центрами.

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

Свойство 1. Справедливо равенство:

.

Иными словами, степень живучести нечеткого графа при его обслуживании одним центром обслуживания совпадает со степенью живучести самого графа.

Свойство 2. Справедливо равенство:

Иными словами, степень живучести нечеткого графа при его обслуживании n центрами обслуживания равно 1.

Свойство 3. Справедливо высказывание:

Иными словами, чем больше центров обслуживания, тем больше возможная степень живучести нечеткого графа.

Рассмотрим нечеткий граф , приведенный на рис.1. Его нечеткое множество живучести определится как:

.

Рис. 1. Пример нечеткого графа 1.

Для нахождения оптимального расположения центров обслуживания, при котором степень живучести нечеткого графа достигает своего наибольшего значения, рассмотрим следующую теорему:

Теорема [4]. Для того чтобы величина была наибольшей степенью живучести нечеткого графа при наличии k центров и при этом , необходимо и достаточно, чтобы существовало единственное разбиение множества вершин X на k классов ={X₁,X₂,…,X_k} так, чтобы нечеткие подграфы , ,…, , определяемые этими классами, являлись максимальными подграфами со степенями внутренней и внешней живучести соответственно , , …, ,, …, , для которых выполнялось бы условие:

(3)

При этом

(4)

Данная теорема позволяет обосновать следующий подход к размещению центров.

Для того чтобы «оптимально» разместить k центров в нечетком графе с n вершинами (k<n) с наибольшей степенью живучести, необходимо произвести разбиение графа на k максимальных, непересекающихся подграфов, для которых выполняется условие (3). Далее, поместить по одному центру обслуживания в любую из вершин выделенных подграфов. При этом степень живучести всего подграфа определится минимальной из степеней выделенных подграфов. Однако, если выделение k максимальных подграфов невозможно, то это означает, что можно «обслуживать» граф, не уменьшая степень живучести и меньшим (по сравнению с k) числом центров.

Метод нахождения сервисных центров с наибольшей степенью живучести. Рассмотрим метод нахождения всех минимальных множеств центров обслуживания, имеющих наибольшую степень живучести. Данный метод является обобщением метода Магу для четких графов [5] и подобен методу нахождения минимальных внешне устойчивых множеств для нечетких графов [3]. нечеткий множество живучесть сервисный

Пусть Y - некоторое подмножество вершин нечеткого графа , в которых находятся центры и при этом степень живучести равна V.

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

а) вершина принадлежит рассматриваемому множеству Y;

б) существует некоторая вершина , которая принадлежит множеству Y и при этом для степеней достижимости выполняются неравенства и .

Переходя к кванторной записи, мы получаем истинность следующего высказывания:

(5)

каждой вершине поставим в соответствие булеву переменную , принимающую значение 1, если и 0 в противном случае. Высказыванию поставим в соответствие нечеткую переменную

Переходя от кванторной записи высказывания (5) к записи через логические операции, получаем истинность логического высказывания

Полагая и учитывая, что для любого выполняется равенство , окончательно получаем:

(6)

В выражении (6) раскроем скобки и приведем подобные члены, используя правила нечеткого поглощения (7):

(7)

если .

Здесь и .

В результате выражение (6) будет представлено в виде:

. (8)

Свойство. Если в выражении (8) дальнейшее упрощение на основе правил (7) невозможно, то для каждого i-го дизъюнктивного члена совокупность всех вершин, соответствующая переменным, дает подмножество вершин YX с вычисленной степенью живучести V_i нечеткого графа . При этом вычисленное подмножество Y является минимальным в том смысле, что любое его подмножество указанным свойством не обладает.

На основании доказанного свойства можно предложить следующий метод нахождения всех минимальных центров обслуживания, при которых рассматриваемый нечеткий граф имеет наибольшую степень живучести:

- Для рассматриваемого нечеткого графа записать выражение (6);

Упрощая выражение (6) с использованием правил нечеткого поглощения (7), привести его к виду (8);

-По полученным дизъюнктивным членам разложения (8), выписать минимальные множества центров с вычисленными максимальными степенями живучести.

Пример оптимального нахождения сервисных центров. Найдем минимальные множества сервисных центров для нечеткого графа, приведенного на рис.2:

Рис. 2. Пример нечеткого графа 2.

Матрица смежности вершин графа имеет вид:

Возведя матрицу смежности в степени 2, 3,…, 6, объединяя их и учитывая, что - единичная матрица размерностью 77, находим матрицу достижимости нечеткого графа в виде:

Выражение (6) для этого графа примет следующий вид:

Логически перемножая полученные скобки и используя правила поглощения, окончательно получаем:

Из последнего равенства следует, что нечеткий граф , приведенный на рис.2, имеет одно максимальное подмножество вершин (т.е. все вершины графа), при помещении центров в которые граф имеет степень живучести 1; имеет одно максимальное подмножество вершин при помещении центров в которые граф имеет степень живучести 0,9; имеет шесть максимальных подмножеств вершин, например при помещении центров в которые граф имеет степень живучести 0,8; имеет 11 максимальных подмножеств вершин, например , при помещении центров в которые граф имеет степень живучести 0,5; имеет 9 максимальных подмножеств вершин, например при помещении центров в которые граф имеет степень живучести 0,2.

Нечеткое множество живучести рассматриваемого графа будет иметь вид:

Анализируя данное множество, можно прийти к выводу, например, что нет смысла размещать 5 центров обслуживания на этом графе, так как наибольшая живучесть при этом будет совпадать с живучестью, достигаемой и при 4 центрах. И наоборот, целесообразно увеличить число центров с 2 до 3, так как в этом случае степень живучести нечеткого графа увеличится более чем в 2 раза (с 0,2 до 0,5).

Заключение

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

Литература

1. Кристофидес Н. Теория графов. Алгоритмический подход: Пер. с англ. - М.: Мир, 1978.

2. Malczewski J. GIS and Multicriteria Decision Analysis. - New York: John Wiley&Sons Inc., 1999.

3. Берштейн Л.С., Боженюк А.В. Нечеткие графы и гиперграфы. - М.: Научный мир, 2005.

4. Боженюк А.В., Розенберг И.Н., Старостина Т.А. Анализ и исследование потоков и живучести в транспортных сетях при нечетких данных - М.: Научный мир, 2006.

5. Кофман А. Введение в прикладную комбинаторику: Пер. с франц. - М.: Наука, 1975.

Размещено на Allbest.ru