3. Оптимизация на графах
Графы очень удобны для представления сетей. Оптимизационные задачи на сети можно описать следующими четырьмя типами моделей:
Минимизация сети.
Нахождение кратчайшего маршрута.
Определение максимального потока.
Минимизация стоимости потока в сети с ограниченными пропускными способностями коммуникаций.
Минимизация сети
Задача минимизации сети состоит в нахождении ребер, соединяющих все узлы сети и имеющих минимальную суммарную длину (решение задачи не должно содержать циклов).
Пример. Планируется создание кабельной сети (рис.4), для обслуживания нескольких районов-новостроек. Числа на ребрах указывает длину кабеля. Узел 1 представляет центр, остальные узлы (2-6) соответствуют пяти новостройкам. Нужно найти такие ребра, которые потребуют кабель минимальной длины для связи (прямой или через другие пункты) всех районов с центром.
Рис.4 Рис.5
На
первом этапе определим два множества.
Первое – с уже связанным узлами
(в которое мы пока включим только узел
1), второе – с еще не связанными узлами
.
Алгоритм минимизации:
Из множества
выбираем узел, ближайший к одному из
узлов множества
и переносим его во множество
.
(
;
)К выбранному узлу проводим соединение на графе.
Переходим к п.1.
В результате получим граф рис.5 с минимальной длиной ребер.
Задача о кратчайшем пути
Задача о кратчайшем пути состоит в нахождении связанных между собой дорог на транспортной сети, которые в совокупности имеют минимальную длину от исходного пункта до пункта назначения.
Алгоритм для сетей без циклов.
Рис.6
Пусть
имеется цепь рис.6 Необходимо найти
кратчайший маршрут между пунктами 1 и
7. Введем следующие обозначения:
– расстояние между i-ым
и j-ым
узлами;
– кратчайшее расстояние от узла 1 до
j-го
узла.
Общая формула для вычисления имеет вид
Решение для графа рис.6:
Очевидно,
что
.
Для
узлов 2 и 3 получим: 
;
.
Узел
4:
=
= 7.
Узлы
5 и 6: 
;
.
Узел
7: 
.
Минимально расстояние равно 13 и соответствующий маршрут 1257.
Алгоритм для сетей с циклами.
В этом случае алгоритм несколько сложнее.
Шаг
1. Пусть
– сумма длин дуг, образующих цепь,
ведущую из узла 1 в узел j.
Положим
и
если
.
При условии, что i
и j
соединены дугой, величина
определяется как
.
Процесс
начинается с
и
.
Шаг 2. Положить .
а)
Вычислить
для всех j.
б)
Если
для всех j,
то между узлами i
и j
не существует более короткого пути.
Если
,
перейти к п.(г). Иначе положить
и перейти к п.(а).
в)
Если
,
вычислить новые значения
и
,
используя формулу
.
Заменить
и
для
на
.
Если
,
перейти к п.(г); в противном случае
положить
и перейти к п.(а).
г) Если значение изменялось в п.(в), повторить шаг 2, используя измененное значение. В противном случае перейти к шагу 3.
Шаг
3. Полученные
значения
определяют кратчайшие расстояния между
узлами 1 и
.
Для получения соответствующих цепей
последняя дуга
в цепи
должна удовлетворять условию
.
После
определения
предпоследняя вершина
должна удовлетворять равенству
.
Процесс продолжается пока не будет достигнут узел 1.
Задача о максимальном потоке
Предположим,
что каждая дуга сети обладает пропускными
способностями в обоих направлениях,
которые определяют максимальное
количество потока, проходящего по
заданной дуге. Ориентированная дуга
соответствует нулевой пропускной
способности в запрещенном направлении.
Пропускные способности
можно представить в матричной форме.
Шаг
1. Найти цепь,
соединяющую s
с t
(источник и приемник), по которой поток
принимает положительное значение в
направлении
.Если
такой цепи не существует, перейти к шагу
3. В противном случае перейти к шагу 2.
Шаг
2. Пусть
(
)
– пропускные способности дуг цепи
в направлении
(
)
и
.
Матрицу пропускных способностей изменить следующим образом:
а) вычесть из всех ;
б) прибавить ко всем .
Заменить текущую матрицу на вновь полученную и перейти к шагу 1.
Шаг
3. Найти
максимальный поток в сети. Пусть
– исходная матрица пропускных
способностей,
– последняя полученная в результате
модификаций матрица. Оптимальный поток
в дугах задается как
.
Максимальный поток из s в t равен
.
Задачи
Решите задачу о минимизации сети для графа
а) Рис.7.
б) Рис.8.
в) Рис.9.
г) Рис.10
Рис.7 Рис.8 Рис.9 Рис.10
Для графа рис.6 решите задачу о нахождении кратчайшего пути.
а) От узла 1 к узлу 5.
б) От узла 1 к узлу 6.
Решите задачу о нахождении кратчайшего пути для графа:
а) Рис.11.
б) Рис.12.
в) Рис.13.
г) Рис.14.
Рис.11 Рис.12
Рис.13 Рис.14