Page 239 - 4685

Граф – універсальний засіб наочного представлення досить різноманітних
задач – сукупність вершин і ребер. Поєднання різних ребер і вершин
представляють різноманіття можливих графів та їх застосування.
Мережами представляють різні задачі, в яких досліджують переміщення
або виконання робіт в часі. Мережа характеризується структурою і
параметрами дуг. Структура (топологія) мережі показує, які вершини
зв'язані між собою, і напрям дуг, що їх сполучають.
Кожну вершину мережі нумерують порядковим номером. Початкову
вершину називають "джерелом", кінцеву – "стоком" в описі руху потоків.
Дугу мережі позначають подвійною індексацією 1 – 2; 3 – 4 і т.д. (за
номерами вершин, на які дуга спирається). У загальному випадку дугу
позначають "i – j", де i – номер вершини, з якої виходить дуга; j – номер
вершини, в яку дуга входить. Кожна дуга має свої характеристики: t –
ij
тривалість руху по дузі i – j; c – вартість переміщення; d – пропускна
ij
ij
спроможність дуги і т.д.:

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

Робота Зміст Слідує Тривалість Позначення
після
робіт

a 1 Закупівля і доставка — 1 1 – 2
устаткування
a Розробка технології — 2 1 – 3
2
a Монтаж і a 4 2 – 3
3
1
налагодження
обладнання

a Навчання a 3 2 – 4
4
1
робітників-
операторів
a Пуск лінії в a , a 6 3 – 4
4
2
5
експлуатацію

235