ЭЛЕКТРОННЫЙ ЛАБОРАТОРНЫЙ ПРАКТИКУМ
ПО УЧЕБНОМУ ПРЕДМЕТУ
"ЭКОНОМИКО-МАТЕМАТИЧЕСКИЕ МЕТОДЫ"
№15. Решение задачи нахождения максимального потока в сети минимальной стоимости с использованием алгоритма Басакера–Гоуэна
Цель: научить находить поток заданной величины минимальной стоимости в сети с применением автоматизированных программных средств.
Оборудование: практикум, тетрадь для лабораторных и практических работ.
Литература:
- Кристофидес Н. Теория графов. Алгоритмический подход. - М.: Мир, 1979. С. 310-329.
- Новиков Ф. А. Дискретная математика для программистов. - СПб.: Питер, 2000. С. 220-226.
- Таха, Хемди. Введение в исследование операций - М.: Издательский дом "Вильямс", 2005. С. 269-283.
Время выполнения: 2 часа.
ВОПРОСЫ ВХОДНОГО КОНТРОЛЯ:
- Дайте определение графа, приведите примеры.
- Объясните понятие сети
- Сформулируйте определение потока.
- Сформулируйте постановку задачи о нахождении поток минимальной стоимости.
- Объясните суть алгоритма Басакера-Гоуэна.
- Объясните суть алгоритма Клейна.
КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ:
Сеть – это связный ориентированный граф G = (V, E) без петель и мультидуг с одним истоком I и одним стоком S, в котором каждой дуге (i, j) приписана пропускная способность bij>=0.
Потоком из истока в сток в сети G назовем множество неотрицательных чисел xij, удовлетворяющих условиям сохранения потока
и ограничениям на дуговые потоки
где переменная v – общая величина потока.
Потоки минимальной стоимости
Пусть дополнительно каждой дуге сети приписан неотрицательный вес cij, равный стоимости транспортировки единицы потока по дуге (i, j). Задача поиска потока заданной мощности v и минимальной стоимости имеет вид
Алгоритм Басакера–Гоуэна
Шаг 0. Положить все дуговые потоки и, следовательно, величину потока v = 0.
Шаг 1. Определить модифицированные дуговые стоимости, зависящие от величины найденного потока
Шаг 2. Найти путь из истока в сток минимальной длины (полагая длину каждой дуги (i, j), равной 
) и увеличить на единицу поток по этому пути. Если величина нового потока равна v, то алгоритм заканчивает работу. В противном случае перейти на шаг 1.
Заметим, что, когда задана неориентированная сеть с выделенными истоком I и стоком S, ориентация ребер, инцидентных I и S, определяется однозначно.
МЕТОДИЧЕСКИЕ УКАЗАНИЯ:
1. Для сети построить поток мощности v = 5 минимальной стоимости. На каждой дуге сети указаны два числа. Первое число означает пропускную способность ребра, а второе число указывает на поток по ребру. Стоимость доставки единицы потока по дуге указана в списке.
|
SA — 2 SC — 3 SD — 5 AB — 4 AC — 8 BC — 4 BT — 6 CD — 9 CE — 3 DE — 7 ET — 9 CT — 3 |
Решение.
СОДЕРЖАНИЕ РАБОТЫ:
Вариант №1
Для сети построить поток мощности 10 минимальной стоимости. На каждой дуге сети указаны два числа. Первое число означает пропускную способность ребра, а второе число указывает на поток по ребру. Стоимость доставки единицы потока по дуге указана в списке.
|
SA — 7 SC — 8 SD — 9 AB — 4 AC — 5 BC — 2 BT — 8 CD — 3 CE — 7 DE — 6 ET — 4 CT — 5 |
Вариант №2
Для сети построить поток мощности 10 минимальной стоимости. На каждой дуге сети указаны два числа. Первое число означает пропускную способность ребра, а второе число указывает на поток по ребру. Стоимость доставки единицы потока по дуге указана в списке.
|
SA — 6 SC — 8 SD — 3 AB — 4 AC — 4 BC — 2 BT — 7 CD — 3 CE — 6 DE — 6 ET — 4 CT — 5 |
Вариант №3
Для сети построить поток мощности 10 минимальной стоимости. На каждой дуге сети указаны два числа. Первое число означает пропускную способность ребра, а второе число указывает на поток по ребру. Стоимость доставки единицы потока по дуге указана в списке.
|
SA — 7 SC — 9 SD — 2 AB — 4 AC — 5 BC — 4 BT — 8 CD — 7 CE — 7 DE — 6 ET — 2 CT — 4 |
Вариант №4
Для сети построить поток мощности 10 минимальной стоимости. На каждой дуге сети указаны два числа. Первое число означает пропускную способность ребра, а второе число указывает на поток по ребру. Стоимость доставки единицы потока по дуге указана в списке.
|
SA — 2 SC — 6 SD — 9 AB — 5 AC — 6 BC — 7 BT — 8 CD — 3 CE — 7 DE — 4 ET — 4 CT — 3 |
Вариант №5
Для сети построить поток мощности 10 минимальной стоимости. На каждой дуге сети указаны два числа. Первое число означает пропускную способность ребра, а второе число указывает на поток по ребру. Стоимость доставки единицы потока по дуге указана в списке.
|
SA — 6 SC — 3 SD — 4 AB — 4 AC — 5 BC — 2 BT — 5 CD — 3 CE — 7 DE — 6 ET — 7 CT — 9 |
Вариант №6
Для сети построить поток мощности 10 минимальной стоимости. На каждой дуге сети указаны два числа. Первое число означает пропускную способность ребра, а второе число указывает на поток по ребру. Стоимость доставки единицы потока по дуге указана в списке.
|
SA — 4 SC — 8 SD — 2 AB — 4 AC — 5 BC — 9 BT — 8 CD — 7 CE — 7 DE — 2 ET — 4 CT — 5 |
Вариант №7
Для сети построить поток мощности 10 минимальной стоимости. На каждой дуге сети указаны два числа. Первое число означает пропускную способность ребра, а второе число указывает на поток по ребру. Стоимость доставки единицы потока по дуге указана в списке.
|
SA — 3 SC — 4 SD — 9 AB — 6 AC — 8 BC — 6 BT — 4 CD — 3 CE — 7 DE — 3 ET — 7 CT — 9 |
Вариант №8
Для сети построить поток мощности 10 минимальной стоимости. На каждой дуге сети указаны два числа. Первое число означает пропускную способность ребра, а второе число указывает на поток по ребру. Стоимость доставки единицы потока по дуге указана в списке.
|
SA — 8 SC — 9 SD — 6 AB — 8 AC — 2 BC — 5 BT — 5 CD — 4 CE — 7 DE — 6 ET — 7 CT — 6 |
Вариант №9
Для сети построить поток мощности 10 минимальной стоимости. На каждой дуге сети указаны два числа. Первое число означает пропускную способность ребра, а второе число указывает на поток по ребру. Стоимость доставки единицы потока по дуге указана в списке.
|
SA — 6 SC — 3 SD — 5 AB — 4 AC — 5 BC — 2 BT — 5 CD — 9 CE — 7 DE — 5 ET — 7 CT — 9 |
Вариант №10
Для сети построить поток мощности 10 минимальной стоимости. На каждой дуге сети указаны два числа. Первое число означает пропускную способность ребра, а второе число указывает на поток по ребру. Стоимость доставки единицы потока по дуге указана в списке.
|
SA — 7 SC — 5 SD — 9 AB — 5 AC — 3 BC — 7 BT — 8 CD — 9 CE — 7 DE — 8 ET — 4 CT — 3 |
Вариант №11
Для сети построить поток мощности 10 минимальной стоимости. На каждой дуге сети указаны два числа. Первое число означает пропускную способность ребра, а второе число указывает на поток по ребру. Стоимость доставки единицы потока по дуге указана в списке.
|
SA — 3 SC — 6 SD — 9 AB — 6 AC — 6 BC — 8 BT — 8 CD — 6 CE — 7 DE — 2 ET — 4 CT — 5 |
Вариант №12
Для сети построить поток мощности 10 минимальной стоимости. На каждой дуге сети указаны два числа. Первое число означает пропускную способность ребра, а второе число указывает на поток по ребру. Стоимость доставки единицы потока по дуге указана в списке.
|
SA — 2 SC — 7 SD — 7 AB — 9 AC — 3 BC — 5 BT — 7 CD — 3 CE — 4 DE — 4 ET — 7 CT — 8 |
Вариант №13
Для сети построить поток мощности 10 минимальной стоимости. На каждой дуге сети указаны два числа. Первое число означает пропускную способность ребра, а второе число указывает на поток по ребру. Стоимость доставки единицы потока по дуге указана в списке.
|
SA — 2 SC — 6 SD — 7 AB — 5 AC — 6 BC — 7 BT — 5 CD — 3 CE — 7 DE — 6 ET — 4 CT — 3 |
Вариант №14
Для сети построить поток мощности 10 минимальной стоимости. На каждой дуге сети указаны два числа. Первое число означает пропускную способность ребра, а второе число указывает на поток по ребру. Стоимость доставки единицы потока по дуге указана в списке.
|
SA — 8 SC — 5 SD — 9 AB — 4 AC — 4 BC — 9 BT — 8 CD — 4 CE — 7 DE — 4 ET — 8 CT — 7 |
Вариант №15
Для сети построить поток мощности 10 минимальной стоимости. На каждой дуге сети указаны два числа. Первое число означает пропускную способность ребра, а второе число указывает на поток по ребру. Стоимость доставки единицы потока по дуге указана в списке.
|
SA — 6 SC — 6 SD — 5 AB — 5 AC — 6 BC — 7 BT — 8 CD — 9 CE — 7 DE — 8 ET — 4 CT — 6 |
Вариант №16
Для сети построить поток мощности 10 минимальной стоимости. На каждой дуге сети указаны два числа. Первое число означает пропускную способность ребра, а второе число указывает на поток по ребру. Стоимость доставки единицы потока по дуге указана в списке.
|
SA — 7 SC — 4 SD — 8 AB — 5 AC — 3 BC — 7 BT — 2 CD — 9 CE — 7 DE — 8 ET — 4 CT — 6 |
Вариант №17
Для сети построить поток мощности 10 минимальной стоимости. На каждой дуге сети указаны два числа. Первое число означает пропускную способность ребра, а второе число указывает на поток по ребру. Стоимость доставки единицы потока по дуге указана в списке.
|
SA — 6 SC — 3 SD — 9 AB — 4 AC — 8 BC — 6 BT — 8 CD — 9 CE — 7 DE — 7 ET — 6 CT — 3 |
Вариант №18
Для сети построить поток мощности 10 минимальной стоимости. На каждой дуге сети указаны два числа. Первое число означает пропускную способность ребра, а второе число указывает на поток по ребру. Стоимость доставки единицы потока по дуге указана в списке.
|
SA — 5 SC — 5 SD — 7 AB — 6 AC — 7 BC — 7 BT — 9 CD — 5 CE — 9 DE — 8 ET — 4 CT — 2 |
ВОПРОСЫ ВЫХОДНОГО КОНТРОЛЯ:
- Дайте определение графа, приведите примеры.
- Объясните понятие сети
- Сформулируйте определение потока.
- Сформулируйте постановку задачи о нахождении потокa минимальной стоимости.
- Объясните суть алгоритма Басакера-Гоуэна.
ДОМАШНЕЕ ЗАДАНИЕ:
Выучить алгоритм Басакера-Гоуэна.