IX Международная студенческая научная конференция Студенческий научный форум - 2017

Задача оптимального размещения центров, нечетко обслуживающих заданную область (например, размещения телевизионных или радиопередающих станций на некоторой территории, станций скорой помощи, предприятий сервиса, размещение центров торговали, обслуживающих некоторый район и т.д.) может быть сформулирована как задача нахождения минимальных нечетких внешних устойчивых множеств [1-3].

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

Будем считать, что некоторая территория разделена на п районов. На территории находится к центров обслуживания. Предполагается, что каждый обслуживающий центр может находиться в некоторой стационарной точке каждого района. Из этой точки центр контроли­рует весь район, а также соседние и некоторые граничащие ними рай­оны с заданной степенью обслуживания. В процессе эксплуатации центры могут выходить из строя (например, в результате поломки или для планового ремонта). Необходимо для заданного числа действующих центров определить места их наилучшего размещения, т. е., тако­го месторасположения, чтобы контроль всей территории осуществлял­ся с максимально возможной степенью обслуживания. [1].

Степень обслуживания всей территории определяется минималь­ным значением из степеней обслуживания каждого района. Учитывая, что степень обслуживания может не обладать свойством симметрич­ности (например, в силу специфики месторасположения центра и рельефа местности), моделью такой задачи является нечеткий ориен­тированный граф, вершины которого представляют районы территории, а нечеткие ориентированные ребра - степени обслуживания. Задача размещения центров в этом случае сводится к нахождению минимальных нечетких внешне устойчивых множеств. [1-3].

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

Будем считать, что территория города Мелитополь разделена на 7 районов (исторически и географически), показанных на рис. 1.

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

Рис. 1. Территория города Мелитополь, разделена на районы

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

Рис. 2. Нечеткий граф, соответствующий территории города Мелитополь

Величина определяет степень обслуживания і-го района в случае нахождения ретранслятора в j-м районе.

Задача размещения ретрансляторов в данном случае сводится к нахождению минимальных нечетких внешних устойчивых множеств.

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

. (1)

Множество X' назовем нечетким внешне устойчивым множеством для вершины y со степенью внешней устойчивости γ(y). Множество X назовем нечетко внешним устойчивым множеством графа G со степенью внешней устойчивости Учитывая выражение (1), получим . Минимальным внешне устойчивым множеством графа со степенью называется подмножество если для любого подмножества выполняется условие [2].

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

Пусть T – некоторое нечеткое внешне устойчивое множество нечеткого графа

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

1. вершина принадлежит множеству T, которое рассматривается;

2. существует некоторая вершина , которая принадлежит множеству T и при этом функция принадлежности [3].

Другими словами, справедливо следующее утверждение:

. (2)

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

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

(3)

Принимая и учитывая, что для любого выполняется равенство , получим . (4)

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

(5)

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

. (6)

Свойство 1. Если в выражении (6) дальнейшее упрощение на основе правил нечеткого поглощения невозможно, тогда для каждого i-го дизъюнктивного члена совокупность всех вершин, соответствующих переменных, которые в ней находятся, дает минимальное внешне устойчивое множество с вычислением степени внешней устойчивости [3].

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

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

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

• по полученным диз'юнктивними членами разложения (6), выписать минимальные нечеткие внешне устойчивые множества за вычетом степенями внешней устойчивости.

Применяя данный метод, найдем все минимальные нечеткие внешне устойчивые множества графа . Для этого запишем все выражения для :

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

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

• при наличии трех или четырех трудоспособных ретрансляторов – их размещение в районах 1, 3 и 6 (один ретранслятор в резерве или ремонте); степень обслуживания территории равна 1;

• при наличии двух трудоспособных ретрансляторов – их размещение в районах 3 и 6 (два в ремонте); степень обслуживания территории равная 0,9;

• при наличии одного трудоспособного ретранслятора – его размещение в районе 4 (три в ремонте); степень обслуживания территории равна 0,5.

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

Список литературы.

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

2. Берштейн Л.С., Беляков С.Л., Боженюк А.В. Метод Магудля нахождения нечеткого множества баз нечеткого темпорального графа // Известия ЮФУ. Технические науки. – 2014. -№ 1 (150) – с. 70-75.

3. Боженюк А.В. Определение внешней устойчивости нечеткого темпорального графа // Материалы международной научно – практической конференции «Современные направления теоретических и прикладных исследований 2012». – Выпуск 1. Том 10. – Одесса: КУПРИЕНКО, 2012. – с. 23-25.

Код для цитирования: Скопировать