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.

4. Потоки в сетях

В этом разделе рассматриваются задача максимизации потока некоторого продукта по сети. Подобного рода задачи возникают при организации перекачки нефти или газа по трубопроводам, железнодорожного или автомобильного движения, передачи информации по сетям и т.д.

Приведём необходимые определения, формализующие соответствующие предметные области.

Сетью называется орграф без циклов с помеченными вершинами и дугами. Числа, которыми помечаются дуги сети, называются пропускными способностями дуг.

Примеры вершин сети: перекрёстки дорог, телефонные узлы, железнодорожные узлы, аэропорты, склады и т.д.

Примеры дуг сети: дороги, трубы, телефонные и железнодорожные линии и т.д.

Сеть, у которой существует ровно один исток[3] и один сток[4], называется транспортной сетью.

Пример транспортной сети:

Потоком в транспортной сети называется неотрицательная функция, определённая на множестве дуг сети, удовлетворяющая двум условиям:

1. величина потока по каждой дуге не превосходит её пропускной способности;
2. сумма потоков, входящих в каждую вершину сети, за исключением истока и стока, равна сумме потоков, выходящих из вершины.

Величина потока есть сумма потоков, выходящих из истока, или сумма потоков, входящих в сток сети.

Пример потока в транспортной сети:

Для любой транспортной сети величина потока имеет максимальное значение, которое определяется теоремой Форда – Фалкерсона, которая утверждает, что величина максимального потока в сети равна величине минимального разреза, где