Русский   English
ДонНТУ   Портал магістрів

Реферат за темою випускної роботи

Зміст

Вступ

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

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

1. Актуальність теми

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

2. Ціль і задачі дослідження

Метою дослідження є розробка системи підтримки прийняття рішень про модернізацію медичного закладу.

Для досягнення поставленої мети поставлені такі завдання:

  1. Розробка математичної моделі плану модернізації медичного закладу.
  2. Пошук і виявлення переваг і недоліків існуючих методів оптимізації.
  3. Вибір оптимального методу для вирішення задачі.

Об’єктом дослідження є: процес модернізації медичного закладу.

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

3. Наукова новизна

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

4. Огляд існуючих методів рішень

Для вирішення поставленої задачі підходять такі алгоритми:

  • Мурашиний алгоритм

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

  • Алгоритм імітації відпалу

    • Алгоритм імітації відпалу відноситься до класу порогових алгоритмів локального пошуку. Метою алгоритму є мінімізація деякого функціоналу. У процесі роботи алгоритму зберігається поточне рішення, яке є проміжним результатом. А після роботи алгоритму воно і буде відповіддю [2].

  • Двійкові дерева пошуку

    • Двійковим деревом пошуку називають дерево, всі вершини якого впорядковані, кожна вершина має не більше двох нащадків, і всі вершини, крім кореня, мають батьків. Вершини, що не мають нащадків, називаються листами [2].

  • Динамічне програмування

    • Динамічне програмування – спосіб вирішення складних задач шляхом розбиття їх на простіші підзадачі. Він застосовується до задач з оптимальною підструктурою. Задача має оптимальну підструктуру, якщо її оптимальне рішення може бути раціонально складено з оптимальних рішень її підзадач [12].

  • Алгоритм А * і його модифікації

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

    Основні переваги і недоліки методів наведені нижче.

    Методи Переваги Недоліки
    Мурашиний алгоритм працюють краще, ніж інші глобальні оптимізації (нейронні мережі, генетичні алгоритми)
    менше схильні до неоптимальних початкових рішень
    для невеликої кількості вузлів TSP може бути вирішена повним перебором
    		необхідне застосування додаткових методів таких, як локальний пошук
    збіжність гарантується, але час збіжності не визначено
    сильно залежать від настроювальних параметрів, які підбираються тільки виходячи з експериментів
    Алгоритм імітації відпалу відсутність обмежень на вид функції
    ефективність при вирішенні задач різних класів, які вимагають оптимізації
    пошук глобального мінімуму     		складність настройки алгоритму
    повільна робота алгоритму
    Двійкові дерева пошуку легкість додавання елемента
    легкість видалення елемента
    швидкий пошук
    Після декількох операцій додавання / видалення елементів такі дерева можуть почати вироджуватися, що істотно сповільнить роботу з бінарним деревом
    Динамічне програмування задача обчислення управління для всього процесу розбивається на ряд більш простих задач обчислення    управління для окремих етапів процесу прокляття розмірності – його складність катастрофічно зростає із збільшенням розмірності задачі
    Алгоритм А * і його модифікації aлгоритм працює з оптимістичною оцінкою шляху через вершину велику проблему представляють собою споживані алгоритмом ресурси пам’яті

    5. Математична постановка задачі

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

    Введемо поняття зваженого графа рішень. Зважений граф рішень (G) – граф, кожному ребру якого поставлено у відповідність вага ребра. Такий граф можна представити у вигляді:

    pic1 (1)

    де

    V – множина вершин (дій),

    E – множина дуг (ребер),

    W – множина ваг.

    Дуги можуть бути представлені як:

    pic2 (2)

    Дуга з’єднує дві вершини графа. В якості вершин графа виступають дії vi vj, які будуть виконуватися над об’єктами модернізації: обладнанням, приміщенням, персоналом.

    Для визначення найкоротшого шляху з однієї вершини в іншу необхідно мати можливість вимірювати відстань між вузлами (діями), тому введемо функцію відстані, визначену на дугах графа d: E→R, де R – множина дійсних чисел.

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

    pic3 (3)

    де wij – вага дуги.

    Крім того введемо функції-обмеження для кожного вузла. Обмеження – функція, яка задана на вершині графа.

    pic4 (4)

    Обмеження:

    Необхідно враховувати такі ризики:

    Критерій необхідності модернізації

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

    Рішення поставленої задачі проводиться в два етапи:

    Мінімум функціонала F досягається послідовності вершин, сума ваг яких дає мінімально можливу вагу.

    pic7 (7)
    pic8

    Рисунок 1 – Граф рішень

    Діями на графі є:

    1. Модернізація
    2. Вибір обладнання
    3. Покупка нового
    4. Наладка
    5. Монтаж
    6. Інші витрати
    7. Ремонт старого
    8. Не робити нічого
    9. Вибір приміщення
    10. Будівництво нового
    11. Ремонт старого
    12. Не робити нічого
    13. Вибір персоналу
    14. Навчання
    15. Найняти нового
    16. Не навчати

    6. Мурашиний алгоритм

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

    Розглянемо випадок, показаний на рисунку 2.

    pic9

    Рисунок 2 – Шляхи проходження мурах від дома до їжі

    Коли на оптимальному шлясі (Рисунок 2 А) виникає перешкода (Рисунок 2.В) мурахам необхідно визначити новий оптимальний шлях. Дійшовши до перепони, мурахи з однаковою ймовірністю будуть обходити її справа і зліва. Те ж саме буде відбуватися і на зворотньому боці перешкоди. Однак, ті мурахи, які випадково виберуть найкоротший шлях, будуть швидше його проходити, і за кілька пересувань він буде більш збагачений феромоном. Оскільки рух мурашок визначається концентрацією феромону, то наступні будуть віддавати перевагу саме цьому шляху (Рисунок 2.D), продовжуючи збагачувати його феромоном до тих пір, поки цей шлях з якої-небудь причини не стане недоступний. Позитивний зворотній зв'язок швидко призведе до того, що шлях найкоротший стане єдиним маршрутом руху більшості мурашок. Моделювання випаровування феромону – негативного зворотного зв’язку – гарантує нам, що знайдене локально оптимальне рішення не буде єдиним – мурашки будуть шукати й інші шляхи. Якщо ми моделюємо процес такої поведінки на деякому графі, ребра якого являють собою можливі шляхи переміщення мурашок, протягом певного часу, то найбільш збагачений феромоном шлях по ребрах цього графа і буде представляти рішення завдання, отримане за допомогою мурашиного алгоритму [11].

    Базовий мурашиний алгоритм, незалежно від модифікацій, можна представити у вигляді схеми (Рисунок 3).

    Рисунок 3 - Загальний мурашиний алгоритм

    Рисунок 3 – Загальний мурашиний алгоритм

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

    Пошук рішень

    Імовірність переходу з вершини i у вершину j визначається згідно формули 8:

    pic10 (8)

    де Ni k представляє безліч можливих вершин, пов'язаних з вершиною i для мурахи k,

    τ ij – рівень феромону,

    d ij – евристична відстань,

    α и β – константні параметри.

    Оновлення феромона відбувається відповідно до формули 9:

    pic11 (9)

    где n(k) – кількість мурах,

    ρ – інтенсивність випаровування,

    L k(t) – довжина шляху, побудованого k-ою мурахою в момент часу t,

    Q – параметр значущості,

    Q/L k(t) – феромон, що відкладався k-ою мурахою, що використовують ребро (i, j)

    Висновки

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

    На момент написання даного реферату було виконано наступне:

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

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

    Важливe зауваження

    При написанні даного реферату магістерська робота ще не завершена. Остаточне завершення: грудень 2014 року. Повний текст роботи і матеріали по темі можуть бути отримані у автора або його керівника після зазначеної дати.

    Список джерел

    1. Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение СПб. БХВ-Петербург, 2003. – 1104 c.
    2. Russel S., Norvig P. / Рассел С., Норвиг П. – Artificial Intelligence. A Modern Approach, Second Edition / Искусственный интеллект. Современный подход (2-е издание),2006. – 1408 с.
    3. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ, 3-е издание – М.: Вильямс, 2013. – 1328 с.
    4. Терелянский П.В. Системы поддержки принятия решений. Опыт проектирования: монография / П. В. Терелянский; ВолгГТУ. – Волгоград, 2009. – 127 c.
    5. Скобцов Ю.А. Основы эволюционных вычислений. – Донецк: ДонНТУ, 2008. – 326 с.
    6. Штовба С.Д. Муравьиные алгоритмы, Exponenta Pro. Математика в приложениях. 2004. № 4, C. 70 – 75.
    7. Поиск в пространстве состояний [Электронный ресурс]. – Режим доступа: http://habrahabr.ru/company/abbyy/blog/217839.
    8. Википедия. Алгоритм поиска А* [Электронный ресурс]. – Режим доступа: http://ru.wikipedia.org/wiki/Алгоритм_поиска_A*.
    9. D. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning. Reading, MA: Addison-Wesley, 1989. – 412 c.
    10. Харчистов Б.Ф. Методы оптимизации: Учебное пособие. / Б.Ф. Харчистов – г. Таганрог: Изд-во ТРТУ, 2004. – 140 с.
    11. Информационные управляющие системы и компьютерный мониторинг 2010/ Сборник материалов к I Всеукраинской научно-технической конференции студентов, аспирантов и молодых ученых. – Донецк, ДонНТУ – 2010, C. 12 – 16.
    12. Электронный учебник Экономико-математические методы. Динамическое программирование [Электронный ресурс]. – Режим доступа: http://math.mrsu.ru/text/courses/method/dinamicheskoe_programmirovanie1.htm.
    13. Муравьиные алгоритмы [Электронный ресурс]. – Режим доступа: http://habrahabr.ru/post/105302/.
    14. Скиена С. Алгоритмы. Руководство по разработке 2-е изд.: Пер. с англ. – СПб.: БХВ-Петербург. 2011. – 720 с.
    15. Системы поддержки принятия решений [Электронный ресурс]. – Режим доступа: https://tpl-it.wikispaces.com/системы+поддержки+принятия+решений.
    16. Введение в оптимизацию. Имитация отжига [Электронный ресурс]. – Режим доступа: http://habrahabr.ru/post/209610/.
    17. Поиск пути [Электронный ресурс]. – Режим доступа: http://ru.wikipedia.org/wiki/Поиск_пути.
    18. Классификация методов поддержки принятия решений [Электронный ресурс]. – Режим доступа: http://www.ipiran.ru/niap/pages/st_19.pdf.
    19. Алгоритмы муравьиной колонии [Электронный ресурс]. – Режим доступа: http://ru.science.wikia.com/wiki/Алгоритмы_муравьиной_колонии.
    20. Динамическое программирование [Электронный ресурс]. – Режим доступа: http://ru.wikipedia.org/wiki/Динамическое_программирование.