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

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

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

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

Постановка задачи

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

• Сеть состоит из узлов, соединенных направленными дугами;
• Каждая дуга имеет ограниченную пропускную способность;
• Поток начинается в истоке (узел 0) и заканчивается в стоке (узел 4);
• Цель - найти максимально возможный поток от истока к стоку.

Дуги графа и их пропускные способности:

• 0 → 1 (20 ед.)
• 0 → 2 (30 ед.)
• 0 → 3 (10 ед.)
• 1 → 2 (40 ед.)
• 1 → 4 (30 ед.)
• 2 → 3 (10 ед.)
• 2 → 4 (20 ед.)
• 3 → 2 (5 ед.)
• 3 → 4 (20 ед.)

Решение задачи

Далее поэтапно рассмотрим реализацию решения задачи максимального потока.

1. Выбор модели

Для решения задачи максимального потока мы воспользуемся специализированной моделью. МодельМаксимальногоПотока специально предназначена для решения подобных задач.

2. Создание модели

Инициализируется объект модели максимального потока.

Модель = О2
    .Модели()
    .МодельМаксимальногоПотока()
    .СоздатьМодель();

3. Ввод данных

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

// Входные данные	
УзелИсток 	= 0;
УзелСток 	= 4;

// Входные данные дуг (хвост, голова, максимальный поток)
ДанныеДуг = Новый Массив;
ДанныеДуг.Добавить("0, 1, 20");
ДанныеДуг.Добавить("0, 2, 30");
ДанныеДуг.Добавить("0, 3, 10");
ДанныеДуг.Добавить("1, 2, 40");
ДанныеДуг.Добавить("1, 4, 30");
ДанныеДуг.Добавить("2, 3, 10");
ДанныеДуг.Добавить("2, 4, 20");
ДанныеДуг.Добавить("3, 2, 5");
ДанныеДуг.Добавить("3, 4, 20");

// Преобразуем входные данные в числовой формат
Для К = 0 По ДанныеДуг.ВГраница() Цикл
    ДанныеДуг[К] = О2.Утилиты().МассивЧиселИзСтроки(ДанныеДуг[К]);
КонецЦикла;

Для преобразования данных в числовой формат мы воспользовались вспомогательной функцией МассивЧиселИзСтроки.

4. Добавление дуг

Добавим дуги в созданную модель и сохраним их в массиве для дальнейшего вывода результатов.

// Добавляем дуги в модель
Дуги = Новый Массив;
Для К = 0 По ДанныеДуг.ВГраница() Цикл
    Дуга = Модель.Дуга(ДанныеДуг[К][0], ДанныеДуг[К][1], ДанныеДуг[К][2]);
    Дуги.Добавить(Дуга);
КонецЦикла;

5. Установка истока и строка

Укажем в модели узлы, которые являются истоком и стоком.

// Устанавливаем исток и сток
Модель.УстановитьИсток(УзелИсток);
Модель.УстановитьСток(УзелСток);

6. Решение модели

Для получения решения достаточно вызвать метод Решить объекта модели.

// Запускаем поиск решения
Решение = Модель.Решить();

7. Вывод результатов

// Вывод результатов
Статус = Решение.Статус();
Если Не Решение.РешениеНайдено() Тогда
    Сообщить("Обнаружена проблема с входными данными.");
    Сообщить("Статус: " + Статус);
    Возврат;
КонецЕсли;

// Выводим максимальный поток
Сообщить("Максимальный поток: " + Строка(Решение.ОптимальныйПоток()));

// Выводим информацию о потоках по дугам
Сообщить("Потоки дуг:");

// Получаем потоки решения для всех дуг
Для Каждого Дуга Из Дуги Цикл
    ПотокДуги = Решение.ЗначениеПотока(Дуга);
    
    Сообщить(
        СтрШаблон(
            "%1 → %2  %3 из %4",
            Дуга.Хвост,
            Дуга.Голова,
            ПотокДуги,
            Дуга.МаксимальныйПоток	
        )
    );
КонецЦикла; 

Для получения расчетного значения потока мы использовали метод ЗначениеПотока объекта решения.

Полный код решения задачи

Ниже представлен полный код решения. Вы также можете скачать пример в виде готовой обработки.

// Создаем объект модели
Модель = О2
    .Модели()
    .МодельМаксимальногоПотока()
    .СоздатьМодель();
    
// Входные данные	
УзелИсток 	= 0;
УзелСток 	= 4;

// Входные данные дуг (хвост, голова, максимальный поток)
ДанныеДуг = Новый Массив;
ДанныеДуг.Добавить("0, 1, 20");
ДанныеДуг.Добавить("0, 2, 30");
ДанныеДуг.Добавить("0, 3, 10");
ДанныеДуг.Добавить("1, 2, 40");
ДанныеДуг.Добавить("1, 4, 30");
ДанныеДуг.Добавить("2, 3, 10");
ДанныеДуг.Добавить("2, 4, 20");
ДанныеДуг.Добавить("3, 2, 5");
ДанныеДуг.Добавить("3, 4, 20");

// Преобразуем входные данные в числовой формат
Для К = 0 По ДанныеДуг.ВГраница() Цикл
    ДанныеДуг[К] = О2.Утилиты().МассивЧиселИзСтроки(ДанныеДуг[К]);
КонецЦикла;

// Добавляем дуги в модель
Дуги = Новый Массив();
Для К = 0 По ДанныеДуг.ВГраница() Цикл
    Дуга = Модель.Дуга(ДанныеДуг[К][0], ДанныеДуг[К][1], ДанныеДуг[К][2]);
    Дуги.Добавить(Дуга);
КонецЦикла;

// Устанавливаем исток и сток
Модель.УстановитьИсток(УзелИсток);
Модель.УстановитьСток(УзелСток);

// Запускаем поиск решения
Решение = Модель.Решить();

// Вывод результатов
Статус = Решение.Статус();
Если Не Решение.РешениеНайдено() Тогда
    Сообщить("Обнаружена проблема с входными данными.");
    Сообщить("Статус: " + Статус);
    Возврат;
КонецЕсли;

// Выводим максимальный поток
Сообщить("Максимальный поток: " + Строка(Решение.ОптимальныйПоток()));

// Выводим информацию о потоках по дугам
Сообщить("Потоки дуг:");

// Получаем потоки решения для всех дуг
Для Каждого Дуга Из Дуги Цикл
    ПотокДуги = Решение.ЗначениеПотока(Дуга);
    
    Сообщить(
        СтрШаблон(
            "%1 → %2  %3 из %4",
            Дуга.Хвост,
            Дуга.Голова,
            ПотокДуги,
            Дуга.МаксимальныйПоток	
        )
    );
КонецЦикла;  

  Скачать пример