Синтез графовых методов и методов теории принятия решений для решения задач многокритериальной оптимизации на графах

М.А. Беляева

Графовое моделирование имеет многочисленные приложения в самых разнообразных областях человеческой деятельности потому, что оно позволяет наглядно представлять и эффективно описывать физические, технические, экономические, биологических, социальные и другие системы.

Однако, несмотря на то, что теория графов в последние годы интенсивно развивается и разработано множество оптимизационных алгоритмов на графах, алгоритмы, как правило, предполагают наличие одного критерия. Например, для решения оптимизационных задач на графах - оптимального размещения, коммивояжера, нахождения кратчайших путей и кратчайших остовов, других оптимизационных задач на графах задается один критерий - минимума длины пути или минимума времени. Но решение реальных задач требует учета множества факторов и показателей, адекватного соответствия многим критериям. Так, при нахождении оптимальных путей бывает важно учитывать не только расстояние, но и качество, пропускную способность дорог, то есть дополнительно к критерию минимума расстояния требуется также введение критериев максимума качества дорог и пропускных способностей дорог.

Возникает задача многокритериальной оптимизации на графах, которую автор статьи предлагает решать на основе синтеза графовых методов и методов теории принятия решений. В теории графов создано множество методов и алгоритмов решения задач однокритериальной оптимизации, а в теории принятия решений разработаны разнообразные математические методы многокритериальной оптимизации - это методы аддитивной и мультипликативной сверток, методы уступок, пересечения нечетких множеств, метод анализа иерархий и другие методы[1].

Для решения задач многокритериальной оптимизации на графах автором предлагается следующий общий подход. Строится обобщенный граф, каждой дуге, ребру которого необходимо приписать вектор весов, размерность которого равна числу заданных критериев оптимизации. Значения компонентов вектора - оценки по критериям, которым ЛПР назначает приоритеты. Затем значения оценок нормализуются и сворачиваются в соответствии с методом аддитивной свертки - получаются обобщенные веса дуг, ребер графа. К графу с обобщенными весами применяется соответствующий однокритериальный оптимизационный алгоритм и таким образом осуществляется решение многокритериальной оптимизационной задачи на графах на основе многих критериев.

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

В настоящее время часто возникает задача многокритериальной оптимизации путей подключения клиентов к оптоволоконным компьютерным сетям. Критериями предпочтительности выбора тех или иных участков маршрута подключения являются следующие основные критерии: минимум количества муфт, минимум количества метров кабеля на пути следования; максимум количества свободных волокон; минимум количества занятых волокон и минимум коэффициента сложности пути.

Оптоволоконная сеть может быть представлена в виде графа, у которого вершины – это соединительные устройства (муфты), которые необходимы для соединения участков кабеля между собой. При этом одна из вершин может быть выбрана в качестве головной станции, т.е. точка, откуда сигнал передается. Ребра графа – отрезки кабеля, по которому информация в цифровом виде поступает до клиента.

Для решения данной многокритериальной задачи была осуществлена интеграция метода нахождения кратчайших путей Дейсктры и метода аддитивной свертки критериев[2].

Макроалгоритм нахождения оптимального пути по многим критериям

Шаг 1. Ввод списка дуг (ребер) графа.

Шаг 2. Ввод количества, наименований и направленности (max, min) критериев.

Шаг 3. Ввод оценок дуг (ребер) по каждому критерию.

Шаг 4. Задание весов частных критериев, при этом их сумма должна быть равна 1.

Шаг 5. Нормализация оценок по критериям.

Шаг 5.1 Нахождение максимума среди оценок по каждому критерию.

Шаг 5.2 Вычисление отношения значения оценок по критериям к максимальному значению, найденному на Шаге 5.1

Шаг 5.3 Если критерий стремится к max, то вычитаем из 1 значение, найденной на этапе 5.2 иначе переход на шаг 6. Переход к Шагу 6.

Шаг 6. Аддитивная свертка частных критериев - вычисление суммы произведений нормализованных значений оценок дуг (ребер) по критериям на веса частных критериев, т.е. нахождение обобщенных весов дуг (ребер) графа.

Шаг 7. Формирование обобщенной матрицы смежности графа. Для этого найденные на шаге 6 обобщенные веса дуг (ребер) графа переносятся в матрицу смежности графа.

Шаг 8. Нахождение значений весов оптимальных путей по обобщенной матрице смежности графа на основе алгоритма Дейкстры.

Шаг 9. Восстановление оптимальных путей, используя веса, найденные на Шаге 8.

Найденные оптимальные пути и будут искомыми обобщенными оптимальными путями подключения клиентов к оптоволоконной сети в соответствии с многими критериями.

Рассмотрим предлагаемый подход также на примере решения задачи нахождения обобщенных критических путей в сетевой модели проекта «Дуга-работа». Обычно ищутся критические пути в сетевой модели - это максимальные по продолжительности пути в ациклическом ориентированном взвешенном графе, веса дуг которого – продолжительности соответствующих дугам работ. Знание критических путей позволяют менеджерам проектов уделять больше внимания работам, от которых в большой степени зависит продолжительность всего проекта. Обобщенными критическими путями назовем пути в сетевой модели, соответствующие не только одному критерию максимума продолжительности пути, но и множеству других критериев.

Если рассмотреть обобщенную сетевую модель проекта [3], в которой определяются пути в соответствии со следующим комплексом критериев: максимума продолжительности, максимума риска, минимума качества работ, максимума затрат, например, то возникает многокритериальная задача нахождения обобщенных критических путей сетевого графа. Найденные обобщенные пути позволяют менеджерам проекта отслеживать работы, от которых зависит не только длительность всего проекта, но и риски, качество, затраты проекта.

Данная задача может быть решена с помощью интеграции метода Флойда[4] нахождения кратчайших путей графа и метода аддитивной свертки критериев теории принятия решений с помощью следующего укрупненного алгоритма.

Шаг 1. Задать множество частных критериев оценок работ проекта.

Шаг 2. Задать приоритеты критериев.

Шаг 3. Построить обобщенную сетевую модель проекта, приписав дугам сетевого графа вектор весов - оценок по заданным частным критериям.

Шаг 4. Произвести нормализацию весовых значений дуг по частным критериям, т.е. привести все оценки к безразмерным величинам из интервала [0,1] в соответствии с принципом максимума эффективности.

Шаг 5. Получить обобщенные веса дуг сетевой модели, свернув нормализованные значения весов дуг графа с помощью метода аддитивной свертки.

Шаг 6. Модифицировать сетевой граф, умножив обобщенные веса дуг сетевого графа на (-1).

Шаг 7. Найти оптимальные пути модифицированного сетевого графа, применив алгоритм Флойда нахождения кратчайших путей в графе.

Шаг 8. Вернуться к исходному графу, вновь умножить все обобщенные веса дуг и вес найденных оптимальных путей на (-1).

Найденные оптимальные пути модифицированного графа в соответствии с заданным множеством частных критериев и будут обобщенными критическими путями исходной сетевой модели.

Предлагаемый подход можно применить и для решения других многокритериальных задач оптимизации на графах.

Рассмотрим реализацию на ЭВМ решения задачи определения оптимальных путей проезда на карте автомобильных дорог от одного заданного пункта до другого при наличии двух критериев - минимума расстояния и максимума пропускных способностей дорог, которая была решена на основе синтеза метода аддитивной свертки критериев и метода Флойда нахождения кратчайших путей в соответствии с небольшой модификацией рассмотренного выше алгоритма. На рисунке 1 представлена экранная форма задания оценок ребер по заданным критериям.

Модификация алгоритма заключается в исключении шагов 6 и 8, что позволит найти оптимальные, в соответствии с заданными критериями, пути графа. Кроме того, на шаге 1 вводятся критерии, по которым оцениваются автомобильные дороги- их длина и пропускные способности дорог.

Рисунок 1-Экранная форма задания весов ребер

После работы алгоритма нахождения кратчайших путей по обобщенным весам ребер получим экранную форму, представленную на рисунке 2. На ней отображен оптимальный путь из Оренбурга (Х1) до Москвы (Х6).

Рисунок 2 – Оптимальный путь из Оренбурга до Москвы

На рисунке 3 представлено схематическое представление оптимального пути от Оренбурга до Москвы.

Рисунок 3 – Схематическое представление оптимального пути (в км)

Таким образом, синтез графовых методов однокритериальной оптимизации и многокритериальных методов теории принятия решений позволяет эффективно решать задачи многокритериальной оптимизации на графах.

Список литературы

1. Андрейчиков, А.В. Анализ, синтез и планирование ре­шений в экономике/ А.В. Андрейчиков, О.Н. Андрейчикова.– М.: Финансы и статистика, 2000.–363с.

2. Арсеньев, Ю.Н. Принятие решений. Интеллектуальные интегрированные системы: Учебное пособие для вузов/ Ю.Н. Арсеньев, С.И. Шелобаев, Т. Ю. Давыдова.-М.: ЮНИТИ_ДАНА, 2006,-447 с.

3. Бережная, Е.В. Математические методы моделирования экономических систем: Учебное пособие/ Е.В. Бережная, В.И. Бережной. - М.: Финансы и статистика, 2001.-368 с.

4. Мазур, И.И. Управление проектами / И.И Мазур., В.Д. Шапиро., Н.Г. Ольдерогге.- М.: Омега-Л, 2004.-664 с.

5. Харари, Ф. Теория графов. Пер. с англ./ Ф. Харари - Едиториал УРСС, 2006.- 501 с.