Методы исследования операций при принятии решений. Бодров В.И - 26 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

Для графа, изображенного на рис. 2.1, можно записать: 1 2, 1 3, 2 4, 2 5, 4 5, 4 6, 5
6.
Сеть считается заданной, если заданы:
а) все работы (вершины);
б) продолжительность работ ρ
i
;
в) порядок следования работ.
Сеть (рис. 2.1) позволяет увидеть, что работа 2 может начаться только после того, как закончится
работа 1 (так как 1 2). Работа 3 также начнется после окончания работы 1 (3 1), работа 5 может на-
чаться только после того, как будут окончены работы 2, 3, 4 (5 3, 5 2, 5 4). Так как 6 4, 6 5,
то работа 6 начнется после окончания работ 4 и 5.
Начальная вершина обозначается буквой В, конечная вершина – буквой F. Иногда продолжительно-
сти работ B и F бывают равными нулю. Это означает, что данная вершина является фиктивной: она про-
сто обозначает "начало" или "конец" выполнения работ всего комплекса.
Необходимо заметить, что граф на рис. 2.1 можно изобразить как граф выполнения работ (рис. 2.3).
Однако изображение (рис. 2.1) удобнее, и именно оно используется в сетевых задачах.
Рис. 2.3 Граф выполнения работ
Для решения сетевых задач можно применять методы и алгоритмы теории графов, однако, здесь
графы не являются деревьями, и хотя имеется множество методов решения задач на графах, но они
менее удобны. К тому же задачи исследования последовательности работ (сетевые задачи) специ-
фичны и эта специфика сделала возможным использовать более простые алгоритмы исследования.
Сетевые задачи делятся на две группы:
1 Задачи исследования комплекса работ.
2 Задачи оптимизации комплекса работ.
2.2 Задача исследования комплекса работ
Задача исследования комплекса работ является важнейшей из двух типов сетевых задач.
Пусть работа 3 начинается лишь после выполнения работ 1 и 2 (рис. 2.4).
Предполагается, что работы 1 и 2 стартовали в одно и то же время. Однако, работа 1 выполняется 5
единиц времени (ρ
1
= 5), а работа 2 выполняется 10 единиц времени (ρ
2
= 10). Следовательно, начало
выполнения работы 3 определяется временем выполнения работы 2. Если выполнение работы 2 запо-
здало на любую величину ∆t, то на эту же величину запоздает начало выполнения работы 3 (рис. 2.5).
Работа 1 может опоздать на некоторое время (на время, равное 5 единиц) и это не вызовет изме-
нения начала выполнения работы 3, так как все равно работа 3 должна "ждать" конца выполнения
работы 2.
Говорят, что работа 2 является критической для работы 3. Этот факт отмечен на рис. 2.4 двойным
кружком. Однако, для работы 4 работа 3 может не являться критической.
Путь от вершины В до вершины F (т.е. от начальной до конечной вершины), который целиком со-
стоит из критических вершин, называется критическим путем.
2
4
1
125
125
3
25
25
6
18
618
5

Страницы