свершение события означает что
Ранние и поздние временные характеристики сетевой модели
 |
Рассмотрим определение ранних и поздних временных характеристик на примере одноцелевых моделей. В сетевом графике (рис. 3.1) числа, проставленные над дугами, указывают на продолжительность в днях соответствующих работ.
Рис. 3.1. Сетевой график проекта
Очевидно, что завершающее событие данной сетевой модели может свершиться не раньше, чем через 20 дней, так как свершение завершающего события сети означает выполнение всех работ проекта. Пять последовательно выполняемых работ (0, 2), (2, 4), (4, 5), (5, 7) и (7, 8) определяют продолжительность выполнения всего комплекса. Событие 3 свершится тогда, когда будут закончены все работы, входящие в него. Очевидно, это может случиться не раньше, чем через 4 дня. Цепочка работ (0, 1) и (1, 3) определяет это время. С другой стороны, событие 3 может свершиться через 15 дней, причем время выполнения комплекса работ проекта еще остается без изменений. Дальнейшее увеличение времени свершения события 3 приведет к увеличению времени выполнения всего комплекса.
Таким образом, в сетевых моделях можно выделить несколько работ, определяющих время выполнения всего проекта, а для некоторых событий сетевой модели существует некоторый интервал времени, в пределах которого это событие может свершиться, не вызывая увеличения срока выполнения комплекса в целом. Ранние и поздние временные характеристики, используемые в анализе сетевых моделей, предназначены для определения указанного интервала времени. Основой при определении этих характеристик является критическое время. Зная продолжительность каждой работы, можно определить продолжительность всех полных путей данной сетевой модели.
Полный путь, имеющий наибольшую продолжительность, называется критическим.
Продолжительность критического пути принято называть критическим временем и обозначать его tкр.
Ранним сроком свершения события называется такой момент времени, раньше которого событие не может произойти.
Ранним сроком свершения события j будем обозначать 
. Очевидно, что 
равен продолжительности максимального из путей, предшествующих событию j:
(3.2)
где L (0 — j)max — максимальный путь, предшествующий событию j.
Очевидно, что для завершающего события ранний срок окончания равен критическому времени. Например, для сетевого графика, представленного на рисунке 3.1, можно определить, что 
= 3, 
= 5, 
= 12, 
= 13 (дней).
Ранним сроком начала работыназывается такой момент времени, раньше которого работа не может быть начата.
. (3.3)
Например, для сетевого графика, представленного на рисунке 3.1, можно определить, что 
= 3, 
= 3, 
= 4, 
= 12 (дней).
Ранним сроком окончания работыназывается такой момент времени, раньше которого работа не может быть закончена.
. (3.4)
Например, для сетевого графика, представленного на рисунке 3.1, можно определить, что 
= 4, 
= 7, 
= 7, 
= 13 (дней).
Поздним сроком свершения события называется такой наибольший момент времени, к которому должно свершиться событие, чтобы обеспечить завершение всего комплекса работ в заданный срок.
Поздний срок свершения события j обозначается 
. При определении поздних сроков свершения событий принимается, что для завершающего события ранний срок его свершения равен позднему сроку. Поздние сроки свершения всех остальных событий сетевой модели определяются из условия обеспечения свершения завершающего события в заданный срок. В дальнейшем принимаем, что заданный срок свершения завершающего события равен критическому времени. Тогда
(3.5)
Здесь L(j — n)max — максимальный путь, следующий за событием j, Очевидно, что для событий, принадлежащих критическому пути, 
. Например, для сетевого графика, представленного на рисунке 3.1, можно определить, что 
= 8, 
= 5, 
= 12, 
= 18 (дней).
Поздним сроком окончания работы называется такой момент времени, к которому должна быть закончена работа, чтобы обеспечить свершение завершающего события в заданный срок.
(3.6)
Например, для сетевого графика, представленного на рисунке 3.1, можно определить, что 
= 15, 
= 12, 
= 18, 
= 18 (дней).
Поздним сроком начала работы называется такой момент времени, в который должна начаться работа, чтобы она могла быть оконченной к позднему сроку своего окончания.
. (3.7)
Например, для сетевого графика, представленного на рисунке 3.1, можно определить, что 
= 14, 
= 8, 
= 15, 
= 17 (дней).
Следует отметить, что вычисление ранних сроков производится в направлении от начала сети до ее конца, а поздних сроков — от конца к началу.
Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет
Ранние и поздние временные характеристики сетевой модели
 |
Рассмотрим определение ранних и поздних временных характеристик на примере одноцелевых моделей. В сетевом графике (рис. 3.1) числа, проставленные над дугами, указывают на продолжительность в днях соответствующих работ.
Рис. 3.1. Сетевой график проекта
Очевидно, что завершающее событие данной сетевой модели может свершиться не раньше, чем через 20 дней, так как свершение завершающего события сети означает выполнение всех работ проекта. Пять последовательно выполняемых работ (0, 2), (2, 4), (4, 5), (5, 7) и (7, 8) определяют продолжительность выполнения всего комплекса. Событие 3 свершится тогда, когда будут закончены все работы, входящие в него. Очевидно, это может случиться не раньше, чем через 4 дня. Цепочка работ (0, 1) и (1, 3) определяет это время. С другой стороны, событие 3 может свершиться через 15 дней, причем время выполнения комплекса работ проекта еще остается без изменений. Дальнейшее увеличение времени свершения события 3 приведет к увеличению времени выполнения всего комплекса.
Таким образом, в сетевых моделях можно выделить несколько работ, определяющих время выполнения всего проекта, а для некоторых событий сетевой модели существует некоторый интервал времени, в пределах которого это событие может свершиться, не вызывая увеличения срока выполнения комплекса в целом. Ранние и поздние временные характеристики, используемые в анализе сетевых моделей, предназначены для определения указанного интервала времени. Основой при определении этих характеристик является критическое время. Зная продолжительность каждой работы, можно определить продолжительность всех полных путей данной сетевой модели.
Полный путь, имеющий наибольшую продолжительность, называется критическим.
Продолжительность критического пути принято называть критическим временем и обозначать его tкр.
Ранним сроком свершения события называется такой момент времени, раньше которого событие не может произойти.
Ранним сроком свершения события j будем обозначать 
. Очевидно, что 
равен продолжительности максимального из путей, предшествующих событию j:
(3.2)
где L (0 — j)max — максимальный путь, предшествующий событию j.
Очевидно, что для завершающего события ранний срок окончания равен критическому времени. Например, для сетевого графика, представленного на рисунке 3.1, можно определить, что 
= 3, 
= 5, 
= 12, 
= 13 (дней).
Ранним сроком начала работыназывается такой момент времени, раньше которого работа не может быть начата.
. (3.3)
Например, для сетевого графика, представленного на рисунке 3.1, можно определить, что 
= 3, 
= 3, 
= 4, 
= 12 (дней).
Ранним сроком окончания работыназывается такой момент времени, раньше которого работа не может быть закончена.
. (3.4)
Например, для сетевого графика, представленного на рисунке 3.1, можно определить, что 
= 4, 
= 7, 
= 7, 
= 13 (дней).
Поздним сроком свершения события называется такой наибольший момент времени, к которому должно свершиться событие, чтобы обеспечить завершение всего комплекса работ в заданный срок.
Поздний срок свершения события j обозначается 
. При определении поздних сроков свершения событий принимается, что для завершающего события ранний срок его свершения равен позднему сроку. Поздние сроки свершения всех остальных событий сетевой модели определяются из условия обеспечения свершения завершающего события в заданный срок. В дальнейшем принимаем, что заданный срок свершения завершающего события равен критическому времени. Тогда
(3.5)
Здесь L(j — n)max — максимальный путь, следующий за событием j, Очевидно, что для событий, принадлежащих критическому пути, 
. Например, для сетевого графика, представленного на рисунке 3.1, можно определить, что 
= 8, 
= 5, 
= 12, 
= 18 (дней).
Поздним сроком окончания работы называется такой момент времени, к которому должна быть закончена работа, чтобы обеспечить свершение завершающего события в заданный срок.
(3.6)
Например, для сетевого графика, представленного на рисунке 3.1, можно определить, что 
= 15, 
= 12, 
= 18, 
= 18 (дней).
Поздним сроком начала работы называется такой момент времени, в который должна начаться работа, чтобы она могла быть оконченной к позднему сроку своего окончания.
. (3.7)
Например, для сетевого графика, представленного на рисунке 3.1, можно определить, что 
= 14, 
= 8, 
= 15, 
= 17 (дней).
Следует отметить, что вычисление ранних сроков производится в направлении от начала сети до ее конца, а поздних сроков — от конца к началу.
Сетевое планирование и управление (стр. 1 )
 | Из за большого объема этот материал размещен на нескольких страницах: 1 2 3 |
2. СЕТЕВОЕ ПЛАНИРОВАНИЕ И УПРАВЛЕНИЕ
2.1. Построение сетевого графика экономического процесса
Целенаправленную экономическую деятельность можно моделировать с помощью сетевого графика. Рассмотрим определения, связанные с этим понятием.
Наглядно граф можно представить как некоторое множество вершин и множество ребер, соединяющих все или некоторые из этих вершин.
Если на ребре указано направление связи между вершинами, то оно называется дугой.
Если все соединения в графе изображаются дугами, то граф называется ориентированным, или орграфом.
Последовательность дуг, в которой конец каждой предыдущей дуги совпадает с началом следующей, называется путем в орграфе.
Путь, у которого начальная вершина совпадает с конечной, называется контуром.
Вершина, из которой дуги только выходят, но не входят, называется истоком.
Вершина, в которую дуги только входят, но не выходят, называется стоком.
Любой путь от истока к стоку называется полным.
Вершина 
(«предок») предшествует в графе вершине 
(«потомок»), если существует путь из в 
.
Граф является упорядоченным, если в нем порядковый номер «предка» всегда меньше порядкового номера «потомка».
Графический способ упорядочения графа реализуется по алгоритму Фалкерсона:
1-ый шаг) выделяем вершины, не имеющие «предков», и последовательно нумеруем их в произвольном порядке;
2-ой шаг) мысленно вычеркиваем из графа все вершины, имеющие номера, и дуги, из них выходящие;
3-ий шаг) в получившемся графе повторяем процедуры 1-ого и 2-ого шагов до тех пор, пока все вершины не будут пронумерованы.
Граф называется связанным, если две любые его вершины можно соединить путем, в котором не учитывается ориентация дуг.
На изображении с помощью сетевого графика основано сетевое планирование и управление (СПУ).
Основными понятиями СПУ являются работа и событие.
Под работой понимаются действия, связанные с затратами ресурсов и приводящие к определенным результатам. Работы обозначаются на сетевом графике дугами.
Под событием понимают результат завершения одной или нескольких работ. События обозначаются на сетевом графике вершинами.
Подготовка исходных данных для построения сетевого графика включает:
— определение начального и конечного событий;
— составление перечня всех событий, следующих за начальным и без которых не может произойти конечное событие;
— составление списка работ, соединяющих намеченные события;
— определение продолжительности выполнения каждой работы.
При построении сетевого графика для СПУ должны учитываться следующие четыре правила:
— график должен иметь только одно начальное событие (исток) и только одно конечное событие (сток);
— ни одно событие не может произойти до тех пор, пока не будут закончены все входящие в него работы;
— ни одна работа, выходящая из какого-либо события, не может начаться до тех пор, пока не произойдет данное событие;
— график должен быть упорядоченным.
2.2. Расчет параметров сетевого графика
Основными параметрами сетевого графика являются:
— резервы времени событий;
— резервы времени работ.
Критическим называется наиболее продолжительный из полных путей.
Критический путь определяет достаточно необходимое время выполнения всех работ, называемое критическим сроком.
Работы и события, лежащие на критическом пути, называются критическими.
Определение критического пути в сетевом графике:
Полные пути и их продолжительности:
Резерв времени событий показывает, на сколько времени может задержаться свершение этого события без изменения срока наступления завершающего (конечного) события (стока).
Для определения резервов времени событий необходимо рассчитать ранние и поздние сроки свершения событий.
Ранний срок 
свершения события 
— это ранний срок, необходимый для выполнения всех работ, предшествующих данному событию:
где 
— ранний срок свершения события 
;
— продолжительность работы
;
— множество работ, входящих в событие .
Определение ранних сроков свершения событий в сетевом графике:
Поздним сроком 
свершения события называется самый поздний момент времени, после которого остается столько времени до критического срока, сколько необходимо для завершения всех работ, следующих за этим событием:
,
где 
— поздний срок свершения события ;
— продолжительность работы ;
— множество работ, выходящих из события .
Определение поздних сроков свершения событий в сетевом графике:
Тогда резерв времени события равен:
.
Определение резервов времени событий в сетевом графике:
Резервы времени работы подразделяются на полный 
и свободный 
.
.
Определение полных резервов времени работ в сетевом графике:
.
Определение свободных резервов времени работ в сетевом графике:
Получается, что резерв времени события связан с резервами времени входящей в него работы следующим образом:
.
Отсюда следует, что любая из работ, входящих в одно и то же событие, имеет одинаковую разность между ее полным и свободным резервами времени.
Резервы времени критических событий и критических работ равны нулю.
2.3. Оптимизация сетевого графика комплекса работ
С каждой работой, имеющей определенный неизменный объем, связаны затраты на ее выполнение. Как правило, затраты на выполнение работы с неизменным ее объемом возрастают с уменьшением ее продолжительности и снижаются при увеличении ее продолжительности.
В связи с этим возможны варианты организации комплекса работ, отличающиеся продолжительностью его выполнения и затратами на его выполнение.
Для выбора наилучшего варианта служит оптимизация. Оптимальным считается тот вариант, который отвечает заданному критерию.
Оптимизация сетевого графика может осуществляться по следующим двум критериям:
— минимизация времени выполнения комплекса работ при заданных затратах на это выполнение;
— минимизация затрат на выполнение комплекса работ при заданном времени этого выполнения.
Таким образом, нельзя добиться выполнения комплекса работ одновременно в минимальные сроки и с наименьшими затратами.
Построен взвешенный график выполнения работ.
Упорядочим график по алгоритму Фалкерсона:
В итоге, построим сетевой график выполнения работ.
Проведем анализ сетевого графика:
Таким образом, наименьшая продолжительность выполнения всего комплекса работ не может быть меньше 13 суток.
Заданы два варианта (нормальный и ускоренный) выполнения работ и связанных с ними затрат:
затрат на одни сутки ускорения
Требуется оптимизировать по критерию минимизации затрат сетевой график при заданной продолжительности выполнения всего комплекса работ за 13 суток.
Оптимизацию можно провести двумя способами.
Первый способ заключается в уменьшении продолжительности выполнения работ, осуществляемых в нормальном режиме, начиная с тех, которые дают наименьший прирост затрат.
Представим алгоритм решения поставленной оптимизационной задачи первым способом в таблице:
Суточный прирост затрат
Количество сокращаемых суток
Итак, при снижении продолжительности выполнения всего комплекса работ с 22 суток до 13 суток оптимальные затраты составляют 1060+520=1580 (у. е.).
Второй способ заключается в увеличении продолжительности выполнения работ, осуществляемых в ускоренном режиме, начиная с тех, которые дают наибольший прирост затрат.
Представим алгоритм решения поставленной оптимизационной задачи вторым способом в таблице:
Суточный прирост затрат
Количество наращиваемых суток
Итак, при повышении продолжительности выполнения всего комплекса ускоренного режима работ до 13 суток оптимальные затраты составляют =1580 (у. е.).
Обязательное условие – оптимальные затраты, определяемые любым из указанных способов, должны иметь одинаковую величину.
Выводы по второму разделу
С помощью сетевого графика модулируется целенаправленная экономическая деятельность. Сетевой график – это связанный упорядоченный взвешенный орграф без контуров. Работа, связанная с затратами ресурсов и приводящая к определенным результатам, обозначается на сетевом графике дугой. Событие как результат завершения одной или нескольких работ обозначается на сетевом графике вершиной.
Критический путь, резервы времени событий и работ являются основными параметрами сетевого графика.
Резерв времени события связан с резервами времени входящей в него работы. Любая из работ, входящих в одно и то же событие, имеет одинаковую разность между ее полным и свободным резервами времени. Резервы времени критических событий и критических работ равны нулю.
Как правило, затраты на выполнение работы с неизменным ее объемом возрастают с уменьшением ее продолжительности и снижаются при увеличении ее продолжительности. Оптимизация сетевого графика комплекса работ осуществляется для минимизации времени выполнения этого комплекса при заданных затратах на это выполнение или для минимизации затрат на выполнение указанного комплекса при заданном времени этого выполнения. Поэтому нельзя добиться выполнения комплекса работ одновременно в минимальные сроки и с наименьшими затратами.
Оптимизировать сетевой график по критерию минимизации затрат при заданной продолжительности выполнения всего комплекса работ можно двумя способами. Первый способ заключается в уменьшении продолжительности выполнения работ, начиная с тех, которые дают наименьший прирост затрат. Второй способ заключается в увеличении продолжительности выполнения работ, начиная с тех, которые дают наибольший прирост затрат. Определяемые любым из указанных способов оптимальные затраты должны иметь одинаковую величину.
Вопросы для самопроверки
— Как можно представить наглядно граф?
— Какой граф называется орграфом?
— Что называется путем в орграфе?
— Какая вершина называется истоком, а какая – стоком?
— Какой путь называется полным?
— Какой граф называется взвешенным?
— Какой граф является упорядоченным?
— Какой граф называется связанным?
— Что представляет собой сетевой график?
— Что понимается под работой и событием и как они обозначаются на сетевом графике?
— Что включают основные параметры сетевого графика?
— Какой из полных путей называется критическим?
— Что показывает резерв времени события?
— Что означают ранний и поздний сроки свершения события?
— Чему равен резерв времени события?
— Какие бывают резервы времени работы?
— Что показывают полный и свободный резервы времени работы?
— Как выражается резерв времени события через резервы времени входящей в него работы?
— Какое численное значение имеют резервы времени критических событий и критических работ?
— По каким критериям может осуществляться оптимизация сетевого графика?
— Какими способами можно провести оптимизацию сетевого графика?
Примеры решения задач
Определить минимальную стоимость комплекса производственных работ при заданной продолжительности его выполнения и других указанных условиях.