2. Упорядоченная структурно-временная таблица |
|||||||
Работа |
Время выполнения |
Можно начать после работы |
Ранг работы |
Новая нумерация |
Работа |
Время выполнения |
Можно начать после работы |
a1 |
10 |
— |
1 |
b1 |
b1 |
10 |
— |
a2 |
5 |
a1, a3 |
2 |
b5 |
b2 |
15 |
— |
a3 |
15 |
— |
1 |
b2 |
b3 |
19 |
— |
a4 |
18 |
a1, a2, a3 |
3 |
b6 |
b4 |
18 |
— |
a5 |
19 |
— |
1 |
b3 |
b5 |
5 |
b1, b2 |
a6 |
18 |
— |
1 |
b4 |
b6 |
18 |
b1, b2, b5 |
a7 |
8 |
a1, a4, a10 |
6 |
b10 |
b7 |
25 |
b1, b5 |
a8 |
25 |
a1, a2 |
3 |
b7 |
b8 |
30 |
b2, b3, b6 |
a9 |
30 |
a3, a4, a5 |
4 |
b8 |
b9 |
8 |
b8 |
a10 |
8 |
a9 |
5 |
b9 |
b10 |
8 |
b1, b6, b9 |
3. Сетевой граф.
Примечание. Сплошная стрелка означает выполнение работы, а пунктирная – ожидание завершения работ, например, стрелки из вершин B1 и B5 можно прочитать так: после завершения работ b1 и b5 можно начинать работу b7.
4. Временн?й сетевой граф.
5. Анализ временн?го сетевого графа.
Минимальное время выполнения комплекса: 86.
Критические работы: b2 – b5 – b6 – b8 – b9 – b10.
Резервы времени с началом выполнения некритических работ:
некритическая работа |
задержка с началом выполнения |
b1 |
? 5 = 15 – 10, |
b3 |
? 66 = 86 – 20, |
b4 |
? 68 = 86 – 18, |
b7 |
?61 = 86 – 25. |
В этом разделе рассматриваются задача максимизации потока некоторого продукта по сети. Подобного рода задачи возникают при организации перекачки нефти или газа по трубопроводам, железнодорожного или автомобильного движения, передачи информации по сетям и т.д.
Приведём необходимые определения, формализующие соответствующие предметные области.
Сетью называется орграф без циклов с помеченными вершинами и дугами. Числа, которыми помечаются дуги сети, называются пропускными способностями дуг.
Примеры вершин сети: перекрёстки дорог, телефонные узлы, железнодорожные узлы, аэропорты, склады и т.д.
Примеры дуг сети: дороги, трубы, телефонные и железнодорожные линии и т.д.
Сеть, у которой существует ровно один исток[3] и один сток[4], называется транспортной сетью.
Пример транспортной сети:
Потоком в транспортной сети называется неотрицательная функция, определённая на множестве дуг сети, удовлетворяющая двум условиям:
Величина потока есть сумма потоков, выходящих из истока, или сумма потоков, входящих в сток сети.
Пример потока в транспортной сети:
Для любой транспортной сети величина потока имеет максимальное значение, которое определяется теоремой Форда – Фалкерсона, которая утверждает, что величина максимального потока в сети равна величине минимального разреза, где