Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Инфоурок / Информатика / Другие методич. материалы / Лабораторная работа в Exсel. "Графы"

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

  • Информатика

Поделитесь материалом с коллегами:

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

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

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

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

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

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

hello_html_m58dd7de.png

Рис.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.


hello_html_6cc9c87f.png

Рис.3

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

hello_html_456fa450.png


Рис. 4

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

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

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

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


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

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

hello_html_4b227b0.png

Рис. 5


hello_html_62edee75.png


hello_html_799b7357.png


hello_html_2fe515b1.png

hello_html_28830d83.png

hello_html_68e9171f.png

hello_html_232b49e3.png

hello_html_m501ed316.png


hello_html_m2e8b52be.png

6


Выберите курс повышения квалификации со скидкой 50%:

Краткое описание документа:

Реализация в 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. Поток, найденный на этом шаге, будет максимальным.

Автор
Дата добавления 23.06.2015
Раздел Информатика
Подраздел Другие методич. материалы
Просмотров461
Номер материала 573653
Получить свидетельство о публикации

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