Методы теории графов в разработке управленческих решений | Пример курсовой работы

Методы теории графов в разработке управленческих решений

Цель курсовой работы – изучить методы теории графов в разработке управленческих решений.

Язык теории графов позволяет упростить формулировки сложных практических задач, приёмы их решения. Также он оказался удобным для изложения разных разделов математики и иных наук, к которым относятся, к примеру, такие, как экономико-математическое моделирование, теория игр, теория алгоритмов и математическая логика, теория формальных грамматик и автоматов, инженерия знаний, теория инженерных сетей, управление и системный анализ в больших системах и др.
Модели в виде графов широкое распространение получили благодаря дополнительным возможностям, которые возникают при геометрическом подходе к трактовке и описанию сути изучаемых явлений или процессов. Графы, являясь строгой и формальной математической моделью, отличаются исключительной наглядностью и информативностью.
Так как графы широко применяются как в качестве моделей для представления знаний и данных в разных областях науки и многочиеленных приложениях, но и как средство и инструмент для решения многих прикладных и математических задач, представляется актуальным рассмотрение моделей принятия решений, которые основаны на использовнаии методов теории графов.
В теории графов есть специфические методы решения экстремальных задач. Для графов с конечным множеством рёбер и вершин, обычно, проблема существования алгоритма решения задач, в т.ч. экстремальных, решается положительно. Решение многих задач, которые связаны с конечными графами, выполнено может быть при помощи полного перебора допустимых вариантов. Но этим способом решить задачу удаётся только для графов с небольшим числом рёбер и вершин. Поэтому большое значение для теории графов имеет построение эффективных алгоритмов, которые находят приближенное или точное решение. Для некоторых задач эти алгоритмы построены, к примеру, для определения изоморфизма деревьев, установления планарности графов, построения на графе связывающего кратчайшего дерева, нахождения кратчайших путей между вершинами графа, нахождения максимального потока на транспортной сети и т.д. [9]
Особенно важно в теоретическом и практическом плане имеют эффективные алгоритмы решения базовых задач теории графов. Методы решения базовых задач применяются при решении проблем из ерыс планирования, обработки и представления знаний, автоматизации процедур выработки и ПР в социально-экономических и организационно-технологических сиетемах.
К базовым относят задачи размещения вершин графа (объёмное, плоскостное, линейное), вершинного покрытия графа (разбиение на классы сходства или толерантности), трассировки соединений между вершинами, декомпозиции (разрезания) графа на подграфы, диагонализации матрицы смежности или агрегирования графа (обобщение, кластеризация), определения эквивалентности (изоморфизма) графов, поиска изоморфного вложения графов, поиска раскраски вершин графа минимальным количеством красок, поиска на графе максимально полного (максимально пустого) подграфа и др.
Большая часть базовых задач связано с построением упорядоченности вершин графа (или столбцов и строк соответствующей матрицы смежности графа), которая отвечает критерию. Одна из базовых – задача линейной упорядоченности вершин графа, которая имеет много интерпретаций в зависимости от предметной области. При этом критерии упорядоченности могут быть как количественные, которые отражают метрические характеристики, так и качественные, которые отражают субъективные предпочтения экспертов, которые могут также измеряться в количественных шкалах. Так, в сиетемах автоматизированного проектирования (САПР) одна из важных – задача линейного упорядочения элементов по критерию минимума суммарной длины связей или минимума более длинной связи. Эта задача имеет место при проектировании технологических линий, инженерных коммуникаций, при организации вычислительного процесса в многопроцессорных структурах, в системах поддержки принятия решений [17]
Другая важная задачей, также связанная с упорядочением вершин графа, – агрегирование графа, или диагонализация его матрицы смежности.
Диагонализация матрицы межотраслевого баланса позволяет определить агрегаты экономически более тесно связанных отраслей. В итоге появляется возможность получить небольшое количество макропоказателей, которые описывают текущее состояние экономики и основные особенности развития страны. В САПР данная задача агрегирования известна как задача компоновки, в системном анализе – как декомпозиция, в теории принятия решений и распознавании образов – как кластеризация, или классификация. Также она возникает при организации вычислительного процесса в многоагентных или многопроцессорных системах, которые организованы по принципу близкодействия, при графовой аппроксимации эмпирических данных, при распределении оборудования по участкам и цехам и т.д.
Ещё одна весьма важная и интересная задача, которая связанас упорядочением вершин графа, – построение упорядоченности, которая обусловит каноническую форму матрицы смежности. Сравнение канонических форм матриц смежности 2-х графов позволяет говорить о том, изоморфны графы или нет. Если графы изоморфны, то построенные упорядоченности их вершин, которые привели к одинаковому каноническому виду матриц смежности, определят подстановку изоморфизма на множествах вершин данных графов. Если же графы не изоморфны, то сравнение их канонических матриц позволит говорить о степени их сходства. Упорядочение вершин графа в соответствии с целевой функцией – основа решения и других важных задач, в частности, задачи коммивояжёра, выбора оптимального распределения ресурсов, оптимального варианта ремонта оборудования и т.д. [21]
Понятие «управленческое решение» используется в основных двух значениях: как явление и как процесс. УР как процесс – анализ, груп- пировка и поиск информации, реализация, утверждение и разработка УР. Как явление – письменное или устное распоряжение, постановление, план мероприятий и т. п.
Методы и результаты теории графов используются при решении транспортных задач, для нахождения оптимальных решений задач о назначениях, для выделения «узких мест» при управлении и планировании разработкой проектов, при составлении оптимальных маршрутов доставки грузов, при моделировании технологических сложных процессов, при построении систем автоматизированного проектирования, в программировании и т.д.
Модели в виде графов широкое распространение получили благодаря дополнительным возможностям, которые возникают при геометрическом подходе к трактовке и описанию сути изучаемых явлений или процессов.
ФГУП «Росморпорт» согласно Уставу ФГУП «Росморпорт» может осуществлять 56 разрешенных видов деятельности. Основные направления: предоставление инфраструктурных комплексных услуг, которые связаны с обеспечением безопасности мореплавания в акватории морских портов и на подходах к ним; оказание сервисных услуг судам в морских портах, в т.ч. связанных с судоходством и безопасной стоянкой; развитие и поддержание в техническом надлежащем состоянии федеральных объектов прибрежно-портовой инфраструктуры в морских портах, в т.ч. реализация целевых федеральных программ в области морского транспорта; выполнение других работ.
ФГУП «Росморпорт» для обеспечения бесперебойной обработки судов на протяжении года планировала строительство морского порта в городе Маячном на Азовском море. Сложность того положения, в котором ФГУП «Росморпорт» оказалась обусловлена была слабой технической проработанностью проекта. Руководство не смогло профессионально провести анализ внешней среды и правильно оценить такие факторы как политическая неустойчивость, инфляция и нежелание иностранных и российских инвесторов вкладывать средства при таких условиях в дорогостоящие проекты.
Главной и основной проблемой, которая встала перед компанией, было то, что ФГУП «Росморпорт» не смогла адекватно оценить экономико-политическую ситуацию в стране.
Проблема решена при помощи методики эвристического прогнозирования. Для обработки данных матриц использован метод графов.
Цель курсовой работы – изучить методы теории графов в разработке управленческих решений.

Что думаете про курсовую?

Поставьте оценку!