Курс лекций по сетевому анализу Степанова Алена Андреевна профессор кафедры математики и моделирования оглавление Сетевой график

Курс лекций по сетевому анализу

• Степанова Алена Андреевна

• профессор кафедры математики и моделирования

оглавление

• Сетевой график

• Нумерация событий. Метод вычеркивания

• Алгоритм Форда нумерации событий

• Критическое время

• Максимальные времена наступления событий

• Резервы времени

оглавление

• 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-й шаг:

• 3-й шаг:

• 4-й шаг:

Разбиение событий по рангам:

Пронумерованная сеть:

Ключевые понятия

• Правильная нумерация событий, ранг события, алгоритм Форда правильной нумерации событий.

Вопросы для самопроверки по теме «Алгоритм Форда нумерации событий»

• Дать определение правильной нумерации событий сетевого графика.

• Что такое ранг события?

• Описать алгоритм Форда нумерации событий сетевого графика.

Лекция 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.

Использование материалов презентации

• Использование данной презентации возможно только при условии

• соблюдения требования законов РФ об авторском праве и

• интеллектуальной собственности ,а также с учётом требований

• настоящего Заявления.

• Презентация является собственностью автора. Разрешается

• распечатывать любую часть презентации для личного

• некоммерческого использования, но не допускается её

• использование с какой-нибудь иной целью.

• Не разрешается вносить изменения в любую часть презентации.