атами. Роботи позначаються на мережевому графіку дугами. p> Під подією розуміють результат завершення однієї або декількох робіт.
Спочатку планований процес розбивається на окремі роботи та події, складається перелік робіт і подій, продумуються їх логічні зв'язки і послідовність виконання, роботи закріплюються за відповідальними виконавцями. З їх допомогою оцінюється тривалість кожної роботи. Потім складається мережевий графік. Після впорядкування мережевого графіка розраховуються параметри подій і робіт, визначаються резерви часу і критичний шлях. Потім проводиться аналіз та оптимізація мережного графіка. p> Відмінною особливістю мережної моделі є чітке визначення всіх тимчасових взаємозв'язків майбутніх робіт.
З математичної точки зору, мережевий графік являє собою пов'язаний орієнтований граф без петель і контурів.
Наочно граф можна представити як деякий безліч вершин і безліч ребер, що з'єднують всі або деякі з цих вершин.
Якщо на ребрі вказано напрямок зв'язку між вершинами, то воно називається дугою. Орієнтація дуги вказується стрілками. Дуга, з'єднує вершину i з вершиною j, позначається символом (i, j) або pij.
Якщо всі з'єднання в графі зображуються дугами, то граф називається орієнтованим, або орграфом.
Послідовність дуг, в якій кінець кожної попередньої дуги збігається з початком наступної, називається шляхом в орграфе.
Шлях, у якого початкова вершина збігається з кінцевою, називається контуром. Контур з однією вершиною - петля. p> Вершина, з якої дуги тільки виходять, але не входять, називається витоком.
Вершина, до якої дуги тільки входять, але не виходять, називається стоком.
Будь-який шлях в мережевому графіку від витоку до стоку називається повним.
Якщо дуг (ребер) графа зіставлені якісь числові характеристики - вагами.
Вершина хi (В«предокВ») передує в графі вершині хj (В«НащадокВ»), якщо існує шлях з хi в хj. p> Граф є впорядкованим, якщо в ньому порядковий номер В«ПредкаВ» завжди менше порядкового номера В«нащадкаВ». p> Графічний номер впорядкування графа реалізується за алгоритмом Фалкерсона:
1-ий крок - виділяємо вершини, що не мають В«предківВ», і послідовно нумеруємо їх у довільному порядку;
2-ий крок - подумки викреслюємо із графа всі вершини, мають номери і дуги з них виходять;
3-ий крок - в отриманому графі повторюємо процедури 1-го і 2-го кроків до тих пір, поки всі вершини не будуть пронумеровані.
Граф називається зв'язаним, якщо будь-які його дві вершини можна з'єднати шляхом, в якому не враховується орієнтація дуг.
Мережевий графік - це зв'язаний зважений орграф без контурів (петель).
На зображенні комплексу робіт за допомогою мережевого графіка засноване мережеве планування і управління (СПУ).
Події позначаються на мережевому графіку вершинами.
Підготовка вихідних даних для побудови мережевого графіка ...
