Во множестве реальных ситуаций используются не
обыкновенные графы, а орграфы, то есть ориентированные графы. В этих
графах к ребрам добавляются стрелки, указывающие направление. Орграф,
изображенный на первом рисунке снизу, может соответствовать, например,
маршруту по улицам с односторонним движением. На втором рисунке снизу
тот же орграф может представлять последовательность задач (А, В, С, D, Е) и порядок, в котором нужно выполнить эти задачи.
В виде орграфов можно представить энергосети,
транспортные потоки, телефонные сети, схемы промышленного производства,
порядок действий при ремонте и многое другое. Как можно увидеть из
второго рисунка, узлы А, В, С, D, Е обозначены не точками, а
кругами или прямоугольниками, внутри которых указаны задачи (разгрузка,
покраска, установка и прочее), а также соответствующие им веса (1000
евро, 12 минут и так далее). На ребрах ориентированного графа, которые
называются дугами, также указаны веса — это оценки затрат финансов,
времени и других ресурсов, которые требуются для выполнения
соответствующего действия.
Именно в таких сложных случаях требуется найти
критические пути, оптимальные с точки зрения затрат или сроков. На
предыдущем рисунке сумма а, Ь, е равна 34 дням, сумма а, с, d — 45 дням. Критическим путем является ABDE. Если критический путь не пройден до конца, хотя другие операции выполнены, проект не может считаться полностью завершенным.
* * *
ОПТИМИЗАЦИЯ ВРЕМЕНИ ПРЕБЫВАНИЯ САМОЛЕТОВ В АЭРОПОРТУ
Авиакомпании стремятся сократить время между
приземлением и следующим взлетом самолета. После остановки самолета
выполняются следующие действия:
А. Высадка пассажиров.
В. Выгрузка багажа.
С. Уборка салона.
D. Загрузка еды и напитков.
Е. Осмотр самолета.
F. Заправка горючим.
G. Загрузка нового багажа.
Н. Посадка новых пассажиров.
Некоторые из этих действий могут выполняться параллельно (например, А и В, С и D, Е и F), другие — последовательно. К примеру, С нельзя начать, пока не закончится A, G можно выполнить только после В и так далее. Завершающим действием является Н. К этому моменту действие F уже выполнено, действие G
еще не закончено. Если на выполнение всех этих действий отводится 20
минут, соответствующий орграф должен быть очень точным. Критический путь
этого графа непосредственно повлияет на расписание перелетов, а также
на задержки рейсов и время ожидания самолета.
| 
