Лабораторная работа в Exсel. Графы

Реализация в ExcelВ качестве начального потока выбираем, например, поток, проходящий по ребрам 1-3-5-6. Максимальная величина потока, который можно пропустить по этим ребрам, равна 2.На чистом рабочем листе заполняем форму решения задачи. В ячейки B3:G8 заносим данные о пропускных способностях ребер сети. Ниже строим матрицу  начального потока на сети.Обратите внимание на то,  что матрица начального потока должна быть антисимметрична. Поэтому  сначала заполняем ее диагональные элементы, выделяя ...
Раздел Информатика
Класс -
Тип Другие методич. материалы
Автор
Дата
Формат doc
Изображения Есть
For-Teacher.ru - все для учителя
Поделитесь с коллегами:

ЛАБОРАТОРНАЯ РАБОТА
«Нахождение максимального потока на сети с помощью алгоритма Форда-Фалкерсона в электронных таблицах
Excel»

Построить максимальный поток от истока I к стоку S в сети, заданной графом (см. рис.1):

РЛабораторная работа в Exсel. Графы

ис.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 заносим данные о пропускных способностях ребер сети.

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

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

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

Лабораторная работа в Exсel. Графы

Рис.2

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

Для заполнения столбца В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.


Лабораторная работа в Exсel. Графы

Рис.3

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

Лабораторная работа в Exсel. Графы

Рис. 4

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

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

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

Задание для самостоятельной работы

Учащиеся выбирают номер варианта согласно списку.

Сеть содержит 10 вершин (рис. 5). Пропускные способности дуг заданы таблицей. Найти максимальный поток между вершинами 1 и 10 (номера вариантов указаны в верхнем левом углу таблицы).

Лабораторная работа в Exсel. Графы

Рис. 5

Лабораторная работа в Exсel. Графы


Лабораторная работа в Exсel. Графы


Лабораторная работа в Exсel. Графы

Лабораторная работа в Exсel. Графы

Лабораторная работа в Exсel. Графы

Лабораторная работа в Exсel. Графы

Лабораторная работа в Exсel. Графы


Лабораторная работа в Exсel. Графы

6

© 2010-2022