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

Міністерство загального характеру і професійної освіти РФ.

Уральський державний университет.

Мережні графики.

Курсова робота студента групи ИС-202 Лисицын В.С.

Керівник Замятін А. П.

Єкатеринбург, 1999.

Багато великих проектів, такі як спорудження будинку, виготовлення верстата, розробка автоматизованої системи бухгалтерського обліку, і т.д., може бути розбитий на багато різноманітних операцій (робіт). Деякі з операцій можуть виконуватися одночасно, інші — лише послідовно: одна операція по закінченні інший. Наприклад, при будівництві вдома можна поєднати у часі внутрішні опоряджувальні роботи і роботи з благоустрою території, проте будувати стіни можна тільки по тому, як буде готовий фундамент.

Завдання планування робіт із здійснення деякого проекту складаються у визначенні часу можливого закінчення як проекту на цілому, і окремих робіт, їхнім виокремленням проект; у визначенні резервів часу для виконання окремих робіт; у визначенні критичних робіт, тобто таких робіт, затримка у яких веде до затримки виконання всього проекту на цілому; під управлінням ресурсами, якщо є і т.п.

Нехай певний проект W складається з робіт V1,…, Vn; кожної роботи Vk, відомо, чи може бути досить точно оцінений час виконання t (Vk). З іншого боку, кожної роботи Vk відомий, можливо порожній, список ПРЕДШ (Vk) робіт, які безпосередньо передують виконання роботи Vk. Інакше кажучи, робота Vk може, розпочати виконуватися тільки після всіх робіт, які входять у список ПРЕДШ (Vk).

Для зручності, до списку робіт проекту W додамо дві фіктивні роботи p. s і p, де робота p. s позначає початком усього проекту W. а робота p — завершення за проектом робіт W. У цьому вважатимемо, робота p. s передує усім тим роботам v (W, котрим список ПРЕДШ (v) порожній, інакше кажучи, всім таких робіт v (W між іншим ПРЕДШ (v)={s}. Поклавши далі ПРЕДШ (s) =(, ПРЕДШ (p)={v (W: v не входить ані за список ПРЕДШ (w)}, тобто вважаємо, що роботі p передують всі ті роботи, що потенційно можуть виконуватися найостаннішими. Час виконання 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).

Зрозуміло, що мережевий графік будь-якого проекту ні утримувати контурів. Справді, нехай вузли Vk1, Vk2,…, Vkr=Vk1 утворюють контур в мережі G. Це означає, робота Vk2 неспроможна розпочатися раніше, чому завершено роботу Vk1, робота Vk3 — раніше, ніж завершиться робота Vk2, і т.д., і, нарешті, Vkr = Vk1 — раніше, чому завершено роботу Vkr-1. Але тоді ніяка з робіт Vk1,…, Vkr не зможе бути виконано. А кожен реальний проект повинен допускати можливість його завершення. Отже, в мережному графіці немає контуров.

Відсутність контурів у мережі G дозволяє пронумерувати роботи проекту W в такий спосіб, щоб кожної дуги (Vi, Vj) мережі G виконувалося умова і= РВЫП (Vn+1).

Через ПВЫП (v) (відповідно ПНАЧ (v)) позначимо найбільш пізній припустимий термін виконання (початку) роботи v, тобто такою термін, який не збільшує термін Т реалізації всього проекта.

Значення можливих і допустимих термінів виконання дозволяють визначити резерви часу до виконання тій чи іншій роботи. Повний резерв (іноді її називають сумарний) часу виконання визначається по формуле:

PE3EPB (v)=ПHAЧ (v)-PHAЧ (v).

Значення PE3EPB (v) одно максимальної затримки у виконанні роботи v, не впливає на плановий термін Т. Зрозуміло, що справедливе і такий рівність: РЕЗЕРВ (v)=ПВЫП (v)-РВЫП (v).

Роботи, мають нульової резерв часу, називаються критичними. Через будь-яку таку роботу проходить певний максимальний s-p-путь у мережі G. Критичні роботи характеризуються тим, будь-яка затримка у виконанні автоматично веде до підвищення часу виконання всього проекта.

Наведемо запис алгоритму, безпосередньо вичислювального характеристики ПВЫП і ПНАЧ.

АЛГОРИТМ 2.

Данные: Мережний графік G робіт V, поставлене списками ПРЕДШ (v), v (V, плановий термін закінчення проекту — Т.

Результаты: Найбільш пізні допустимі строки виконання й конкуренції початку робіт ПВЫП (v) і ПНАЧ (v).

1. Оголосити всім робіт v (V значення найбільш пізнього терміну виконання рівним Т — значенням планового терміну закінчення проекту й вершину vp фіктивної роботи p оголосити поточної vk.

2. Присвоїти значення ПНАЧ поточної роботи vk рівним значенням ПВЫП праці та відняти час виконання поточної работы.

3. Присвоїти значенням ПВЫП (v) всім робіт v (ПРЕДШ (v) попередніх поточної роботі vk мінімальне значення з значень ПВЫП виконання роботи v чи ПНАЧ виконання поточної роботи vk, коли їх немає перейти в Крок 4.

4. Якщо є попередня вершина (робота) до поточної, то оголосити її поточної, інакше перейти в Крок 6.

5. Перейти в Крок 2.

6. Видати найбільш пізні допустимі строки виконання і міст початку робіт ПВЫП (v) і ПНАЧ (v), кінець роботи алгоритму. Проілюструємо роботу наведених алгоритмів наступних примерах:

Приклад 1: Проект гаражу для стоянки автопогрузчиков.

|n |Найменування роботи |Предшеству-ю|Время | | | |щие роботи |вы-полнения | | | | |t (vk) | |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 |.

[pic].

Рис 1. Проект гаражу для стоянки автопогрузчиков.

Знайдемо значення найбільш раннього початку будівництва і виконання проекту у вигляді алгоритму 1. Роботу алгоритму викладемо як послідовності виконуваних шагов.

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

[pic].

Рис 2. Проект складу сажі та інших матеріалів приміщення виробничого цеха.

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

[pic].

Рис 3. Проект водопостачання і зовнішньої каналізації при забудови квартали вул. Токарей-Синяева м. Екатеринбурге.

Знайдемо значення найбільш раннього початку будівництва і виконання проекту у вигляді алгоритму 1. Роботу алгоритму викладемо як послідовності виконуваних кроків. |Крок n |Дії що їх кроком | |1 |Оголошення значень РНАЧ (v) і РВЫП (v), v (V рівним нулю. | | |Поточна вершина vk=1. | |2 |Вершин попередньої першої немає. | | |Значення РНАЧ (1)=РВЫП (1)+t (1). | |3 |Поточна вершина vk=2. | |4 |Перехід в Крок 2. | |2 |РНАЧ (2)=МАКС{РВЫП (1), РНАЧ (2)}{РНАЧ (2) досяг 0} | | |РВЫП (2)=РНАЧ (2)+t (2) {РВЫП (2) досяг 16}. | |3 |Поточна вершина vk=3. | |4 |Перехід в Крок 2. | |2 |РНАЧ (3)=МАКС{РВЫП (2), РНАЧ (3)}{РНАЧ (2) досяг 16} | | |РВЫП (3)=РНАЧ (3)+t (3) {РВЫП (3) досяг 26}. | |3 |Поточна вершина vk=4. | |4 |Перехід в Крок 2. | |2 |РНАЧ (4)=МАКС{РВЫП (1), РНАЧ (4)}{РНАЧ (4) досяг 0} | | |РВЫП (4)=РНАЧ (4)+t (4) {РВЫП (4) досяг 32}. | |3 |Поточна вершина vk=5. | |4 |Перехід в Крок 2. | |2 |РНАЧ (5)=МАКС{РВЫП (3), РНАЧ (5)}{РНАЧ (5) досяг 26} | | |РВЫП (5)=РНАЧ (5)+t (5) {РВЫП (5) досяг 47}. | |3 |Поточна вершина vk=6. | |4 |Перехід в Крок 2. | |2 |РНАЧ (6)=МАКС{РВЫП (5), РНАЧ (6)}{РНАЧ (6) досяг 47} | | |РВЫП (6)=РНАЧ (6)+t (6) {РВЫП (6) досяг 52}. | |3 |Поточна вершина vk=7. | |4 |Перехід в Крок 2. | |2 |РНАЧ (7)=МАКС{РВЫП (5), РНАЧ (7)}{РНАЧ (7) досяг 47 | | |РВЫП (7)=РНАЧ (7)+t (7) {РВЫП (7) досяг 61}. | |3 |Поточна вершина vk=8. | |4 |Перехід в Крок 2. | |2 |РНАЧ (8)=МАКС{РВЫП (5), РНАЧ (8)}{РНАЧ (8) досяг 47} | | |РВЫП (8)=РНАЧ (8)+t (8) {РВЫП (8) досяг 57}. | |3 |Поточна вершина vk=9. | |4 |Перехід в Крок 2. | |2 |РНАЧ (9)=МАКС{РВЫП (6), РНАЧ (9)}{РНАЧ (9) досяг 52} | | |РВЫП (9)=РНАЧ (9)+t (9) {РВЫП (9) досяг }. | |3 |Поточна вершина vk=10. | |4 |Перехід в Крок 2. | |2 |РНАЧ (10)=МАКС{РВЫП (9), РНАЧ (10)}{РНАЧ (10) досяг 59} | | |РВЫП (10)=РНАЧ (10)+t (10) {РВЫП (10) досяг 64}. | |3 |Поточна вершина vk=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 рівним Т. | | |Поточна вершина vk=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 |Поточна вершина vk=10. | |5 |Перехід в Крок 2. | |2 |ПНАЧ (10)=ПВЫП (10)-t (10) {ПНАЧ (10) досяг 59}. | |3 |ПВЫП (9)=МИН{ПВЫП (9), ПНАЧ (10)} {ПВЫП (9) досяг 59}. | |4 |Поточна вершина vk=9. | |5 |Перехід в Крок 2. | |2 |ПНАЧ (9)=ПВЫП (9)-t (9) {ПНАЧ (9) стало ранвым 52}. | |3 |ПВЫП (6)=МИН{ПВЫП (6), ПНАЧ (9)}{ПВЫП (6) досяг 52}. | |4 |Поточна вершина vk=8. | |5 |Перехід в Крок 2. | |2 |ПНАЧ (8)=ПВЫП (8)-t (8) {ПНАЧ (8) досяг 54}. | |3 |ПВЫП (5)=МИН{ПВЫП (5), ПНАЧ (8)}{ПВЫП (5) досяг 54}. | |4 |Поточна вершина vk=7. | |5 |Перехід в Крок 2. | |2 |ПНАЧ (7)=ПВЫП (7)-t (7) {ПНАЧ (7) досяг 50}. | |3 |ПВЫП (5)=МИН{ПВЫП (5), ПНАЧ (7)}{ПВЫП (5) досяг 50} | | |ПВЫП (4)=МИН{ПВЫП (4), ПНАЧ (7)}{ПВЫП (4) досяг 50}. | |4 |Поточна вершина vk=6. | |5 |Перехід в Крок 2. | |2 |ПНАЧ (6)=ПВЫП (6)-t (6) {ПНАЧ (6) досяг 47}. | |3 |ПВЫП (5)=МИН{ПВЫП (5), ПНАЧ (6)}{ПВЫП (5) досяг 47}. | |4 |Поточна вершина vk=5. | |5 |Перехід в Крок 2. | |2 |ПНАЧ (5)=ПВЫП (5)-t (5) {ПНАЧ (5) досяг 26}. | |3 |ПВЫП (3)=МИН{ПВЫП (3), ПНАЧ (5)}{ПВЫП (3) досяг 26}. | |4 |Поточна вершина vk=4. | |5 |Перехід в Крок 2. | |2 |ПНАЧ (4)=ПВЫП (4)-t (4) {ПНАЧ (4) досяг 18}. | |3 |ПВЫП (1)=МИН{ПВЫП (1), ПНАЧ (4)}{ПВЫП (1) досяг 18}. | |4 |Поточна вершина vk=3. | |5 |Переходв Крок 2. | |2 |ПНАЧ (3)=ПВЫП (3)-t (3) {ПНАЧ (3) досяг 16}. | |3 |ПВЫП (2)=МИН{ПВЫП (2), ПНАЧ (3)}{ПВЫП (2) досяг 16}. | |4 |Поточна вершина vk=2. | |5 |Перехід в Крок 2. | |2 |ПНАЧ (2)=ПВЫП (2)-t (2) {ПНАЧ (2) досяг 0}. | |3 |ПВЫП (1)=МИН{ПВЫП (1), ПНАЧ (2)}{ПВЫП (1) досяг 0}. | |4 |Поточна вершина vk=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.