Реализация в Excel

В качестве начального потока выбираем, например, поток, проходящий по ребрам 1-3-5-6. Максимальная величина потока, который можно пропустить по этим ребрам, равна 2.

На чистом рабочем листе заполняем форму решения задачи. В ячейки B3:G8 заносим данные о пропускных способностях ребер сети.

Ниже строим матрицу  начального потока на сети.

Обратите внимание на то,  что матрица начального потока должна быть антисимметрична. Поэтому  сначала заполняем ее диагональные элементы, выделяя их каким-либо цветом, и ту часть матрицы, которая находится выше главной диагонали.

Для заполнения  нижней части матрицы воспользуемся функцией ТРАНСП(массив).

Эта функция возвращает вертикальный диапазон ячеек в виде горизонтального и наоборот. Функция ТРАНСП должна быть введена как формула массива в интервал, который имеет столько же строк и столбцов, сколько столбцов и строк имеет аргумент массив.

Для заполнения столбца В13:В17 установите курсор в ячейку В13, введите формулу  = - ТРАНСП(C12:G12) и нажмите клавишу <ENTER> (знак <–> перед формулой вводится для того, чтобы матрица получилась антисимметричной).  В ячейке появится знак ошибки. Затем нужно выделить диапазон В13:В17, нажать клавишу , а затем клавиши . В результате будет сформирован первый столбец матрицы потока. Остальные столбцы под нижней диагональю заполняются аналогично.

Ниже матрицы потока строим матрицу ненасыщенности ребер.

Для этого в ячейку В21 вводим формулу:

=B3:G8-B12:G17

После чего выделяем диапазон В21: G26, нажимаем клавишу , а затем клавиши .

В результате третья матрица заполняется значениями, равными «недогрузке» ребер.

Находим ненасыщенные пути. Для этого в матрице ненасыщенности выбираем ненулевые элементы:

1|| 2, 3, 4

2|| 3, 4, 5

3|| -

4|| 5, 6

Таким образом, можно выбрать путь 1-2-4-6 с максимально возможным  объемом дополнительного груза, равным 4.

Для удобства можно выписать процедуру поиска ненасыщенного пути справа от матрицы ненасыщенности ребер:

Выделяя потоки по выбранным ребрам каким-либо цветом, легко найти их минимум . Строим справа матрицу дополнительного потока по аналогии с матрицей начального потока.

Ниже строим матрицу нового потока №1 путем суммирования матриц начального и дополнительного потока (не забываем, что формулы вводятся как формулы массива). Снова находим матрицу ненасыщенных ребер для потока №1.

Процедуру повторяем до тех пор, пока не останется ненасыщенного пути из вершины 1 в вершину 6. Поток, найденный на этом шаге, будет максимальным.