Мои Конспекты
Главная | Обратная связь


Автомобили
Астрономия
Биология
География
Дом и сад
Другие языки
Другое
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Металлургия
Механика
Образование
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Туризм
Физика
Философия
Финансы
Химия
Черчение
Экология
Экономика
Электроника

Тема2: Сіткові графи



Побудуємо величини Тіm для СГ, зображеного на малюнку 1. Щоб розмістити результати обчислень в СГ, поділимо кожну його вершину (кружок) на три (сектори): у верхньому секторі запишемо номер вершини, у правому — мінімальний строк настання відповідної події, у лівому — максимальний строк настання події, який позначимо через Тіm для події і (про це буде сказано далі).

За означенням покладемо Т0m == 0. У вершину 1 входить одна стрілка і Т1m = 0 + 16 = 16. У вершину 3 входять дві стрілки: з вершин 0 i l. Тому обчислюємо дві суми: 16 + 9 = 25 і 0 + 16 = 16, вибираємо більшу 25 і записуємо в правий сектор вершини 3. У вершину 4 також входять 2 стрілки, аналогічно до попереднього знаходимо, що Т4m = 26. У вершину 2 входить одна стрілка з початкової вершини, тому Т2m = 13. У вершину 5 входять дві стрілки—3 вершин 1 і 2 знаходимо Т5m = 31. Аналогічно: Т6m = max {31 + 10; 26+ 10} = 41, Т7m = max {31+ 14; 25+11} =45, Т8m = max {41 + 18; 3І + 19; 45+10} = 59.

Отже, при даних строках виконання робіт проект повинен бути закінчений через Т8m = 59 одиниць часу (скажемо, через 59 днів). Критичний шлях, який відповідає цьому терміну (на малюнку він позначений подвійними стрілками), такий: 0→1→ 5→6 → 8.

Розглянемо тепер величини Т5m і Т7m для подій 5 і 7. Очевидно, що величину Т5m=31 збільшувати не можна, бо із збільшенням її збільшиться відповідно величина Т6m а отже, і Т8m , тобто строк виконання проекту буде порушено. Інша справа з подією 7, вона може наступити й пізніше, ніж через Т7m = 45 днів, і це не вплине на знайдений строк завершення проекту Т8m = 59 днів. Максимальний строк настання події 7, який не збільшить строку завершення всього проекту, очевидно, дорівнюватиме 59 — 10 = 49 (днів). Для настання події 7 є ре-верв часу, що дорівнює 49—45 = 4 (дні): роботи, які приводять до появи події 7, можна виконати з максимальним запізненням на 4 дні, а відповідні резерви використати на інших, напруженіших ділянках роботи. Аналогічні розрахунки можна провести стосовно всіх інших подій СГ. Це дає підставу ввести поняття максимального строку настання події, тобто такого строку, перевищення якого спричинить відповідну затримку завершення всього проекту. Позначатимемо його через ТiM для події і. Різницю Dt = ТiM Тim називають резервом часу для події і.

Варіанти завдань