Контрольная работа по теории потоков в сетях. Билет 1
1.
Дана сеть G с дугами (1, 2), (1, 3), (1,4), (2, 3), (2, 5), (2,6), (3, 5), (3, 6), (3, 7), (4, 3), (4, 5), (4, 7), (5, 8), (6, 8), (7, 8), пропускные способности которых равны соответственно 2, 4, 6, 1, 1, 1, 2, 2, 2, 1, 3, 3, 5, 3, 4.
A.
Найти максимальный поток из узла 1 в узел 8 и его величину с помощью алгоритма Форда-Фалкерсона. В качестве начального взять нулевой поток. Для каждой итерации указать увеличивающий путь и величину увеличения потока.
B.
Найти максимальный поток из узла 1 в узел 8 и его величину с помощью алгоритма Карзанова. В качестве начального взять нулевой поток. Для каждого этапа указать сеть G(f), слоистую сеть G*(f) и тупиковый поток в ней.
C.
Построить минимальный разрез в сети G.
2.
Дана сеть G с дугами (0, 1), (0,2), (1,2), (2, 1), (1, 3), (2, 3), (3, 0), параметры которых равны соответственно (2, 4, 2), (2, 4, 5), (0, 1, 1), (0, 1, 1), (3, 4, 3), (1, 2, 6), (3, 4, 0) (дуга (i,j) имеет параметры Lij, Uij, cij, где Lij - нижняя граница потока по дуге, Uij - верхняя граница потока по дуге, с,, - стоимость единицы потока по дуге). С помощью алгоритма дефекта найти циркуляцию минимальной стоимости в сети G. В качестве начального взять нулевой поток. Для каждой итерации указать поток по каждой дуге, наличие или отсутствие ее дефекта, возможные изменения потока по ней, узловые числа. При изменении потоков указать соответствующий цикл и величину изменения потока, а при изменении узловых чисел привести соответствующие вычисления.
3.
Даны вычислительная система, состоящая из двух идентичных процессоров, и четыре работы со следующими
характеристиками:
Работа I |
bi |
fi |
ti |
1 |
0 |
4 |
3 |
2 |
2 |
5 |
2 |
3 |
1 |
6 |
2 |
4 |
0 |
6 |
5 |
(bi, fi, ti - соответственно начальный директивный срок, конечный директивный срок и длительность выполнения работы i). Определить, существует ли допустимое расписание с прерываниями и найти его, если оно существует. Издержками на прерывания и переключения пренебречь. Свести указанную задачу к задаче о максимальном потоке в сети. При нахождении максимального потока привести все вычисления.
