Клауди Альсина - Том 11. Карты метро и нейронные сети. Теория графов
* * *
Графы и планирование: система 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. Формируется сеть, или граф, который является основной моделью системы.
При построении этого графа нужно руководствоваться следующими правилами:
а) события (начало или завершение действия) являются вершинами графа. Они изображаются кругами и прямоугольниками, внутри которых записывается название события и его порядковый номер;
б) действиям соответствуют ребра, или дуги графа, которые соединяют соответствующие события. Над каждым ребром указывается число, обозначающее реальное время выполнения этого действия (Те).
Также существуют дополнительные правила, которые способствуют эффективному построению графа и облегчают его прочтение:
а) каждое действие имеет одно предыдущее и одно последующее событие.
Можно вводить фиктивные действия нулевой длительности, что равносильно записи одного и того же события несколько раз под разными номерами, если это действие имеет несколько последующих;
б) событие считается произошедшим только тогда, когда выполнены все предшествующие ему действия;
* * *
ПРИМЕР ИСПОЛЬЗОВАНИЯ СИСТЕМЫ PERT В СТРОИТЕЛЬСТВЕ
Далее приведен пример анализа строительства дома (точнее, начальных действий) по системе PERT. Нужно составить список начальных задач, присвоить каждой задаче букву или номер, а также определить зависимости и примерное время выполнения (Тe) каждой задачи.
Теперь можно построить соответствующий граф, расположив рядом с каждой его вершиной квадрат и треугольник. В квадратах будем указывать день от начала работ, когда может начаться событие, в треугольниках — день его завершения.
Продолжение графа (вплоть до завершения работ) приведено на следующем рисунке.
* * *
в) следует избегать ситуаций, когда предшествующее и последующее событие для двух действий совпадают. Этого можно избежать путем ввода фиктивных событий нулевой длительности;
г) необходимо создать промежуточные события и фиктивные действия, чтобы устранить вершины 4-й степени и выше;
д) никакое событие не может быть одновременно начальным и конечным в последовательности событий.
6. Наконец, анализируется построенный граф. Например, интерес представляют следующие параметры:
а) дата, наиболее удаленная от завершения проекта, то есть дата начала первого события в последовательности событий;
б) допустимый крайний срок. Завершение события позднее этого срока негативно повлияет на проект в целом;
в) продолжительность события — разница между двумя предыдущими параметрами;
г) избыток времени, доступный при реализации данного действия;
д) критический путь — путь на графе с наибольшим временем выполнения (между двумя данными событиями или для всего графа).
Так называемая система PERT/COST имеет ту же структуру, но в ней учитываются не сроки выполнения задач, а их стоимость. Система PERT также допускает комбинирование сроков и финансовых затрат. В настоящее время для всех систем планирования разработаны простые в использовании информационные системы.
Глава 4
Графы и геометрия
Вдохновение нужно в геометрии не меньше, чем в поэзии.
Александр Пушкин
Многие свойства фигур, которые изучаются в геометрии, зависят от их параметров: величин углов, расстояний, перпендикулярности прямых, площади фигур, объема тел и так далее. Однако теория графов и топология помогли выявить геометрические закономерности, которые не зависят ни от параметров геометрических фигур, ни от их формы. В этой короткой главе мы расскажем об известной формуле Эйлера и обнаружим множество ее удивительных следствий, которые проявляются в многогранниках и мозаиках.
В формуле Декарта 1640 года и формуле Эйлера 1752 года фигурируют только грани, ребра и вершины, поэтому эти формулы применимы к множеству различных фигур и по-прежнему выполняются даже после определенных преобразований.
