Вторая половина XX века ознаменовалась не только стремительным развитием теории графов, но и началом ее широкого применения в задачах планирования и оптимизации. Развитию теории графов способствовал технический прогресс и расцвет информатики и вычислительной техники, но никогда прежде не проводилось столь обширного исследования методов и алгоритмов поиска решений, оптимальных по времени или денежным затратам. Масштабная программа NASA по запуску ракеты «Аполлон-2», сбор мусора и уборка улиц в крупных городах, производственные цепочки, системы распределения продукции — для всех этих задач требовались методы, позволявшие найти оптимальное решение. Исследование операций достигло своего расцвета, а теория графов вызвала интерес, который не угасает и поныне. В этой главе мы приглашаем читателя оценить возможности этой теории для решения практических задач оптимизации.
Эйлеровы циклы
В связном графе эйлеровым циклом называется путь, содержащий все ребра графа, начальная и конечная вершины которого совпадают. При этом вершины могут повторяться, а ребра — нет.
На первом из следующих рисунков вы можете видеть эйлеров цикл. Во втором графе эйлерова цикла не существует.
Эйлер с точностью определил, когда в связном графе существует эйлеров цикл. Для этого он использовал понятие степени вершины, равное числу ребер, исходящих из данной вершины. Критерий существования эйлерова цикла выражен теоремой, которая звучит так:
«Связный граф содержит эйлеров цикл тогда и только тогда, когда все его вершины имеют четную степень».
Следует подчеркнуть, что если граф содержит эйлеровы циклы, то каждое ребро при обходе графа имеет «пару». Поэтому логично, что из каждой вершины будет выходить четное число ребер, то есть все вершины будут иметь четную степень. Эта теорема позволяет мгновенно определить, содержит ли граф эйлеров цикл, путем простого подсчета степеней вершин. Эффективный поиск эйлеровых циклов — совершенно другой вопрос.
* * *
ЭЙЛЕРОВЫ ЦИКЛЫ В ЗАНИМАТЕЛЬНЫХ ЗАДАЧАХ
Классическая математическая игра с карандашом и бумагой заключается в том, чтобы обойти все вершины графа и вернуться в исходную, пройдя по всем ребрам ровно один раз, не отрывая карандаша от бумаги. Попробуйте найти такой путь в графе, который показан на рисунке.
* * *
Задача китайского почтальона
Представьте себе добросовестного почтальона, которому нужно обойти все улицы, где проживают адресаты писем. Оптимальным для него будет такой маршрут, при котором ему придется пройти по каждой улице ровно один раз. Если мы изобразим улицы на графе, то эта задача будет равносильна поиску эйлерова цикла в этом графе. Но если этот граф не содержит эйлеров цикл, почтальону придется пройти по некоторым улицам несколько раз, но так, чтобы число повторов было минимальным. Этой задачей занимался китайский математик Мэй-Ку Куан в 1962 году, поэтому она получила название задачи о китайском почтальоне.
Если мы внимательно посмотрим на рисунки выше, то увидим, что две вершины имеют степень, равную 3. Следовательно, данный граф не содержит эйлеров цикл. Однако на втором рисунке видно, что если мы добавим всего одно ребро (выделено пунктиром), то граф будет содержать эйлеров цикл (последовательность обхода ребер обозначена цифрами). При этом нужно будет пройти два раза всего по одной улице (5 и 6). Именно так выглядит алгоритм решения задачи китайского почтальона: если граф не содержит эйлеров цикл, нужно добавить к нему минимально возможное число ребер, которые будут дублировать уже имеющиеся, чтобы получить эйлеров цикл.
На следующих рисунках приведен один из возможных вариантов решения и оптимальный путь почтальона.
Эта задача широко применяется при доставке разнообразных грузов. Поиск оптимальных маршрутов в крупных городах представляет особый интерес, так как позволяет снизить финансовые и трудовые затраты при уборке улиц, доставке различных товаров и в других процессах. К счастью, в настоящее время при поиске таких маршрутов нам помогают компьютеры.
Гамильтоновы циклы
Рассмотрим следующую задачу. Можно ли найти такой путь в связном графе, который бы проходил через все вершины графа только один раз, причем начальная и конечная вершины при этом совпадали? Такие пути называют гамильтоновыми циклами.
На рисунке выше изображен гамильтонов цикл DABCED. Не следует путать гамильтоновы и эйлеровы циклы: в эйлеровых циклах нужно пройти ровно один раз по всем ребрам графа (вспомним задачу о кёнигсбергских мостах), а в гамильтоновых циклах нужно пройти ровно один раз по всем вершинам. Некоторые графы не содержат гамильтоновых циклов, другие содержат сразу несколько. Например, граф, изображенный на предыдущем рисунке, содержит два гамильтоновых цикла: DABCED и DCEBAD. Разумеется, обойти каждый гамильтонов цикл можно двумя способами: в прямом и в обратном направлении.
Несмотря на сложность поиска гамильтоновых циклов в больших графах, эта задача представляет огромный интерес при организации путешествий, доставке товаров, распределении продуктов в сетях супермаркетов и так далее.
* * *
ИЗОБРЕТЕНИЕ ЦЕНОЙ В ДВЕ ГИНЕИ
Подобные циклы на графах открыл Томас Киркман (1806–1895) . Исследованием этих циклов занимался ирландский математик Уильям Роуан Гамильтон (1805–1865) , он же сделал их широко известными. В 1859 году Гамильтон придумал такую игру: 20 вершин додекаэдра (правильного 12-гранника) соответствуют 20 городам. Нужно обойти все города по одному разу и при этом вернуться в тот же город, с которого началось путешествие. Восторженный Гамильтон продал идею производителю игрушек за смехотворную сумму в две гинеи. Блестящие идеи не всегда ценятся по достоинству!
Математик Уильям Роуан Гамильтон и придуманная им игра.
* * *
МЕТОД ПОСТРОЕНИЯ ДЕРЕВА
На рисунках ниже показано, как можно сопоставить исходному графу ABCD дерево всех возможных маршрутов для поиска гамильтоновых циклов, которые начинаются и заканчиваются в вершине А , а вершины В , С и D обходятся ровно один раз. С увеличением числа вершин поиск гамильтоновых циклов усложняется: в каждом случае исходным является полный граф с n вершинами (им соответствует n городов). Из каждого города можно попасть в n — 1 город, из каждого из них — в n — 2 города и так далее, пока мы не вернемся в начальную точку. Следовательно, число маршрутов будет равно ( n — 1)·( n — 2)·( n — 3)·… ·3·2·1. Вспомним, что факториалом числа называется произведение всех натуральных чисел от 1 до этого числа включительно (например, 6! = 6·5·4·3·2·1), следовательно, общее число циклов будет равно ( n — 1)!. Так как каждый цикл можно пройти в прямом и обратном направлении, то общее число различных циклов будет в два раза меньше: ( n -1)1/2. Впрочем, и это число будет очень велико: для n — 6 оно составит (6–1)!/2 = 60 циклов.
* * *
Задача коммивояжера
В предыдущем разделе мы говорили о гамильтоновых циклах — путях, которые содержат каждую вершину графа ровно один раз, причем начальная и конечная вершина этих путей совпадают. В большинстве практических задач ребрам графа соответствуют некоторые значения; это может быть стоимость перевозки, расстояние и другие параметры. Следовательно, встает вопрос о поиске цикла, для которого стоимость, время или расстояние будут наименьшими.
Почтальон хочет обойти всех адресатов так, чтобы пройти за день как можно меньше. Точно так же действуете и вы, когда планируете отпуск: вы ищете самый короткий маршрут или же более длинный, но при этом самый дешевый, и так далее. В главе 5 мы покажем, что этот вопрос является ключевым в линейном программировании.
* * *
АЛГОРИТМ БЛИЖАЙШЕГО СОСЕДА
Допустим, что А , B , С и D — города, числа на ребрах графа — расстояние между городами в километрах. Вы находитесь в городе А и можно выбрать одну из трех дорог длиной в 300 км, 500 км и 600 км. Вы выбираете ближайший город D . Из города D ведут две дороги длиной 350 и 400 км. Вы снова выбираете ближайший город, на этот раз B . Из города В вы едете в С , затем возвращаетесь в А . Этот алгоритм относится к так называемым «жадным» алгоритмам, так как мы выбираем оптимальное решение на каждом шаге: наименьшие затраты, минимальное время или расстояние (так называемый «жадный» выбор). Этот алгоритм не гарантирует, что конечное решение всегда будет оптимальным. Альтернативой является алгоритм сортировки ребер графа, который также не гарантирует оптимальность решения. В этом алгоритме на каждом шаге выбирается ребро с наименьшим весом, если они не препятствуют построению гамильтонова цикла.
* * *
Решить задачу путешественника на больших графах очень сложно. По этой причине она является классическим примером так называемых NP-полных задач, то есть задач, для которых невозможно найти «быстрый» алгоритм поиска оптимальных решений. В информатике под быстротой алгоритма понимается скорость выполнения компьютерных программ, реализующих этот алгоритм.
* * *
АЛГОРИТМ КРУСКАЛА
Джозеф Бернард Крускал (1928–2010) , выпускник Принстонского университета и специалист по комбинаторике из компании Bell Laboratories, в 1950-е годы разработал замечательный алгоритм. Этот алгоритм позволяет получить минимальное остовное дерево (то есть соответствующее наименьшим общим затратам) путем последовательного добавления к нему ребер графа, упорядоченных по возрастанию веса.
* * *
Критические пути
Во множестве реальных ситуаций используются не обыкновенные графы, а орграфы, то есть ориентированные графы. В этих графах к ребрам добавляются стрелки, указывающие направление. Орграф, изображенный на первом рисунке снизу, может соответствовать, например, маршруту по улицам с односторонним движением. На втором рисунке снизу тот же орграф может представлять последовательность задач (А, В, С, 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/(3 m )] Т . Однако никогда не стоит недооценивать частные эвристические решения.
* * *
Система PERT, которую мы сейчас обсудим, основана на следующих принципах.
1. Формируется упорядоченное структурное разделение задач проекта. Разделение задач может выполняться с помощью органиграммы, на которой отображаются основные действия. Также можно сформировать группы действий, которые должна выполнить каждая группа, участвующая в реализации проекта.
2. Определяются задачи. Описание основных задач и необходимых технологий позволяет разграничить участки проекта. На этом этапе определяются все действия и их последовательность.
3. Каждой задаче присваиваются ресурсы, фиксируются сроки выполнения задач. Здесь необходимо составить «календарь» реализации проекта, в котором будет указано общее время и время выполнения отдельных действий с учетом всех возможных факторов: ресурсов, технологий, рабочих групп и так далее.
Одна из оригинальных особенностей PERT — введение различных понятий времени:
а) Т о — оптимистичное время выполнения, достигающееся при безукоризненном выполнении всех задач без сбоев;
б) Тр — пессимистичное время, в котором учитываются все возможные действия и события, препятствующие выполнению проекта;
в) Т т — среднее, или вероятное время, или время, рассчитанное с помощью статистических методов на основе прошлого опыта;
г) Те — реальное время, которое используется в PERT для каждого действия и рассчитывается по формуле (обосновывается статистически):
Иными словами, реальное время вычисляется как средневзвешенное оптимистичного, пессимистичного и среднего времени. Также рассчитывается стандартная ошибка (Т p + Т o )/6, квадрат которой будет оценкой отклонения.
4. Анализируются и определяются зависимости. На этом этапе определяются все возможные зависимости между действиями проекта: ограниченность ресурсов, физического пространства, рабочих групп; ограничения, вызванные особенностями месторасположения, и другие.
5. Формируется сеть, или граф, который является основной моделью системы.
При построении этого графа нужно руководствоваться следующими правилами:
а) события (начало или завершение действия) являются вершинами графа. Они изображаются кругами и прямоугольниками, внутри которых записывается название события и его порядковый номер;
б) действиям соответствуют ребра, или дуги графа, которые соединяют соответствующие события. Над каждым ребром указывается число, обозначающее реальное время выполнения этого действия (Т е ).
Также существуют дополнительные правила, которые способствуют эффективному построению графа и облегчают его прочтение:
а) каждое действие имеет одно предыдущее и одно последующее событие.
Можно вводить фиктивные действия нулевой длительности, что равносильно записи одного и того же события несколько раз под разными номерами, если это действие имеет несколько последующих;
б) событие считается произошедшим только тогда, когда выполнены все предшествующие ему действия;
* * *
ПРИМЕР ИСПОЛЬЗОВАНИЯ СИСТЕМЫ PERT В СТРОИТЕЛЬСТВЕ
Далее приведен пример анализа строительства дома (точнее, начальных действий) по системе PERT. Нужно составить список начальных задач, присвоить каждой задаче букву или номер, а также определить зависимости и примерное время выполнения ( Т e ) каждой задачи.
Теперь можно построить соответствующий граф, расположив рядом с каждой его вершиной квадрат и треугольник. В квадратах будем указывать день от начала работ, когда может начаться событие, в треугольниках — день его завершения.
Продолжение графа (вплоть до завершения работ) приведено на следующем рисунке.
* * *
в) следует избегать ситуаций, когда предшествующее и последующее событие для двух действий совпадают. Этого можно избежать путем ввода фиктивных событий нулевой длительности;
г) необходимо создать промежуточные события и фиктивные действия, чтобы устранить вершины 4-й степени и выше;
д) никакое событие не может быть одновременно начальным и конечным в последовательности событий.
6. Наконец, анализируется построенный граф. Например, интерес представляют следующие параметры:
а) дата, наиболее удаленная от завершения проекта, то есть дата начала первого события в последовательности событий;
б) допустимый крайний срок. Завершение события позднее этого срока негативно повлияет на проект в целом;
в) продолжительность события — разница между двумя предыдущими параметрами;
г) избыток времени, доступный при реализации данного действия;
д) критический путь — путь на графе с наибольшим временем выполнения (между двумя данными событиями или для всего графа).
Так называемая система PERT/COST имеет ту же структуру, но в ней учитываются не сроки выполнения задач, а их стоимость. Система PERT также допускает комбинирование сроков и финансовых затрат. В настоящее время для всех систем планирования разработаны простые в использовании информационные системы.