Головна

Розробка алгоритму побудови дерева досяжності.

  1. I.5.2) Розробка Зводу Юстиніана.
  2. IV. Організація методологічної роботи та проблеми побудови системного підходу
  3. Алгоритм побудови ієрархічного розбиття (дендограмм) завдань управління СОТС
  4. Алгоритм побудови інформаційно-логічної моделі предметної області
  5. Алгоритм побудови сгруппированного (або табулированного) ряду
  6. Архітектура мереж. Загальні принципи побудови обчислювальних мереж, їх ієрархія, архітектура
  7. Блок-схема алгоритму

Основними методами аналізу досяжності є: метод побудови дерева досяжності і матричний метод дослідження досяжності.

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

У процесі зазначеного руху по дереву можуть досягатися такі граничні вершини, яким відповідає маркування, тупикова по відношенню до всіх переходах (при цій маркуванні не існує дозволених переходів). Дані вершини називаються термінальними вершинами. Очевидно, термінальні вершини є кінцевими (висячими) вершинами дерева.

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

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

Загальний алгоритм побудови дерева досяжності (для обмежених і необмежених мереж Петрі).

Крок 0. Внести в список нерозглянутих (граничних) вершин вершину з початкової маркуванням  , Перейти до кроку 1.

Крок 1. Вилучити зі списку нерозглянутих вершин деяку вершину  з маркуванням  і виконати наступні операції:

а) якщо для  не один перехід  не вирішено, оголосити  термінальної вершиною;

б) якщо серед розглянутих вершин дерева знаходиться така вершина  , для котрої  , оголосити  дублюючої вершиною;

в) якщо пункти "а" або "б" виконані, перейти до кроку 3, інакше оголосити  внутрішньої вершиною і перейти до кроку 2.

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

а якщо  , то ;

б) якщо для внутрішньої вершини  має місце  , То для тих позицій  , Для яких ця нерівність суворе, приймається ;

в) у всіх інших випадках приймається .

Кожну таку вершину  з маркуванням  вносимо до списку нерозглянутих вершин і переходимо до кроку 1.

Крок 3. Якщо список нерозглянутих вершин не порожній, перейти до кроку 1; якщо він порожній, зупинити алгоритм. В останньому випадку кожна вершина виявляється внутрішньої, термінальної або дублюючої.

Алгоритм многокритериального аналізу і вибору найбільш бажаних варіантів реструкторізаціі.

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

Існують різні інструменти розв'язання багатокритеріальних задач, серед яких можна, в першу чергу виділити, наступні методи:

· Метод аналізу ієрархій;

· Принцип Еджворта-Парето (принцип Парето);

· Метод послідовних поступок;

· Метод головного критерію;

Принцип Еджворта-Парето (принцип Парето). Набір складових ІС можна представити у вигляді деякого безлічі X = {x1, x2, ..., Xm}, Де m - потужність множини. Кожен елемент безлічі характеризується вектором показників якості xi = {Xi1, xi2, ..., XiN}, Де N - розмірність вектора. Таким чином, весь набір складових моделі і алгоритму планування можна представити у вигляді безлічі, розташованого в просторі характеристик RN. По кожному зі складових вектора Xi визначені критеріальні функції оптимізації. Тут передбачається мінімізувати всі показники, що може бути несправедливим в деяких ситуаціях, однак не важко показати, що показник, чий критерій не збігається із загальним, може бути перетворений до зручного виду, там же показано, як різнорідні показники можуть бути перетворені до єдиного масштабу і розмірності.

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

 (3)

Причому хоча б для одного xi нерівність має бути суворим.

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

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

 (4)

ми отримаємо координати точки x * = {x1 *, x2 *, ..., xN *} в просторі RN, співвідношення характеристик якої можна прийняти за оптимальне. Так як оптимальне рішення має належати подмножеству не гірших варіантів, то їм буде така альтернатива (точка), одночасно належить цьому подмножеству і має співвідношення показників, аналогічне центру координат. Геометрично її місце можна визначити на перетині підмножини не гірших точок і вектора центру координат, тому що всі точки, що лежать на цьому векторі, мають однакове співвідношення характеристик. Тут слід зауважити, що в реальному дискретній множині оптимальна точка, як правило, буде абстрактною, тобто їй не буде відповідати жодна з точок вихідного безлічі, тому оптимальне рішення слід шукати як найближчу до неї точку. Для цього зручно представити безліч Par (X) у вигляді векторів, що виходять з точки початку координат і закінчуються в відповідних їм точках множини.

Рис 6. Вибір оптимальної точки.

Визначивши вектор, який має найменший кут розбіжності з вектором центру координат, ми знайдемо шукане рішення.

Якщо включити в розгляд всі параметри характеризують даний компонент ІС, то безліч, розташоване в просторі своїх характеристик RN, має цілком входити в безліч не гірших варіантів (безліч Парето).

Якщо безумовно гірші точки все-таки існують, то це свідчить або про "вмирання" моделі і алгоритму планування розвитку або про те, що в розгляд були включені деякі характеристики. При постановці завдання визначені в якості оптимізуються всі характеристики елементів безлічі, однак такий підхід не зовсім коректним, тому що зазвичай при виборі визначальним є лише обмежене число параметрів, а решта використовуються для завдання обмежень або не розглядаються взагалі. Розглядаючи безліч в просторі оптимізуються характеристик RL (L

Очевидно що Y, що містить елементи з X, що не увійшли в безліч не гірших варіантів при розгляді L-характеристик призначені для інших цілей, ніж ті, які переслідувалися, при визначенні оптимізуються параметрів. Виходячи з цього, розумно припустити, що елементи множини, що не увійшли в безліч Парето при обмеженому числі параметрів, не повинні впливати на вибір, отже, визначення центру координат безлічі необхідно проводити тільки по точках безлічі Парето[1,11,15].

Метод послідовних поступок. В його основі ідея зниження розмірності вихідної задачі шляхом призначення головного критерію в спеціально формованих двовимірних підзадача умовної оптимізації. Для цього в ході вербального аналізу результатів операції всі приватні критерії wi i = 1, 2, ..., m ранжируют і нумерують в порядку убування важливості. Потім максимізують перший, найважливіший критерій w1 і знаходять його найбільше значення  . Далі, виходячи з практичних міркувань, ЛПР призначається деяка поступка D1 від досягнутого значення  . Величина поступки - це своєрідна плата за можливість підвищити значення чергового по важливості критерію w2 від його досягнутого до даного кроку рівня w2(А) для альтернативи а, що забезпечує величину  . В результаті другий критерій може досягти величини  , Що залежить, природно, від величини D1 поступки за першим критерієм. Потім призначають поступку D2 за критерієм w2 (Від значення  ), Ціною якої прагнуть збільшити значення критерію w3, і т.д. Таким чином, величини поступок послідовно призначаються в результаті аналізу тільки попарной взаємозв'язку критеріїв. Вибираючи поступки, ОПР має розглядати тільки залежність  , Не звертаючи увагу на інші критерії. При цьому найчастіше спочатку навіть незначна поступка Di від значення  призводить до істотного збільшення значення критерію  , А потім з ростом величини поступки маргінальні збільшення в значеннях критерію  різко зменшуються. Зіставляючи отриманий в цьому випадку виграш за критерієм  з втратами в значеннях критерію  , ЛПР остаточно призначає величину поступки Di і визначає значення  . Отже, саме ранжування критеріїв за важливістю дозволяє ЛПР обмежуватися призначенням величини поступки для попереднього критерію тільки з урахуванням поведінки наступного.

Метод головного критерію. Тут агрегування зводиться до призначення одного з критеріїв, наприклад wj, Головним і додатково вимагають, щоб значення всіх інших, «неголовних» критеріїв wi,  задовольняли додатковим обмеженням. Зазвичай зазначена подобласть задається обмеженнями-нерівностями виду  , Тому завдання оптимізації приминає вид:

У даній роботі докладніше зупинимося на методі аналізу ієрархій.

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

Список застосувань методу досить різноманітний: дослідження транспортної системи Судану, пивоварна промисловість Мексики, проведення аналізу «вартість-ефективність», розподіл ресурсів. В Ізраїлі професор Амі Арбель знайшов метод корисним при прийнятті рішень як по формалізованих, так і формалізації фактори, для яких були відсутні зв'язують їх аналітичні залежності. Метод постійно використовується при плануванні промисловості Піттсбурга, банківської справи, сталеливарної промисловості, у сфері міського господарства і координації громадських послуг. Крім того, необхідно відзначити, що і в Росії цей метод набуває дедалі більшого поширення: різні види маркетингових досліджень, визначення сценаріїв розвитку міста, оцінки різних комерційних ризиків і т.д. У багатьох ВУЗах Росії, що мають економічні спеціальності, вводяться відповідні дисципліни.

Роль подібного мови в МАІ виконують різні ієрархічні структури. Відповідно, в МАІ будь-яке завдання або проблема попередньо структуруються і представляються у вигляді ієрархії деревовидної або мережного.

Таким чином, в МАІ основна мета дослідження і всі фактори, в тій чи іншій мірі впливають на досягнення мети, розподіляються за рівнями залежно від ступеня і характеру впливу.

На першому рівні ієрархії завжди знаходиться одна вершіна- мета проведеного дослідження.

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

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

Проводиться порівняння досліджуваних факторів попарно по відношенню до їх впливу ( «вазі», або «інтенсивності») на загальну для них характеристику.

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

   A1  A2  ...  An
 A1 a12   a1n
 A2 a21   a2n
 ...      ...  
 An an1 an2  

Якщо позначити частку фактора Ai через wi, То елемент матриці aij = wi/ wj.

При цьому очевидно aij = 1 / aji. Отже, матриця парних порівнянь в даному випадку є позитивно певної, обратносімметрічной матрицею.

Робота експертів полягає в тому, що, виробляючи попарне порівняння факторів A1, ..., An експерт заповнює таблицю парних порівнянь. Важливо зрозуміти, що якщо w1, w2, ..., Wn невідомі заздалегідь, то попарні порівняння елементів виробляються з використанням суб'єктивних суджень, чисельно оцінюються за шкалою, а потім вирішується проблема знаходження компонента w.

У такій постановці завдання вирішення проблеми полягає в знаходженні вектора (w1, w2, ..., Wn). Існує кілька різних способів обчислення шуканого вектора. Кожен з методів дозволяє крім безпосереднього знаходження вектора відповідати ще на деякі додаткові питання. Детальніше про це буде написано нижче.

Підкреслимо, що експерт порівнюючи n факторів реально проводить не n (як це відбувається при заповненні звичайних анкет) порівнянь, а n * (n-1) / 2 порівнянь. Але це ще не все. Насправді (враховуючи співвідношення aij= aІк * Aкj справедливе для всіх значень індексу k) проводиться опосередковане порівняння факторів Ai і Aj через відповідні порівняння цих факторів з фактором Ak. Беручи до уваги зроблене зауваження можна стверджувати, що в дійсності експерт виробляє значно більше порівнянь, ніж навіть показує перша оцінка рівна n * (n-1) / 2. Таким чином, кожна клітина матриці парних порівнянь реально містить не одне число (результат безпосереднього порівняння), а цілий вектор (з урахуванням всіх опосередкованих порівнянь через порівняння з іншими факторами). Облік цих додаткових порівнянь дозволяє значно підвищити надійність одержуваних результатів, або дозволяє значно зменшити кількість необхідних експертів.

Один з основних методів відшукання вектора w ґрунтується на одному з тверджень лінійної алгебри.

Очевидно, що шуканий вектор є власним вектором матриці парних порівнянь, відповідним максимальному власному числу (?max). У цьому випадку по одному з великого max, а потім досить вирішити кількості існуючих алгоритмів відшукується векторне рівняння A * w = ?max * W.

Тут необхідно зазначити наступне. З лінійної алгебри відомо, що у позитивно певної, обратносімметрічной матриці, що має ранг рівний 1, максимальне власне число дорівнює розмірності цієї матриці (тобто n). При проведенні порівнянь в реальній ситуації обчислене максимальне власне число ?max буде відрізнятися від відповідного власного числа для ідеальної матриці. Ця різниця характеризує так звану неузгодженість реальної матриці. І, відповідно, характеризує рівень довіри до отриманих результатів. Чим більше ця відмінність, тим менше довіра. Таким чином, ця модифікація методу парних порівнянь містить внутрішні інструменти дозволяють визначити якість оброблюваних даних і ступінь довіри до них. Ця особливість даної методики вигідно відрізняє його від більшості зазвичай застосовуються при дослідженні ринку методів.

Інший підхід у визначенні вектора w складається в наступному. Підсумовуються по рядках елементи матриці парних порівнянь (для кожного значення i обчислюється сума a i= ai1+ ai2+ ... + Ain). Потім все ai нормуються так, щоб їх сума дорівнювала 1. В результаті отримуємо шуканий вектор w. Таким чином, wi = ai/ (A1+ a2+ ... + An).

Цей спосіб знаходження вектора w, значно простіше в реалізації, але він не дозволяє визначати якість вихідних даних.

Метод парних порівнянь дозволяє визначити якість вихідних даних. Причому Т. Сааті рекомендує при погано узгодженої матриці або змінити експертів, або знайти додаткові дані, або вирішувати проблему іншим шляхом. У тому випадку, коли проблема не в експертів, а в власне об'єкті вивчення. Неузгодженість матриці парних порівнянь може бути викликана, по крайней мере двома факторами:

· Особистими якостями експерта;

· Ступенем невизначеності об'єкта оцінки.

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

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

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

Побудувати алгоритм обробки матриці порівнянь, що представляє результати в необхідній формі, дозволяє зазначене вище властивість матриці порівнянь: кожен елемент матриці є, по суті, цілим вектором, складеним з різних порівнянь (прямих і опосередкованих) відповідних факторів. З огляду на це властивість можна для кожного елемента матриці зіставити його середнє значення та його стандартне квадратичне відхилення (СКО). Далі користуючись методами стохастичного моделювання можна побудувати послідовності матриць порівняння, кожна з яких буде відповідати одній з можливих реалізацій відносин характерних для даного об'єкта в рамках його неоднозначності і компетентності оцінюють його експертів. Визначаючи для кожної такої матриці вектор w, отримаємо досить великий набір векторів, що представляють можливі реалізації структури об'єкта відповідно до його неоднозначністю і компетентністю оцінюють його експертів. Сприймаючи, побудований таким чином, набір векторів, як статистичну вибірку, можна отримати необхідний результат в тому вигляді, який необхідний в конкретному випадку. Зокрема легко можна отримати середні значення компонент вектора w і значення їх СКО[6].

Отримані таким чином значення СКО і є наслідком ступеня неузгодженості матриці парних порівнянь. Чим більше неузгодженість, тим більше значення СКО.

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

Дійсно, при порівнянні фактора Ai з фактором Aj експерт поставить оцінку aij, А при порівнянні фактора Aj з фактором Ai експерт поставить оцінку aji. При цьому на взаємне співвідношення цих оцінок не впливає стан ІС, а тільки професіоналізм експерта (в ідеальному випадку, як уже зазначалося, має виконуватися рівність aji = 1 / aij). Таким чином, відхилення aji від 1 / aij є випадковою величиною і її СКО відповідає рівню професіоналізму експерта. Отже, з огляду на властивості дисперсії, можна з оцінок елементів матриці порівнянь прибрати вплив непрофесіоналізму експерта і в результаті зменшити СКО компонентів вектора w. В результаті вектор w, точніше середні значення його компонент і їх СКО, буде відповідати даному об'єкту (зокрема ринку) і адекватно описувати його.

Для проведення суб'єктивних парних порівнянь Т. Сааті була розроблена шкала відносної важливості (таблиця 5).

Таблиця 5.

 Інтенсивність відносної важливості  визначення  пояснення
 непорівнянні  Експерт не може у порівнянні
 рівна важливість  Рівний внесок двох видів діяльності в ціль
 Помірне перевагу одного над іншим  Досвід і судження дають легке перевагу одному виду діяльності над іншим
 Значне або сильне перевага  Досвід і судження дають сильне перевагу одному виду діяльності над іншим
 значну перевагу  Одному з видів діяльності дається настільки сильне перевагу, що воно стає практично значним
 Дуже сильне перевага  Очевидність переваги одного виду діяльності над іншим підтверджується найбільш сильно
 2,4,6,8  Проміжні рішення між двома сусідніми судженнями  Застосовуються в компромісному випадку
 Зворотні величини наведених вище чисел  Якщо при порівнянні одного виду діяльності з іншим отримано одне з вищевказаних чисел (наприклад, 3), то при порівнянні другого виду діяльності з першим отримаємо зворотну величину (тобто 1/3)  

Вибір шкали визначався наступними вимогами:

(А) Шкала повинна давати можливість вловлювати різницю в почуттях людей, коли вони проводять порівняння, розрізняти якомога більше відтінків почуттів, які мають люди.

(Б) Експерт повинен бути впевненим у всіх градаціях своїх суджень одночасно.

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

Глава 4. Управлінський аналіз функціонування ВАТ «Ютейр» в 2004-2008 роках і розробка нової стратегії розвитку авіакомпанії.




Місія сучасної авіакомпанії в РФ. | Аналіз зовнішнього середовища. | Управлінський аналіз функціонування авіапідприємства. | Аналіз кон'юнктури і прогнозування ринку повітряних перевезень в РФ на сучасному етапі розвитку. | Цілі і завдання авіапідприємства. | Генеральна стратегія авіапідприємства | Система функціональних стратегій. | Змістовна і формальна постановка задачі комплексного моделювання процесів реструктуризації сучасного авіапідприємства. | Аналіз можливостей мережі Петрі для моделювання процесів розвитку сучасного авіапідприємства. | Модель процесу реструкторізаціі сучасного авіапідприємства. |

© um.co.ua - учбові матеріали та реферати