Українська   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. На основании анализа литературных источников выделены основные алгоритмы, которые могут быть использованы в решении поставленной задачи, были выделены их достоинства и недостатки.

    Исходя из сравнения различных методов, для решения данной задачи предполагается использовать муравьиный алгоритм.

    Важное замечание

    При написании данного реферата магистерская работа еще не завершена. Окончательное завершение: декабрь 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/Динамическое_программирование.