Задача назначения
В данном разделе рассматривается классическая задача назначения (Assignment Problem) — одна из фундаментальных задач комбинаторной оптимизации. Суть задачи заключается в оптимальном распределении работников по задачам таким образом, чтобы минимизировать общие затраты или максимизировать общую эффективность.
Задача назначения встречается во многих практических ситуациях: распределение сотрудников по проектам, азначение водителей на маршруты, распределение станков по заказам, назначение преподавателей на курсы. В каждом случае известны индивидуальные характеристики выполнения работы — например, время выполнения, стоимость или качество работы конкретного исполнителя на конкретной задаче.
Ключевая особенность задачи — взаимная однозначность: каждый работник может выполнять не более одной задачи, а каждая задача должна быть выполнена ровно одним работником. Это создаёт структуру идеального паросочетания между множествами работников и задач.
Постановка задачи
Имеется 5 работников и 4 задачи. Для каждой комбинации "работник-задача" известны затраты на выполнение.
- Каждый работник может быть назначен не более чем на одну задачу;
- Каждая задача должна быть выполнена ровно одним работником;
- Требуется минимизировать суммарные затраты на выполнение всех задач
Решение задачи
1. Выбор модели
Поскольку данная задача в матрице затрат содержит вещественные значения, целесообразно выбрать ЛинейнаяСмешанноЦелочисленнаяМодель, так как она позволяет точно учитывать дробные значения в расчетах и эффективно сочетает линейное программирование с целочисленной оптимизацией.
2. Создание модели
Инициализируется объект линейной смешанно-целочисленной модели.
// Создание линейной смешанно-целочисленной модели
Модель = О2.Модели().ЛинейнаяСмешанноЦелочисленнаяМодель().СоздатьМодель();
3. Ввод данных
Данные о затратах представляются в виде матрицы, где строки соответствуют работникам, а столбцы — задачам.
// Вводим данные
ЗатратыНаЗадачу = Новый Массив();
ЗатратыНаЗадачу.Добавить("90.5, 80.2, 75.0, 70.3");
ЗатратыНаЗадачу.Добавить("35.1, 85.0, 55.5, 65.7");
ЗатратыНаЗадачу.Добавить("125.0, 95.3, 90.1, 95.0");
ЗатратыНаЗадачу.Добавить("45.2, 110.5, 95.0, 115.1");
ЗатратыНаЗадачу.Добавить("50.0, 100.2, 90.5, 100.0");
// Оцифровываем массивы входных данных с помощью вспомогательной функции
Затраты = Новый Массив(ЗатратыНаЗадачу.Количество());
Для К = 0 По ЗатратыНаЗадачу.Количество() - 1 Цикл
Затраты[К] = О2.Утилиты().МассивЧиселИзСтроки(ЗатратыНаЗадачу[К]);
КонецЦикла;
КоличествоРаботников = Затраты.Количество();
КоличествоЗадач = Затраты[0].Количество();
4. Регистрация переменных
Для каждой пары (работник, задача) создаётся булева переменная, которая равна 1, если работник назначен на эту задачу, и 0 в противном случае.
// Регистрируем булевы переменные для каждой комбинации (работник, задача)
РаботникиЗадач = Новый Массив(КоличествоРаботников);
Для Р = 0 По КоличествоРаботников - 1 Цикл
РаботникиЗадач[Р] = Модель.МассивБулевыхПеременных(КоличествоЗадач);
КонецЦикла;
5. Описание ограничений
Ограничение на работников. Каждый работник может выполнять не более одной задачи — сумма всех его назначений не превышает 1.
// Ограничение: каждый работник выполняет не более одной задачи
Для Р = 0 По КоличествоРаботников - 1 Цикл
СуммаЗадач = Модель.Выражения().Сумма(РаботникиЗадач[Р]);
Модель.Ограничения().ЗначениеМеньшеИлиРавно(СуммаЗадач, 1);
КонецЦикла;
Ограничение на задачи. Каждая задача должна быть выполнена ровно одним работником — сумма назначений на задачу равна 1:
// Ограничение: каждая задача выполняется ровно одним работником
Для З = 0 По КоличествоЗадач - 1 Цикл
РаботникиНаЗадачу = Новый Массив(КоличествоРаботников);
Для Р = 0 По КоличествоРаботников - 1 Цикл
РаботникиНаЗадачу[Р] = РаботникиЗадач[Р][З];
КонецЦикла;
СуммаРаботников = Модель.Выражения().Сумма(РаботникиНаЗадачу);
Модель.Ограничения().ЗначениеРавно(СуммаРаботников, 1);
КонецЦикла;
6. Описание целевой функции
Целевая функция представляет собой сумму произведений переменных назначения на соответствующие затраты. Использование метода ДобавитьТерм позволяет добавлять слагаемые вида (переменная × коэффициент). Минимизация данной функции обеспечивает поиск назначения с наименьшими общими затратами.
// Целевая функция: минимизируем общие затраты
ОбщиеЗатраты = Модель.Выражения().СоздатьПостроительВыражений();
Для Р = 0 По КоличествоРаботников - 1 Цикл
Для З = 0 По КоличествоЗадач - 1 Цикл
ОбщиеЗатраты.ДобавитьТерм(РаботникиЗадач[Р][З], Затраты[Р][З]);
КонецЦикла;
КонецЦикла;
Модель.Минимизировать(ОбщиеЗатраты.ПолучитьВыражение());
7. Решение модели
Для получения решения достаточно вызвать метод Решить объекта модели.
// Решение модели
Решение = Модель.Решить();
8. Вывод результатов
Результаты выводятся с указанием назначений и общей стоимости.
// Вывод результатов
Если Решение.РешениеНайдено() Тогда
ФорматВывода = "ЧДЦ=2; ЧН=0; ЧГ=0";
ЗначениеЗатрат = Решение.ЗначениеВыражения(ОбщиеЗатраты.ПолучитьВыражение());
Сообщение = "Оптимальное распределение работников" + Символы.ПС + Символы.ПС;
Сообщение = Сообщение + СтрШаблон("Общая стоимость: %1%2", Формат(ЗначениеЗатрат, ФорматВывода), Символы.ПС);
Сообщение = Сообщение + Символы.ПС + "Назначения:" + Символы.ПС;
Для Р = 0 По КоличествоРаботников - 1 Цикл
Для З = 0 По КоличествоЗадач - 1 Цикл
Если Решение.ЗначениеПеременной(РаботникиЗадач[Р][З]) > 0.5 Тогда
Сообщение = Сообщение + СтрШаблон(
"Работник %1 → Задача %2 (затраты: %3)%4",
Р,
З,
Формат(Затраты[Р][З], ФорматВывода),
Символы.ПС
);
КонецЕсли;
КонецЦикла;
КонецЦикла;
Сообщить(Сообщение);
Иначе
Сообщить("Решение не найдено!");
КонецЕсли;
Полный код решения задачи
Ниже представлен полный код решения. Вы также можете скачать пример в виде готовой обработки.
// Создаем линейную смешанно-целочисленную модель
Модель = О2.Модели().ЛинейнаяСмешанноЦелочисленнаяМодель().СоздатьМодель();
// Вводим данные
ЗатратыНаЗадачу = Новый Массив();
ЗатратыНаЗадачу.Добавить("90.5, 80.2, 75.0, 70.3");
ЗатратыНаЗадачу.Добавить("35.1, 85.0, 55.5, 65.7");
ЗатратыНаЗадачу.Добавить("125.0, 95.3, 90.1, 95.0");
ЗатратыНаЗадачу.Добавить("45.2, 110.5, 95.0, 115.1");
ЗатратыНаЗадачу.Добавить("50.0, 100.2, 90.5, 100.0");
// Оцифровываем массивы входных данных с помощью вспомогательной функции
Затраты = Новый Массив(ЗатратыНаЗадачу.Количество());
Для К = 0 По ЗатратыНаЗадачу.Количество() - 1 Цикл
Затраты[К] = О2.Утилиты().МассивЧиселИзСтроки(ЗатратыНаЗадачу[К]);
КонецЦикла;
КоличествоРаботников = Затраты.Количество();
КоличествоЗадач = Затраты[0].Количество();
// Регистрируем булевы переменные для каждой комбинации (работник, задача)
РаботникиЗадач = Новый Массив(КоличествоРаботников);
Для Р = 0 По КоличествоРаботников - 1 Цикл
РаботникиЗадач[Р] = Модель.МассивБулевыхПеременных(КоличествоЗадач);
КонецЦикла;
// Ограничение: каждый работник выполняет не более одной задачи
Для Р = 0 По КоличествоРаботников - 1 Цикл
СуммаЗадач = Модель.Выражения().Сумма(РаботникиЗадач[Р]);
Модель.Ограничения().ЗначениеМеньшеИлиРавно(СуммаЗадач, 1);
КонецЦикла;
// Ограничение: каждая задача выполняется ровно одним работником
Для З = 0 По КоличествоЗадач - 1 Цикл
РаботникиНаЗадачу = Новый Массив(КоличествоРаботников);
Для Р = 0 По КоличествоРаботников - 1 Цикл
РаботникиНаЗадачу[Р] = РаботникиЗадач[Р][З];
КонецЦикла;
СуммаРаботников = Модель.Выражения().Сумма(РаботникиНаЗадачу);
Модель.Ограничения().ЗначениеРавно(СуммаРаботников, 1);
КонецЦикла;
// Целевая функция: минимизируем общие затраты
ОбщиеЗатраты = Модель.Выражения().СоздатьПостроительВыражений();
Для Р = 0 По КоличествоРаботников - 1 Цикл
Для З = 0 По КоличествоЗадач - 1 Цикл
ОбщиеЗатраты.ДобавитьТерм(РаботникиЗадач[Р][З], Затраты[Р][З]);
КонецЦикла;
КонецЦикла;
Модель.Минимизировать(ОбщиеЗатраты.ПолучитьВыражение());
// Решение модели
Решение = Модель.Решить();
// Вывод результатов
Если Решение.РешениеНайдено() Тогда
ФорматВывода = "ЧДЦ=2; ЧН=0; ЧГ=0";
ЗначениеЗатрат = Решение.ЗначениеВыражения(ОбщиеЗатраты.ПолучитьВыражение());
Сообщение = "Оптимальное распределение работников" + Символы.ПС + Символы.ПС;
Сообщение = Сообщение + СтрШаблон("Общая стоимость: %1%2", Формат(ЗначениеЗатрат, ФорматВывода), Символы.ПС);
Сообщение = Сообщение + Символы.ПС + "Назначения:" + Символы.ПС;
Для Р = 0 По КоличествоРаботников - 1 Цикл
Для З = 0 По КоличествоЗадач - 1 Цикл
Если Решение.ЗначениеПеременной(РаботникиЗадач[Р][З]) > 0.5 Тогда
Сообщение = Сообщение + СтрШаблон(
"Работник %1 → Задача %2 (затраты: %3)%4",
Р,
З,
Формат(Затраты[Р][З], ФорматВывода),
Символы.ПС
);
КонецЕсли;
КонецЦикла;
КонецЦикла;
Сообщить(Сообщение);
Иначе
Сообщить("Решение не найдено!");
КонецЕсли;