Опишіть параметри сітьових моделей та їх розрахунок. Аналіз та оптимізація сітьових моделей.

Міністерство освіти і науки України

Національний університет водного господарства та природокористування

Кафедра транспортних технологій та технічного сервісу

Самостійна робота

З дисципліни

«Дослідження операцій в транспортних системах»

Виконав: студент групи

ТТАТз-21(інт)

Козелець С.В.

Перевірив: Кристопчук М.Є.

Рівне - 2015

Опишіть параметри сітьових моделей та їх розрахунок. Аналіз та оптимізація сітьових моделей.

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

Сітьові моделі відносно прості, зручні для аналізу і при використанні відповідного програмного забезпечення для ЕОМ дозволяють швидко знаходити найкращі варіанти управлінських дій.

Метод оцінки та огляду програм (PERT) і метод критичногошляху(СRМ) - два найбільш відомі методи, які в кінці 50-х р.р. ХХ століття почали широко застосовуватись в США при розробці ракетного озброєння “Поларіс” та для управління будівельними роботами. Вони дозволяють представляти послідовність взаємозалежних і незалежних одна від одної робіт. Використовуючи ці методи, можна швидко оцінити проект, що складається з тисяч і десятків тисяч робіт, тобто відповісти на такі запитання:

1. Коли буде завершений проект у цілому?

2. Які роботи або задачі є критичними в проекті? Тобто ті, затримка у виконанні яких визначає затримку у виконанні проекту у цілому.

3. Які роботи не є критичними? Тобто ті, що можуть протікати повільніше, без затримки завершення проекту у цілому.

4. Яка імовірність того, що проект буде завершений у певний термін?

5. На будь-яку конкретну дату виконання проекту можна отримати відповідь: виповнюється проект відповідно до графіка, відстає від графіка або випереджає графік?

6. На кожну дату можна одержати відповідь: чи витрачаються гроші у відповідності з кошторисом на проект, витрачено менше передбачених засобів або витрати перевищують те, що передбачено кошторисом?

7. Чи вистачить ресурсів, щоб закінчити проект вчасно?

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

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

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

Ціль СПУ - забезпечення визначених оптимальних показників. Такими показниками в залежності від конкретних умов, заданих вимог можуть бути: мінімальний час виконання всього комплексу робіт, мінімальна вартість розробки, максимальна економія ресурсів та ін.

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

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

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

· великі розробки (кількість подій в сіті 10000...12000);

· середні розробки (кількість подій в сіті 1500...10000);

· малі розробки (кількість подій в сіті до 1500).

У випадку невеликих розробок від кількох десятків подій до 100 використовуються ручні методи розрахунку і аналізу сітьових моделей.

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

Основу сітьового графіка складають три елементи: робота, подія, шлях.

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

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

· очікування – технологічна операція яка вимагає часу без витрати ресурсів (охолоджування відливок, старіння, сушіння);

· фіктивна (залежність) – вказує тільки на логічний зв’язок між роботами і не вимагає ні часу, ні ресурсів.

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

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

Будь-яка робота з’єднує дві події: початкову i і кінцеву j, яка кодується номерами її початкової і кінцевої події (i-j) (Рис. 1.).

Рис.1. Позначення роботи на сітьовому графіку

Припустимо, що при складанні деякого проекту виділено 12 подій: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 і 24 роботи, що їх з’єднують: (0, 1), (0, 2), (0, 3), (1, 5), (1, 4), (1, 2), (2, 3) (2, 5), (2, 7), (3, 7), (3, 6), (3, 10), (4, 8), (5, 8), (5, 7), (6, 10), (7, 6), (7, 8), (7, 9), (7, 10), (8, 9), (9, 11), (10, 9), (10, 11). Необхідно скласти й упорядкувати сітьовий графік.

Як випливає з переліку робіт, вихідною подією сітьового графіка є подія 0 (їй не передують ніякі роботи), а завершальною — подія 11 (за нею не слідує жодна робота). Будемо вважати що на сітьових графіках зміна часу відбувається зліва-направо, помістимо подію 0 у ліву частину графіка, а подія 11 — у праву частину, розмістивши між ними проміжні події в деякому порядку, що відповідає їхнім номерам (рис.2). Події зв'яжемо роботами-стрілками відповідно до переліку робіт.

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

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

Рис. 2. Сітьовий графік проекту

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

Помістивши в I шарі початкову подія 0 (рис.3), уявно викреслимо із графіка (рис.2) цю подію і усі вихідні з неї роботи-стрілки. Тоді без вхідних стрілок залишиться подія 1, що утворить II шар. Викресливши уявно подію 1 і усі вихідні з неї роботи, побачимо, що без вхідних стрілок залишаються події 4 і 2, що утворять III шар. Продовжуючи зазначену процедуру викреслювання, одержимо IV шар з подіями 5 і 3, V шар — з подією 7, VI з подіями 8 і 6, VII шар — з подією 10, VIII з подією 9 і, нарешті, IX шар — з подією 11.

Тепер бачимо, що первинна нумерація подій не зовсім правильна: так, подія 6 лежить у VI шарі і має номер, менший, ніж подія 7 з попереднього шару. Те ж можна сказати про події 9 і 10.

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

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

Рис. 3. Розбивання сітьового графіка на вертикальні шари

Рис.4. Упорядкований сітьовий графік із зазначеними тривалостями робіт

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

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

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

Рис.5. Лінійна діаграма проекту

По відношенню до передуючих і наступних робіт події бувають:

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

· вихідними – виражають готовність до початку робіт. Вони не мають вхідних робіт. В сіті може бути тільки одна початкова подія;

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

Шлях – будь яка послідовність робіт, яка з’єднує деякі дві події. Тривалість шляху дорівнює сумарній тривалості робіт із яких він складається. Розрізняють шляхи:

· повний – послідовність робіт, яка з’єднує вихідну і завершальну події;

· передуючий події і – послідовність робіт, яка з’єднуює вихідну подію і проміжну подію і;

· наступний за подією і – послідовність робіт, яка з’єднує подію і із завершальною;

· між подіями i та j;

· критичний – повний шлях, який має найбільшу тривалість.

В сітьовому графіку завжди кілька повних шляхів. Максимальний із них – критичний.