Задача назначения как задача потока минимальной стоимости

Задача назначения (Assignment Problem) — классическая задача комбинаторной оптимизации, в которой требуется оптимально распределить исполнителей (работников) по задачам таким образом, чтобы минимизировать общую стоимость выполнения всех задач. Каждый работник может выполнить только одну задачу, и каждая задача должна быть выполнена ровно одним работником.

Эту задачу можно решать разными способами. Например, для решения этой задачи мы также использовали модель ограничений, что особенно удобно при работе с булевыми переменными и логическими ограничениями. Альтернативный подход — формулировка задачи как задачи потока минимальной стоимости (Minimum Cost Flow), представленный в данном примере. Такой подход естественным образом моделирует задачу через направленный граф и часто работает быстрее для задач с групповыми ограничениями, такими как распределение работников по бригадам или командам.

Преимущества подхода через поток минимальной стоимости:

• Гибкость: легко добавлять дополнительные ограничения (бригады, квоты, приоритеты);
• Масштабируемость: эффективно работает с большими объёмами данных;
• Унификация: единый подход для решения широкого класса задач распределения ресурсов.

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

Имеется 6 работников, разделённых на две бригады, и 4 задачи, которые необходимо выполнить.

• Бригада 1: работники 1, 3, 5;
• Бригада 2: работники 2, 4, 6;
• Каждый работник может выполнить только одну задачу;
• Каждая задача должна быть выполнена ровно одним работником;
• Каждая бригада должна выполнить ровно 2 задачи (балансировка нагрузки);
• Стоимость назначения работника на задачу известна.

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

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

Для решения задачи назначения с учётом бригад используется специализированная модель потока минимальной стоимости. Эта модель естественным образом представляет задачу назначения в виде направленного графа, где поток по дугам соответствует назначениям работников на задачи.

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

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

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

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

Задача представляется в виде направленного графа со следующими узлами:

• Узел 0 — исток (источник потока);
• Узлы 11, 12 — промежуточные узлы для бригад 1 и 2;
• Узлы 1-6 — работники;
• Узлы 7-10 — задачи;
• Узел 13 — сток (приёмник потока).

// Входные данные дуг (хвост, голова, максимальный поток и стоимости)
ДанныеДуг = Новый Массив;

ДанныеДуг.Добавить("0, 11, 2, 0");  // Исток → Бригада 1 (макс. 2 задачи)
ДанныеДуг.Добавить("0, 12, 2, 0");  // Исток → Бригада 2 (макс. 2 задачи)

// Бригада 1 → Работники бригады 1
ДанныеДуг.Добавить("11, 1, 1, 0");
ДанныеДуг.Добавить("11, 3, 1, 0");
ДанныеДуг.Добавить("11, 5, 1, 0");

// Бригада 2 → Работники бригады 2
ДанныеДуг.Добавить("12, 2, 1, 0");
ДанныеДуг.Добавить("12, 4, 1, 0");
ДанныеДуг.Добавить("12, 6, 1, 0");

// Работники → Задачи (с указанием стоимости)
// Работник 1
ДанныеДуг.Добавить("1, 7, 1, 90");
ДанныеДуг.Добавить("1, 8, 1, 76");
ДанныеДуг.Добавить("1, 9, 1, 75");
ДанныеДуг.Добавить("1, 10, 1, 70");

// Работник 2
ДанныеДуг.Добавить("2, 7, 1, 35");
ДанныеДуг.Добавить("2, 8, 1, 85");
ДанныеДуг.Добавить("2, 9, 1, 55");
ДанныеДуг.Добавить("2, 10, 1, 65");

// Работник 3
ДанныеДуг.Добавить("3, 7, 1, 125");
ДанныеДуг.Добавить("3, 8, 1, 95");
ДанныеДуг.Добавить("3, 9, 1, 90");
ДанныеДуг.Добавить("3, 10, 1, 105");

// Работник 4
ДанныеДуг.Добавить("4, 7, 1, 45");
ДанныеДуг.Добавить("4, 8, 1, 110");
ДанныеДуг.Добавить("4, 9, 1, 95");
ДанныеДуг.Добавить("4, 10, 1, 115");

// Работник 5
ДанныеДуг.Добавить("5, 7, 1, 60");
ДанныеДуг.Добавить("5, 8, 1, 105");
ДанныеДуг.Добавить("5, 9, 1, 80");
ДанныеДуг.Добавить("5, 10, 1, 75");

// Работник 6
ДанныеДуг.Добавить("6, 7, 1, 45");
ДанныеДуг.Добавить("6, 8, 1, 65");
ДанныеДуг.Добавить("6, 9, 1, 110");
ДанныеДуг.Добавить("6, 10, 1, 95");

// Задачи → Сток
ДанныеДуг.Добавить("7, 13, 1, 0");
ДанныеДуг.Добавить("8, 13, 1, 0");
ДанныеДуг.Добавить("9, 13, 1, 0");
ДанныеДуг.Добавить("10, 13, 1, 0");

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

Определение бригад и параметров:

Бригада1        = О2.Утилиты().МассивЧиселИзСтроки("1, 3, 5");
Бригада2        = О2.Утилиты().МассивЧиселИзСтроки("2, 4, 6");

Исток           = 0;
Сток            = 13;
КоличествоЗадач = 4;

Вклады узлов (supply/demand). В задаче потока каждый узел имеет вклад:

• Положительный вклад (supply) означает, что узел является источником потока;
• Отрицательный вклад (demand) означает, что узел является потребителем потока;
• Нулевой вклад означает транзитный узел.

// Вклады узлов: исток производит 4 единицы потока, сток потребляет 4
ВкладыУзлов = О2.Утилиты().МассивЧиселИзСтроки("4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -4");

Здесь:

• Узел 0 (исток): +4 — производит 4 единицы потока (по числу задач);
• Узлы 1-12: 0 — транзитные узлы;
• Узел 13 (сток): -4 — потребляет 4 единицы потока.

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

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

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

Метод Дуга принимает четыре параметра:

1. Хвост (начальный узел);
2. Голова (конечный узел);
3. Максимальный поток;
4. Стоимость единицы потока.

5. Установка вкладов узлов

Для каждого узла устанавливается его вклад в сеть (производство или потребление потока).

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

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

Запускается процесс поиска оптимального решения.

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

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

Результаты извлекаются из решения и выводятся в читаемом формате.

// Вывод результатов
СтатусРешения        = Решение.Статус();
ОптимальнаяСтоимость = Решение.ОптимальнаяСтоимость();

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

Сообщение = "Оптимальное назначение работников на задачи" + Символы.ПС + Символы.ПС;
Сообщение = Сообщение + "Итоговая стоимость: " + ОптимальнаяСтоимость + Символы.ПС + Символы.ПС;

Для Каждого Дуга Из Дуги Цикл 
    // Пропускаем дуги от истока и к стоку
    Если Дуга.Хвост <> Исток И Дуга.Голова <> Сток Тогда
        ПотокДуги           = Решение.ЗначениеПотока(Дуга);
        СтоимостьПотокаДуги = ПотокДуги * Дуга.Стоимость;
        
        // Выводим только дуги с ненулевой стоимостью (назначения)
        Если СтоимостьПотокаДуги > 0 Тогда
            Сообщение = Сообщение + СтрШаблон(
                "Работник %1 назначен на задачу %2. Стоимость: %3%4",
                Дуга.Хвост,
                Дуга.Голова,
                Дуга.Стоимость,
                Символы.ПС
            );
        КонецЕсли;
    КонецЕсли;    
КонецЦикла;

Сообщить(Сообщение);

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

• Каждый работник назначен максимум на одну задачу (максимальный поток дуг от работников = 1);
• Каждая задача выполняется одним работником (максимальный поток дуг к задачам = 1);
• Каждая бригада выполняет ровно 2 задачи (максимальный поток дуг от истока к узлам бригад = 2).

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

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

// Создание модели потока минимальной стоимости
Модель = О2
    .Модели()
    .МодельПотокаМинимальнойСтоимости()
    .СоздатьМодель();
    
// Входные данные дуг (хвост, голова, максимальный поток и стоимости)
ДанныеДуг = Новый Массив;

ДанныеДуг.Добавить("0, 11, 2, 0");
ДанныеДуг.Добавить("0, 12, 2, 0");
ДанныеДуг.Добавить("11, 1, 1, 0");
ДанныеДуг.Добавить("11, 3, 1, 0");
ДанныеДуг.Добавить("11, 5, 1, 0");
ДанныеДуг.Добавить("12, 2, 1, 0");
ДанныеДуг.Добавить("12, 4, 1, 0");
ДанныеДуг.Добавить("12, 6, 1, 0");
ДанныеДуг.Добавить("1, 7, 1, 90");
ДанныеДуг.Добавить("1, 8, 1, 76");
ДанныеДуг.Добавить("1, 9, 1, 75");
ДанныеДуг.Добавить("1, 10, 1, 70");
ДанныеДуг.Добавить("2, 7, 1, 35");
ДанныеДуг.Добавить("2, 8, 1, 85");
ДанныеДуг.Добавить("2, 9, 1, 55");
ДанныеДуг.Добавить("2, 10, 1, 65");
ДанныеДуг.Добавить("3, 7, 1, 125");
ДанныеДуг.Добавить("3, 8, 1, 95");
ДанныеДуг.Добавить("3, 9, 1, 90");
ДанныеДуг.Добавить("3, 10, 1, 105");
ДанныеДуг.Добавить("4, 7, 1, 45");
ДанныеДуг.Добавить("4, 8, 1, 110");
ДанныеДуг.Добавить("4, 9, 1, 95");
ДанныеДуг.Добавить("4, 10, 1, 115");
ДанныеДуг.Добавить("5, 7, 1, 60");
ДанныеДуг.Добавить("5, 8, 1, 105");
ДанныеДуг.Добавить("5, 9, 1, 80");
ДанныеДуг.Добавить("5, 10, 1, 75");
ДанныеДуг.Добавить("6, 7, 1, 45");
ДанныеДуг.Добавить("6, 8, 1, 65");
ДанныеДуг.Добавить("6, 9, 1, 110");
ДанныеДуг.Добавить("6, 10, 1, 95");
ДанныеДуг.Добавить("7, 13, 1, 0");
ДанныеДуг.Добавить("8, 13, 1, 0");
ДанныеДуг.Добавить("9, 13, 1, 0");
ДанныеДуг.Добавить("10, 13, 1, 0");

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

// Входные данные
Бригада1        = О2.Утилиты().МассивЧиселИзСтроки("1, 3, 5");
Бригада2        = О2.Утилиты().МассивЧиселИзСтроки("2, 4, 6");

Исток           = 0;
Сток            = 13;
КоличествоЗадач = 4;

ВкладыУзлов     = О2.Утилиты().МассивЧиселИзСтроки("4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -4");

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

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

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

// Вывод результатов
СтатусРешения        = Решение.Статус();
ОптимальнаяСтоимость = Решение.ОптимальнаяСтоимость();

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

Сообщение = "Оптимальное назначение работников на задачи" + Символы.ПС + Символы.ПС;
Сообщение = Сообщение + "Итоговая стоимость: " + ОптимальнаяСтоимость + Символы.ПС + Символы.ПС;

Для Каждого Дуга Из Дуги Цикл 
    Если Дуга.Хвост <> Исток И Дуга.Голова <> Сток Тогда
        ПотокДуги           = Решение.ЗначениеПотока(Дуга);
        СтоимостьПотокаДуги = ПотокДуги * Дуга.Стоимость;
        
        Если СтоимостьПотокаДуги > 0 Тогда
            Сообщение = Сообщение + СтрШаблон(
                "Работник %1 назначен на задачу %2. Стоимость: %3%4",
                Дуга.Хвост,
                Дуга.Голова,
                Дуга.Стоимость,
                Символы.ПС
            );
        КонецЕсли;
    КонецЕсли;    
КонецЦикла;

Сообщить(Сообщение);

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