Курсова робота
по предмету: В«Математичні методиВ»
на тему: В«Основні часові параметри мережевих графіків і їх розрахункиВ»
2009
Теорія графів - область дискретної математики, що займається дослідженням і вирішенням різноманітних проблем, пов'язаних з об'єктом, званим графом. Граф визначається завданням двох множин. Перше - X - множина вершин графа. Елементи цього графа можна зобразити у вигляді точок площини або простору. Друге - U - безліч пар елементів з Х. Кожен елемент множини U вказує пару вершин, між якими існує зв'язок; вона може зображуватися лінією, що з'єднує відповідні вершини графа. При такому зображенні вимагається, щоб лінія проходила тільки через вершини, які вона з'єднує, і щоб різні лінії могли перетинатися тільки у вершинах. Іноді в парах складових безліч U, вказується, яка вершина є першою. У цьому випадку елементи множини U називаються дугами графа (X, U), а сам граф - орієнтованим. Якщо орієнтація не вказана, то елементи U називаються ребрами, а граф (X, U) - неорієнтованим графом або про сто графом. Елемент U, який вказує на зв'язок вершини з нею самої, називається петлею.
Граф (X, U) називається кінцевим, якщо множини X і U складаються з кінцевого числа елементів. В іншому випадку граф (X, U) називається нескінченним.
Основні часові параметри мережевих графіків і їх розрахунки
Найважливішим параметром мережевого графіка є критичний шлях. Шляхом в мережевому графіку називається будь-яка послідовність робіт (стрілок), що зв'язує небудь дві події. При цьому шляхи, що зв'язують вихідні і завершальні події мережі, вважається повними, а всі інші шляхи - неповними. Кожен шлях характеризується своєю тривалістю, що дорівнює сумі тривалостей складових його робіт.
-->p>
Повний шлях, що має найбільшу тривалість, називається критичним шляхом.
Роботи та події, що лежать на критичному шляху, також називаються критичними роботами і подіями. Повна тривалість виконання всього комплексу робіт, відображеного мережевим графіком, дорівнює тривалості критичного шляху. На графіку критичний шлях зазвичай виділяється жирною лінією.
Для кожної події, включеного в мережевий графік, розраховуються такі показники:
Ранній термін настання події, що характеризує найбільш ранній з можливих термінів здійснення того чи іншої події;
Пізній термін настання подій, що характеризує найбільш пізній з допустимих строків того чи іншого події. Якщо встановлений термін настання завершального події, що є результатом всього комплексу робіт, що проводяться, то кожне проміжна подія має настати не пізніше визначеного терміну. Цей термін і є гранично допускаються строком настання події;
Резерв часу настання подій, який визначається як різниця між пізнім і раннім термінами настання події.
Знаючи зазначені показники для подій, для кожної з робіт складеного графіка можна визначити наступні параметри: ранній термін початку роботи, який визначається моментом настання початкового ної роботи події в його ранній термін; пізній термін початку роботи, обумовлений моментом настання кінцевого для даної роботи події в його пізній термін за вирахуванням тривалості роботи (тимчасової оцінки); ранній термін закінчення роботи і, нарешті, пізній термін закінчення роботи, тобто гранично допустимий термін закінчення.
Розрахунок основних тимчасових параметрів проводиться за відповідними формулами.
Ранній термін настання будь-якого подальшого події (j-го) визначається величиною шляху максимальної тривалості, ведучого до нього від вихідного події. Вибір цієї тривалості може бути здійснений за наступною формулою:
Виробляючи розрахунки, зручно приймати, що ранній термін настання вихідного (1-го) події дорівнює нулю, тобто Тоді
Оскільки до події 2 йде тільки один шлях від події 1, то вибирати максимальні тривалості шляхів не доводиться:. Сказане тільки що відноситься і до даного розрахунку. Поїному йде справа, коли ми підійшли до події 4. До нього ведуть два шляхи: прямий від події 1 і опосередкований подією 2. Тут треба використовувати у всій повноті нижченаведену формулу:
Маємо:
Значить, 4-е подія зможе наступити на 14-й день від загального початку робіт (але не через 7 днів, як це може здатися спочатку).
Продовжуємо розрахунки. Черговим є подія 5. До нього ведуть два шляхи: від події 4 та від події 3. Застосовуємо формулу
Аналогічно робимо і з розрахунками ранніх строків настання подій 6 і 7:
Потім розраховуємо. До події 8 ведуть чотири шляхи, тому доведеться мати справу з вибором максимальної величини з чотирьох доданків.
Отже, завершальне (8-е) подія може наступити лише на 36-й день від початку виконання всього комплексу робіт.
Пізній термін настання будь-якого попереднього (i-го) події визначається величиною шляху мінімальної тривалості, ведучого до нього від завершального події. Вибір цієї тривалості може бути здійснений за формулою
.
Приймемо найпізніший термін настання (8-го) події, рівний 36 одиницям часу, оскільки ранній термін (За попередніми розрахунками) був дорівнює цьому числу.
Визначимо цей показник для наступних подій:
При розрахунках подальших подій 5,4 і т. д., до яких ідуть кілька шляхів, необхідно повною ступеня використовувати вищенаведену формулу
;
;
В кінці розраховуємо, до якого ведуть три шляхи, і, як в попередніх розрахунках, вибираємо мінімальний шлях
Отриманий результат говорить про те, що розрахунки проведені правильно.
На основі цих розрахунків визначаються резерви часу для подій як різниця між самим пізнім і найбільш раннім термінами їх настання. Резерви часу для подій показують, на який гранично допустимий період часу може затриматися наступ того чи іншої події, не викликаючи при цьому небезпеки зриву наступу завершального події. Зрозуміло, події, що знаходяться на критичному шляху, не мають резервів часу. Маємо:
;
;
;
;
;
;
;
;
Отже, критичний шлях проходить від 1-го до 8-го події через 2 -, 4 - і 6-е події, у яких резерви часу дорівнюють нулю.
Звернемо увагу на той факт, що якщо дві події, початкове і кінцеве, для даної роботи критичні, то це ще не означає, що зв'язує їх робота знаходиться на критичному шляху. На аналізованому графіку 2-е і 6-е події - критичні, а робота (2,6) не лежить на критичному шляху. Це обумовлено тим, що зазначені події пов'язані між собою ще одним шляхом більшої тривалості, в нашому прикладі роботами (2,4) і (4,6). Слід також сказати і про роботу (4,8), зв'язує два критичних події - 4-е і 8-е.
Роботи також можуть розташовувати резервами часу для їх виконання. При цьому розрізняють наступні різновиди резервів часу.
Повний резерв часу - це максимально можливий запас часу для виконання даної роботи понад тривалості самої роботи за умови, що в результаті такої затримки кінцеве для даної роботи подія настане не пізніше ніж у свій пізній термін. Іншими словами, це різниця між пізнім терміном здійснення кінцевого події і сумою раннього терміну настання початкового події та тривалості роботи. Отже, повні резерви часу для робіт можна обчислити за формулою
, де - повний резерв часу для (i, j)-й роботи.
Наприклад, повний резерв часу для роботи (3,5) складе
.
Значить, робота (3,5) може бути виконана не за сім днів, а за 27 днів (20 + 7) без затримки виконання всього комплексу робіт, передбачених мережевим графіком. Звичайно, це граничний максимальний термін, бо затримка у виконанні роботи хоча б на один день загрожує зривом терміну настання завершального (8-го в нашому прикладі) події.
...
