Реферат на тему:

Дослідження операцій. Задачі упорядкування та координації. Сітьове
планування та керування

План :

Зміст та сфери використання сітьових методів планування та управління.

Елементи сітьового графіка, методика його побудови.

Управління комплексом робіт за допомогою сітьового графіка.

Після вивчення теми студенти повинні

знати: структуру СМО та способи визначення її операційних
характеристик; особливості різних класів СМО та способи їх
аналізу

вміти будувати моделі СМО для реальних систем та їх
досліджувати; розраховувати операційні характеристики для
декількох варіантів СМО; каналізувати СМО на чутливість до
зміни значень її параметрів.

КЛЮЧОВІ ПОНЯТТЯ ТА ТЕРМІНИ

граф

дуга

ребра

орграф (орієнтований граф)

завантажений граф

маршрут

простий ланцюг

цикл

шлях

модель мережі

графік мережі

робота

фіктивна робота

подія

вихідна подія

завершальна подія

початкова та кінцева події

ПУМ (планування та управління мереж)

завершений шлях

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

максимальний шлях

коефіцієнт напруженості

1.Зміст та сфери використання сітьових методів планування та управління.

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

Методи планування та управління мережею забезпечують:

• складання календарного плану виконання певного комплексу робіт;

• оцінку необхідних трудових, матеріальних та фінансових ресурсів,
затрат часу;

• контроль комплексу робіт з прогнозуванням і запобіганням можливих
зривів при виконанні робіт;

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

• оцінку дієздатності та якості системи стосовно певних критеріїв.

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

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

2.Елементи сітьового графіка, методика його побудови.

Основні поняття теорії графів

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

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

Приклади графів.

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

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

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

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

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

Простим ланцюгом називається маршрут, в якому вершини не повторюються.
Будемо користуватися лише простими ланцюгами, опускаючи слово простий.

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

Цикл — це ланцюг, початкова вершина якого співпадає з кінцевою.

Шляхом називається орієнтований ланцюг. Отже, поняття “шлях”стосується
лише орієнтованих графів.

а)

б)

Рис. 1. Схема використання обладнання при запуску бензинового двигуна
внутрішнього згоряння (а) та її граф (б).

Побудова правильної нумерації вершин графу

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

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

I. Умовно виділимо всі дуги, які виходять з початкової вершини, назвемо
її вершиною нульового рангу та дамо їй номер “00” (V00). Тепер
розглянемо вершини, в які не заходять інші дуги, окрім викреслених. Такі
вершини назвемо вершинами 1-го рангу та пронумеруємо їх у довільному
порядку, дотримуючись неперервності в нумерації. За цих умов кожній
вершині будемо надавати два індекси: перший -ранг вершини, другий — її
порядковий номер серед множини вершин однакового рангу. На графові рис.
2 маємо одну вершину “11”(V11) першого рангу.

II. Умовно викреслимо всі дуги, які виходять з вершин 1-го рангу.
Вершини, в які не заходять інші дуги, окрім уже позначених, назвемо
вершинами 2-го рангу та пронумеруємо їх у довільній послідовності,
зберігаючи неперервність в нумерації стосовно раніше використаних чисел
натурального ряду. Для графу рис. 2 це вершини “22”(V22) та «23» (V23).

V11 4 V45

2

3 3 V23 2

2 1 V56

00

1 2 5

V22

V34

3

Рис.2.

Припустимо, пройдений n-1 етап і визначено вершини (n-1)-го рангу.
Викреслимо всі дуги, які виходять з вершин (n-1)-го рангу. Розглянемо
всі вершини, в яких закінчуються викреслені на цьому етапі дуги.
Вершини, в які заходять лише дуги, визначені на (n-1)-му етапі,
утворюють множину вершин n-го рангу. Пронумеруємо їх у довільному
порядку, використовуючи неперервно числа натурального ряду, починаючи з
найменшого, яке не було використане для нумерації вершин (п-1)-го рангу.
Алгоритм завершується по досягненні кінцевої вершини. Для нашого
прикладу (рис. 2) це вершина “56”( V56), де індекс 5 означає ранг
кінцевої вершини, а індекс 6 — її порядковий номер. Виконавши правильно
нумерацію вершин графу, в подальшому індекс рангу вершини можна не
вказувати. Алгоритм правильної нумерації вершин графу може бути
представлений по-іншому .

Алгоритм пошуку найкоротшого шляху мережі (графу)

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

Розглянемо реалізацію алгоритму на прикладі графу, зображеного на рис.
2. Згідно з алгоритмом будемо рухатися від кінцевої вершини V56 до
початкової V00, крокуючи послідовно від вершин більш високого рангу до
вершин меншого рангу. У кружках, які зображають вершини графу, будемо
записувати найкоротшу віддаль від вершини (n-l)-ro рангу до кінцевої
вершини. Одночасно найкоротший шлях від кожної вершини до кінцевої
будемо відмічати подвійною стрілкою. У кружку останньої кінцевої вершини
V56 записуємо “0”, бо звідси виконуємо відлік віддалі.

Потім переходимо до вершини 4-го рангу — в прикладі це вершина V45. Від
цієї вершини в кінцеву маємо лише один шлях: (V45, V56) , його довжина
дорівнює двом одиницям виміру, її і запишемо у вершині V45, а відповідну
дугу позначимо на графові подвійною стрілкою.

Переходимо до вершини 3-го рангу V34. З цієї вершини в кінцеву маємо два
шляхи: (V34 , V56) та

(V34 , V45 ,V56). Найкоротшим є останній. Його одержуємо, додаючи дугу
(V34, V45) до вже побудованого шляху (V45, V56 ) та відмічаючи шлях
(V34, V45 ) подвійною стрілкою.

Довжина шляху (V34 , V45 ,V56) дорівнює 1+2=3 , записуємо це число у
вершині V34 . Шлях (V34 , V56 ) при наступних пошуках не використовуємо,
тому що з вершини 3-го рангу вже знайдено найкоротший шлях до кінцевої
вершини.

Переходимо до вершин 2-го рангу: V22 , V23. Розглянемо шляхи, якими
можна перейти від цих вершин до вершин вищого рангу. З вершини V22 до
вершини вищого рангу можна потрапити лише по дузі (V22, V34). її
відмічаємо подвійною лінією та записуємо в V22 число 3+3=6 — найкоротша
віддаль від V22 до V56 , враховуючи, що найкоротша віддаль від V34 до
V56 уже визначена.

З вершини V23 можна потрапити в вершини вищого рангу або по дузі (V23,
V34), або по дузі (V23, V45 ). Обчислюємо шлях від V23 до V56 за умов
руху із V23 по названим дугам. Шлях (V23 ,V45, V56) має довжину 2+2=4 ,
шлях (V23, V34, V56) 2+3=5 . Порівнявши названі величини, приходимо до
висновку, що найкоротшим шляхом від V23 до V56 буде шлях (V23, V45,
V56), отже дугу (V23 , V45) позначаємо подвійною лінією, а в вершині V23
ставимо “4”.

Розглянувши всі вершини 2-го рангу, переходимо до вершин 1-го рангу. У
наведеному прикладі це лише V11 , з якої виходять дуги (V11 , V22 ),
(V11, V23) та (V11 , V45). Розглядаємо й оцінюємо шляхи, які починаються
цими дугами та закінчуються в V56 : (V11, V45 , V56 ), (V45, V23 , V45 ,
V56 ) та (V11 , V22 , V34 , V45 , V56 ). Решту шляхів, що починаються
цими дугами й закінчуються в V56 , не розглядаємо, бо вони мають дуги,
які не позначені подвійною стрілкою (шляхи з непозначеними подвійною
стрілкою дугами не можуть бути найкоротшими до кінцевої вершини).
Обчислюємо довжину кожного з трьох названих шляхів та вибираємо
найкоротший: (V11,V45 ,V56 ). Довжину цього шляху 4+2=6 записуємо в V11
, позначивши подвійною лінією дугу (V11 ,V45). Отже, найкоротші шляхи як
від V11 , так і від V22 до V56 мають однакову довжину — шість одиниць.

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

Якщо завантаження графу рис. 2 тлумачити не як відстані, а як тарифи
перевезень вантажу, то ми знайшли шлях найменшої вартості перевезення з
вершини V00 до V56 .

Зауваження 1. Використання описаного алгоритму дає можливість визначити
найкоротший шлях та найменшу відстань від довільної вершини графу до
кінцевої: найменша відстань записується в кружках, які зображають
вершини, а найкоротший шлях відмічається на графові подвійною лінією.
Наприклад (рис. 2): найкоротший шлях з вершини V11 до V56 має довжину
шість одиниць і проходить через вершини (V11 , V45 , V56), з вершини V22
— теж шість одиниць і проходить через вершини (V22 , V34 , V45 , V56).

Зауваження 2. Описаний алгоритм побудований на так званому “принципі
оптимальності”: якщо найкоротший шлях від початкової вершини до кінцевої
проходить через деяку вершину Vi , то відрізок цього шляху від вершини
Vi , до кінцевої вершини є найкоротшим серед усіх шляхів, які з’єднують
вершину Vi , та кінцеву. Так, у розглянутому прикладі найкоротший шлях
від V00 до V56 (V00 ,V22 ,V34 ,V45 ,V56 ) як свої складові має
найкоротші шляхи до кінцевої вершини від усіх вершин, через які він
проходить.

Побудова графу планування та управління мережею (ПУМ)

Розглянемо методи планування та управління при реалізації проектів
створення складних систем, якими можуть бути як виробничі, так і
науково-дослідні системи. Щоб скласти план виконання робіт за такими
проектами, необхідно зобразити його деякою математичною моделлю, яка
називається моделлю мережі і є відображенням певних послідовностей
виконання робіт і взаємозв’язків між ними з урахуванням необхідних
матеріальних ресурсів. Отже, під моделлю мережі будемо розуміти план
виконання комплексу взаємопов’язаних робіт, представлений у специфічній
формі графу, який називається графіком мережі.

Основними елементами графіка мережі є поняття події та роботи.

Термін робота використовується в системі планування та управління мереж
(ПУМ) у широкому розумінні.

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

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

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

ph

&

&

i

?

i

?

o

ue

??

c

¤

i

o

o

th

® ° ?

?

i

o

??

???

?

??

??

??

???? ???

ph. Подія може бути як результатом однієї роботи, так і підсумковим
результатом декількох робіт. Подія може відбутися лише тоді, коли будуть
виконані всі роботи, які передують події. Наступні роботи можуть
розпочатися лише за умови, що відповідна подія відбулася. Отже, для всіх
безпосередньо попередніх робіт подія фіксує момент їх закінчення, а для
безпосередньо наступних — початок.

Серед подій ПУМ виділяють вихідну та завершальні події.

Вихідна подія не має попередніх робіт та подій стосовно досліджуваного в
моделі комплексу робіт.

Завершальна подія не може мати наступних робіт і подій.

Події, які визначають термін виконання певної роботи, назвемо початковою
та кінцевою.

Подію на графові ПУМ зображають кружками (вершини графу), а роботи
-орієнтованими угами, які показують, які роботи необхідно виконати, щоб
відбулася певна подія, та які роботи можна виконувати, якщо подія
відбувалася. Отже, будь-яка робота на графові ПУМ позначається двома
подіями, між якими вона знаходиться. Подія ж може належати кільком
роботам, які можна розпочинати, якщо відповідна подія відбулася.
Фіктивні роботи на графові ПУМ позначаються штриховою лінією без
зазначення часу. На рис. 3 наведено граф, який узагальнено описує
комплекс будівельних робіт при спорудженні виробничого корпусу.

І на початку, і по завершенні реальної роботи повинна бути лише одна
подія, бо роботи ідентифікуються за номерами подій, між якими
виконуються, тому на графові рис.3 введено фіктивні роботи (3; 4) та (5;
4).

Рис. 3.

Використовуються два принципи побудови графів ПУМ.

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

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

Побудовані за таким принципом графи ПУМ, як правило, більш місткі та
менш зручні для аналізу та реалізації в ЕОМ. З вищезазначених причин на
практиці ширше використовується побудова графу ПУМ за принципом “події –
роботи”. Саме цей принцип будемо використовувати в подальшому.

Управління комплексом робіт за допомогою сітьового графіка.

Порядок та правила побудови графів ПУМ.

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

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

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

1. Граф ПУМ не повинен мати “глухих кутів”, тобто подій, з яких не
виходить жодної роботи, окрім завершальної події (рис. 4 а). Поява
“глухих кутів” подій свідчить про не досить ретельно виконаний
аналіз робіт та їх взаємозв’язків.

2. На графові не може бути “хвостових” подій (окрім вихідної події),
тобто подій, яким не передує жодна робота. На рис. 4 б такою
“хвостовою”подією є подія 3; вона не може відбутися, отже, не можуть
відбутися і наступні події.

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

4. Дві довільні події повинні бути безпосередньо пов’язаними не
більше ніж однією дугою — роботою. Ця вимога обумовлена тим, що роботи
позначають двома індексами ( і , j ), які відповідають подіям “і” та “ j
“ . Якщо в дійсності треба виконати кілька робіт, які розпочинаються та
завершуються одночасно, при одних і тих же подіях початкових та
кінцевих, то в таких випадках необхідно ввести фіктивні події та
фіктивні роботи (рис. 4 д ), паралельні роботи при цьому замикаються на
фіктивні події (рис. 4 є ).

5. На графові ПУМ повинна бути лише одна вихідна та лише одна
завершальна подія. Якщо це об’єктивно не так (початок реалізації
комплексу робіт можна розпочинати паралельно з декількох робіт — рис. 4
є ), то необхідно ввести фіктивні події та роботи, як це показано на
рис. 4 ж .

а)
б) в)

г)
д) е)

є)
ж)

А С

В

F

В D

А

з)
и)

Рис. 4. Графічне зображення вимог до побудови графів ПУМ.

Фіктивні події та роботи можуть вводитися і через інші умови.

Однією з таких умов є відображення залежності подій, не пов’язаних з
реальними роботами.

Наприклад, роботи А тв В (рис. 4 з ) можуть виконуватися
технологічно незалежно одна від одної, але в умовах конкретного
виробництва робота В не може розпочатися раніше, ніж завершиться робота
А . За таких обставин необхідно ввести фіктивну роботу С (рис. 4 и ).

Другий випадок — неповна залежність робіт.

Наприклад, робота С може бути розпочата лише по завершенні робіт А та В
, але робота D — лише по завершенні роботи В і не залежить від роботи А
. Тоді необхідно ввести фіктивну роботу F . Ta фіктивну подію 3′ , як
показано на рис. 4 и .

Фіктивні роботи можуть бути введені і для відображення реальних
відстрочок і чекань — в цих випадках вони характеризуються відповідним
часом.

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

Одним з визначальних основних понять графу ПУМ є поняття шляху.

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

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

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

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

Максимальним шляхом між двома подіями “і” та “j” називають шлях від і-ої
події до j-ої, який має максимальний термін, тобто сума термінів робіт,
які складають такий шлях, є не меншою ніж відповідна сума для довільного
шляху від і-ої події до j- ої .

Наприклад, для графу рис. 6 завершеними шляхами будуть

L1=[2; 6; 7] , L2=[4; 5; 7], L3=[3; 6; 7] і т. д. Їх терміни
t(L1)=3+5+16=24; t(L2)=8+7+18=33; t(L3)=4+10+16=30. Критичний шлях слід
визначати за алгоритмом, описаним у питанні 1 , використовуючи
завантаження дуги не пропускною спроможністю, а терміном виконання
роботи, що відповідає дузі. Розглянемо інший спосіб обчислення терміну
критичного шляху. Критичний шлях для графу рис.6 Lкp=[l; 2; 4; 5; 7], а
його термін t(Lkp)=3+9+7+18=37. На рис.6 він зображений подвійною
лінією. Критичними роботами будуть: (1; 2), (2; 4), (4; 5), (5; 7).

Рис.6.

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

Основні параметри ПУМ за критерієм часу наведені в табл.1.

Основні параметри планування й управління мережі

Таблиця 1.

Елемент мережі,

характеризований

параметром

Назва параметра

Умовні позначення

параметра

Подія і

Ранній термін звершення події tp(i)

Пізній термін звершення події tn(i)

Резерв часу події Rp(i)

Робота (i, j)

Термін виконання роботи t(i,j)

Ранній термін початку роботи tpn(i,j)

Ранній термін завершення роботи tpз(i,j)

Пізній термін початку роботи tnn(I,j)

Пізній термін завершення роботи tпз(I,j)

Повний резерв часу роботи Rn(i,j)

Частковий резерв першого виду часу роботи R1(i,j)

Частковий резерв другого виду часу роботи R2(i,j)

Незалежний резерв часу роботи Rн(i,j)

Шлях L

Термін шляху t(L)

Термін критичного шляху tkp

Резерв часу шлях Rt(L)

Розглянемо формули обчислення параметрів, указаних в табл.1.
Використання формул покажемо стосовно графу ПУМ, схему запису параметрів
часу якого наведено на рис.6.

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

t(i,j)[Rn(i,j);R1(i,j);Rн(i,j)]

Рис. 7.

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

(1)

(Lbj — будь-який шлях, який передує j -й подій, тобто шлях від вихідної
до j -ої події).

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

(2)

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

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

(3)

(Liз , — будь-який шлях L від і -ої події до завершальної).

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

(4)

Резерв часу R(i) i -ої події обчислюється як різниця пізнього та
раннього термінів звершення i -ої події:

(5)

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

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

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

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

Аналіз та оптимізація планування й управління мережею

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

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

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

Ступінь напруженості терміну виконання роботи ( i , j ) прийнято
характеризувати коефіцієнтом напруженості K( i, j ) , величина якого
визначається відношенням суми термінів виконання неспівпадаючих робіт
максимального шляху, якому належить дана робота, та критичного шляху:

(6)

— термін виконання робіт максимального шляху, який містить роботу (i,j)
,

— термін виконання робіт критичного шляху;

— сума термінів виконання тих робіт максимального шляху, відповідного
роботі (і, j) , які співпадають з роботами критичного шляху). Формулу
(1) можна записати і в такому вигляді:

(7)

— повний резерв часу роботи (i,j) .

Коефіцієнт напруженості К(і, j) приймає значення від 0 до 1 . Чим більше
його величина, тим важче своєчасно виконати дану роботу.

Третім етапом аналізу ПУМ є розрахунки запитів виробничих ресурсів та їх
розподіл у часі.

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

Усі вказані етапи аналізу системи ПУМ передують її оптимізації.

Література

Карлин С. Математические методы в теории игр, программировании и
экономике. -М.: Мир, 1964.

Вентцель Е.С. Введение в исследование операций. Сов. радио, 1964.

Пономаренко О.І., Пономаренко В.О. Системні методи в економіці, бізнесі
й менеджменті. -К.: Либідь, 1995.

Пономаренко О.І., Перестюк М.О., Бурим В.М. Основи математичної
економіки. -К.: Інформтехніка, 1995.

Горелик В.А., Ушаков М.А. Исследование операций. -М.: Машиностроение,
1986.

PAGE

PAGE 17

Вмикання

Акумулятор

Високовольтний

трансформатор

Генератор

Трамплер

Колінчастий вал двигуна

Система запалення

Генератор

1

2

3

4

5

6

7

8

1

3

2

8

5

4

7

6

7

6

6

2

3

4

0

0

1

3

6

4

5

2

1

2

5

6

4

3

4

закладка

фундаменту

підготовка котловану

монтаж

підйомного

крана

доставка будматеріалів і металоконструкцій

виконання

будівельних

робіт

3

3

4

6

5

2

1

6

5

2

1

7

7

3

4

6

5

2

1

N

2

1

3

2

1

3

1

3

2

2

3

5

1

4

2

1

0

3

6

4

1

2

4

5

3′

5

3

2

tp(i)

i

tn(i)

R(i)

R(j)

tn(j)

2

3»»»»»»»»»»

5

3’@@@@@@22

1

4

tp(j)

j

Похожие записи