Мережеві графіки

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

Багато великих проекти, такі як будівництво будинку, виготовлення верстата, розробка автоматизованої системи бухгалтерського обліку і т.д., можна розбити на велику кількість різних операцій (робіт). Деякі з цих операцій можуть виконуватися одночасно, інші - тільки послідовно: одна операція після закінчення іншої. Наприклад, при будівництві будинку можна поєднати в часі внутрішні оздоблювальні роботи та роботи з благоустрою території, проте зводити стіни можна тільки після того, як буде готовий фундамент.
Завдання планування робіт по здійсненню деякого проекту полягають у визначенні часу можливого закінчення як всього проекту в цілому, так і окремих робіт, що утворюють проект; у визначенні резервів часу для виконання окремих робіт; у визначенні критичних робіт, тобто таких робіт, затримка у виконанні яких веде до затримки виконання всього проекту в цілому; в управлінні ресурсами, якщо такі є і т.п.
Нехай деякий проект W складається з робіт V 1 ,..., V n; для кожної роботи V k, відомо, чи може бути досить точно оцінений час її виконання t (V k). Крім того, для кожної роботи V k відомий, можливо порожній, список предше (V k) робіт, які безпосередньо передують виконанню роботи V k. Інакше кажучи, робота V k може почати виконуватися тільки після завершення всіх робіт, що входять до списку предше (V k).
Для зручності, в список робіт проекту W додамо два фіктивні роботи s і p, де робота s позначає початок всього проекту W. а робота p - завершення робіт за проектом W. При цьому будемо вважати, що робота s передує всім тим роботам vÎW, для яких список предше (v) порожній, інакше кажучи, для всіх таких робіт vÎW покладемо предше (v) = {s}. Покладемо далі предше (s) = Æ, предше (p) = {vÎW: v не входить до жодного списку предше (w)}, тобто вважаємо, що роботу p передують всі ті роботи, які можуть виконуватися самими останніми. Час виконання робіт s і p природно покласти рівними нулю: t (s) = t (p) = 0.
Весь проект W тепер зручно представити у вигляді мережі G = (V, E, c). Орієнтований зважений граф G = (V, E, c) називається мережею. Мережа може бути представлена ​​матрицею ваг дуг, масивами смежностей СЛІД або предше, або списками СЛІД [v] або пе [v]. При цьому записи в списках суміжності складаються з трьох компонент: поля назви вузла, поля ваги відповідної дуги і поля посилання на наступний запис), де мережа G = (V, E, c) визначимо за правилами:
1. V = W, тобто безліччю вузлів оголосимо безліч робіт;
2. E = {(v, w): vÎПРЕДШ (w)}, тобто відношення передування задає дуги в мережі;
3. c (v, w) = t (w).
Так побудовану мережу G часто називають мережевим графіком виконання робіт за проектом W. Легко бачити, що списки смежностей цієї мережі предше [v] збігаються із заданими для проекту списками попередніх робіт предше (v).
Зрозуміло, що мережевий графік будь-якого проекту не повинен містити контурів. Дійсно, нехай вузли V k 1, V k 2 ,..., V kr = V k 1 утворюють контур в мережі G. Це означає, що робота V k 2 не може початися раніше, ніж буде завершено роботу V k 1, робота V k 3 - раніше, ніж завершиться робота V k 2, і т.д., і, нарешті, V kr = V k 1 - раніше, ніж буде завершено роботу V kr -1. Але тоді ніяка з робіт V k 1 ,..., V kr ніколи не зможе бути виконана. А кожен реальний проект повинен допускати можливість його завершення. Отже, в мережевому графіку немає контурів.
Відсутність контурів в мережі G дозволяє пронумерувати роботи проекту W таким чином, щоб для кожної дуги (V i, V j) мережі G виконувалася умова i <j, тобто кожна дуга йде з вузла з меншим номером у вузол з великим номером. Здійснити таку нумерацію вузлів мережі G можна за допомогою алгоритму топологічного сортування. Тому надалі будемо вважати, що вузли в мережі G топологічно відсортовані.
Кінцевою метою побудови мережевої моделі є отримання інформації про можливі терміни виконання як окремих робіт, так і про можливий термін виконання всього проекту в цілому. Позначимо через PBИП (v) (відповідно PHAЧ (v)) найбільш ранній можливий термін виконання роботи v (відповідно найбільш ранній можливий термін початку роботи v). Зручно вважати, що PBИП (s) = PHAЧ (s) = 0. Оскільки почати виконувати роботу v можна тільки після того, як будуть виконані всі роботи, що передують даній роботі v, то отримаємо такі формули для розрахунку значень PHAЧ (v) і PBИП (w):
PHAЧ (v) = МАКС {PBИП (w): wÎПРЕДШ (v)},
PBИП (v) = PHAЧ (v) + t (v).
Значення PBИП (p) дає найбільш ранній можливий термін завершення всього проекту в цілому. Наведемо запис алгоритму, безпосередньо обчислює характеристики РНАЧ і РВИП.
АЛГОРИТМ 1.
Дані: Мережевий графік G робіт V, заданий списками предше (v), vÎV.
Результати: Найбільш ранні можливі терміни початку і виконання робіт РНАЧ (v), РВИП (v), vÎV.
Крок 1. Оголосити можливі ранні терміни початку РНАЧ (v) та виконання РВИП (v) робіт рівними нулю. Поточною вершиною оголосити першу вершину v k = v 1.
Крок 2. Всім вершин v попереднім поточної вершині v k, значення РНАЧ (v k) присвоїти максимум зі значень РВИП (v) і РНАЧ (v k). Значення РВИП (v k) покласти рівним значенням РНАЧ (v k) плюс час виконання самої роботи поточної вершини t (v k).
Крок 3. Якщо є наступна вершина (робота) після поточної, то оголосити її поточної вершиною v k, інакше перейти в Крок 5.
Крок 4. Повернутися в Крок 2.
Крок 5. Видати найбільш ранні можливі терміни початку і виконання робіт РНАЧ (v), РВИП (v), vÎV, кінець роботи алгоритму.
Нехай T - плановий термін виконання проекту W. Ясно, що Т має задовольняти нерівності Т> = РВИП (V n +1).
Через ПВИП (v) (відповідно ПНАЧ (v)) позначимо найбільш пізній допустимий термін виконання (початку) роботи v, то є такий термін, який не збільшує термін Т реалізації всього проекту.
Значення можливих і допустимих термінів виконання робіт дозволяють визначити резерви часу для виконання тієї чи іншої роботи. Повний резерв (іноді його називають сумарний) часу виконання робіт визначається за формулою:
PE3EPB (v) = ПHAЧ (v)-PHAЧ (v).
Значення PE3EPB (v) дорівнює максимальній затримці у виконанні роботи v, не впливає на плановий термін Т. Зрозуміло, що справедливо і така рівність: РЕЗЕРВ (v) = ПВИП (v)-РВИП (v).
Роботи, які мають нульовий резерв часу, називаються критичними. Через будь-яку таку роботу проходить деякий максимальний sp-шлях у мережі G. Критичні праці характеризуються тим, що будь-яка затримка в їх виконанні автоматично веде до збільшення часу виконання всього проекту.
Наведемо запис алгоритму, безпосередньо обчислює характеристики ПВИП і ПНАЧ.
АЛГОРИТМ 2.
Дані: Мережевий графік G робіт V, заданий списками предше (v), vÎV, плановий термін закінчення проекту - Т.
Результати: Найбільш пізні допустимі строки виконання і початку робіт ПВИП (v) і ПНАЧ (v).

Крок 1. Оголосити для всіх робіт vÎV значення найбільш пізнього строку виконання робіт рівним Т - значенням планового терміну закінчення проекту і вершину v p фіктивної роботи p оголосити поточної v k.
Крок 2. Присвоїти значення ПНАЧ поточної роботи v k рівним значенням ПВИП роботи і відняти час виконання поточної роботи.
Крок 3. Присвоїти значенням ПВИП (v) для всіх робіт vÎПРЕДШ (v) попередніх поточній роботі v k мінімальне значення із значень ПВИП виконання роботи v або ПНАЧ виконання поточної роботи v k, якщо таких немає перейти в Крок 4.
Крок 4. Якщо є попередня вершина (робота) до поточної, то оголосити її поточної, інакше перейти в Крок 6.
Крок 5. Перейти в Крок 2.
Крок 6. Видати найбільш пізні допустимі строки виконання і початку робіт ПВИП (v) і ПНАЧ (v), кінець роботи алгоритму.

Проілюструємо роботу наведених алгоритмів на наступних прикладах:
Приклад 1: Проект гаража для стоянки автонавантажувачів.
n
Найменування роботи
Предшеству ющіе роботи
Час ви-конання t (v k)
1
Початок проекту (фіктівн. робота)
Ні
0
2
Зрізування рослинного шару грунту
1
5
3
Монтаж каркаса
2
30
4
Обшивка стін профнастилом
3
15
5
Покрівля з профнастилу
3
12
6
Заповнення отвору воротами
4
5
7
Масляна забарвлення воріт і профнастилу
5,6
10
8
Щебеневе підстава під підлоги
7
3
9
Асфальтове покриття
8
3
10
Прибирання будівельного сміття після будує.
7
3
11
Кінець проекту (фіктивна робота)
9,10
0

Рис 1. Проект гаража для стоянки автонавантажувачів.
Знайдемо значення найбільш раннього початку та виконання робіт проекту за допомогою алгоритму 1. Роботу алгоритму викладемо у вигляді послідовності виконуваних кроків.
Крок n
Дії виконуються кроком
1
Оголошення значень РНАЧ (v) і РВИП (v), vÎV рівними нулю. Поточна вершина v k = 1.
2
Вершин попередньої першої немає.
РВИП (1) = РНАЧ (1) + t (1). {РНАЧ (1) стало рівним 0}
3
Поточна вершина v k = 2.
4
Перехід в Крок 2.
2
РНАЧ (2) = МАКС {РВИП (1), РНАЧ (2)} {РНАЧ (2) стало рівним 0}
РВИП (2) = РНАЧ (2) + t (2) {РВИП (2) стало рівним 5}.
3
Поточна вершина v k = 3.
4
Перехід в Крок 2.
2
РНАЧ (3) = МАКС {РВИП (2), РНАЧ (3)} {РНАЧ (3) стало рівним 5}
РВИП (3) = РНАЧ (3) + t (3) {РВИП (3) стало рівним 35}.
3
Поточна вершина v k = 4.
4
Перехід в Крок 2.
2
РНАЧ (4) = МАКС {РВИП (3), РНАЧ (4)} {РНАЧ (4) стало рівним 35}
РВИП (4) = РНАЧ (4) + t (4) {РВИП (4) стало рівним 50}.
3
Поточна вершина v k = 5.
4
Перехід в Крок 2.
2
РНАЧ (5) = МАКС {РВИП (3), РНАЧ (5)} {РНАЧ (5) стало рівним 35}
РВИП (5) = РНАЧ (5) + t (5) {РВИП (5) стало рівним 47}.
3
Поточна вершина v k = 6.
4
Перехід в Крок 2.
2
РНАЧ (6) = МАКС {РВИП (4), РНАЧ (6)} {РНАЧ (6) стало рівним 50}
РВИП (6) = РНАЧ (6) + t (6) {РВИП (6) стало рівним 55}.
3
Поточна вершина v k = 7.
4
Перехід в Крок 2.
2
РНАЧ (7) = МАКС {РВИП (5), РНАЧ (7)} {РНАЧ (7) стало рівним 47}
РНАЧ (7) = МАКС {РВИП (6), РНАЧ (7)} {РНАЧ (7) стало рівним 55}
РВИП (7) = РНАЧ (7) + t (7) {РВИП (7) стало рівним 65}.
3
Поточна вершина v k = 8.
4
Перехід в Крок 2.
2
РНАЧ (8) = МАКС {РВИП (7), РНАЧ (8)} {РНАЧ (8) стало рівним 65}
РВИП (8) = РНАЧ (8) + t (8) {РВИП (8) стало рівним 68}.
3
Поточна вершина v k = 9.
4
Перехід в Крок 2.
2
РНАЧ (9) = МАКС {РВИП (8), РНАЧ (9)} {РНАЧ (9) стало рівним 68}
РВИП (9) = РНАЧ (9) + t (9) {РВИП (9) стало рівним 71}.
3
Поточна вершина v k = 10.
4
Перехід в Крок 2.
2
РНАЧ (10) = МАКС {РВИП (7), РНАЧ (10)} {РНАЧ (10) стало рівним 65}
3
Поточна вершина v k = 11.
4
Перехід в Крок 2.
2
РНАЧ (11) = МАКС {РВИП (9), РНАЧ (11)} {РНАЧ (11) стало рівним 71}
РНАЧ (11) = МАКС {РВИП (10), РНАЧ (11)} {РНАЧ (11) стало рівним 71}
3
Перехід в Крок 5.
5
Кінець роботи алгоритму, видача значень найбільш раннього початку та виконання робіт.
Таблиця результатів роботи алгоритму.
n
1
2
3
4
5
6
7
8
9
10
11
РНАЧ (v)
0
0
5
35
35
50
55
65
68
65
71
РВИП (v)
0
5
35
50
47
55
65
68
71
68
71
Отримали, що мінімальний час, необхідний для виконання проекту одно Т = РВИП (11), Т = 71. Тепер знайдемо за допомогою алгоритму 2 значення часу найбільш пізнього початку і виконання робіт. Роботу алгоритму викладемо у вигляді послідовності виконуваних кроків.
Крок n
Дії виконуються кроком
1
Оголошення значень ПВИП (v), vÎV рівним Т.
Поточна вершина v k = 11.
2
ПНАЧ (11) = ПВИП (11)-t (11) {ПНАЧ (11) стало рівним 71}.
3
ПВИП (9) = МІН {ПВИП (9), ПНАЧ (11)} {ПВИП (9) стало рівним 71}
ПВИП (10) = МІН {ПВИП (10), ПНАЧ (11)} {ПВИП (10) стало рівним 71}
4
Поточна вершина v k = 10.
5
Перехід в Крок 2.
2
ПНАЧ (10) = ПВИП (10)-t (10) {ПНАЧ (10) стало рівним 68}
3
ПВИП (7) = МІН {ПВИП (7), ПНАЧ (10)} {ПВИП (7) стало рівним 68}
4
Поточна вершина v k = 9.
5
Перехід в Крок 2.
2
ПНАЧ (9) = ПВИП (9)-t (9) {ПНАЧ (9) стало рівним 68}
3
ПВИП (8) = МІН {ПВИП (8), ПНАЧ (9)} {ПВИП (8) стало рівним 68}
4
Поточна вершина v k = 8.
5
Перехід в Крок 2.
2
ПНАЧ (8) = ПВИП (8)-t (8) {ПНАЧ (8) стало рівним 65}
3
ПВИП (7) = МІН {ПВИП (7), ПНАЧ (8)} {ПВИП (7) стало рівним 65}
4
Поточна вершина v k = 7.
5
Перехід в Крок 2.
2
ПНАЧ (7) = ПВИП (7)-t (7) {ПНАЧ (7) стало рівним 55}
3
ПВИП (5) = МІН {ПВИП (5), ПНАЧ (7)} {ПВИП (5) стало рівним 55}
ПВИП (6) = МІН {ПВИП (6), ПНАЧ (7)} {ПВИП (6) стало рівним 55}
4
Поточна вершина v k = 6.
5
Перехід в Крок 2.
2
ПНАЧ (6) = ПВИП (6)-t (6) {ПНАЧ (6) стало рівним 50}
3
ПВИП (4) = МІН {ПВИП (4), ПНАЧ (6)} {ПВИП (5) стало рівним 50}
4
Поточна вершина v k = 5.
5
Перехід в Крок 2.
2
ПНАЧ (5) = ПВИП (5)-t (5) {ПНАЧ (5) стало рівним 43}
3
ПВИП (3) = МІН {ПВИП (3), ПНАЧ (5)} {ПВИП (3) стало рівним 43}
4
Поточна вершина v k = 4.
5
Перехід в Крок 2.
2
ПНАЧ (4) = ПВИП (4)-t (4) {ПНАЧ (4) стало рівним 35}
3
ПВИП (3) = МІН {ПВИП (3), ПНАЧ (4)} {ПВИП (3) стало рівним 35}
4
Поточна вершина v k = 3.
5
Перехід у крок 2.
2
ПНАЧ (3) = ПВИП (3)-t (3) {ПНАЧ (3) стало рівним 5}
3
ПВИП (2) = МІН {ПВИП (2), ПНАЧ (3)} {ПВИП (2) стало рівним 5}
4
Поточна вершина v k = 2.
5
Перехід в Крок 2.
2
ПНАЧ (2) = ПВИП (2)-t (2) {ПНАЧ (2) стало рівним 0}
3
ПВИП (1) = МІН {ПВИП (1), ПНАЧ (2)} {ПВИП (1) стало рівним 0}
4
Поточна вершина v k = 1.
5
Перехід в Крок 2.
2
ПНАЧ (1) = ПВИП (1)-t (1) {ПНАЧ (1) стало рівним 0}
3
Перехід в Крок 4.
4
Перехід в Крок 6.
6
Кінець роботи алгоритму, видача значень часу найбільш пізнього початку і виконання робіт.

Дамо таблицю результатів роботи алгоритму з результатами попереднього алгоритму і порахуємо резерв часу для кожної роботи за формулою PE3EPB (v) = ПНАЧ (v)-PHAЧ (v) або РЕЗЕРВ (v) = ПВИП (v)-РВИП (v).
Роботи
РНАЧ
РВИП
ПНАЧ
ПВИП
Резерв
1
0
0
0
0
0
2
0
5
0
5
0
3
5
35
5
35
0
4
35
50
35
50
0
5
35
47
43
55
8
6
50
55
50
55
0
7
55
65
55
65
0
8
65
68
65
68
0
9
68
71
68
71
0
10
65
68
68
71
3
11
71
71
71
71
0
З таблиці видно, що критичними роботами є 1, 2, 3, 4, 6, 7, 8, 9, 11, які і утворюють в мережі G критичний шлях. Розрахунки виконані при Т = 71.
Приклад 2: Проект складу сажі та інших матеріалів у приміщення виробничого цеху.
n
Найменування роботи
Предшеству ющіе роботи
Час ви-конання t (v k)
1.
Початок проекту (фіктівн. робота)
Ні
0
2.
Монтаж металоконструкцій нижньої обв'язки каркаса
1
5
3.
Пристрій бетону під стійки
2
3
4.
Монтаж стояків
3
10
5.
Монтаж опорних столиків
4
5
6.
Монтаж балок
2
7
7.
Монтаж металоконструкцій воріт
6
7
8.
Обшивка стін і покрівлі хвилястим листом
6
12
9.
Монтаж козлового крана
7
5
10.
Пристрій асфальтобетонних покриттів
8
5
11.
Кінець проекту (фіктівн. робота)
5,9,10
0

Рис 2. Проект складу сажі та інших матеріалів у приміщення виробничого цеху.
Знайдемо значення найбільш раннього початку та виконання робіт проекту за допомогою алгоритму 1. Роботу алгоритму викладемо у вигляді послідовності виконуваних кроків.
Крок n
Дії виконуються кроком
1
Оголошення значень РНАЧ (v) і РВИП (v), vÎV рівним нулю.
Поточна вершина v k = 1.
2
Вершин попередньої першої немає.
Значення РНАЧ (1) = РВИП (1) + t (1).
3
Поточна вершина v k = 2.
4
Перехід в Крок 2.
2
РНАЧ (2) = МАКС {РВИП (1), РНАЧ (2)} {РНАЧ (2) стало рівним 0}
РВИП (2) = РНАЧ (2) + t (2) {РВИП (2) стало рівним 5}.
3
Поточна вершина v k = 3.
4
Перехід в Крок 2.
2
РНАЧ (3) = МАКС {РВИП (2), РНАЧ (3)} {РНАЧ (3) стало рівним 5}
РВИП (3) = РНАЧ (3) + t (3) {РВИП (3) стало рівним 8}.
3
Поточна вершина v k = 4.
4
Перехід в Крок 2.
2
РНАЧ (4) = МАКС {РВИП (3), РНАЧ (4)} {РНАЧ (4) стало рівним 8}
РВИП (4) = РНАЧ (4) + t (4) {РВИП (4) стало рівним 18}.
3
Поточна вершина v k = 5.
4
Перехід в Крок 2.
2
РНАЧ (5) = МАКС {РВИП (4), РНАЧ (5)} {РНАЧ (5) стало рівним 18}
РВИП (5) = РНАЧ (5) + t (5) {РВИП (5) стало дорівнює 23}.
3
Поточна вершина v k = 6.
4
Перехід в Крок 2.
2
РНАЧ (6) = {РВИП (2), РНАЧ (6)} {РНАЧ (6) стало рівним 5}
РВИП (6) = РНАЧ (6) + t (6) {РВИП (6) стало рівним 12}.
3
Поточна вершина v k = 7.
4
Перехід в Крок 2.
2
РНАЧ (7) = МАКС {РВИП (6), РНАЧ (7)} {РНАЧ (7) стало рівним 12}
РВИП (7) = РНАЧ (7) + t (7) {РВИП (7) стало рівним 19}.
3
Поточна вершина v k = 8.
4
Перехід в Крок 2.
2
РНАЧ (8) = МАКС {РВИП (6), РНАЧ (8)} {РНАЧ (8) стало рівним 12}
РВИП (8) = РНАЧ (8) + t (8) {РВИП (8) стало рівним 24}.
3
Поточна вершина v k = 9.
4
Перехід в Крок 2.
2
РНАЧ (9) = МАКС {РВИП (7), РНАЧ (9)} {РНАЧ (9) стало рівним 19}
РВИП (9) = РНАЧ (9) + t (9) {РВИП (9) стало рівним 24}.
3
Поточна вершина v k = 10.
4
Перехід в Крок 2.
2
РНАЧ (10) = МАКС {РВИП (8), РНАЧ (10)} {РНАЧ (10) стало рівним 24}
РВИП (10) = РНАЧ (10) + t (10) {РВИП (10) стало рівним 29}.
3
Поточна вершина v k = 11.
4
Перехід в Крок 2.
2
РНАЧ (11) = МАКС {РВИП (9), РНАЧ (11)} {РНАЧ (11) стало рівним 24}
РНАЧ (11) = МАКС {РВИП (10), РНАЧ (10)} {РНАЧ (11) стало рівним 29}
РВИП (11) = РНАЧ (11) + t (11) {РВИП (11) стало рівним 29}.
3
Перехід в Крок 5.
5
Кінець роботи алгоритму, видача значень найбільш раннього початку та виконання робіт.
Таблиця результатів роботи алгоритму.
n
1
2
3
4
5
6
7
8
9
10
11
РНАЧ (v)
0
0
5
8
18
5
12
12
19
24
29
РВИП (v)
0
5
8
18
23
12
19
24
24
29
29
Отримали, що мінімальний час, необхідний для виконання проекту одно Т = РВИП (11), Т = 29. Тепер знайдемо за допомогою алгоритму 2 значення часу найбільш пізнього початку і виконання робіт. Роботу алгоритму викладемо у вигляді послідовності виконуваних кроків.
Крок n
Дії виконуються кроком
1
Оголошення значень ПВИП (v), vÎV рівним Т.
Поточна вершина v k = 11.
2
ПНАЧ (11) = ПВИП (11)-t (11) {ПНАЧ (11) стало рівним 29}.
3
ПВИП (9) = МІН {ПВИП (9), ПНАЧ (11)} {ПВИП (9) стало рівним 29}
ПВИП (10) = МІН {ПВИП (10), ПНАЧ (11)} {ПВИП (10) стало рівним 29}.
4
Поточна вершина v k = 10.
5
Перехід в Крок 2.
2
ПНАЧ (10) = ПВИП (10)-t (10) {ПНАЧ (10) стало рівним 24}.
3
ПВИП (8) = МІН {ПВИП (8), ПНАЧ (10)} {ПВИП (8) стало рівним 24}
4
Поточна вершина v k = 9.
5
Перехід в Крок 2.
2
ПНАЧ (9) = ПВИП (9)-t (9) {ПНАЧ (9) стало рівним 24}.
3
ПВИП (7) = МІН {ПВИП (7), ПНАЧ (9)} {ПВИП (7) стало рівним 24}.
4
Поточна вершина v k = 8.
5
Перехід в Крок 2.
2
ПНАЧ (8) = ПВИП (8)-t (8) {ПНАЧ (8) стало рівним 12}.
3
ПВИП (6) = МІН {ПВИП (6), ПНАЧ (8)} {ПВИП (6) стало рівним 12}.
4
Поточна вершина v k = 7.
5
Перехід в Крок 2.
2
ПНАЧ (7) = ПВИП (7)-t (7) {ПНАЧ (7) стало рівним 17}.
3
ПВИП (6) = МІН {ПВИП (6), ПНАЧ (7)} {ПВИП (6) стало рівним 12}.
4
Поточна вершина v k = 6.
5
Перехід в Крок 2.
2
ПНАЧ (6) = ПВИП (6)-t (6) {ПНАЧ (6) стало рівним 5}.
3
ПВИП (2) = МІН {ПВИП (2), ПНАЧ (6)} {ПВИП (2) стало рівним 5}.
4
Поточна вершина v k = 5.
5
Перехід у крок 2.
2
ПНАЧ (5) = ПВИП (5)-t (5) {ПНАЧ (5) стало рівним 24}.
3
ПВИП (4) = МІН {ПВИП (4), ПНАЧ (5)} {ПВИП (4) стало рівним 24}.
4
Поточна вершина v k = 4.
5
Перехід в Крок 2.
2
ПНАЧ (4) = ПВИП (4)-t (4) {ПНАЧ (4) стало рівним 14}.
3
ПВИП (3) = МІН {ПВИП (3), ПНАЧ (4)} {ПВИП (3) стало рівним 14}.
4
Поточна вершина v k = 3.
5
Перехід в Крок 2.
2
ПНАЧ (3) = ПВИП (3)-t (3) {ПНАЧ (3) стало рівним 11}.
3
ПВИП (2) = МІН {ПВИП (2), ПНАЧ (3)} {ПВИП (2) стало рівним 5}.
4
Поточна вершина v k = 2.
5
Перехід в Крок 2.
2
ПНАЧ (2) = ПВИП (2)-t (2) {ПНАЧ (2) стало рівним 0}.
3
ПВИП (1) = МІН {ПВИП (1), ПНАЧ (2)} {ПВИП (1) стало рівним 0}.
4
Поточна вершина v k = 1.
5
Перехід в Крок 2.
2
ПНАЧ (1) = ПВИП (1)-t (1) {ПНАЧ (1) стало рівним 0}.
3
Перехід в Крок 4.
4
Перехід в Крок 6.
6
Кінець роботи алгоритму, видача значень часу найбільш пізнього початку і виконання робіт.
Дамо таблицю результатів роботи алгоритму з результатами попереднього алгоритму і порахуємо резерв часу для кожної роботи за формулою PE3EPB (v) = ПHAЧ (v)-PHAЧ (v) або РЕЗЕРВ (v) = ПВИП (v)-РВИП (v).
Роботи
РНАЧ
РВИП
ПНАЧ
ПВИП
Резерв
1
0
0
0
0
0
2
0
5
0
5
0
3
5
8
11
14
3
4
8
18
14
24
10
5
18
23
24
29
5
6
5
12
5
12
0
7
12
19
17
24
7
8
12
24
12
24
0
9
19
24
24
29
5
10
24
29
24
29
0
11
29
29
29
29
0
З табл видно, що критичними роботами є 1, 2, 6, 8, 10, 11, які і утворюють в мережі G критичний шлях. Розрахунки виконані при Т = 29.
Приклад 3: Проект водопостачання та зовнішньої каналізації при забудови кварталу по вул. Токарів-Синяева в м. Єкатеринбурзі.
n
Найменування роботи
Предшеству ющіе роботи
Час ви-конання t (v k)
1.
Початок проекту (фіктівн. Робота)
Ні
0
2.
Розробка грунту екскаваторами з ковшем 0.5 м 3 з навантаженням на автомобілі-самоскиди.
1
16
3.
Зачистка дна і стінок з викідкой грунту.
2
10
4.
Монтаж водопровідних колодязів
1
32
5.
Монтаж плит перекриттів з легкого бетону.
3
21
6.
Пробивання в бетонних стінах і підлогах отворів.
5
5
7.
Обклеювання плит руберойдом та гідроізоляційні на нафтобітуму в 1 шар.
4,5
14
8.
Закладення сальників при проході труб через фундаменти або стіни підвалів.
5
10
9.
Монтаж скоб.
6
7
10.
Улаштування стяжок цементних.
9
5
11.
Кінець проекту. (Фіктівн. Робота)
7,8,10
0

Рис 3. Проект водопостачання та зовнішньої каналізації при забудови кварталу по вул. Токарів-Синяева в м. Єкатеринбурзі.
Знайдемо значення найбільш раннього початку та виконання робіт проекту за допомогою алгоритму 1. Роботу алгоритму викладемо у вигляді послідовності виконуваних кроків.
Крок n
Дії виконуються кроком
1
Оголошення значень РНАЧ (v) і РВИП (v), vÎV рівним нулю.
Поточна вершина v k = 1.
2
Вершин попередньої першої немає.
Значення РНАЧ (1) = РВИП (1) + t (1).
3
Поточна вершина v k = 2.
4
Перехід в Крок 2.
2
РНАЧ (2) = МАКС {РВИП (1), РНАЧ (2)} {РНАЧ (2) стало рівним 0}
РВИП (2) = РНАЧ (2) + t (2) {РВИП (2) стало рівним 16}.
3
Поточна вершина v k = 3.
4
Перехід в Крок 2.
2
РНАЧ (3) = МАКС {РВИП (2), РНАЧ (3)} {РНАЧ (2) стало рівним 16}
РВИП (3) = РНАЧ (3) + t (3) {РВИП (3) стало рівним 26}.
3
Поточна вершина v k = 4.
4
Перехід в Крок 2.
2
РНАЧ (4) = МАКС {РВИП (1), РНАЧ (4)} {РНАЧ (4) стало рівним 0}
РВИП (4) = РНАЧ (4) + t (4) {РВИП (4) стало рівним 32}.
3
Поточна вершина v k = 5.
4
Перехід в Крок 2.
2
РНАЧ (5) = МАКС {РВИП (3), РНАЧ (5)} {РНАЧ (5) стало рівним 26}
РВИП (5) = РНАЧ (5) + t (5) {РВИП (5) стало рівним 47}.
3
Поточна вершина v k = 6.
4
Перехід в Крок 2.
2
РНАЧ (6) = МАКС {РВИП (5), РНАЧ (6)} {РНАЧ (6) стало рівним 47}
РВИП (6) = РНАЧ (6) + t (6) {РВИП (6) стало рівним 52}.
3
Поточна вершина v k = 7.
4
Перехід в Крок 2.
2
РНАЧ (7) = МАКС {РВИП (5), РНАЧ (7)} {РНАЧ (7) стало рівним 47
РВИП (7) = РНАЧ (7) + t (7) {РВИП (7) стало рівним 61}.
3
Поточна вершина v k = 8.
4
Перехід в Крок 2.
2
РНАЧ (8) = МАКС {РВИП (5), РНАЧ (8)} {РНАЧ (8) стало рівним 47}
РВИП (8) = РНАЧ (8) + t (8) {РВИП (8) стало рівним 57}.
3
Поточна вершина v k = 9.
4
Перехід в Крок 2.
2
РНАЧ (9) = МАКС {РВИП (6), РНАЧ (9)} {РНАЧ (9) стало рівним 52}
РВИП (9) = РНАЧ (9) + t (9) {РВИП (9) стало рівним}.
3
Поточна вершина v k = 10.
4
Перехід в Крок 2.
2
РНАЧ (10) = МАКС {РВИП (9), РНАЧ (10)} {РНАЧ (10) стало рівним 59}
РВИП (10) = РНАЧ (10) + t (10) {РВИП (10) стало рівним 64}.
3
Поточна вершина v k = 11.
4
Перехід в Крок 2.
2
РНАЧ (11) = МАКС {РВИП (7), РНАЧ (11)} {РНАЧ (11) стало рівним 61}
РНАЧ (11) = МАКС {РВИП (8), РНАЧ (11)} {РНАЧ (11) стало рвним 61}
РНАЧ (11) = МАКС {РВИП (10), РНАЧ (11)} {РНАЧ (11) стало рівним 64}
РВИП (11) = РНАЧ (11) + t (11) {РВИП (11) стало рівним 64}.
3
Перехід в Крок 5.
5
Кінець роботи алгоритму, видача значень найбільш раннього початку та виконання робіт.
Таблиця результатів роботи алгоритму.
n
1
2
3
4
5
6
7
8
9
10
11
РНАЧ (v)
0
0
16
0
26
47
47
47
52
59
64
РВИП (v)
0
16
26
32
47
52
61
57
59
64
64
Отримали, що мінімальний час, необхідний для виконання проекту одно Т = РВИП (11), Т = 64. Тепер знайдемо за допомогою алгоритму 2 значення часу найбільш пізнього початку і виконання робіт. Роботу алгоритму викладемо у вигляді послідовності виконуваних кроків.
Крок n
Дії виконуються кроком
1
Оголошення значень ПВИП (v), vÎV рівним Т.
Поточна вершина v k = 11.
2
ПНАЧ (11) = ПВИП (11)-t (11) {ПНАЧ (11) стало рівним 64}.
3
ПВИП (7) = МІН {ПВИП (7), ПНАЧ (11)} {ПВИП (7) стало рівним 64}
ПВИП (8) = МІН {ПВИП (8), ПНАЧ (11)} {ПВИП (8) стало рівним 64}
ПВИП (10) = МІН {ПВИП (10), ПНАЧ (10)} {ПВИП (9) стало рівним 64}.
4
Поточна вершина v k = 10.
5
Перехід в Крок 2.
2
ПНАЧ (10) = ПВИП (10)-t (10) {ПНАЧ (10) стало рівним 59}.
3
ПВИП (9) = МІН {ПВИП (9), ПНАЧ (10)} {ПВИП (9) стало рівним 59}.
4
Поточна вершина v k = 9.
5
Перехід в Крок 2.
2
ПНАЧ (9) = ПВИП (9)-t (9) {ПНАЧ (9) стало Ранвей 52}.
3
ПВИП (6) = МІН {ПВИП (6), ПНАЧ (9)} {ПВИП (6) стало рівним 52}.
4
Поточна вершина v k = 8.
5
Перехід в Крок 2.
2
ПНАЧ (8) = ПВИП (8)-t (8) {ПНАЧ (8) стало рівним 54}.
3
ПВИП (5) = МІН {ПВИП (5), ПНАЧ (8)} {ПВИП (5) стало рівним 54}.
4
Поточна вершина v k = 7.
5
Перехід в Крок 2.
2
ПНАЧ (7) = ПВИП (7)-t (7) {ПНАЧ (7) стало рівним 50}.
3
ПВИП (5) = МІН {ПВИП (5), ПНАЧ (7)} {ПВИП (5) стало рівним 50}
ПВИП (4) = МІН {ПВИП (4), ПНАЧ (7)} {ПВИП (4) стало рівним 50}.
4
Поточна вершина v k = 6.
5
Перехід в Крок 2.
2
ПНАЧ (6) = ПВИП (6)-t (6) {ПНАЧ (6) стало рівним 47}.
3
ПВИП (5) = МІН {ПВИП (5), ПНАЧ (6)} {ПВИП (5) стало рівним 47}.
4
Поточна вершина v k = 5.
5
Перехід в Крок 2.
2
ПНАЧ (5) = ПВИП (5)-t (5) {ПНАЧ (5) стало рівним 26}.
3
ПВИП (3) = МІН {ПВИП (3), ПНАЧ (5)} {ПВИП (3) стало рівним 26}.
4
Поточна вершина v k = 4.
5
Перехід в Крок 2.
2
ПНАЧ (4) = ПВИП (4)-t (4) {ПНАЧ (4) стало рівним 18}.
3
ПВИП (1) = МІН {ПВИП (1), ПНАЧ (4)} {ПВИП (1) стало рівним 18}.
4
Поточна вершина v k = 3.
5
Переходв Крок 2.
2
ПНАЧ (3) = ПВИП (3)-t (3) {ПНАЧ (3) стало рівним 16}.
3
ПВИП (2) = МІН {ПВИП (2), ПНАЧ (3)} {ПВИП (2) стало рівним 16}.
4
Поточна вершина v k = 2.
5
Перехід в Крок 2.
2
ПНАЧ (2) = ПВИП (2)-t (2) {ПНАЧ (2) стало рівним 0}.
3
ПВИП (1) = МІН {ПВИП (1), ПНАЧ (2)} {ПВИП (1) стало рівним 0}.
4
Поточна вершина v k = 1.
5
Перехід в Крок 2.
2
ПНАЧ (1) = ПВИП (1)-t (1) {ПНАЧ (1) стало рівним 0}.
3
Перехід в Крок 4.
4
Перехід в Крок 6.
6
Кінець роботи алгоритму, видача значень часу найбільш пізнього початку і виконання робіт.
Дамо таблицю результатів роботи алгоритму з результатами попереднього алгоритму і порахуємо резерв часу для кожної роботи за формулою PE3EPB (v) = ПHAЧ (v)-PHAЧ (v) або РЕЗЕРВ (v) = ПВИП (v)-РВИП (v).
Роботи
РНАЧ
РВИП
ПНАЧ
ПВИП
Резерв
1
0
0
0
0
0
2
0
16
0
16
0
3
16
26
16
26
0
4
0
32
18
50
32
5
26
47
26
47
0
6
47
52
47
52
0
7
47
61
50
64
3
8
47
57
54
64
10
9
52
59
52
59
0
10
59
64
59
64
0
11
59
64
64
64
0
З таблиці видно, що критичними роботами є 1, 2, 3, 5, 6, 9, 10, 11, які і утворюють в мережі G критичний шлях. Розрахунки виконані при Т = 64.
Література:
1. Асанов М. О. «Дискретна оптимізація», УралНАУКА, Єкатеринбург 1998.
Додати в блог або на сайт

Цей текст може містити помилки.

Програмування, комп'ютери, інформатика і кібернетика | Курсова
311.4кб. | скачати


Схожі роботи:
Мережеві можливості Windows 9X за версіями Основні мережеві програми і їх призначення
Мережеві моделі
Мережеві адаптери
Мережеві комунікації
Мережеві принтери
Мережеві можливості ОС Windows
Мережеві операційні системи
Мережеві сканери та аналізатори
Мережеві адаптери карти
© Усі права захищені
написати до нас