Мережевий граф та його розрахунок

У практиці дослідження операцій часто зустрічаються задачі планування різноманітних робіт. Під комплексом робіт (операцій) слід розуміти будь-яку задачу, для виконання якої необхідно здійснити велику кількість різноманітних робіт. Це може бути і будівництво споруди, корабля, літака або будь-якого іншого складного об’єкта, і розробка проекту цієї споруди, і навіть процес побудови планів реалізації проекту.

Для того, щоб створити план робіт по здійсненню великих і складних проектів, які складаються з великої кількості окремих досліджень і операцій, необхідно описати їх за допомогою математичної моделі. Таким засобом є мережева модель. Вона являє собою план виконання деякого комплексу взаємопов’язаних робіт (операцій), заданих в специфічній формі мережі, графічне зображення якої називається мережевим графом.

Головними елементами мережевого графа є події і роботи. Термін «робота» використовується в мережевому плануванні в широкому сенсі. По-перше – це дійсно робота – процес, на який потрібно витратити час і ресурси. Кожна така робота повинна бути конкретно описана.

По-друге – це чекання – процес, який не потребує затрат праці, але потребує часу (наприклад, процес сушки виробів, затвердіння бетону і т.п.)

По-третє – це залежність, або фіктивна робота. Вона показує, що можливість однієї роботи безпосередньо залежить від результатів іншої. Ця робота не потребує часу і ресурсів.

Подія – момент завершення деякого процесу (роботи), який відображає окремий етап виконання проекту. Подія може статися лише після того, як закінчаться усі роботи, що їй передують. Наступні роботи можуть початися лише тоді, коли подія здійсниться. Звідси витікає двоїстий характер події: для всіх робіт, що їй безпосередньо передують, вона є кінцевою, а для всіх робіт, які безпосередньо слідують за нею – початковою. При цьому вважають, що подія не має тривалості і здійснюється миттєво. Тому кожна подія, що включена до мережевої моделі, повинна бути повністю означена. Серед подій мережевої моделі виділяють окремо початкову і завершальну. Початкова подія не має попередніх робіт і подій, завершальна не має наступних подій і робіт. Події на мережевому графі відображаються вершинами графа, а роботи – дугами, що вказують зв’язок між роботами.

Таким чином, для побудови мережевого графа необхідно задати:

1)перелік усіх операцій проекту;

2)час, необхідний для кожної операції;

3)перелік операцій, що безпосередньо передують кожній операції.

При побудові мережевого графа необхідно виконувати ряд правил.

1В мережевому графі не повинно бути тих подій, з яких не виходить жодна робота, за винятком завершальної.

2В мережевому графі не повинно бути подій (крім початкової), якій не передує хоча б одна робота.

3В мережі не повинно бути замкнених контурів і петель, тобто шляхів, що з’єднують деякі події з ними ж самими.

4Будь-які дві події повинні бути безпосередньо зв’язані не більше, ніж однією роботою (дугою). Тобто у графі не може бути такого:

Щоб уникнути цього,рекомендується ввести фіктивну подію і відповідно фіктивну роботу. Зауважимощо фіктивна робота відображається на графі пунктирною лінією. Тобто, зробити треба так

Одна з паралельних робіт (1,2’) замикається на фіктивну подію.

5В мережі рекомендується мати одну початкову і одну завершальну подію. Якщо це не так, то можна зробити це за допомогою введення фіктивних подій і робіт

Фіктивні роботи і події необхідно вводити і в інших випадках. Один із них – відображення залежності подій, не пов’язаних з реальними роботами. Наприклад, роботи А і B можуть бути виконані незалежно одна від іншої, але за умовами виробництва робота B не може початися раніше, ніж закінчиться робота А. Ця обставина потребує введення фіктивної роботи С.

Другий випадок – неповна залежність робіт. Наприклад, робота С потребує для свого початку завершення робіт А і В, але робота D зв’язана лише з роботою В, а від роботи А не залежить. Тоді потрібно ввести фіктивну роботу Е і фіктивну подію 3’:

Введемо деякі числові характеристики мережевого графу.

Для будь-якої події позначимо через E(x) – найбільш ранній з можливих термінів настання події , а через L(x) – найпізніший термін настання події , який ще припускає своєчасне закінчення проекту.

Раніше було зауважено, що подія не може настати раніше, ніж завершаться всі попередні роботи. Якщо подія має декілька шляхів, що передують цій події, тобто шляхів від початкової події до -ї, то E(у) зручно знаходити за формулою

,

де t_xy – час виконання роботи (x,y).

Якщо подія має декілька наступних шляхів і, відповідно, декілька наступних подій , то найпізніший термін настання події зручно знаходити за формулою

.

З цих формул і означень випливає наступне:

E(x) – це довжина найдовшого шляху від початкової події до події ;

L(n)–L(x) – це довжина найдовшого шляху від події до завершальної події .

При розрахунку мережевих моделей цікавляться такими питаннями.

1 Яку максимальну кількість часу можна виділити для операції (x,y) без затримки своєчасного закінчення всього проекту? Ця кількість часу називається повним резервом часу операції (x,y) і позначається R_П(x,y). Можна довести, що повний резерв часу операції (x,y) дорівнює

R_П(x,y) = L(y)–E(x)– t_xy.

2 Яка максимальна кількість часу може бути виділена для операції (x,y) без запровадження додаткових обмежень на наступні операції? Ця кількість часу називається вільним резервом часу операції (x,y) і визначається за формулою

R_В(x,y) = E(y)–E(x)– t_xy.

3 Яка максимальна кількість часу може бути виділена на операцію (x,y) без запровадження додаткових обмежень на будь-яку операцію проекту? Ця кількість часу називається незалежним резервом часу операції (x,y) і визначається за формулою

R_Н(x,y) = E(y)–L(x)– t_xy.

Зауважимо, що має місце очевидне співвідношення

R_Н(x,y) ≤ R_В(x,y) ≤ R_П(x,y).

Далі дамо наступне означення. Операція називається критичною, якщо будь-яка затримка в її виконанні призводить до затримки виконання всього проекту (тобто повний резерв часу цієї операції дорівнює нулю).

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

Приклад. Розглянемо проект будівництва житлового будинку (за приведеною нижче таблицею).

Потрібно скласти:

1)мережевий граф, що відповідає цьому проекту;

2)знайти резерви часу для всіх операцій проекту;

3)знайти критичні операції і критичний шлях у графі.

1Мережевий граф цього проекту виглядає таким чином

2Для розрахунку резервів часу для кожної операції необхідно знайти найбільш ранній і найбільш пізній термін настання кожної операції проекту.

Е(1) = 0 – проект починається з нульового моменту часу.

Е(2) = Е(1) + 1 = 0 + 1 = 1.

Е(3) = Е(2) + 3 = 1 + 3 = 4.

Е(4) = Е(3) + 6 = 4 + 6 = 10.

Е(5) = max (Е(2)+2, Е(4)+0) = max (1+2, 10+0) = 10.

Е(6) = Е(5) + 2 = 10 + 2 = 12.

Е(7) = Е(4) + 2 = 10 + 2 = 12.

Е(8) = max (Е(4)+1, Е(5)+1, Е(6)+1) = max (10+1, 10+1, 12+1) = 13.

Е(9) = max (Е(4)+1, Е(8)+4) = max (10+1, 13+4) = 17.

Таким чином, найбільш ранній термін настання завершальної події дорівнює 17 одиниць часу.

Помітимо це на графі. Ці терміни вказані на графі як числа в квадратика х біля відповідної вершини.

Далі знайдемо найбільш пізній термін настання події.

L(9) = 17.

L(8) = L(9) – 4 = 13.

L(7) = L(8) – 0 = 13 – 0 =13.

L(6) = L(8) – 1 = 12.

L(5) = min( L(8) – 1, L(6) – 2) = min( 13 – 1, 12 – 2 ) = 10.

L(4) = min(L(9)–1, L(7)–2, L(8)–1, L(5)–0) = min(17–1, 13–2, 13–1,10) = 10.

L(3) = L(4) – 6 = 10 – 6 = 4.

L(2) = L(3) – 3 = 4 – 3 =1.

L(1) = L(2) – 1 = 1 – 1 =0.

На графі ці терміни позначимо цифрами у колах біля кожної вершини.

3Знайдемо резерви часу кожної операції проекту.

4За даними резервів часу кожної операцій можна знайти критичні операції ( ) і критичний шлях у графі.

Критичні операції – це операції (1,2), (2,3), (3,4), (4,5), (5,6), (6,8), (8,9) і відповідно це і є критичний шлях у графі.