Лабораторна робота №16, Критичний шлях

« Назад

Теоретична довідка

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

Причиною даної задачі стала практика сучасного менеджменту щодо управління складними проектами, заснована в США (1968 р.). Відповідна методологія отримала назву «мережеве планування і управління» (МПУ).

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

У мережевому графіку реалізовані два принципи:

- операція починається тільки тоді , коли досягнуто її початкова подія;

- подія вважається досягнутою, якщо виконані всі операції, які є входами.

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

- критичного шляху (Critical Path Method, CPM), де тривалість операцій однозначно визначено і задано конкретними числами;

- аналізу та перегляду програм (Program Evaluation and Review Technique, PERT), де тривалість операцій невизначено, тому їх задають певними ймовірносними оцінками.

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

Постановка задачі

Задано мережевий графік у вигляді орієнтованого графа, який складається з 9 вузлів (подій) і 13 дуг (операцій). Потрібно знайти критичний шлях від вузла № 1 до вузла № 2.

Економіко - математична модель

Знайти вектор невідомих (Дуга ), щоб

- Загальна довжина шляху = Дуга * Тривалість → max

- За умови збереження балансу потоків для кожного вузла:

+ для вузла -джерела - Вихід - Вхід = 1;

+ для проміжних вузлів - Вихід - Вхід = 0;

+ для вузла - стоку - Вихід - Вхід = -1;

+ всі невідомі більше нуля.

Хід роботи

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

1. У таблиці для операцій визначаємо діапазон для невідомих (Дуга ) і обчислюємо значення цільової комірки (Тривалість) використовуючи СУММПРОИЗВ (Дуга ; Тривалість).

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

3. Для обчислення потоку у вузлах використовують функцію обчислення суми величин, координати яких задовольняють певні умови (СУММЕСЛИ).

4. Аналогічно підсумовують вихідні потоки.

Необхідно:

1. Знайти тривалість критичного шляху.

2. Заповнити та пояснити значення Т-цін та Н-вартостей для дуг та вузлів.

3. Побудувати орієнтований граф із виділенням критичного шляху.

Рис. 1 – Задача про критичний шлях, Excel

Аналіз результату

Нормовані вартості (Н- вартості) некритичних робіт вказують на резерв часу.

Контрольні запитання

1. Що таке резерв часу?

2. Який шлях називаємо критичним?

3. Яка сфера застосування задач про критичний шлях?

4. Зміст нормованої вартості у задачі про критичний шлях?