Теоретичні засади підвищення ступеня живучості нечіткої мережі аеропортів до заданого рівня

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

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

Теоретичні засади підвищення ступеня живучості нечіткої мережі аеропортів до заданого рівня

У статті наведено теоретичні засади побудови графової моделі живучості нечіткої мережі в термінах теорії нечітких множин другого типу. Вивчена можливість і коректність узагальнення поняття нечіткого графа з точки зору представлення сукупності n-арних відношень для довільного скінченного . Введені визначення нечіткого гіперграфу . Показане природнє поширення поняття степеня живучості на гіперграфи . Відмічені основні випадки зниження живучості нечіткого орієнтованого графу Проаналізована задача збільшення степеня живучості нечіткої транспортної мережі за критерієм найменших витрат і її тлумачення в питаннях авіаційних перевезень. Запропоновано модифікацію відомого алгоритму, який дозволяє збільшити сумарне значення функцій належності ребер нечіткого графа, щоб степінь його живучості досягла необхідного значення. Обґрунтовано, що за допомогою розглянутих теоретичних засад запропонований алгоритм дозволяє підвищити степінь живучості нечіткої мережі аеропортів до заданого рівня.

Досліджуючи питання життєвих циклів конкретного аеропорту автори прийшли до висновку доцільності розгляду мережі аеропортів і знаходження її степені живучості. Поняття живучості транспортної мережі на сьогодні знаходиться на початковому етапі вивчення, а загальних термінів «живучість мережі авіаперевезень», «живучість системи аеропортів» не існує. Під економічною живучістю мережі аеропортів будемо розуміти здатність її економічних об'єктів і зв'язків між ними протидіяти внутрішнім і зовнішнім впливам політичних, соціальних, економічних інцидентів, зберігаючи при цьому здатність повністю або частково відновлювати об'єкти, які зазнали негативного впливу. Вводячи поняття економічної живучості мережі аеропортів маємо на меті розробку інструментарію оцінки ризиків виникнення економічної нестабільності системи аеропортів та можливих загроз банкрутства, який в свою чергу доповнить існуючі методи вимірювання економічної безпеки окремих аеропортів (елементів досліджуваної мережі), виявляючи в системі додаткові якісні характеристики. Враховуючи те, що живучість мережі аеропортів залежить від вилучення або доповнення певного елемента, розриву деякої гілки зв'язку, доцільно вивчати мережу аеропортів на основі теоретико-графового підходу як складну систему з властивими їй характеристиками. Майже всім складним системам, до яких, зокрема, відносяться економічні, соціально-економічні, притаманна проблема невизначеності. Насьогодні ця проблема передбачає застосування нових інформаційних технологій, складовою частиною яких є інтелектуальні засоби обробки інформації.

Задачі, що включають в себе умови невизначеності, являють собою слабо структуровані або неструктуровані задачі. Слабо структуровані задачі відрізняються невідомими або невимірюваними компонентами, тобто компонентами, кількісно неоцінюваними. Такі задачі, в свою чергу, характеризуються відсутністю методів розв'язання на основі безпосереднього перетворення даних. Застосування THM дозволяє побудувати формальні схеми розв'язання задач, що характеризується тим чи іншим ступенем невизначеності, яка може бути обумовлена неповнотою, внутрішнім протиріччям, неоднозначністю і розмитістю початкових даних, що являють собою наближені кількісні або якісні оцінки параметрів об'єктів.

В останні роки разом із звичайними нечіткими множинами першого типу (HM) [4, с. 5-49] більшого застосування знаходить теорія нечітких множин другого типу (THM₂), хоча її використання супроводжується підвищенням обчислювальної складності алгоритмів [9,10]. Використання THM₂ доцільно у випадках очікування суттєвого покращення результатів (зокрема підвищення «точності» прогнозування, покращення якості кластеризації). Аналіз теорій невизначеностей показує, що задачі в умовах невизначеності в багатьох випадках відносяться до класу NP-повних задач, розв'язання яких можливе з використанням вкладених методів «м'яких обчислень» [1, 6].

Наведені міркування вказують на актуальність даних досліджень з використаннямTHM₂ при вивченні задачі підвищення степеня живучості нечіткої системи аеропортів і побудови на її основі нечіткого графа .

Теорія живучості транспортних систем і проблема підвищення степеня живучості нечітких транспортних мереж на сьогоднішній день знаходиться на стадії становлення. Авторам відомі наступні публікації в даному напрямку [3, 8].

Метою дослідження є вивчення теоретичних засад підвищення степеня живучості нечіткої множини аеропортів.

Для розв'язання конкретних практичних задач запропоновананаступна інтерпретація нечітких множин типу 1HM₁ та типу 2 HM₂:

Визначення 1., (1)

граф мережа аеропорт

де - універсальна множина, - функція належності елемента множині, називається нечіткою множиною типу 1 [5].

Визначення 2. , (2)

де - універсальна множина, - множина функцій належності , що характеризує степінь належності символів і - множина, що характеризує вторинну функцію належності множині, називається нечіткою множиною 2-го типу.

Пропонується наступнакласифікація теорій нечітких множин першого типу(THM₁) в залежності від визначення операцій перетину і об'єднання нечітких множин:

Таблиця 1. Класифікація теорій нечітких множин першого типу, авторська розробка

В теоріяхHM₂ вирізняють, зокрема, загальну (ЗHM₂) і інтервальну (IHM₂) нечіткі множини [8]. Крім того, автори статті виокремлюють теорії HM₂ (аналогічноTHM₁) в залежності від визначення операцій об'єднання і перетину, заданих в них.

Наведемо завдання дискретноїHM₂ наступним чином. Нехай елемент може приймати значення.Тоді функція належності. Цей факт можна описати матрицею (табл. 2):

Таблиця 2. Матриця значень функції належності, авторська розробка

і множиною точок в декартовій системі координат на площині рис. 1.:

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

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

Рис. 1. Графік дискретної функції належності нечіткої множини типу 2, авторська розробка

Зауваження. У випадку, коли для кожного неоднакова кількість тобто не існує єдиного , матрицю доповнюють нулями.

Кожне значення має свою функцію належності

. (3)

Цей факт, в свою чергу, можна описати матрицею (Табл.3):

Таблиця 3. Матриця значень функції належності, авторська розробка

і множиною точок в декартовій системі координат в тривимірному проекторі рис. 2.:

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

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

Рис. 2. Графік неперервної функції належності нечіткої множини типу 2, авторська розробка

Третій вимір характеризує вторинну функцію належності нечіткій множині - функція належності для . Її ще називають слідом невизначеності (FOU).

При побудові графових моделей нечіткої мережі аеропортів виникає задача представлення знань у вигляді, що дозволяє компактно зберігати і формально опрацьовувати необхідну різноманітну інформацію, залишаючи при цьому первісний зміст і взаємозв'язки. Природними моделями, які підтримують об'єктно-предикатний підхід, є неорієнтовані і орієнтовані гіперграфи, що є суттєвим узагальненням поняття графів з точки зору представлення ними сукупності n-арних відношень для довільного скінченного [2]. Нечіткий орієнтований гіперграф можна розглядати або як довільний набір нечітких підмножин, визначених в одній множині, або як сукупність нечітких симетричних відношень різної n-ості [7].

Вивчаючи питання живучості мережі аеропортів для врахування природної невизначеності скористаємося поняттям нечіткого орієнтовного графа[8] та введемо поняття нечіткогоорієнтованогогіперграфа.

Визначення 3. Нечітким орієнтованим гіперграфомбудемо називати пару множин: нечітку множину ,- множину вершин і чітку множину - множину орієнтованих ребер, причому кожна- вершинає розпливчатим кортежем в D. Тут . Деяка вершинаможезустрічатись в кортежінеодноразово, причому може мати різні значення в залежності від місця в кортежі.

Якщо кожне реброгіперграфа містить рівно дві вершини (елемента) в кортежі, то отримується нечіткий орієнтований граф.

Величину

(4)

будемо називати міцністю вершини .

Будь-який відрізок ребра , який складається з попарно сусідніх елементів і містить не менше двох сусідніх елементів, називається фрагментом. Можна визначити міцність фрагменту як мінімальне значення функцій належності вершин, що входить в нього. Кожна вершина гіперграфа однозначно зображається нечітким орієнтованим графом, який має ту ж саму множину дуг, що й гіперграф.

Дві вершини ібудемо називати суміжними по ребру , якщо вони розташовані в кортежі на сусідніх позиціях, а величину - степенем суміжності вершини іпо ребру .

Визначення 4. Величину

(5)

будемо називати ступенем суміжності вершин ів гіперграфі.

Ступенем живучості нечіткого графа називають величину, що визначається виразом,

(6)

де- степінь досяжності вершини з вершини , - сім'я нечітких шляхів з вершини в вершину

,,. (7)

Останнє поняття природно узагальнюється для гіперграфа.

Визначення 5. Нечітким орієнтованим графом будемо називати пару множин, - нечітку множину типу 2 вершин в деякій універсальній множині, тобто з множинною функцій належності .Функції належності, і - чітку множину ребер, де .

Іншими словами, кон'юнктивна міцність шляху нечіткого графа визначається найменшим значенням вторинної функції належності вершин, що входять до нього, за виключенням початкової і кінцевої вершин від найменшого значення первинних функцій належності.

Поняття ступеня живучості нечітких графів фактично співпадають, базуючись на співпадаючих поняттях ступеня досяжності[8].

Якщо позначити через деякий підграф нечіткого графа ,, то ступень його живучості визначається виразом:

(8)

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

Питання живучості нечіткого орієнтованого графу (як і для ) пов'язане, зокрема, з двома можливими випадками:

1) руйнування частин шляхів (ребер) між вершинами (зокрема за причини руйнування (вершин) може привести до порушення сильної зв'язності графа, і живучість сурграфа буде дорівнювати 0.

2) руйнування частин шляхів (ребер) зберігає сильну зв'язність всієї мережі. Це означає, що аналогічно, як і в графі, який є сильно зв'язним, між будь-якими двома вершинами існує шлях з кон'юнктивною міцністю не меншою , і вилучення одного або декількох ребер не зменшує ступінь живучості отриманого графа.

3) З наведених міркувань випливає наступна властивість.

Властивість 1. Якщо руйнування шляхів (ребер) між вершинами нечіткого графа зберігає його сильну зв'язність, то має місце нерівність, де- сурграф нечіткого орієнтованого графа.

Розглядаючи нечіткий граф (для спрощення усвідомлення постановки задачі, збільшення степеня живучості нечіткої транспортної мережі, в подальшому ), розглянемо вказану задачу за критерієм найменших витрат. Тут під витратами при вивченні системи аеропортів можуть розумітись додавання нових ребер (поява нових авіарейсів), збільшення значень функцій належності вершин (аеропортів), тощо. В загальному випадку розв'язання такої задачі зводиться до громіздкого перебору і значних часових витрат. З іншого боку, модифікуючи відомий алгоритм [3] для нечіткого графа другого роду, який дозволяє знаходити найменшу величину, на яку необхідно збільшити сумарне значення функції належності ребер нечіткого графа другого роду, щоб степінь його живучості досягла необхідного значення , можна розв'язати подібну задачу для нечіткого графа. Для цього можна засто-совувати перетворення в . Тоді основну ідею цього алгоритму можна сформулювати наступним чином:

Вводимо чотири вектори-стовпчики і чотири вектори-рядочки розмірністю і відповідно:

· Вектор-стовпчик необхідного збільшення значення функції належності вершин і ребер , тобто, значення, на яке треба збільшити функцію належності вершини і ребра для досягнення необхідної величини;

· Вектор-стовпчик L-довжина шляху від зафіксованої вершини (і названої першого) до розгадуваної;

· Вектор-стовпчик попередніх вершин, де - це номер вершини, з якої шлях приводить в вершину ;

· Вектор-стовпчик розгляду вершин . Якщо всі шляхи з вершини розглянуті, то навпроти даної вершини в усьому стовпчику ставиться «1», в протилежному випадку «0»;

· Вектор-рядок необхідного збільшення значення функції належності вершин і ребер , де - значення, на яке треба збільшити функцію належності вершини і ребра , щоб досягнути необхідної величини ;

· Вектор-рядок - довжина шляху (кількість ребер) від досліджуваної вершини до першої;

· Вектор-рядок попередніх вершин, де- номер вершини, в яку можна прийти з вершини ;

· Вектор-рядок розгляду вершин . Якщо всі шляхи, по яких можна прийти в вершину розглянуті, то відповідно даній вершині присвоюється «1», в протилежному випадку «0».

Вибираючи у першу чергу для якої ми обходимо тільки ті вершини нечіткого графа, яких достатньо для досягнення необхідного значення .

Підсумовуючи результати проведеного дослідження, можна зазначити, що вказаний метод сприяє підвищенню степені живучості мережі аеропортів з врахуванням інформації про об'єкти мережі до заданого значення без врахування вартості необхідних для цього заходів.

Поглиблення вивчення питань, розглянутих в даному дослідженні та [8], а також вивчення питання мінімізації витрат на підвищення степені живучості нечіткої мережі аеропортів є перспективним напрямком подальших досліджень.

Література

граф мережа аеропорт

1. Аверкин А.Н. Нечеткие множества в моделях управления и искуственного интелекта / А.Н. Аверкин; [под. ред. Д.А. Поспелова]. - М.: Наука 1986. - 312 с.

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

3. Боженюк А.В. Нахождение живучести нечетких транспортних сетей с применением геоинформационных систем - А.В. Боженюк, И.Н. Розенберг, Д.Н. Ястребинская. - М.: Научний мир, 2012. - 176 с.

4. Заде Л. Основы нового подхода к анализу сложных систем и процессов принятия решений: Пер. с англ. // Математика сегодня: Сборник статей. - М.: Знание. - 1974. -193 с.

5. Заде Л. Понятия лингвистической переменной и его применение к принятию приближенных решений / Л. Заде. - М.: Мир, 1976. - 100 с.

6. Кофман А. Введение в теорию нечетких множеств - А. Кофман; [пер. с фр.]. - М.: Радиосвязь, 1982. - 432 с.

7. Круглов В.В. Нечеткая логика и искусственные нейронные сети / В.В. Круглов, М.М. Дли, Р.Ю. Голунов. - М.: Физмалит, 2001. - 224 с.

8. Олешко Т.І. Побудова графової моделі живучості нечіткої мережі аеропортів. // Т.І. Олешко, О.Л. Лещинський, О.М. Горбачова // Проблемиекономіки: Харківський Національний Економічний Університет МОН України, ВидавничійДім «ІНЖЕК», - 2015. - №1. - С. 366 - 371.

9. Фрэнк Г. Сети. Связь и потоки / Г. Фрэнк, И. Вриш - М.: Связь, 1978. - 488 с.

10. Monderson J.N. Fussy graphs and fussy hypergraphs / J.N. Monderson, P.S. Nair. - Heidelberg; New York: Physica-Verl., 2000. - 248 p.