- •Глава 6. Элементы теории графов. Сетевое планирование и управление.
- •§1. Основные понятия теории графов
- •§2. Маршруты, цепи, циклы
- •§3. Числовые функции на графе
- •§4. Деревья и леса
- •Алгоритм Краскала поиска остовного дерева минимальной длины
- •§5. Эйлеровы и Гамильтоновы графы
- •§6. Сетевые модели планирования и управления
- •§7. Расчётные параметры сетевого графика
- •§8. Сетевое планирование в условиях неопределенности
- •§9. Построение сетевой модели
§9. Построение сетевой модели
Структура сетевой модели и оценки продолжительности работ (в сутках) заданы в табл. 3. Требуется:
а) получить все характеристики СМ;
б) оценить вероятность выполнения всего комплекса работ за 35 дней, за 30 дней;
в)
оценить максимально возможный срок
выполнения всего комплекса работ с
надежностью 95% (т. е.
).
Три первые графы табл. 3. содержат исходные данные, а две последние графы - результаты расчетов по формулам. Так, например,
,
,
,
……………………………….
,
,
.
Работа |
Продолжительность |
Ожидаемая |
Дисперсия |
|
|
|
|
Продолжительность
|
|
(1.2) |
5 |
7.5 |
5 |
0.25 |
(2.3) |
4 |
6.5 |
5 |
0.25 |
(2.4) |
3 |
6 |
3 |
1.00 |
(2.5) |
1 |
5.5 |
4 |
0.25 |
(3.7) |
0.5 |
3.5 |
1 |
0.36 |
(4.5) |
5 |
7.5 |
6 |
0.25 |
(4.6) |
3 |
5.5 |
4 |
0.25 |
(4.9) |
5 |
10 |
7 |
1.00 |
(5.8) |
2 |
4.5 |
3 |
0.25 |
(5.10) |
7 |
12 |
9 |
1.00 |
(6.9) |
0 |
0 |
0 |
0.00 |
(6.11) |
3 |
8 |
5 |
1.00 |
(7.10) |
4 |
9 |
6 |
1.00 |
(8.10) |
2 |
7 |
4 |
1.00 |
(9.10) |
1 |
6 |
3 |
1.00 |
(10.11) |
8 |
10.5 |
9 |
0.25 |
Получим сетевую модель аналогичную рассматриваемой во второй главе:
Таким
образом, ход расчета характеристик
модели остается аналогичен рассмотренному
ранее. Причём критическим является
путь:
,
а его продолжительность равна
дня.
Дисперсия критического пути составляет:
Для
использования формулы показателя
дисперсии необходимо иметь среднее
квадратическое отклонение, вычисляемое
путем извлечения из значения дисперсии
квадратного корня, т. е.
Тогда
,
Таким образом, вероятность того, что весь комплекс работ будет выполнен не более чем за 35 дней, составляет 88,5%, в то время как вероятность его выполнения за 30 дней - всего 3,5% .
Для
решения второй (по существу обратной)
задачи прежде всего в табл.2 найдем
значение аргумента z,
которое соответствует заданной
вероятности 95% . В графе
наиболее близкое значение (0,9545
100%)
к ней соответствует
.
В этой связи в формуле (3.61) используется
именно это (не совсем точное) значение.
Получаем:
дня.
Следовательно,
максимальный срок выполнения всего
комплекса работ при заданном уровне
вероятности
составляет 36,2 дня.
Составим словесно-формульное описание алгоритма
Начало процесса.
Ввод данных
Организация цикла
Вычисление для каждого значения работы:
.
Завершение цикла.
Вычисление дисперсии критического пути
.Вычисление вероятности выполнения работ за 35 и 30 дней
,
Организация цикла для нахождения .
Завершение цикла.
Вычисление срока выполнения всего комплекса работ .
Вывод результатов.
Конец процесса.
