Дискретная математика
Методические указания
по выполнению расчетно-графической работы № 5 на тему «Расчеты по алгоритмам управления проектом»
Задание на выполнения расчетно-графической (РГР) работы № 5.
Найти критический путь по алгоритмам управления проектом (СПУ), полный, свободный, независимый и гарантированный резервы времени. Продолжительности работ на рис. 1 приведены в условных единицах. Различия вариантов заключены в присоединении к модели двух фиктивных работ и удалении трех работ (см. табл. 1).
Данные по вариантам
Таблица 1
| Старший разряд номера варианта |
Удалить дугу ( )
| ||
| 1-ая дуга | 2-ая дуга | 3-я дуга | |
( )
| ( )
| ( )
| |
( )
| ( )
| ( )
| |
( )
| ( )
| ( )
| |
( )
| ()
| ( )
| |
( )
| ( )
| ()
| |
| ()
| ( )
| ( )
|
Таблица 1 (продолжение)
| Младший разряд номера варианта | Ввести фиктивную работу | |
| 1-ая фиктивная работа | 2-ая фиктивная работа | |
( )
| ( )
| |
( )
| ( )
| |
( )
| ()
| |
( )
| ()
| |
( )
| ( )
| |
( )
| ( )
| |
( )
| ()
| |
| ()
| ()
| |
| ()
| ()
| |
| ()
| ()
|
Обозначения
Введем следующие обозначения:
- событие «Начало проекта»,
- событие «Окончание проекта»,
- промежуточные события проекта, фиксирующие начало и окончание работы,
- работа,
- ранний момент наступления события,
- поздний момент наступления события.
Ниже, на рис. 2, дана схема идентификации вершин графа – сети.
 |
Введем дополнительные обозначения:
- формула для расчета раннего момента наступления события,
- формула для расчета позднего момента наступления события.
Ниже, на рис. 3, 4, приведены схемы, поясняющие расчет раннего и позднего моментов наступления событий.
Ниже, на рис. 5, дано обозначение и пояснения фиктивной работы.
 |
Фиктивная работа (
) обуславливает возможность одновременного начала работ 
и 
.
Введем дополнительные обозначения:
- резерв времени события , т.е. максимальное время, на которое можно задержать наступление события без задержки сроков завершения проекта.
 |
Таким образом, полная схема идентификации вершин графа-сети показана на рис. 6.
Равенство 
позднего и раннего сроков наступления события обозначает ситуацию недопустимости задержки наступления события .
Введем следующие обозначения:
- полный резерв времени
работы 
.
Если 
= 0, то работа лежит на критическом пути (рис. 7).
Ниже приведены расчеты, поясняющие рис. 7. Поскольку 
= 4 - 2 - 2 = 0, 
= 8 - 2 - 4 =20, 
= 8 - 4 - 4 = 0, то работы 12 и 23 лежат на критическом пути.
Введем следующие обозначения:
- свободный резерв времени работы ,
- независимый резерв времени работы ,
- гарантированный резерв времени работы .
 |
Пример и методические указания по выполнению РГР № 5.
Пусть в качестве задания на РГР № 5 задан граф-сеть на рис. 8.
3.1. Выполним нумерацию вершин графа.
Нумерация вершин ациклического графа называется правильной на дуге 
, если 
и правильной на графе, если она правильна на всех его дугах.
Результаты нумерации вершин графа приведены на рис. 9.
Рассчитаем ранние моменты наступления событий.
Расчет ранних моментов наступления событий для графа – сети приведен в табл. 1. При выполнении расчетов принято, что вершина имеет 
.
Результаты расчета ранних моментов наступления событий
Таблица 1.
| i | j | 
| 
|
| 
| |||
| ||||
| 
| |||
| 
| |||
| ||||
| 
| |||
| ||||
| 
| |||
| ||||
| 
| |||
| ||||
| 
| |||
|
Обозначения: p – шаг, i, j – номера вершин графа- сети.
Результаты расчета отражены на графе – сети (рис. 10).
Рассчитаем поздние моменты наступления событий.
Расчет поздних моментов наступления событий для графа – сети приведен в табл. 2. При выполнении расчетов принято, что вершина 
имеет 
.