ПОЗНАВАТЕЛЬНОЕ

Сила воли ведет к действию, а позитивные действия формируют позитивное отношение

Как определить диапазон голоса - ваш вокал

Игровые автоматы с быстрым выводом

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

Целительная привычка

Как самому избавиться от обидчивости

Противоречивые взгляды на качества, присущие мужчинам

Тренинг уверенности в себе

Вкуснейший "Салат из свеклы с чесноком"

Натюрморт и его изобразительные возможности

Применение, как принимать мумие? Мумие для волос, лица, при переломах, при кровотечении и т.д.

Как научиться брать на себя ответственность

Зачем нужны границы в отношениях с детьми?

Световозвращающие элементы на детской одежде

Как победить свой возраст? Восемь уникальных способов, которые помогут достичь долголетия

Как слышать голос Бога

Классификация ожирения по ИМТ (ВОЗ)

Глава 3. Завет мужчины с женщиной

Оси и плоскости тела человека - Тело человека состоит из определенных топографических частей и участков, в которых расположены органы, мышцы, сосуды, нервы и т.д.

Отёска стен и прирубка косяков - Когда на доме не достаёт окон и дверей, красивое высокое крыльцо ещё только в воображении, приходится подниматься с улицы в дом по трапу.

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

Метод критичного шляху (МКШ)

Щоб описати деякий проект як мережу необхідні наступні вихідні дані:

1. Перелік всіх операцій (робіт) проекту;
2. Час, необхідний для виконання кожної операції.
3. Перелік операцій, які безпосередньо передують кожній операції.

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

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

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

1. Початкова подія отримує номер 1.

2. Надати наступний номер будь-якій не пронумерованій події, для якої всі попередні події мають номери.

3. Якщо існують не пронумеровані події, то перейти в п.2.

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

1. Встановити Е(1)=0. Тобто для першої події найбільш раннім терміном є нуль.

2. Збільшити номер події на 1.

3. Якщо всі події вичерпані – закінчити роботу. В противному разі – перейти в п.4.

4. Для поточної події визначити найбільш ранній термін закінчення за формулою E(j)=max{E(i)+t(i, j)}.

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

1. Встановити L(n) рівним заданому часу завершення проекту. Пам’ятати, що в реальному житті виконується умова L(n)>=E(n).

2. Зменшити номер події на 1.

3. Якщо події вичерпались – припинити роботу, В противному разі – перейти в п.4.

4. Для поточної події визначити термін найбільш пізнього закінчення: L(i)=min{E(j) – t(i, j)}

Потім для всіх операцій знаходиться повний резерв часу операції (ПРЧО)

ПРЧО = L(y)–E(x) –t(x, y) (1)

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

Метод оцінки і перегляду планів PERT(Program Evaluation Review Technique)

В МКШ вважається, що час виконання роботи точно відомий і детермінований. В PERT вводиться статистична невизначеність в час виконання робіт. Для кожної роботи задають три оцінки часу виконання роботи:

1) найбільш ймовірний час виконання роботи m;

2) оптимістична оцінка часу виконання a;

3) песимістична оцінка b.

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

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

m=(a + 4m + b)/6. (2)

А дисперсія

s²= ((b – a )/6)² (3)

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

Послідовність виконання робіт при використання ПЕРТ.

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

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

(4)

Приклад виконання роботи

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

Таблиця 6.1. Вихідна інформація для побудови мережного графіка (приклад)

Побудована за цими вихідними даними мережа з пронумерованими подіями-вершинами показана на рис.6.2.

Операція – це вивчення певного курсу і вона має свою протяжність (час виконання). Операціям відповідають дуги (ребра) графа. Події (вершини графа) – це завершення певного етапу в навчанні (в даному випадку), наприклад сесія. Можуть бути дуги нульової довжини. Вони виникають в тому випадку, коли для якоїсь події обов’язково потрібне виконання іншої події, а відповідних робіт, які їх зв’язували б, немає. Наприклад, якби у нас для вивчення курсі «Методи оптимізації» необхідно було б обов’язково спочатку вивчити курс «Математичне програмування», то нам потрібно було б додати дугу 6–7 з нульовою довжиною і, відповідно враховувати її в розрахунках критичного шляху.

Рис.6.2. Мережа, побудована за вихідними даними

Відповідність дуг мережі і операцій показана в табл..6.2.

Таблиця 6.2. Відповідність дуг і операцій

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

E(1) = 0;

E(2) = max (E(1)+t(1,2)) = 0 + 1 = 1;

E(3) = max (E(2)+t(2,3)) = 1 + 1 = 2;

E(4) = max (E(2)+t(2,4)) = 1 + 1 = 2;

E(5) = max (E(2)+t(2,5); E(4) + t(4,5)) = max (1 + 1; 2 + 0) = 2;

E(6) = max (E(5)+t(5,6)) = 2 + 2 = 4;

E(7) = max (E(3)+t(3,7); E(4) + t(4,7)) = max (2 + 0; 2 + 1) = 3;

E(8) = max (E(3)+t(3,8)) = 2 + 1 = 3;

E(9) = max (E(8)+t(8,9); E(7)+t(7,9)) = max (3 + 1; 3 + 0) = 4;

E(10) = max (E(2)+t(2,10); E(9)+t(9,10)) = max (1 + 1; 4 + 0) = 4;

E(11) = max (E(5)+t(5,11); E(6)+t(6,11); E(10)+t(10,11)) = max (2 + 0; 4 + 0; 4 + 2) = 6;

E(12) = max (E(7)+t(7,12)) = 3 + 1 = 4;

E(13) = max (E(11)+t(11,13); E(12)+t(12,13)) = max (6 + 1; 4 + 0) = 7;

E(14) = max (E(13)+t(13,14)) = 7 + 2 =9;

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

L(14) = 9;

L(13) = L(14) – t(13,14) = 9 – 2 = 7;

L(12) = L(13) – t(12,13) = 7 – 0 = 7;

L(11) = L(13) – t(11,13) = 7 – 1 = 6;

L(10) = L(11) – t(10,11) = 6 – 2 = 4;

L(9) = L(10) – t(9,10) = 4 – 0 = 4;

L(8) = L(9) – t(8,9) = 4 – 1 = 3;

L(7) = min (L(9) – t(7,9); L(12) – t(7,12))= min (4 – 0; 7 – 0) = 4;

L(6) = L(11) – t(6,11) = 6 – 0 = 6;

L(5) = min (L(6) – t(5,6); L(11) – t(5,11))= min (6 – 2; 6 – 0) = 4;

L(4) = min (L(5) – t(4,5); L(7) – t(4,7)) = min (4 – 0; 4 – 1) = 3;

L(3) = min (L(8) – t(3,8); L(7) – t(3,7) )= min (3 – 1; 4 – 0) = 2;

L(2) = min (L(3) – t(2,3); L(4) – t(2,4); L(5) – t(2,5); L(10) – t(2,10))= min (2 – 1; 3 – 1; 4 – 1; 4 – 1) = 1;

L(1) = L(2) – t(1,2) = 1 – 1 = 0;

Результати розрахунків зведені в табл..6.3

Таблиця 6.3. Розраховані значення часу для подій

Тепер можна розрахувати повний резерв часу (результати див. в табл..6.4)

Таблиця 6.4. Розраховані значення часу для операцій

З таблиці виходить, що критичний шлях проходить через події 1 – 2 – 3 – 8 – 9 –10– 11 –13 –14. Довжина його 9 семестрів.

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

Таблиця 6.5. Оцінки часу вивчення для методу ПЕРТ

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

E(1) = 0;

E(2) = max (E(1)+t(1,2)) = 0 + 1,1 = 1,1;

E(3) = max (E(2)+t(2,3)) = 1,1 + 1 =2,1;

E(4) = max (E(2)+t(2,4)) = 1,1 + 1,1 =2,2;

E(5) = max (E(2)+t(2,5); E(4) + t(4,5)) = max (1,1 + 1,05; 2,2 + 0) = 2,2;

E(6) = max (E(5)+t(5,6)) = 2,2 + 2 = 4,2;

E(7) = max (E(3)+t(3,7); E(4) + t(4,7)) = max (2,1 + 0; 2,2 + 1,1) = 3,3;

E(8) = max (E(3)+t(3,8)) = 2,1 + 1,1 = 3,2;

E(9) = max (E(8)+t(8,9); E(7)+t(7,9)) = max (3,2 + 1,1; 3,3 + 0) = 4,3;

E(10) = max (E(2)+t(2,10); E(9)+t(9,10)) = max (1,1 + 1,1; 4,3 + 0) = 4,3;

E(11) = max (E(5)+t(5,11); E(6)+t(6,11); E(10)+t(10,11)) = max (2,2 + 0; 4,2 + 0; 4,3 + 2,2) = 6,5;

E(12) = max (E(7)+t(7,12)) = 3,3 + 1,25 =4,55;

E(13) = max (E(11)+t(11,13); E(12)+t(12,13)) = max (6,5 + 1,1; 4,55 + 0) = 7,6;

E(14) = max (E(13)+t(13,14)) = 7,6 + 2 = 9,6;

Для визначення найбільш пізнього часу будемо вважати, що на вивчення всіх курсів виділяється 9,6 семестри (тобто, L(n)=9,6).

L(14) = 9,6;

L(13) = L(14) – t(13,14) = 9,4 – 2 = 7,6;

L(12) = L(13) – t(12,13) = 7,4 – 0 = 7,6;

L(11) = L(13) – t(11,13) = 7,6 – 1,1 = 6,5;

L(10) = L(11) – t(10,11) = 6,5 – 2,2 = 4,3;

L(9) = L(10) – t(9,10) = 4,3 – 0 = 4,3;

L(8) = L(9) – t(8,9) = 4,3 – 1,1 = 3,2;

L(7) = min (L(9) – t(7,9); L(12) – t(7,12))= min (4,3 – 0; 7,6 – 0) = 4,3;

L(6) = L(11) – t(6,11) = 6,5 – 0 = 6,5;

L(5) = min (L(6) – t(5,6); L(11) – t(5,11))= min (6,5 – 2; 6,5 – 0) = 4,5;

L(4) = min (L(5) – t(4,5); L(7) – t(4,7)) = min (4,5 – 0; 4,3 – 1,1) = 3,3;

L(3) = min (L(8) – t(3,8); L(7) – t(3,7) )= min (3,2 – 1,1; 4,2 – 0) = 2,1;

L(2) = min (L(3) – t(2,3); L(4) – t(2,4); L(5) – t(2,5); L(10) – t(2,10))= min (2,1 – 1; 3,3 – 1,1; 4,5 – 1; 4,3 – 1,1) = 1,1;

L(1) = L(2) – t(1,2) = 1,1 – 1,1 = 0;

Результати його пошуку приведені в табл..6.6 і 6.7.

Таблиця 6.6. Розраховані значення часу для подій

Тепер можна розрахувати повний резерв часу (результати див. в табл..6.7)

Таблиця 6.7. Розраховані значення часу для операцій

З неї виходить, що критичний шлях проходить через події 1 – 2 – 3 – 8 – 9 – 10 – 11 –13 –14. Довжина його 9,6 семестрів.

Дисперсія для часу виконання проекту – 3,45. Відповідно можливо розрахувати довірчий інтервал для середнього часу проекту. Напівширину довірчого інтервалу в Excel можна розрахувати за допомогою функції =ДОВЕРИТ(0,05;1,856;7). Тут 0,05 – рівень значущості; 7 – розмір вибірки, а 1,856 – стандартне відхилення, котре визначається як корінь квадратний з дисперсії.

Крім того, можливо розрахувати ймовірність виконання проекту за певний час. Тут також можемо скористатись засобами Excel. Функція =НОРМСТРАСП((9-9,6)/ 1,856) дозволить визначити ймовірність закінчити вивчення за 9 семестрів. Вона буде 0,373. За 10 семестрів – 0,585. І тільки за 12 семестрів ймовірність буде 0,901. Це зв’язано з відносно великим розсіянням оцінок часу вивчення окремих курсів.

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

1. Які вихідні дані необхідні для побудови мережного графіку виконання проекту?

2. Що таке події і операції в мережному графіку.

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

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

5. Як визначається повний резерв часу операції.

6. Як визначається критичний шлях. Фізична сутність його.

7. Які дані необхідні для використання методу ПЕРТ.

8. Які припущення лежать в основі використання статистичних методів в ПЕРТ.

9. Що використовується як час виконання операції в ПЕРТ.

10. Які статистичні характеристики і як визначаються в ПЕРТ.

Література

1. Майника Э. Алгоритмы оптимизации на сетях и графах ­ М.: Мир, 1981, - 323с.
2. Филипс Д., Гарсиа-Диас А. Методы анализа сетей -М.: Мир, 1984. - 496с.

[1] N_diag – діагональна матриця, головна діагональ якої взята з N; N_sqr матриця, кожний елемент якої є квадратом відповідного елементу із N