Задача линейного программирования при максимизации потока

Лабораторная работа № 13

Тема: Экстремальные задачи на графах (продолжение)

Рассматриваемые вопросы:

- Задача о кратчайшем пути

- Алгоритм Дейкстры

- Задача о максимальном потоке

- Алгоритм Форда-Фалкерсона

1. Задача о кратчайшем пути

Как кратчайшим путем попасть из одной вершины графа в другую? В терминах производственного менеджмента: как кратчайшим путем (и, следовательно, с наименьшим расходом топлива и времени, наиболее дешево) попасть из пункта А в пункт Б?

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

Пример 1.

Рис.1. Исходные данные к задаче о кратчайшем пути

Ситуацию можно описать не только ориентированным графом с весами, приписанными дугам, но и таблицей (табл.1).

Табл.1. Исходные данные к задаче о кратчайшем пути.

Начало дуги	Конец дуги	Время в пути

Спрашивается в задаче: как кратчайшим путем попасть из вершины 1 в вершину 4?

Решение.Введем обозначение: С(Т) - длина кратчайшего пути из вершины 1 в вершину Т. (Поскольку любой путь, который надо рассмотреть, состоит из дуг, а дуг конечное число, и каждая входит не более одного раза, то претендентов на кратчайший путь конечное число, и минимум из конечного числа элементов всегда достигается.) Рассматриваемая задача состоит в вычислении С(4) и указании пути, на котором этот минимум достигается.

Для исходных данных, представленных на рис.1 и в табл.1, в вершину 3 входит только одна стрелка, как раз из вершины 1, и около этой стрелки стоит ее длина, равная 1, поэтому С(3) = 1.

Кроме того, очевидно, что С(1) = 0.

В вершину 4 можно попасть либо из вершины 2, пройдя путь, равный 4, либо из вершины 5, пройдя путь, равный 5. Поэтому справедливо соотношение

С(4) = min {С(2) + 4 ; С(5) + 5}.

Таким образом, проведена реструктуризация задачи - нахождение С(4) сведено к нахождению С(2) и С(5).

В вершину 5 можно попасть либо из вершины 3, пройдя путь, равный 2, либо из вершины 6, пройдя путь, равный 3. Поэтому справедливо соотношение

С(5) = min {С(3) + 2 ; С(6) + 3}.

Мы знаем, что С(3) = 1. Поэтому

С(5) = min {3 ; С(6) + 3}.

Поскольку очевидно, что С(6) - положительное число, то из последнего соотношения вытекает, что С(5) = 3.

В вершину 2 можно попасть либо из вершины 1, пройдя путь, равный 7, либо из вершины 3, пройдя путь, равный 5, либо из вершины 5, пройдя путь, равный 2. Поэтому справедливо соотношение

С(2) = min {С(1) + 7 ; С(3) + 5 ; С(5) + 2}.

Нам известно, что С(1) = 0, С(3) = 1, С(5) = 3. Поэтому

С(2) = min {0 + 7 ; 1 + 5 ; 3 + 2} = 5.

Теперь мы можем найти С(4):

С(4) = min {С(2) + 4 ; С(5) + 5} = min {5 + 4 ; 3 + 5} = 8.

Таким образом, длина кратчайшего пути равна 8. Из последнего соотношения ясно, что в вершину 4 надо идти через вершину 5. Возвращаясь к вычислению С(5), видим, что в вершину 5 надо идти через вершину 3. А в вершину 3 можно попасть только из вершины 1. Итак, кратчайший путь таков:

1 → 3 → 5 → 4 .

Задача о кратчайшем пути для конкретных исходных данных (рис.1 и табл.1) полностью решена.

2. Алгоритм Дейкстры

Найдем кратчайший путь от вершины x_i до всех вершин, используя алгоритм Дейкстры. Он заключается в том, что вершинам графа присваиваются временные метки, которые затем по определенным правилам заменяются на постоянные метки. Будем использовать обозначения:

L* (x_i ) - постоянная метка вершины x_i ,

L^н (x_i )- новая временная метка вершины x_i,

L^с (x_i )- старая временная метка вершины x_i,

R_ij - вес ребра, соединяющего вершины x_i и x_j.

Новая временная метка вычисляется по формуле:

L^н (x_i )= min{ L^с (x_i ), R_{ij +} L* (x_i )}

После этого из всех временных меток выбирается наименьшая, и она становится постоянной меткой. Действия продолжаются, пока не будут найдены постоянные метки для всех вершин графа. Результаты действий на каждом шаге будем заносить в таблицу. В предпоследний столбец заносим вершину, получившую постоянную метку, в последний столбец – величину этой метки (для данного шага).

Пример 2.Найти кратчайшие пути в орграфе от первой вершины ко всем остальным, используя алгоритм Дейкстры. Построить дерево кратчайших путей.

Рис.2. Исходные данные к задаче о кратчайшем пути

Шаг 1. Начальная вершина x₁ , имеет постоянную метку L* (x₁ ) =0, остальные вершины имеют временную метку ∞ .

Шаг 2. Определяем множество последователей вершины Г (x₁)={ x₃ ,x₄, x₅ ,x₂}

Пересчитываем их временные метки по основной формуле. L^н (x₃) =85, L^н(x₄)=75, L^н (x₅ )=57, L^н (x₂) =32.

Берем вершину x₂ с минимальной временной меткой 32, присваиваем этой вершине постоянную метку L* (x₂) = 32 .

Шаг 3. Определяем множество последователей вершины Г (x₂)={ x₃, x₅, x₈}. Пересчитываем их временные метки по основной формуле.

L^н (x₃)= min{ 85, 32+70}=85, L^н (x₅ )= min{ 57, 32+23}= 55, L^н (x₈ )= 32+ 64= 96 . Берем вершину x₅ с минимальной временной меткой 55, присваиваем этой вершине постоянную метку L* (x₅)= 55 .

Шаг 4. Определяем множество последователей вершины Г (x₅)={x₄, x₆, x₇}. Пересчитываем их временные метки по основной формуле.

L^н (x₄ )= min{ 75, 55+10}= 65, L^н (x₆ )= 55+ 11= 66, L^н (x₇ )= 55+20= 75. Берем вершину x₄ с минимальной временной меткой 65, присваиваем этой вершине постоянную метку L* (x₄)=65 .

Шаг 5. Определяем множество последователей вершины Г(x₄)={x₃}. Пересчитываем их временные метки по основной формуле. L^н (x₃ )= min{ 85, 65+18}= 83. Берем вершину x₆ с минимальной временной меткой 66, присваиваем этой вершине постоянную метку L*(x₆)=66 .

Шаг 6. Определяем множество последователей вершины Г(x₆)={x₄, x₇}. Пересчитываем их временные метки по основной формуле. L^н (x₇ )= min{ 75, 66+7}= 73. Берем вершину x₇ с минимальной временной меткой 73, присваиваем этой вершине постоянную метку L*(x₇)=73.

Шаг 7. Определяем множество последователей вершины Г(x₇)={x₈}. Пересчитываем их временные метки по основной формуле. L^н (x₈ )= min{ 96, 73+12}= 85. Берем вершину x₃ с минимальной временной меткой 83, присваиваем этой вершине постоянную метку L*(x₃)=83.

Шаг 8. Определяем множество последователей вершины Г(x₃)={x₆}. Эта вершина уже имеет постоянную метку. Поэтому берем последнюю вершину x₈ с временной меткой 85, присваиваем этой вершине постоянную метку L*(x₈)=85.

Кратчайшие пути найдены, их длина приведена в последних двух столбцах расчетной таблицы. Построим дерево кратчайших путей (ребра дерева обведены жирным) – ребра (1,2), (2,5), (5,4), (4,3), (5,6), (6,7), (7,8).

Рис.3. Решение задачи о кратчайшем пути

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

3. Задача о максимальном потоке

Как (т.е. по каким маршрутам) послать максимально возможное количество грузов из начального пункта в конечный пункт, если пропускная способность путей между пунктами ограничена?

Для решения этой задачи каждой дуге ориентированного графа, соответствующего транспортной системе, должно быть сопоставлено число - пропускная способность этой дуги.

Пример 3.

Рис.4. Исходные данные к задаче о максимальном потоке

Исходные данные о транспортной системе, например, внутризаводской, приведенные на рис.4, можно также задать таблицей (табл.2).

Табл.2. Исходные данные к задаче о максимальном потоке

Пункт отправления	Пункт назначения	Пропускная способность

Решение задачи о максимальном потоке может быть получено из следующих соображений.

Очевидно, максимальная пропускная способность транспортной системы не превышает 6, поскольку не более 6 единиц грузов можно направить из начального пункта 0, а именно, 2 единицы в пункт 1, 3 единицы в пункт 2 и 1 единицу в пункт 3.

Далее надо добиться, чтобы все 6 вышедших из пункта 0 единиц груза достигли конечного пункта 4. Очевидно, 2 единицы груза, пришедшие в пункт 1, можно непосредственно направить в пункт 4. Пришедшие в пункт 2 грузы придется разделить: 2 единицы сразу направить в пункт 4, а 1 единицу - в промежуточный пункт 3 (из-за ограниченной пропускной способности участка между пунктами 2 и 4). В пункт 3 доставлены такие грузы: 1 единица из пункта 0 и 1 единица из пункта 3. Их направляем в пункт 4.

Итак, максимальная пропускная способность рассматриваемой транспортной системы - 6 единиц груза. При этом не используются внутренние участки (ветки) между пунктами 1 и 2, а также между пунктами 1 и 3. Не догружена ветка между пунктами 1 и 4 - по ней направлены 2 единицы груза при пропускной способности в 3 единицы.

Решение можно представить в виде таблицы (табл.3)

Табл.3. Решение задачи о максимальном потоке

Пункт отправления	Пункт назначения	План перевозок	Пропускная способность

Задача линейного программирования при максимизации потока.

Дадим формулировку задачи о максимальном потоке в терминах линейного программирования.

Пусть Х_KM - объем перевозок из пункта К в пункт М.

Согласно рис.4 К = 0,1,2,3, М = 1,2,3,4, причем перевозки возможны лишь в пункт с большим номером. Значит, всего имеется 9 переменных Х_KM, а именно, Х_{01 ,} Х_{02 ,} Х_{03 ,} Х_{12 ,} Х_{13 ,} Х_{14 ,} Х_{23 ,} Х_{24 ,} Х₃₄ .

Задача линейного программирования, нацеленная на максимизацию потока, имеет вид:

F → max ,

Х₀₁ +Х₀₂ +Х₀₃ =F (0)

-Х₀₁ +Х₁₂ +Х₁₃ +Х₁₄ = 0 (1)

-Х₀₂ -Х₁₂ +Х₂₃ +Х₂₄ = 0 (2)

-Х₀₃ -Х₁₃ -Х₂₃ +Х₃₄ = 0 (3)

-Х₁₄ -Х₂₄ -Х₃₄ = - F (4)

Х₀₁ ≤ 2

Х₀₂ ≤ 3

Х₀₃ ≤ 1

Х₁₂ ≤ 4

Х₁₃ ≤ 1

Х₁₄ ≤ 3

Х₂₃ ≤ 1

Х₂₄ ≤ 2

Х₃₄ ≤ 2

Х_КМ ≥ 0 , К, М = 0, 1, 2, 3, 4

F ≥ 0 .

Здесь F - целевая функция, условие (0) описывает вхождение грузов в транспортную систему.

Условия (1) - (3) задают балансовые соотношения для узлов 1- 3 системы. Другими словами, для каждого из внутренних узлов входящий поток грузов равен выходящему потоку, грузы не скапливаются внутри и системы и не "рождаются" в ней.

Условие (4) - это условие "выхода" грузов из системы. Вместе с условием (0) оно составляет балансовое соотношение для системы в целом ("вход" равен "выходу").

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

Затем указана неотрицательность объемов перевозок и целевой функции. Ясно, что последнее неравенство вытекает из вида целевой функции (соотношения (0) или (4)) и неотрицательности объемов перевозок.

Однако последнее неравенство несет некоторую общую информацию - через систему может быть пропущен либо положительный объем грузов, либо нулевой (например, если внутри системы происходит движение по кругу), но не отрицательный (он не имеет экономического смысла, но формальная математическая модель об этом "не знает").

4. Алгоритм Форда–Фалкерсона (алгоритм расстановки пометок)

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

Увеличивающей цепью является цепь из источника в сток, все дуги которой допустимы. Дугу из вершины a в вершину b назовем допустимой, если выполняется одно из следующих условий:

1. f(e) < c(e) и дуга согласованна

2. f(e) > 0 и дуга несогласованна

По увеличивающей цепи можно пустить поток величины Q, где Q = min{q(e_i), 1 ≤ i ≤ l} и q(e) = {с(e) – f(e), если дуга согласована, f(e), если дуга не согласована}. Для того, чтобы увеличить величину потока сети на Q, необходимо увеличить на Q поток на каждой согласованной дуге цепи и уменьшить на каждой несогласованной.

Форд и Фалкерсон (Ford and Fulkerson) доказали, что поток в сети, для которой нельзя построить увеличивающую цепь, является максимальным.

Для нахождения увеличивающей цепи ими был предложен “Метод расстановки пометок”. Процесс расстановки меток начинается в источнике сети и заканчивается в ее стоке. Как только сток оказался помеченным, мы можем говорить о существовании увеличивающей цепи из источника в сток. Метка, “наносимая” на вершины сети, содержит необходимый минимум информации, достаточный для того, чтобы восстановить эту цепь и определить величину, на которую можно изменить поток в ней. Вершина сети может находиться в одном из 3-х состояний: “непомеченная”, “помеченная” и “просмотренная”.