Відомі два методу розрахунку параметрів мережного графа.обчислення безпосередньо на мережевому графі; аналітичний (табличний).

Розрахунок основних показників мережевої моделіможе зробити так.

• 1. Розрахунок ранніх термінів:
  • ? ранній термін початку робітвизначається тривалістю найдовшого шляху від вихідної події до початку виконання цієї роботи,
  • ? ранні терміни закінчення робіт- це найбільш ранній термін із можливих термінів закінчення роботи. Ранній термін закінчення робіт дорівнює сумі раннього термінупочатку роботи та тривалості самої роботи.
• 2.Розрахунок критичного шляху.Його тривалість окреслюється сумарний час робіт, що лежать на критичному шляху, тобто. час завершення всього комплексу робіт при найбільшому запаралелювання всіх робіт. Цей час дорівнює найбільшому з часів ранніх закінчень завершальних робіт мережевого графа. Критичний шлях проходить через події, які мають резервів часу (через критичні роботи).
• 3.Розрахунок пізніх термінів початку та закінчення робітвизначаються з можливостей граничного зсуву вправо числової осі строків виконання робіт так, щоб не було змінено час критичного шляху. Тому логічно розрахунки вести від останньої подіїдо першого та визначати спочатку час пізнього закінчення робіт, а потім розраховувати час пізнього початку робіт:
  • ?пізній термін початку робіт (ij) визначається як різниця між пізнім терміном закінчення робіт та тривалістю самої роботи,
  • ? пізній термін закінчення робітвизначається величиною шляху мінімальної тривалості, що веде до нього від завершальної події, і розраховується як різницю критичного шляху та максимальної тривалості роботи від завершальної події мережевого графікадо кінцевої події цієї роботи.
• 4. Розрахунок резервів часу.

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

• ? приватні (вільні) резерви часу.
• 1)приватний резерв часу першого видувизначається можливістю змінити пізній початок роботи ( ij)більш ранні терміни без зміни пізніх термінів закінчення безпосередньо попередніх робіт,
• 2) приватний резерв часу другого видувизначається можливістю змінити раннє закінчення роботи (ij)більш пізні терміни без зміни ранніх термінів початку безпосередньо наступних робіт; визначається різницею між раннім початком подальшої роботи та раннім закінченням даної роботи.

Розглянемо порядок розрахунку параметрів з прикладу. Мережевий графік представлений на рис. 7.5.

Мал. 7.5.

Для розрахунку параметрів скористаємося табличним методом і з метою спрощення сприйняття зведемо все в одну табл. 7.1.

Правила застосування резервів часу у мережевому плануванні.

• 1. Для того щоб повний і приватні резерви роботи (у) були рівні, необхідно й достатньо, щоб кінцева подія розглядуваної роботи була подією критичного шляху.
• 2. Якщо повний резерв (Я і]1)деякої роботи дорівнює нулю, то приватний резерв другого виду (г"ф)також дорівнює нулю. Між цими резервами завжди має місце співвідношення R(IJ) > r" ijyПовний та приватні резерви часу завжди більші або рівні нулю.
• 3. Для того щоб приватний резерв часу роботи (у) дорівнював нулю, необхідно і достатньо, щоб ця робота лежала на шляху максимальної довжини від першої події до події у.
• 4. Якщо тривалість роботи (у) збільшити величину р, тобто. р то ранній термін початку наступної роботи збільшиться на величину р - г" ("уу
• 5. Якщо тривалість роботи збільшити на величину повного резерву часу цієї роботи, то утворюється новий критичний шлях, тривалість якого дорівнює тривалості старого.
• 6. Повний резерв часу роботи (у) дорівнює сумі приватного резерву часу другого виду цієї роботи та мінімального із сукупності повних резервів усіх безпосередньо наступних робіт.

Результати розрахунку параметрів мережного графіка

Таблиця 7.1

	Тривалість	Ранні	терміни, год	Пізні терміни, год		Резерви часу, год
	робіт, год	Початок	Закінчення	Початок	Закінчення	Повні	Вільні
	Критичний шлях, ч		(роботи 1-3

7. Якщо тривалість роботи (г/) збільшити на величину р, то з'явиться новий критичний шлях, тривалість якого перевищить тривалість старого критичного шляху на величину р -

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

Розрахунок та аналіз мережевих графіків

Основні поняття та визначення

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

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

1.2. Мережевий графік (мережева модель чи мережу) - це модель всього процесу виконання даного комплексу робот, зображена як орієнтованого графа і відбиває взаємозв'язок і параметри всіх робіт.

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

Очікування - робота, що не вимагає витрат праці (та інших ресурсів), але потребує витрат часу.

Робота на мережевому графіку позначається суцільною лінією зі стрілкою.

Тривалість роботи вказується числом над стрілкою. Одиницею виміру тривалості робіт може бути день, тиждень, декада, місяць. Довжина стрілки вибирається довільно. Вона не відбиває тривалості роботи. Робота позначається шифрами початкової та кінцевої події ( ij). Тривалість роботи tij.

Залежність чи фіктивна робота - логічний зв'язок між двома чи кількома подіями, які потребують витрат ні часу, ні ресурсів. На графіку фіктивна робота позначається пунктирною стрілкою.

1.4. Подія - це результат здійснення однієї або кількох робіт, що дає можливість розпочати одну або кілька наступних робіт. Подія не має тривалості за часом, вона означає лише факт здійснення якоїсь роботи. Подія на графіку зображається кружком ( i), усередині якого вказується номер його. Подія, за якою слідує робота, називається початковою (позначається індексом – i), а якому передує робота - кінцевим ( j). У мережі існує одна вихідна подія ( J) та одне завершальне – (С).

І.5. Шлях - це будь-яка послідовність робот мережевої моделі, в якій кінцева подія кожної роботи збігається з початковою подією за нею. Шлях позначається індексом ( L). Тривалість шляху визначається сумою тривалостей робіт, що вводять у даний шлях, і позначається t(L). Розрізняють шлях повний ( L(J- C)), тобто шлях від вихідної події до завершальної, і шлях від будь-якої події до іншої L(m1 - m 2).

Критичний шлях - це повний шлях, що має максимальну тривалість з усіх можливих на даному графіку - Lкр. У мережевому графіку може бути кілька критичних шляхів. Критичний шлях визначає термін виконання цього комплексу робіт (проекту загалом).

За побудованою мережевою моделлю для кожної роботи визначається очікувана тривалість її виконання - tож, і навіть дисперсія часу виконання - .

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

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

У практиці СПУ найбільш широке застосуванняотримали такі формули для визначення очікуваної тривалості роботи та дисперсії часу її виконання.

Нижче наведено три різновиди цих формул, які відповідають варіантам індивідуальних завдань:

1-й спосіб ; ;

2-й спосіб; ;

3-й спосіб ; .

Для розрахунку за цими формулами від відповідальних виконавців одержують шляхом опитування наступні експертні оцінкичасу виконання робіт:

а(або tmin) - мінімальна (оптимістична) тривалість роботи, тобто оцінка тривалості роботи у припущенні найбільш сприятливого збігу обставин;

b(або tmax) - максимальна (песимістична) тривалість роботи, т. е. тривалість роботи у припущенні найбільш несприятливого збігу обставин;

m(або tн. в.) - найімовірніша оцінка тривалості роботи - оцінка тривалості за умов виконання роботи.

Розрахунок параметрів мережного графіка

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

1. Тривалість шляху

,

де До- кількість робіт, що входять у цей шлях.

Таким чином, тривалість шляху це сумарна тривалість робіт, що становлять цей шлях.

Тривалість критичного шляху

Ткр = t[L(J-C)max] .

Тривалість критичного шляху визначає термін настання завершальної події мережі, тобто визначає термін виконання проекту (планованого комплексу робіт) загалом.

2. Резерв часу шляху - це різниця між тривалістю критичного та даного шляху. Він показує, наскільки у сумі може бути збільшено тривалість робіт, які належать цьому шляху, не змінюючи термін виконання проектів

R(L) = Tкр - t(L) .

3. Ранній термін здійснення події - термін, необхідний для виконання всіх робіт, що передують даній події i

Тр( i) = t[L(J-i)max] або Тр( j) = max .

Ранній термін вихідної події мережі приймається рівним нулю: Тр( J) = 0 .

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

Тп( i) = Tкр - t[(i-C)max] або Тп( i) = [Тп( j)-tij]min .

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

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

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

R(i) = Tп( i) - Tp( i) = R(Lmax) .

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

6. Ранній термін початку роботи - це найраніший із можливих термінів початку роботи: tнар. н. ij) = Tp( i) .

7. Ранній термін закінчення роботи - це найраніший із можливих термінів закінчення роботи

tнар. о.( ij) = tнар. н. ij) + tij= Tp ( i) + tij .

8. Пізній термін початку роботи - найпізніший термін початку роботи, у якому не збільшується тривалість критичного шляху, т. е. термін закінчення проекту загалом

tп. н.( ij) = tп. о.( ij) - tij= Tп( j) - tij .

9. Пізній термін закінчення роботи - найпізніший термін закінчення роботи, при якому не збільшується тривалість критичного шляху, тобто термін закінчення проекту

tп. о.( ij) = Tп( j) .

Для робіт критичного шляху:

tнар. н. ij) = tп. н.( ij) та tнар. о.( ij) = tп. о.( ij) .

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

Rп( ij) = Tп( j) - Tp( i) - tij .

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

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

Повний резерв часу робіт критичного шляху дорівнює нулю, а інших робіт він позитивний.

11. Вільний резерв часу роботи - дорівнює різниці між ранніми термінами настання подій jі iза вирахуванням тривалості роботи ( ij):

R c( ij) = Tp( j) - Tp( i) - tij .

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

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

3.12. Коефіцієнт напруженості роботи використовується в мережевому плануванні для характеристики напруженості термінів виконання робіт і визначається за такою формулою:

,

де t(Lmax) - тривалість максимального шляху, що проходить через цю роботу;

t¢( Lкр) - тривалість відрізка колії t(Lmax), що збігається з критичним шляхом.

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

Величина коефіцієнта напруженості у різних робіт у мережі лежить у межах 0 Кн( ij) £ i.

Для всіх робіт критичного шляху Кн( ij) = 1.

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

Способи розрахунку параметрів мережевих графіків

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

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

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

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

Tp( J) = 0 .

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

Тр( З) = Тп ( З) .

Пізній термін події jвизначається шляхом віднімання з пізнього терміну попередньої події iтривалості роботи, що веде до цієї події j.

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

Резерв часу події iвизначається безпосередньо на мережі шляхом віднімання з величини, записаної в правому секторі події Тп( i) величини, записаної у лівому секторі - Тр( i). Знайдена величина є резервом часу здійснення події і записується в нижньому секторі події.

Усі події в мережі, за винятком подій, що належать критичному шляху, мають резерв часу. Критичний шлях визначиться в результаті виявлення всіх подій, що послідовно лежать, з резервами, рівними нулю, а його тривалість величиною пізнього (теж самого раннього) терміну звершення завершальної події.

На рис. 1 наведено розрахунок мережі безпосередньо на графіку.

Мал. 1. Розрахунок параметрів мережного графіка

2. При табличному способі розрахунку визначаються, як правило, параметри, що відносяться до робіт, а саме: ранні та пізні терміни початків та закінчень робіт, резерви часу робіт. Розрахунок параметрів у разі проводиться у таблиці за певною формою. Приклад такого розрахунку мережного графіка, зображеного на рис. 1, показаний в наведеній нижче табл. 1.

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

Таблиця 1

Розрахунок параметрів робіт мережевого графіка

i-j	Тривалість роботи, tij	Ранній початок роботи, tнар. н.	Раннє закінчення роботи, tнар. о.	Пізніше початок роботи, tп. н.	Пізніше закінчення роботи, tп. о.	Резерви часу	Коефіцієнт напруженості роботи, Дон
повний, Rп	вільний, Rз

Аналіз та оптимізація мережного графіка

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

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

Аналітична ймовірність того, що завершальна подія настане в заданий (директивний) термін або раніше за нього, визначається наступним чином:

,

де - Відповідне значення функції Ф( Z), взяте з таблиці нормального розподілу; Z- аргумент нормальної функціїрозподілу імовірності.

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

,

де ijкр - послідовність робіт, що лежать на критичному шляху;

До- кількість робіт, що становлять критичний шлях;

Дисперсія роботи лежить на критичному шляху.

приклад.Для графіка, зображеного на рис. 1, визначити ймовірність виконання проекту у заданий директивний термін, що дорівнює 8 од. часу. Раніше було визначено, що розрахунковий термін виконання проекту складає Ткр = 9 од. Припустимо, що також визначено і дисперсії робіт, що становлять критичний шлях, наприклад:

тоді і .

Користуючись таблицею значень функції Лапласа за величиною Z= - 1,7 (див. табл. 2), знаходимо шукану ймовірність РК» 0,045.

Висновок.При плануванні в системах СПУ прийнято, якщо:

0,85 < РК < 0,65 - то это считается границами допустимого риска (то есть считается нормальним становищем); при РК< 0,85 - то считается, что опасность нарушения заданного срока очень большая (неприемлема) и необходимо в этом случае и произвести повторное планирование с перераспределением ресурсов с целью минимизации срока выполнения проекта; при РК >0,65 - вважається ймовірність занадто велика, тобто роботах критичного шляху є надлишкові ресурси. І тут також проводять повторне планування з метою скорочення потрібних ресурсів.

При неможливості досягнення задовільного значення РК може знадобитися зміна заданого терміну виконання проекту. Це завдання вирішується як зворотне розглянутої вище. Задаючись бажаною величиною ймовірності РК звершення завершальної події в заданий термін, можна з вищенаведеного рівняння визначити значення функції , і, знаючи величини Ткр і визначити величину Тд.

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

Таблиця 2

Таблиця значень функції Лапласа Рк = Ф ( Z)

Розрахунок мережного графіка табличним способом проводиться у разі формулам, раніше викладеним у розділі 4 (1-10). Під час визначення параметрів мережевих моделей аналітичним способом розрахунок виконується у формі таблиці. Розглянемо особливості розрахунку мережевих моделей даним способом (приождення 1) на прикладі розрахунку параметрів мережного графіка, зображеного в завданні до даної курсової роботи(Варіант 15).

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

Розрахунок мережного графіка починається з визначення значень ранніх властивостей робіт. Раннє початок роботи 1-2 дорівнює нулю (формула 1), яке раннє закінчення за формулою 2.

Раннє початок робіт 2-6 і 2-7 (відповідно до формули 3) дорівнює ранньому закінченню роботи 1-2.

Максимальне значення раннього закінчення роботи 19-21, що дорівнює 36, визначає тривалість критичного шляху і, отже, загальну тривалістьвиконання всіх робіт за вихідною мережевою моделлю. Отримане значення раннього закінчення цієї роботи 19-21 = 36 переноситься до графи пізнього закінчення завершальної роботи 20-21.

Пізніше початок роботи 20-21 визначається відповідно до формули 5 (= 34)

Пізніше початок роботи 20-21 є пізнім закінченням попередньої роботи 15-20 (=).

Далі розрахунок пізніх параметрів виконується аналогічно, крім випадків, коли в роботи є кілька наступних робіт (наприклад, у роботи 6-9 є дві наступних - 9-10 і 9-14). У цьому випадку, відповідно до формули 4, пізнє закінчення роботи 6-9 дорівнює мінімальному значенню пізніх почав наступних робіт 9-10 і 9-14.

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

Загальний резерв часу робіт, згідно з формулами 8-9, визначається як різниця пізнього та раннього закінчення або як різниця пізнього та раннього почав відповідних робіт. Корисно визначити значення загального резерву часу обома способами збіг отриманих значень може розглядатися як додаткова перевірка. Наприклад, для роботи 6-7:

Приватний резерв часу роботи, згідно з формулою 10, визначається як різницю значення раннього початку подальшої роботи та значення раннього закінчення даної роботи. Наприклад, для роботи 6-7:

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

Графічний метод розрахунку мережевих графіків

Розрахунок мережного графіка графічним способом ведеться аналогічно до табличного методу (формули 1-10) , проте графічний або секторний спосібРозрахунок параметрів мережного графіка передбачає їх запис безпосередньо на моделі (додаток 2). При цьому кожна подія (кружок) поділяється на чотири сектори. Позначення секторів наведено на наступному малюнку:

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

Для перевірки правильності виконаних розрахунків слід переконатися, що:

• * Виявлено безперервний критичний шлях;
• * Розраховані резерви часу мають невід'ємне значення;
• * значення приватного резерву часу для всіх робіт менше або дорівнює значенню загального резерву часу для даних робіт;
• * хоча б одне значення пізнього початку робіт (роботи), що виходять з першої події, дорівнює нулю.

Основні параметри мережного графіка

До основних параметрів мережного графіка відносяться:

Критичний шлях

Резерви часу здійснення подій

Резерви часу для виконання робіт

Шлях - Послідовність робіт, в якій кінцева подія однієї роботи, збігається з початковою подією іншої.

Повний шлях - Шлях, початком якого є вихідна подія, а кінцем завершальне.

Тривалість, довжина колії, дорівнює сумі тривалостей робіт. Його складових.

Критичний шлях - Повний шлях. найбільший за тривалістю зі всіх шляхів мережного графіка від вихідної події (I) до завершального (С).

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

Повні шляхиможуть проходити поза критичним або частково збігатися з ним. Ці менші за тривалістю шляху називаються ненапруженими.Особливості в тому. Що мають резерви часу. А критичний шлях – ні. Для кожної i-ї події визначається:

t pi– ранній термін наступу– мінімальний із можливих термінів настання цієї події при заданій тривалості робіт.

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

R i – резерв часу для події– проміжок часу, який може бути відстрочено наступ цієї події без порушення терміну розробки планованого комплексу загалом. Визначається як різницю між пізнім ( t п i) та раннім ( t р i) термінами здійснення даної події.

Резерви події критичного шляху дорівнюють нулю, тому що на ньому t п i = t р i

Для кожної роботи ( t ij) визначається:

ранній термін початку (t р.н. ij)- Мінімальний з можливих термінів початку даної роботи.

ранній термін закінчення (t р.о. ij)– мінімальний із можливих термінів закінчення даної роботи, при заданій тривалості робіт

пізній термін початку (t п.н. ij)– максимальний із допустимих термінів початку цієї роботи

пізній термін закінчення (t п.о. ij)– максимальний із допустимих термінів закінчення даної роботи, за яких ще можливе виконання наступних робіт з дотриманням встановленого строку настання завершальної події.

Очевидно, ранній термін початку роботи збігається з раннім терміном настання її початкової події, а ранній термін закінчення перевищує його на тривалість роботи:

t р.н. ij = t р i

t р.о. ij = t р i + t ij

Пізній термін закінчення роботи збігається з пізнім терміном її кінцевої події, а пізній термін початку роботи менший на час виконання роботи:

t п.о. ij = t п j

t п.н. ij = t п j - t ij

Повний резерв часу для виконання роботи R nij– максимальний період часу, на який можна відкласти початок або збільшити тривалість роботи, не змінюючи встановлений термін настання завершальної події.

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

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

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

3.Розрахунок мережевих моделей

Параметри мережі для мережного графіків розраховуються графічним та табличним методом, а для складних математичним методом.

Графічно метод розрахунку здійснюється безпосередньо на графіку і застосовується у тих випадках, коли кількість подій невелика. Для цього кожен кружечок ділиться на 4 сектори.

Верхній сектор – резерв часу настання події R i

лівий сектор – ранній термін настання події t pi

правий сектор – пізній термін настання події t п i

внизу – номер події

Методика розрахунку параметрів

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

t pj = (t pi +t ij) max та записується на графік (лівий сектор події)

2) Пізні терміни події . Пізній термін здійснення завершальної події приймається рівним його ранньому терміну. Розрахунок пізніх термінів здійснення всіх інших подій ведеться у зворотній послідовності, за меншими номерами подій. Для визначення пізнього терміну звершення попередньої події i розглядаються всі роботи, що виходять з i-ї події. За кожною роботою ведеться розрахунок пізнього терміну звершення початкової події t п i ,як різниця між пізнім терміном звершення кінцевої події цієї роботи t п jта тривалістю даної роботи t ij.З отриманого значення вибирають мінімальний час пізнього терміну звершення i-го події: t п i = (t п j - t ij) minта записується у правий сектор.

3) Тривалість критичного шляху дорівнює ранньому терміну настання завершальної події.

4) Резерви часу подій . При визначенні резервів часу для подій слід відняти від числа, записаного в правому секторі даної події, число, записане в лівому секторі і поставити його у верхній сектор.

5) При визначенні повного резерву часу для роботи слід відняти від числа, записаного в правому секторі кінцевої події, число, записане в лівому секторі початкової події, та тривалість самої роботи.

6) При визначенні вільного резерву для роботи слід відняти від числа, записаного в лівому секторі кінцевої події, число, записане в лівому секторі початкової події, та тривалість самої роботи.

Вихідні дані:

Табличний метод

Коди робіт у таблиці записуються за зростанням індексу i.

Стовпці 2 та 3 заповнюються допоміжними даними: кодами попередніх та наступних робіт. Ці дані будуть потрібні для розрахунків. Якщо роботи початкові, тобто попередніх робіт немає, чи кінцеві, тобто наступних робіт немає, то відповідних графах ставляться прочерки. Попередніх і наступних робіт може бути дещо відповідно до кількості векторів, що закінчуються або починаються в цій події./

У стовпці 4 розмішають значення тривалості робіт.

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

Раннє початок робіт, які мають попередніх (у графі 2 – прочерк), може бути прийнято за 0, а то й задано якесь інше значення. Раннє закінчення роботи визначається згідно з формулою t р.о. ij = t рн ij + t ij та записується до графи 6.

Раннє початок інших можна визначити як, якщо розглядається, наприклад робота 2,5, яка має початкова подія 2, то час її раннього початку дорівнює часу раннього закінчення роботи 12, так як у неї кінцева подія 2. Значення з графи 6 переписується в графу 5 Коди попередніх робіт зазначені у графі 2. Раннє закінчення також визначається за формулою t р.о. ij = t рн ij + t ij

Якщо, у графі 2 зазначено, що певній роботі передує більше, ніж одна робота (роботі 5,6 передують роботи 2,5 і 3,5), необхідно вибрати значення раннього початку з кількох варіантів значення (9 – за часом закінчення роботи 2 ,5 чи 13 – за часом закінчення роботи 3,5). Правило вибору відповідає формулі t p . ij = (t pi + t ij) max , тобто вибирається максимальне значення (у прикладі – 16). Ранні закінчення визначаються як зазначалося вище.

Максимальне значення раннього закінчення у графі 6 відповідає значенню тривалості критичного шляху (16).

Другий прохід вздовж рядків таблиці від роботи, записаної в останньому рядку, до роботи, записаної в першому рядку, дозволяє визначити значення пізніх показників робіт. Для робіт, які не мають наступних робіт (у графі 3 – прочерк, у прикладі роботи 46, 5,6) у графу пізнього закінчення (8) записується значення критичного шляху. Для цих робіт значення пізнього початку обчислюється за формулою t п.н. ij t по ij - t ij

Пізніше закінчення інших можна визначити як, якщо розглядається, наприклад робота 3,5, яка має кінцеву подію 5, то час її пізнього закінчення дорівнює часу пізнього початку роботи 5,6, так як у неї кінцева подія 5. Значення з графи 7 переписується в графу 8. Коди наступних робіт зазначені у графі 3. Пізній початок також визначається за формулою t п.н. ij t по ij - t ij .

Якщо, у графі 3 зазначено, що певній роботі слід більше, ніж одна робота (роботі 0,1 слідують роботи 1,2 і 1,3), необхідно вибрати значення пізнього закінчення з кількох варіантів значення (3 – за часом початку роботи 1 ,3 чи 7 – за часом початку роботи 1,2), вибирається мінімальне значення (у прикладі – 3). Пізніше початок визначаються як зазначалося вище за формулою t п.н. ij t по ij - t ij .

Значення повного резерву часу (стовпець 9) розраховується за формулою

R nij = t по ij - t рн ij - t ij.

Значення вільного резерву часу (стовпець 10) розраховується за формулою

R з ij = t ро ij - t рн ij - t ij

Мережі чи мережеві моделі мають широке практичне застосування. З усієї різноманітності методів та моделей розглянемо тут лише метод критичного шляху (МКП). Мережа у разі – це графічне відображення комплексу робіт. Основними елементами мережі тут є події та роботи.
Подія - це момент завершення процесу, що відображає окремий етап виконання проекту. Комплекс робіт починається з вихідного та закінчується завершальною подією.
Робота – це тривалий у часі процес, необхідний здійснення події і, зазвичай, потребує витрат ресурсів.
Події на мережевому графіку зазвичай зображуються кружками, а роботи – дугами, що з'єднують події. Подія може відбутися лише тоді, коли закінчаться усі роботи, які йому попередні.
У мережевому графіку не повинно бути "тупикових" подій, за винятком завершального, не повинно бути подій, яким не передує хоча б одна робота (крім вихідного), не повинно бути замкнутих контурів та петель, а також паралельних робіт.
Розгляд основних понять та положень МКП вестимемо на основі наступного прикладу. Нехай задана наступна послідовність робіт зі своїми тимчасовими характеристиками: Побудуємо мережевий графік те щоб всі дуги роботи були
спрямовані зліва направо (рис.2). Над дугами проставлено тривалість робіт.

Мал. 2. Мережевий графік прикладу

Критичний шлях є шлях від початкової до кінцевої роботи, що має найбільшу тривалість. Будь-яке уповільнення виконання робіт критичного шляху неминуче призведе до зриву виконання всього комплексу робіт, тому критичному шляху і приділяється стільки уваги.
Розглянемо основні поняття, пов'язані з критичним шляхом.
Ранній термін настання події(Є).Він визначається для кожної події при русі по мережі зліва направо від початкової до кінцевої події. Для початкової події ЕТ = 0. Для інших визначається за формулою, де ЕТ 1 – ранній термін настання події i, що передує події j; t ij - Тривалість роботи (ij).

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

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

Потім розрахунки виконати у зворотному напрямку та знайти пізні терміни настання подій.
Покласти ЕТ10 = LT10. LT 9 = LT 10 - t 9,10 = 51 -11 = 40.
LT 8 = LT 10 - t 89 ​​= 51 - 9 = 42, і т.д.
Можливий інший спосіб обчислення показників – табличний.
Події відзначаються у квадратах "головної" діагоналі. Роботи відзначаються двічі у верхніх та нижніх "побічних" квадратах щодо головної діагоналі таблиці. У верхніх "побічних" квадратах таблиці номер рядка відповідає попередній події, номер стовпця – наступному. У нижніх "побічних" квадратах навпаки.
Порядок заповнення таблиці

1. Спочатку заповнюються чисельники верхніх та нижніх побічних квадратів. Вони записуються тривалості відповідних робіт.
2. Заповнюються знаменники верхніх "побічних" квадратів як суми чисельника головного квадрата та чисельника верхнього "побічного" у тому самому рядку.
3. Чисельник першого головного квадрата приймається рівним нулю, чисельники інших основних квадратів рівні максимуму знаменників верхніх " побічних " квадратів у тому стовпці.
4. Знаменник останнього головного квадрата приймається рівним чисельнику цього квадрата. Знаменники нижніх "побічних" квадратів рівні різниці знаменника головного та чисельника "нижнього" побічного в тому ж рядку.
5. Знаменники головних квадратів рівні мінімуму знаменників " нижніх " побічних у тому стовпці.
Розрахунок показників мережевого графіка

З таблиці перебувають показники графіка:
1. Ранні терміни настання подій (лічильники основних квадратів).
2. Пізні терміни настання подій (знаменники основних квадратів).
3. Резерви часу подій (різниця між знаменником та чисельником головного квадрата). У нашому випадку критичними подіями (що не мають резервів) є 1, 3, 4, 6, 7, 8, 10. Вони становлять критичний шлях. Тривалість критичного шляху дорівнює 51 (числитель чи знаменник останнього головного квадрата).
4. Ранній термін закінчення робіт (знаменники верхніх "побічних" квадратів).
5. Пізній термін настання робіт (знаменники відповідних нижніх "побічних" квадратів).

6. Загальні резерви часу робіт (різниця між знаменником головного квадрата та знаменником верхнього "побічного" у тому ж стовпці).
7. Вільні резерви часу робіт (різниця між чисельником головного квадрата та знаменником верхнього "побічного" квадрата в тому ж стовпці).

Відтворимо графік мережі, проставивши над кожною подією зліва – ранній, а праворуч – пізній терміннастання події (рис.3).

Мал. 3. Мережевий графік із тимчасовими характеристиками

Отже, критичний шлях проходить вздовж робіт 1-3-4-6-7-8-10, і його тривалість дорівнює 51.
Резерв часу події визначається як різниця між їх LT і ET. Зрозуміло, що резерви часу подій вздовж критичного шляху дорівнюють нулю. Для нашого прикладу резерв часу, наприклад, події 2 дорівнює 28–10 = 18, а події 9 дорівнює 40–36 = 4. На ці проміжки часу може бути затримано виконання відповідних робіт без ризику затримати проект загалом.
То були тимчасові характеристики подій. Розглянемо часові показники робіт. До них відносяться вільний та загальний (повний) резерви часу робіт.
Загальний резерв часу роботи (ТS) визначається із співвідношення

TS ij = LT j – ET i – t ij

і показує, скільки можна збільшити тривалість роботи за умови, що термін виконання всього комплексу робіт не зміниться.
Вільний резерв часу роботи (FS) визначається із співвідношення

FS ij = ET j – ET i – t ij

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

Некритичні роботи	Тривалість	Загальний	Вільний резерв FS
1-2	10	18	0
1-4	6	5	5
2-5	9	18	0
4-5	3	23	5
3-6	8	9	9
4-7	4	15	15
5-8	5	18	18
6-9	7	12	8
7-9	6	4	0
7-10	8	13	13
9-10	11	4	4

Завдання для контрольних завдань №4

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

Робота	(1,2)	(1,3)	(1,4)	(2,5)	(2,4)	(3,4)	(3,6)	(4,5)	(4,6)
Тривалість	5+n/3	6+n/3	7+ n/3	4+n	8+ n/3	3+n	4+n/2	10+ n/3	2+n
(4,7)	(5,7)	(5,8)	(6,7)	(6,9)	(7,8)	(7,9)	(7,10)	(8,10)	(9,10)
8+ n/3	9+n/2	10+ n/3	12+n/2	9+n	7+ n/3	5+n	9+n	11+n/2	8+ n/3