2020-07-01
208
Элементы и виды сетевых моделей. Правила построения сетевых графиков
Одним из важнейших приложений теории графов является сетевое планирование и управление (СПУ) сложными комплексами взаимосвязанных работ. Графической моделью комплекса работ или производственного процесса является сетевой график (сетевая модель, сеть). С математической точки зрения сетевой график – это связанный орграф без петель и контуров.
Сетевые модели состоят из следующих элементов: работа (или задача); событие.
Работа – это процесс, который необходимо выполнить для получения, определенного (заданного) результата, как правило, позволяющего приступить к последующим действиям. Различают три вида работ.
| Вид работы (обозначение) | Определение | Пример |
| действительная (сплошная стрелка) | процесс, требующий затрат времени и ресурсов | разработка проекта, подвоз материалов, выполнение монтажных работ |
| ожидание (штрихпунктирная стрелка) | процесс, требующий времени, но не потребляющий ресурсы | процессы затвердения бетона, сушки пиломатериалов |
| фиктивная работа (пунктирная стрелка) | работа, не требующая времени и ресурсов, но указывающая, что возможность начала одной работы непосредственно зависит от результатов другой (продолжительность равна нулю) |
Событие – момент изменения состояния системы, в частности, момент начала или окончания любой работы по своей сути является событием. Предполагается, что события не имеют продолжительности и наступают мгновенно. В сетевом графике различают три вида событий.
| Вид события | Определение |
| исходное | это такое событие, с которого начинается выполнение комплекса операций |
| завершающее | соответствует достижению конечной цели, то есть завершению комплекса работ |
| промежуточные | все прочие события |
Виды сетевых моделей
По способу представления информации существуют два принципиально различных вида сетевых моделей (графиков).
1. Сеть вида «вершина – событие, дуги - работы»: вершины соответствуют событиям, а соединяющие их дуги – работам. При графическом представлении работа изображается стрелкой, которая соединяет два события. Она обозначается парой заключенных в скобки чисел (i, j), где i — номер события, из которого работа выходит, а j — номер события, в которое она входит. События изображаются кружками. Этот вид сетевой модели представлен на рис. 6.1.
Каждая работа имеет определенную продолжительность t (i, j). Например, запись t (2,5) = 4 на рис. 6.1. означает, что работа (2,5) имеет продолжительность 4 единицы.
Рис. 6.1. Сетевая модель «вершина – событие»
2. Сеть вида «вершина – работа»: вершины соответствуют работам, а дуги – связям. События при необходимости отображаются какими-либо фигурами, например – треугольниками.
Замечание. Мы будем использовать сетевые графики в терминах «вершина – событие, дуги – работы».
Требования, предъявляемые к сетевым моделям
1. События правильно пронумерованы, т. е. для каждой работы (i, j) выполняется условие i <j.
2. Отсутствуют тупиковые события (кроме завершающего), т.е. такие, за которыми не следует хотя бы одна работа.
3. Отсутствуют события (за исключением исходного), которым не предшествует хотя бы одна работа.
4. Отсутствуют циклы, т. е. замкнутые пути, соединяющие событие с ним же самим.
Однако иногда в исходном сетевом графике события имеют неупорядоченную нумерацию. Поэтому после построения графика в случае необходимости рекомендуется перенумеровать его события (номер начального события любой работы должен быть меньше номера её конечного события).
Алгоритм нахождения
