- 23.06.2015
- 3027
- 26
ЛАБОРАТОРНАЯ
РАБОТА
«Нахождение максимального потока на сети с помощью алгоритма Форда-Фалкерсона
в электронных таблицах Excel»
Построить максимальный поток от истока I к стоку S в сети, заданной графом (см. рис.1):
Рис.1
В скобках заданы пропускные способности ребер в направлении от меньшего номера вершины к большему и в обратном направлении.
Решение задачи:
Согласно алгоритму Форда-Фалкерсона:
1. Строим произвольный начальный поток на сети.
2. Находим подмножество А вершин, достижимых из истока I по ненасыщенным ребрам.
3. Если S не принадлежит A, то построенный поток максимальный и задача решена. Если S принадлежит A, то переходим к пункту 4.
4. Выделяем путь из I к S, состоящий из ненасыщенных ребер, и увеличиваем поток xij по каждому ребру этого пути на величину, равную min по всем ребрам (i,j) выделенного пути. После построения нового потока возвращаемся к пункту 2 алгоритма.
Реализация в Excel
|
В качестве начального потока выбираем, например, поток, проходящий по ребрам 1-3-5-6. Максимальная величина потока, который можно пропустить по этим ребрам, равна 2. На чистом рабочем листе заполняем форму решения задачи. В ячейки B3:G8 заносим данные о пропускных способностях ребер сети. Ниже строим матрицу начального потока на сети. Обратите внимание на то, что матрица начального потока должна быть антисимметрична. Поэтому сначала заполняем ее диагональные элементы, выделяя их каким-либо цветом, и ту часть матрицы, которая находится выше главной диагонали. Для заполнения нижней части матрицы воспользуемся функцией ТРАНСП(массив). |
Рис.2 |
Эта функция возвращает вертикальный диапазон ячеек в виде горизонтального и наоборот. Функция ТРАНСП должна быть введена как формула массива в интервал, который имеет столько же строк и столбцов, сколько столбцов и строк имеет аргумент массив.
Для заполнения столбца В13:В17 установите курсор в ячейку В13, введите формулу = - ТРАНСП(C12:G12) и нажмите клавишу <ENTER> (знак <–> перед формулой вводится для того, чтобы матрица получилась антисимметричной). В ячейке появится знак ошибки. Затем нужно выделить диапазон В13:В17, нажать клавишу <F2>, а затем клавиши <CTRL+SHIFT+ENTER>. В результате будет сформирован первый столбец матрицы потока. Остальные столбцы под нижней диагональю заполняются аналогично.
|
Ниже матрицы потока строим матрицу ненасыщенности ребер. Для этого в ячейку В21 вводим формулу: =B3:G8-B12:G17 После чего выделяем диапазон В21: G26, нажимаем клавишу <F2>, а затем клавиши <CTRL+SHIFT+ENTER>. В результате третья матрица заполняется значениями, равными «недогрузке» ребер. Находим ненасыщенные пути. Для этого в матрице ненасыщенности выбираем ненулевые элементы: 1|| 2, 3, 4 2|| 3, 4, 5 3|| - 4|| 5, 6
Таким образом, можно выбрать путь 1-2-4-6 с максимально возможным объемом дополнительного груза, равным 4. |
Рис.3 |
Для удобства можно выписать процедуру поиска ненасыщенного пути справа от матрицы ненасыщенности ребер:
Рис. 4
Выделяя потоки по выбранным ребрам каким-либо цветом, легко найти их минимум (см. рис.4). Строим справа матрицу дополнительного потока по аналогии с матрицей начального потока.
Ниже строим матрицу нового потока №1 путем суммирования матриц начального и дополнительного потока (не забываем, что формулы вводятся как формулы массива). Снова находим матрицу ненасыщенных ребер для потока №1.
Процедуру повторяем до тех пор, пока не останется ненасыщенного пути из вершины 1 в вершину 6. Поток, найденный на этом шаге, будет максимальным.
Задание для самостоятельной работы
Учащиеся выбирают номер варианта согласно списку.
Сеть содержит 10 вершин (рис. 5). Пропускные способности дуг заданы таблицей. Найти максимальный поток между вершинами 1 и 10 (номера вариантов указаны в верхнем левом углу таблицы).
Рис. 5
Рабочие листы
к вашим урокам
Скачать
Реализация в 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. Поток, найденный на этом шаге, будет максимальным.
6 665 123 материала в базе
Настоящий материал опубликован пользователем Орехов Павел Игоревич. Инфоурок является информационным посредником и предоставляет пользователям возможность размещать на сайте методические материалы. Всю ответственность за опубликованные материалы, содержащиеся в них сведения, а также за соблюдение авторских прав несут пользователи, загрузившие материал на сайт
Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.
Удалить материал
Ваша скидка на курсы
40%
Курс профессиональной переподготовки
500/1000 ч.
Курс повышения квалификации
36 ч. — 180 ч.
Курс повышения квалификации
72 ч. — 180 ч.
Мини-курс
3 ч.
Мини-курс
7 ч.
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.