Графы. Алгоритм Форда — Фалкерсона. Метод CPM

Лекция 10: Графы.Алгоритм Форда — Фалкерсона Алгоритм Форда — Фалкерсона решает задачу нахождения максимального потока в транспортной сети. Определение критического пути Будем предполагать, что время выполнения каждой работы точно известно. Введем следующие определения. Путь— последовательность взаимосвязанных работ, ведущая из одной вершины проекта в другую вершину. Например (см. Рисунок 48), {A, D, G} и {C, F} – два различных пути. Рисунок 48. Различные пути на сетевом графике Длина пути— суммарная продолжительность выполнения всех работ пути. Полный путь— это путь от исходного к завершающему событию. Критический путь— полный путь, суммарная продолжительность выполнения всех работ которого является наибольшей. очередность работ выглядит следующим образом: Рисунок 2. Очередность работ и критический путь. Очевидно, что минимальное время, необходимое для выполнения любого проекта равно длине критического пути. Именно на работы, принадлежащие критическому пути, следует обращать особое внимание. Если такая работа будет отложена на некоторое время, то время окончания проекта будет отложено на то же время. Если необходимо сократить время выполнения проекта, то в первую очередь нужно сократить время выполнения хотя бы одной работы на критическом пути. Для того, чтобы найти критический путь, достаточно перебрать все пути и выбрать тот, или те из них, которые имеют наибольшую суммарную продолжительность выполнения работ. Однако для больших проектов реализация такого подхода связана с вычислительными трудностями. Метод критического пути (метод CPM — Critical Path Method) позволяет получить критический путь намного проще. Расчет сетевой модели начинают с временных параметров событий, которые вписывают непосредственно в вершины сетевого графика : –ранний срок наступления события i, минимально необходимый для выполнения всех работ, которые предшествуют событию i; –поздний срок наступления события i, превышение которого вызовет аналогичную задержку наступления завершающего события сети; –резерв события i, т.е. время, на которое может быть отсрочено наступление события i без нарушения сроков завершения. Метод CPM — Critical Path Method Задачи сетевого планирования Общими правилами построения сетевых графиков являются: - направление стрелок в сетевом графике принимается слева направо. Код начального события должен быть меньше кода конечного события; - форма графика должна быть простой, без лишних пересечений. ... - каждая работа должна иметь отдельный код. Временные параметры сетевого графика. Для определения продолжительности критического пути и сроков выполнения каждой работы определяют следующие временные параметры сетевой модели: Ранее начало работы - Tpн– это самый ранний из возможных сроков начала работы при условии выполнения всех предшествующих работ. Ранее окончание работы -Tpo – время окончания работы, если она начата в самый ранний из возможных сроков и равно раннему началу работы плюс продолжительность работы. Позднее начало работы-Tпн – самый поздний из допустимых сроков начала работы, при котором не увеличивается общая продолжительность работ (критический путь). Позднее окончание работы-Tno– самый поздний из допустимых сроков окончания работы, при котором не увеличивается общая продолжительность работ сетевого графика. Поздние сроки всегда больше или равны ранним срокам. Для критических работ ранние и поздние сроки начала и окончания работ равны. Общий (полный) резерв времени -R– время, на которое можно увеличить продолжительность работы или позднее ее начать, не меняя при этом продолжительности критического пути. Частный (свободный) резерв времени–r – это время, на которое можно увеличить продолжительность работы или позднее ее начать, не меняя при этом ранее начало последующей работы. Частный резерв времени равен или меньше общего резерва времени. Для работ, которые лежат на критическом пути, частный и общий резервы времени равны нулю. Если ранние и поздние характеристики совпадают, то работы лежат на критическом пути. Продолжительность работ (дни) – t. Продолжительность критического пути (дни, месяцы) – Ткр. Путь– непрерывная последовательность работ в сетевом графике. Его длину определяют суммой продолжительности составляющих его работ. В сетевом графике между исходными и завершающими событиями имеется несколько путей. Полным путем– называют путь от исходного до завершающего события сетевого графика. Предшествующий путь– это участок полного пути от исходного события графика до данного. Последующий путь– это участок полного пути от данного события до любого последующего. Путь описывается последовательностью работ или событий. Критическим путем– называют полный путь, имеющий наибольшую длину (продолжительность) из всех полных путей. Его длина определяет срок выполнения работ по сетевому графику. В графике может быть несколько критических путей. Работы, которые лежат на критическом пути, называюткритическими.Увеличение продолжительности критических работ соответственно увеличивает общую продолжительность работ по сетевому графику, а сокращение приводит к некоторому уменьшению. Пути, продолжительность которых несколько меньше продолжительности критического пути на заданную величину, называют подкритическими,а совокупность всех критических и подкритических работ называют критической зоной. Критический путь обычно выделяется утолщенной , двойной или линией красного цвета. Расчет ранних сроков. В графе 4и5записывают расчет ранних параметров работы – раннее начало и раннее окончание. Расчет ведут от исходного события до завершающего. Ранние сроки начала и окончания работ рассчитываются по таблице сверху вниз Самое раннее начало работы определяется продолжительностью максимального пути от исходного события графика до начального события данной работы. Tрн (i-j)= max th-i Для простых событий, в которые входит только одна работа, раннее начало этой работы равно раннему окончанию предшествующей работы. Tрнi-j ­= Tроh-i Раннее начало работ, выходящих из первого события, равно нулю. Раннее окончание работы равно сумме ее раннего начала плюс продолжительность данной работы. Tроi-j = Tрнi-j + ti-j При рассмотрении сложного события, т.е. когда ему предшествует две работы и более, раннее начало последующей работы будет равно наибольшему значению их ранних окончаний предшествующих работ. Tрнi-j = max Tроh-i Расчет поздних сроков. В графе 6и7записывают расчеты поздних параметров работ – позднее начало и позднее окончание. Расчет ведут в обратном порядке, т.е. от завершающих работ до исходной снизу вверх. Для простого события, из которого выходит только одна работа, позднее окончание предшествующей работы равно позднему началу рассматриваемой работы. Tпоh-i = Tпнi-j Позднее началоданной работы равно разности между ее поздним окончанием и продолжительностью. Для сложного события, из которого выходит несколько работ, позднее окончание предшествующих работ равно меньшему из поздних начал рассматриваемых работ. Tпоh-i = min Tп-нi-j Позднее начало исходной работы должно быть равно нулю. После установления ранних сроков начала и окончания всех работ переходят к расчету позднего начала работ. Позднее начало работ определяется как самый поздний срок начала работы, при котором не будет задержки в выполнении всех работ на объекте. Позднее начало равно разности между продолжительностью критического пути и продолжительностью максимального пути от предшествующего события данной работы до конечного события. После нахождения позднего начала работ переходят к расчету позднего окончанияданной работы TПО, которое определяется как сумма позднего начала работы и продолжительности выполнения рассматриваемой работы. Расчет резервов времени. В графе 8 записываемобщий (полный) резерв времени, который равен разности позднего окончания и раннего окончания работ или позднего начала и раннего начала работ. Ri-j = Tпнi-j - Tрнi-j = Tпоi-j - Tроi-j В графе 9записываютчастный (свободный) резерв времени, который определяют как разность между ранним началом последующей работы и ранним окончанием данной работы. ri-j = Tр-нj-k - Tр-оi-j Критический путь при табличном методе расчета лежит на работах, общий и частный резервы времени которых равны нулю. На графике критический путь должен представлять собой непрерывную последовательность работ от начального события до конечного. Анализируя таблицу, мы получаем сведения о длине критического пути, ранних и поздних началах и окончаниях каждой из работ, общих и частных резервах времени. Если у работ нет последующих работ, т.е. они входят в завершающее событие, их частный резерв равен общему. Работы, у, которых общий и частный резервы времени равны нулю, входят в состав критического пути, определяющего общий срок строительства. Работы, не лежащие на критическом пути, могут выполняться менее интенсивно или можно изменить срок начала их выполнения без нарушения срока окончания работ. Таким образом, для всех работ, не входящих в критический путь, могут быть два срока начала работ и два срока их окончания — наиболее ранний и наиболее поздний. Для установления всех зависимостей в сетевом графике производится его расчет, который обычно осуществляется в табличной форме. По результатам определяется и наносится на график критический путь и устанавливаются резервы времени для работ некритического пути. 2 4 4 5 1 6 5 5 3 4 2 2 3 3 Расчет сетевого графика в табличной форме Номера начальных событий предшествующих работ Код работ i-j Продолжительность работ ti-j Раннее начало работ Tрнi-j Раннее оконча­ние работ Tроi-j Позднее начало работ Tпнi-j Позднее оконча­ние работ Tпоi-j Полный резерв времени работ Ri-j Свобод­ный резерв времени работ ri-j Отметка критического пути 1 2 3 4 5 6 7 8 9 10 - 1-2 1 1 1 К - 1-3 2 2 3 5 3 3 - 1-4 3 3 5 8 5 1 2-3 4 1 5 1 5 К 1 2-5 5 1 6 4 9 3 1 2-7 6 1 7 4 10 3 3 1,2 3-7 5 5 10 5 10 К 1,2 3-9 4 5 9 12 16 7 7 1 4-6 3 3 6 8 11 5 2 2 5-6 2 6 8 9 11 3 2 5-7 6 6 10 10 4 4 5 6-8 3 8 11 11 14 3 3 2,3,5 7-8 4 10 14 10 14 К 2,3,5 7-9 5 10 15 11 16 1 1 6,7 8-9 2