Карты метро и нейронные сети. Теория графов

* * *

Критические пути

Во множестве реальных ситуаций используются не обыкновенные графы, а орграфы, то есть ориентированные графы. В этих графах к ребрам добавляются стрелки, указывающие направление. Орграф, изображенный на первом рисунке снизу, может соответствовать, например, маршруту по улицам с односторонним движением. На втором рисунке снизу тот же орграф может представлять последовательность задач (А, В, С, D, Е) и порядок, в котором нужно выполнить эти задачи.

В виде орграфов можно представить энергосети, транспортные потоки, телефонные сети, схемы промышленного производства, порядок действий при ремонте и многое другое. Как можно увидеть из второго рисунка, узлы А, В, С, D, Е обозначены не точками, а кругами или прямоугольниками, внутри которых указаны задачи (разгрузка, покраска, установка и прочее), а также соответствующие им веса (1000 евро, 12 минут и так далее). На ребрах ориентированного графа, которые называются дугами, также указаны веса — это оценки затрат финансов, времени и других ресурсов, которые требуются для выполнения соответствующего действия.

Именно в таких сложных случаях требуется найти критические пути, оптимальные с точки зрения затрат или сроков. На предыдущем рисунке сумма а, Ь, е равна 34 дням, сумма а, с, d — 45 дням. Критическим путем является ABDE. Если критический путь не пройден до конца, хотя другие операции выполнены, проект не может считаться полностью завершенным.

* * *

ОПТИМИЗАЦИЯ ВРЕМЕНИ ПРЕБЫВАНИЯ САМОЛЕТОВ В АЭРОПОРТУ

Авиакомпании стремятся сократить время между приземлением и следующим взлетом самолета. После остановки самолета выполняются следующие действия:

А. Высадка пассажиров.

В. Выгрузка багажа.

С. Уборка салона.

D. Загрузка еды и напитков.

Е. Осмотр самолета.

F. Заправка горючим.

G. Загрузка нового багажа.

Н. Посадка новых пассажиров.

Некоторые из этих действий могут выполняться параллельно (например, А и В, С и D, Е и F), другие — последовательно. К примеру, С нельзя начать, пока не закончится A, G можно выполнить только после В и так далее. Завершающим действием является Н. К этому моменту действие F уже выполнено, действие G еще не закончено. Если на выполнение всех этих действий отводится 20 минут, соответствующий орграф должен быть очень точным. Критический путь этого графа непосредственно повлияет на расписание перелетов, а также на задержки рейсов и время ожидания самолета.

* * *

Графы и планирование: система PERT

С начала Второй мировой войны начал формироваться широкий спектр методов оптимизации планирования. После того как СССР запустил в космос первый спутник, в США началась работа над различными крупными проектами, начиная от баллистической ракеты «Поларис», размещаемой на подводных лодках, и заканчивая высадкой человека на Луну. Для столь больших проектов требовались соответствующие методы планирования. В этих методах используются так называемые сетевые диаграммы.

К важнейшим подобным методам относятся следующие.

1. PERT (Program Evaluation and Review Technique — техника оценки и анализа программ). Была разработана по заказу ВМС США в 1958 году. Этот метод доказал свою эффективность при планировании длительных, сложных и затратных проектов.

2. СРМ (метод критического пути). Этот метод особенно подходит для планирования последовательности задач и изучения критических путей, то есть последовательности координируемых действий, невыполнение которых может вызвать задержки проекта. Похожими методами являются СРА (анализ критического пути), РЕР (процедура оценки программы), LESS (оценка наименьших затрат и планирование) и SCANS (планирование и контроль посредством автоматизированной сети).

3. RAMPS (выделение ресурсов и многопроектное планирование). Этот метод включает метод PERT и применяется при распределении ограниченных ресурсов между несколькими независимыми проектами.

Схема анализа по системе PERT

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

* * *

СОСТАВЛЕНИЕ РАСПИСАНИЯ С ИСПОЛЬЗОВАНИЕМ КРИТИЧЕСКИХ ПУТЕЙ

В отраслях, где в производственной цепочке задействуется различное оборудование и персонал, интерес представляют алгоритмы производства, методы составления расписания и анализ критических путей. Наиболее важным для этого является изучение зависимостей между задачами или их отсутствия. Рональд Грэхем разработал алгоритм обработки списка задач с помощью m обработчиков. При оптимальном времени выполнения задач Т алгоритм гарантирует, что будет найдена последовательность, время выполнения которой не будет превышать (2 — (1/m))Т. Обработчиком может быть человек, устройство или система, время работы которых запрограммировано. В алгоритме, в котором задачи выполняются в порядке убывания сроков выполнения, общее время не будет превосходить [4/3 — 1/(3m)]Т. Однако никогда не стоит недооценивать частные эвристические решения.

* * *

Система PERT, которую мы сейчас обсудим, основана на следующих принципах.

1. Формируется упорядоченное структурное разделение задач проекта. Разделение задач может выполняться с помощью органиграммы, на которой отображаются основные действия. Также можно сформировать группы действий, которые должна выполнить каждая группа, участвующая в реализации проекта.

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

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

Одна из оригинальных особенностей PERT — введение различных понятий времени:

а) Т_о — оптимистичное время выполнения, достигающееся при безукоризненном выполнении всех задач без сбоев;

б) Т_р  — пессимистичное время, в котором учитываются все возможные действия и события, препятствующие выполнению проекта;

в) Т_т — среднее, или вероятное время, или время, рассчитанное с помощью статистических методов на основе прошлого опыта;

г) Т_е  — реальное время, которое используется в PERT для каждого действия и рассчитывается по формуле (обосновывается статистически):

Иными словами, реальное время вычисляется как средневзвешенное оптимистичного, пессимистичного и среднего времени. Также рассчитывается стандартная ошибка (Т_p + Т_o)/6, квадрат которой будет оценкой отклонения.

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

5. Формируется сеть, или граф, который является основной моделью системы.

При построении этого графа нужно руководствоваться следующими правилами:

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

б) действиям соответствуют ребра, или дуги графа, которые соединяют соответствующие события. Над каждым ребром указывается число, обозначающее реальное время выполнения этого действия (Т_е).