Курс лекций по сетевому анализу Степанова Алена Андреевна профессор кафедры математики и моделирования
оглавление Сетевой график Нумерация событий. Метод вычеркивания Алгоритм Форда нумерации событий Критическое время Максимальные времена наступления событий Резервы времени
оглавление 7. Подкритические пути 8. Линейная диаграмма проекта 9. Оптимальное по времени распределение ресурсов при постоянных интенсивностях 10. Уплотнение ресурса
Оглавление(продолжение) 5.Прямые и плоскости 6. Кривые второго порядка 7.Поверхности второго порядка 8.Замечательные кривые 9.Комплексные числа
Лекция 1. Сетевой график
Ориентированный граф(орграф) – это пара (V;E), где V - непустое множество, E -множество упорядоченных пар элементов из V. Элементы множества V называются вершинами, элементы множества Е называются дугами орграфа.
Сеть – это орграф, в котором существует единственная вершина, в которую не входит ни одна дуга и существует единственная вершина, из которой не выходит ни одна дуга, при этом каждой дуге сопоставлено некоторое число, которое называется длиной дуги.
Пусть (V;E) – орграф. Последовательность u1,(u1,u2),u2,…,un-1,(un-1,un),un, где u1 ,…, un - вершины орграфа, (u1,u2),…, ,(un-1,un) – дуги орграфа, называется путем в орграфе. Число дуг пути называется длиной пути.
Сетевой график – это наглядное изображение проекта в виде орграфа, отображающее технологическую связь между работами. Вершины сетевого графика называются событиями. Дуги сетевого графика называются работами. Замечание. В сетевом графике не существует циклов.
Правила составления сетевого графика Если k>1 работ выходят из одного события Pi и входят в одно событие Pj, то вводим k-1 дополнительных событий Pi1,…, Pi(k-1), которые соединяем с Pj фиктивными работами нулевой продолжительности, изображаемых пунктиром. Если событие Pi (I отлично от m и 0) не имеет выходящих (входящих) дуг, то Pi (P0) следует соединить фиктивной работой с Pm (Pi).
Ключевые понятия Орграф, вершина, дуга, путь, длина пути, сеть, сетевой график
Вопросы для самопроверки по теме «Сетевой график» Дать определение орграфа. Как определяется понятие пути в орграфе? Как посчитать длину пути в орграфе? Что такое сеть? Определить понятие сетевого графика.
Вопросы для самопроверки по теме «Сетевой график»(продолжение) Является ли сетевой график сетью? Какие существуют правила построения сетевого графика?
Лекция 2. Нумерация событий. Метод вычеркивания дуг
Сетевой график называется правильно занумерованным, если из того, что - работа следует, что .
Метод вычеркивания дуг (алгоритм правильной нумерации сетевого графика) Первый шаг: просматриваем сеть с события , которое отнесем к событиям 0-го ранга, и вычеркиваем все дуги, выходящие из ; события без входящих дуг отнесем к событиям 1-го ранга.
Общий шаг: вычеркиваем все дуги, выходящие из события k –го ранга; события без входящих дуг отнесем к событиям (k+1) –го ранга.
После разбиения событий по рангам нумеруем события: событию присваиваем номер 0; событиям 1-го ранга в произвольном порядке присваиваем номера 1, 2, … , k1; событиям 2-го ранга в произвольном порядке присваиваем номера k1+1, … , k1+k2; и т.д.
Утверждение 1. На каждом шаге алгоритма вычеркивания дуг найдется событие, в которое не входит ни одна дуга.
Утверждение 2. Ранг события – наибольшая из длин путей из P0 в данное событие, где под длиной пути мы понимаем число дуг, входящих в этот путь.
пример
Разбиение событий по рангам:
Пронумерованная сеть:
Ключевые понятия Правильная нумерация событий в сетевом графике, ранг события, алгоритм правильной нумерации событий (метод вычеркивания дуг).
Вопросы для самопроверки по теме «Нумерация событий. Метод вычеркивания дуг» Дать определение правильной нумерации событий. Для чего применяется метод вычеркивания дуг? Описать этот метод? Что такое ранг события?
Лекция 3. Алгоритм Форда нумерации событий
Алгоритм Форда нумерации событий (алгоритм правильной нумерации сетевого графика) Первый шаг: каждой вершине ставят в соответствие число ; каждой дуге ставят в соответствие число .
Общий шаг: просматриваем все события сети в каком-нибудь порядке, например , и полагаем , , где равно или в зависимости от того, просматривалось ли на -м шаге событие или нет.
Обозначение: для всех . Утверждение 3. Число есть максимальная из длин цепей из события в событие , т.е. совпадает с рангом события .
После разбиения событий по рангам нумеруем события: событию присваиваем номер 0; событиям 1-го ранга в произвольном порядке присваиваем номера 1, 2, … , k1; событиям 2-го ранга в произвольном порядке присваиваем номера k1+1, … , k1+k2; и т.д.
пример
1-й шаг: для всех 2-й шаг:
Разбиение событий по рангам:
Пронумерованная сеть:
Ключевые понятия Правильная нумерация событий, ранг события, алгоритм Форда правильной нумерации событий.
Вопросы для самопроверки по теме «Алгоритм Форда нумерации событий» Дать определение правильной нумерации событий сетевого графика. Что такое ранг события? Описать алгоритм Форда нумерации событий сетевого графика.
Лекция 4. Критическое время
Длина работы - это продолжительность ее выполнения. Длина пути – это продолжительность выполнения всей последовательности работ этого пути, т.е. сумма длин работ этого пути. Считаем, что время наступления события равна нулю.
Минимальное (наиболее раннее) время возможного наступления события равно максимальной длине пути из в . Критическое время проекта – это минимальное время наступления последнего события . Критический путь – путь из в максимальной длины . Критическая работа – это работа, принадлежащая критическому пути.
Алгоритм вычисления минимальных времен и критического времени Первый шаг: каждой вершине ставят в соответствие число ; каждой дуге ставят в соответствие число .
Общий шаг: просматриваем все события пронумерованной сети в порядке , полагаем , , и записываем около каждого вычисленного номера тех событий , на которых был достигнут максимум.
Утверждение 4. Для правильно занумерованной сети третий шаг не изменит ни одного из чисел , полученных после второго шага.
Утверждение 5. Каждое из чисел определяет максимальную длину пути из в , т.е. равно минимальному времени наступления события . Число дает критическое время .
Утверждение 6. Путь из в является критическим тогда и только тогда, когда для всех дуг этого пути.
Следствие. Если по пометках, полученным в алгоритме вычисления минимальных времен, восстановить путь из в начиная с пометок события , то этот путь будет критическим.
пример
1-й шаг: для всех 2-й шаг:
Таким образом, критическое время равно 16; критические пути:
Ключевые понятия Минимальное время наступления события, критическое время проекта, критический путь, критическая работа, алгоритм вычисления минимальных времен, критического времени и нахождения критического пути.
Вопросы для самопроверки по теме «Критическое время» Дать определение минимального времени наступления события. Что такое критическое время проекта? Определить понятие критического пути. Какая работа называется критической?
Вопросы для самопроверки по теме «Критическое время» (продолжение) Описать алгоритм вычисления минимальных времен. За сколько шагов данный алгоритм сходится при условии правильной нумерации сети?
Лекция 5. Максимальные времена наступления событий
Максимальным (наиболее поздним) временем наступления события называется наиболее позднее время окончания всех работ, входящих в , не увеличивающее критическое время проекта. Замечание. Максимальное время наступления события равно разности между критическим временем проекта и максимальной длиной пути из в .
Утверждение 7. Для того, чтобы событие принадлежало критическому пути, необходимо и достаточно, чтобы выполнялось равенство
Алгоритм вычисления максимальных времен Первый шаг: каждой вершине ставят в соответствие число ; каждой дуге ставят в соответствие число .
Общий шаг: просматриваем все события пронумерованной сети в порядке от до ; полагаем и . Максимальные времена получаем по формуле:
пример
1-й шаг: для всех 2-й шаг:
Максимальные времена получаем по формуле :
Ключевые понятия Максимальное время наступления события, критическое время проекта, критический путь, алгоритм вычисления максимальных времен наступления события.
Вопросы для самопроверки по теме «Максимальные времена наступления событий» Дать определение максимального времени наступления события. Описать алгоритм вычисления минимальных времен. За сколько шагов данный алгоритм сходится при условии правильной нумерации сети? Сформулировать критерий принадлежности события критическому пути.
Лекция 6. Резервы времени
Величина называется полным резервом времени работы . Свойства полного резерва времени работы : при увеличении продолжительности выполнения работы на полный резерв времени этой работы критическое время выполнения проекта не меняется; при увеличении на полный резерв времени работы критическое время выполнения проекта не меняется;
полный резерв времени работы равен нулю тогда и только тогда, когда данная работа критическая; увеличение продолжительности некритической работы на полный резерв времени влечет появление нового критического пути, содержащего эту работу; полный резерв времени работы – это разность между критическим временем выполнения проекта и максимальной длиной пути, проходящего через эту работу.
Величина называется свободным резервом времени работы Свойства свободного резерва времени работы : при увеличении продолжительности выполнения работы на полный резерв времени этой работы критическое время выполнения проекта не меняется; при увеличении продолжительности выполнения работы на полный резерв времени не меняется;
увеличение продолжительности работы на часть ее свободного резерва может уменьшить полный резерв времени работ, входящих в событие и не влияет на полные резервы работ, выходящих из события ; для работ, оканчивающихся в событиях, лежащих на критическом пути, полный резерв времени совпадает со свободным.
Величина называется независимым резервом времени работы . Свойства независимого резерва времени работы : независимый резерв времени работы - это максимально допустимое время для увеличения продолжительности этой работы или запаздывания ее начала при условии, что все работы, входящие в событие , заканчиваются во время , а все работы, выходящие из события , начинаются во время ;
при увеличении продолжительности выполнения работы на независимый резерв времени этой работы критическое время выполнения проекта не меняется; использование на работе ее независимого резерва времени не влияет на резервы других работ; для работы, выходящей из события, лежащего на критическом пути, независимый резерв времени совпадает со свободным.
ПРИМЕР
Ключевые понятия Полный резерв времени работы, свободный резерв времени работы, независимый резерв времени работы.
Вопросы для самопроверки по теме «Резервы времени» Дать определение полного резерва времени работы. Перечислить свойства полного резерва времени работы. Дать определение свободного резерва времени работы. Перечислить свойства свободного резерва времени работы. Дать определение независимого резерва времени работы. Перечислить свойства независимого резерва времени работы.
Лекция 7. Подкритические работы
Работы, лежащие на путях, длина которых отличается от длины критического пути не более чем на величину , называются подкритическими с величиной отклонения . Замечание. Работа длины является подкритической с величиной отклонения , если
Подкритическим путем с величиной отклонения называется путь из в , длина которого удовлетворяет неравенствам
Утверждение. Работа является подкритической с величиной отклонения тогда и только тогда, когда ее полный резерв времени не превосходит .
ПРИМЕР
Пусть =2. Подкритическими работами являются критические работы и работа . Подкритическими путями являются критические пути и путь
Ключевые понятия Подкритическая работа, подкритический путь, полный резерв времени работы.
Вопросы для самопроверки по теме «Подкритические работы» Дать определение подкритической работы. Что такое подкритический путь? Какая существует связь между понятиями подкритической работы и полного резерва времени этой работы?
Лекция 8. Линейная диаграмма проекта
Алгоритм построения линейной диаграммы проекта: на горизонтальной оси наносится равномерная шкала времени; каждая работа изображается полоской, параллельной оси времени, длины, равной продолжительности этой работы; работы откладываются в порядке возрастания индекса , при равенстве этих индексов – в порядке возрастания индекса .
Критическое время проекта равно координате по оси времени самого правого конца всех полосок-работ линейной диаграммы. Нахождение критического пути: рассматриваем полоску любой работы, заканчивающейся в критическое время; находим полоску-работу, правый конец которой совпадает с левым концом уже выбранной полоски-работы, и т.д. Полученная последовательность работ составляет критический путь. Минимальное время наступления события - это координата начала полоски- работы для любого .
Нахождение максимального времени наступления события : сдвигаем вправо до вертикали критического времени полоски-работы , правым концом которых служит последнее событие; спускаясь затем сверху вниз, сдвигаем одну за другой все полоски вправо на максимально допустимые отрезки, т.е. так, чтобы правые концы сдвигаемых полосок попали на одну вертикаль с самым левым концом уже сдвинутых полосок; левый конец ранее сдвинутых полосок определяет максимальное время наступления события .
Полный резерв времени работы - это величина сдвига полоски-работы при нахождении максимальных времен появления событий. Свободный резерв времени работы - это наибольшая длина отрезка, на который можно сдвинуть вправо полоску-работу , не сдвигая других полосок-работ.
Нахождение независимого резерва времени работы : сдвигаем полоску-работу до совпадения с ; тогда независимый резерв времени работы - это длина отрезка от конца сдвинутой полоски до минимального времени события .
пример
Минимальное время появления события : Максимальное время появления события :
Полный резерв времени (ПРВ) некритической работы : Свободный резерв времени (СРВ) некритической работы :
Независимый резерв времени (НРВ) некритической работы :
Ключевые понятия Линейная диаграмма проекта, максимальные и минимальные времена появления события, полный, свободный и независимый резервы времени.
Вопросы для самопроверки по теме «Линейная диаграмма проекта» Описать алгоритм построения линейной диаграммы проекта. Как по линейной диаграмме проекта находятся максимальные и минимальные времена появления события? Как по линейной диаграмме проекта находятся полный, свободный и независимый резервы времени?
Лекция 9. Оптимальное по времени распределение ресурсов при постоянных интенсивностях
Пусть проект выполняется s различными ресурсами, ежедневное наличие которых Интенсивность потребления k – го ресурса - это количество k – го ресурса, потребляемого в единицу времени.
Для каждого ресурса известно: - интенсивность потребления этого ресурса для работы - продолжительность выполнения работы при этой интенсивности
Постановка задачи: оптимальное распределение ресурсов по работам, т.е. размещение работ, которое при заданных ограниченных ресурсах обеспечило бы выполнение проекта в минимальное время
Алгоритм приближенного решения задачи
проектируем начало и конец каждой работы на ось времени, проекции обозначаем через ; рассматриваем совокупность работ над промежутком ; нумеруем эти работы в порядке возрастания их ПРВ, при равенстве ПРВ – в порядке убывания их интенсивностей;
6) суммируем интенсивности этих работ в порядке возрастания их номеров; 7) работы, для которых после прибавления их интенсивностей сумма превосходит , сдвигаем вправо к моменту .
Предположим проделано k шагов алгоритма, так что суммарная интенсивность работ, размещенных над промежутком , не превышает .
Общий шаг: момент считаем моментом начала оставшейся части проекта; определяем критическое время, критические работы, полные резервы времени для всех работ, начинающихся не ранее ; рассматриваем совокупность работ над промежутком ;
4) нумеруем эти работы в зависимости от условий задачи: а) если работы проекта не допускают перерыва в их выполнении, то первые номера присваиваем продолжающимся работам, остальные работы нумеруем в порядке возрастания их ПРВ, при равенстве ПРВ – в порядке убывания их интенсивностей;
б) если работы проекта допускают перерыв в своем выполнении, то нумеруем работы в порядке возрастания их ПРВ, при равенстве ПРВ – в порядке убывания их интенсивностей; 5) суммируем интенсивности этих работ в порядке возрастания их номеров;
6) работы, для которых после прибавления их интенсивностей сумма превосходит , сдвигаем вправо к моменту , причем, если при нумерации а) сдвигу подлежит продолжающаяся работа, то сдвигаем ее полностью. Алгоритм закончен, когда просмотрены все работы проекта.
пример (работы проекта не допускают перерыва в их выполнении, А=12)
Линейная диаграмма проекта: (0,2): (P0,P1), (P0,P3), (P0,P2)
(2,5): (P0,P3), (P1,P3), (P0,P2) , (P1,P4)
(5,6): (P0,P2), (P1,P3), (P1,P4)
(6,9): (P3,P4), (P2,P5), (P1,P4), (P3,P5)
(9,10): (P3,P4), (P2,P5), (P3,P5), (P1,P4)
(10,12): (P3,P4), (P2,P5), (P1,P4)
(12,13): (P2,P5), (P1,P4) (13,15): (P1,P4) (15,17): (P4,P5)
Ключевые понятия Интенсивность потребления ресурса на работе, оптимальное по времени распределение ресурсов при постоянных интенсивностях.
Вопросы для самопроверки по теме «Оптимальное по времени распределение ресурсов при постоянных интенсивностях » Дать определение интенсивности потребления ресурса на работе. Сформулировать задачу оптимального по времени распределения ресурсов при постоянных интенсивностях. Описать алгоритм приближенного решения этой задачи, если работы проекта не допускают перерыва в их выполнении. Описать алгоритм приближенного решения этой задачи, если работы проекта допускают перерыва в их выполнении.
Лекция 10. Уплотнение ресурса
Алгоритм уплотнения ресурсов применяется к линейной диаграмме проекта, полученного в результате применения алгоритма приближенного решения задачи оптимального по времени распределения ресурсов при постоянных интенсивностях.
Алгоритм уплотнения ресурсов 1 шаг: проектируем начало и конец каждой работы на ось времени, проекции обозначаем через ; 2) рассматриваем промежуток ; 3) если количество ресурса, потребляемого на этом промежутке меньше имеющегося в наличии, то нумеруем работы, заканчивающиеся событием в момент в порядке убывания их интенсивностей;
4) суммируем потребляемое на промежутке количество ресурса и ресурсом каждой из работ из предыдущего промежутка в порядке их номеров; 5) если полученная сумма не превышает наличия ресурса, то сдвигаем эту работу вправо так, чтобы ее конец совпал с ; 6) после просмотра всех работ их предыдущего промежутка снова проектируем начала и концы всех работ на временную ось.
Общий шаг: 1) рассматриваем промежуток ; 2) если количество ресурса, потребляемого на этом промежутке, меньше имеющегося в наличии, то нумеруем работы, заканчивающиеся в момент , которые сетевой график позволяет сдвигать, в порядке убывания их интенсивностей; 3) если работы проекта не допускают перерыв в своем выполнении, то пронумерованные работы сдвигаем в промежуток как на первом шаге; если наличие ресурса позволяет дальнейший сдвиг работ вправо, то производим его;
4) если работы проекта допускают перерыв в своем выполнении, то пронумерованные работы сдвигаем в промежуток полностью или частично; если наличие ресурса позволяет дальнейший сдвиг части работы вправо, то производим его; 5) проектируем начала и концы всех работ на временную ось.
пример
(12,15): работу сдвигаем на 2 единицы
(10,12): работу сдвигаем на 4 единицы, работу сдвигаем на 10 единицы
(9,10):сдвигов нет, (8,9): сдвигов нет (6,8): работа сдвигается на 2 единицы, работа сдвигается на 3 единицы
Таким образом, продолжительность выполнения проекта сократилась на 2 единицы.
(8,10): работу сдвигаем на 4 единицы
Ключевые понятия Оптимальное по времени распределение ресурсов при постоянных интенсивностях, алгоритм уплотнения ресурсов.
Вопросы для самопроверки по теме «Уплотнение ресурсов » Описать алгоритм уплотнения ресурсов, если работы проекта не допускают перерыва в их выполнении. Описать алгоритм уплотнения ресурсов, если работы проекта допускают перерыва в их выполнении.
Основная литература Зуховицкий С.И., Радчик И.А., Математические методы сетевого планирования. - М.: Наука, 1965. Разумов И.М., Белова Л.Д., Ипатов М.И., Проскуряков А.В., Сетевые графики в планировании: учебное пособие. – М.: Высшая школа, 1975. Абрамов С.А., Мариничев М.И., Поляков П.Д., Сетевые методы планирования и управления, М., 1965. Новицкий Н.И., Сетевое планирование и управление производством. Учебно-практическое пособие, - М.: Новое знание, 2004.
Дополнительная литература Зайденман И.А., Маргулис А.Я., Математика в сетевом планировании. – М.: Знание, 1967. Васильев В.М., Вальковский Б.В., Лавров М.Ф., Методы планирования и управления по сетевым графикам и их использование в капитальном строительстве МО СССР. – Л.: Высшее военное инженерно-техническое краснознаменное училище, 1966. Кофман А., Дебазей Г., Сетевые методы планирования. Применение системы ПЕРТ и ее разновидностей при управлении производственными и научно-исследовательскими проектами, пер. с франц., М., 1968.
Использование материалов презентации Использование данной презентации возможно только при условии соблюдения требования законов РФ об авторском праве и интеллектуальной собственности ,а также с учётом требований настоящего Заявления. Презентация является собственностью автора. Разрешается распечатывать любую часть презентации для личного некоммерческого использования, но не допускается её использование с какой-нибудь иной целью. Не разрешается вносить изменения в любую часть презентации.
|