Назначение с разрешенными бригадами

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

Такая постановка актуальна для ситуаций, где существуют логистические, организационные или технологические ограничения на одновременную работу определённых сотрудников. Например, в медицинском учреждении некоторые врачи не могут работать одновременно из-за требований по дежурствам; в производстве определённые операторы не могут быть задействованы вместе из-за требований безопасности или необходимости присутствия на других участках; в проектной команде могут быть ограничения на одновременную занятость ключевых специалистов из-за участия в других проектах.

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

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

• Бригада 1: работники 0, 1, 2, 3;
• Бригада 2: работники 4, 5, 6, 7;
• Бригада 3: работники 8, 9, 10, 11;
• Для каждой бригады определены допустимые комбинации одновременной работы;
• Каждый работник может быть назначен не более чем на одну задачу;
• Каждая задача должна быть выполнена ровно одним работником;
• Комбинация работающих работников в каждой бригаде должна соответствовать одной из разрешённых;
• Требуется минимизировать суммарные затраты на выполнение всех задач.

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

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

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

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

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

// Создаем модель ограничений
Модель = О2.Модели()
    .МодельОграничений()
    .СоздатьМодель();

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

Помимо матрицы затрат, задаются допустимые комбинации для каждой бригады.

// Вводим данные
ЗатратыНаЗадачу = Новый Массив();
ЗатратыНаЗадачу.Добавить("90, 76, 75, 70, 50, 74");
ЗатратыНаЗадачу.Добавить("35, 85, 55, 65, 48, 101");
// ... остальные работники

// Оцифровываем массивы входных данных с помощью вспомогательной функции
Затраты = Новый Массив(ЗатратыНаЗадачу.Количество());
Для К = 0 По ЗатратыНаЗадачу.Количество() - 1 Цикл
    Затраты[К] = О2.Утилиты().МассивЧиселИзСтроки(ЗатратыНаЗадачу[К]);
КонецЦикла;

// Разрешенные комбинации для Бригады 1
Бригада1 = Новый Массив();
Бригада1.Добавить("0, 0, 1, 1");  // Работают 2 и 3
Бригада1.Добавить("0, 1, 0, 1");  // Работают 1 и 3
Бригада1.Добавить("0, 1, 1, 0");  // Работают 1 и 2
Бригада1.Добавить("1, 1, 0, 0");  // Работают 0 и 1
Бригада1.Добавить("1, 0, 1, 0");  // Работают 0 и 2

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

// Аналогично для Бригад 2 и 3

4. Регистрация переменных

Создаются два типа булевых переменных:

• Переменные назначения (работник → задача);
• Переменные статуса работника (работает/не работает).

// Регистрируем булевы переменные для каждой комбинации (работник, задача)
РаботникиЗадач = Новый Массив(КоличествоРаботников);
Для Р = 0 По КоличествоРаботников - 1 Цикл
    РаботникиЗадач[Р] = Модель.МассивБулевыхПеременных(КоличествоЗадач);
КонецЦикла;

// Регистрируем булевы переменные для статуса работы каждого работника
РаботникиРаботают = Модель.МассивБулевыхПеременных(КоличествоРаботников); 

5. Описание ограничений

Каждый работник выполняет не более одной задачи.

// Ограничение: каждый работник выполняет не более одной задачи
Для Р = 0 По КоличествоРаботников - 1 Цикл
    Модель.Ограничения().НиБолееОдного(РаботникиЗадач[Р]);
КонецЦикла;

Каждая задача выполняется ровно одним работником.

// Ограничение: каждая задача выполняется ровно одним работником
Для З = 0 По КоличествоЗадач - 1 Цикл
    РаботникиНаЗадачу = Новый Массив(КоличествоРаботников);
    Для Р = 0 По КоличествоРаботников - 1 Цикл
        РаботникиНаЗадачу[Р] = РаботникиЗадач[Р][З];
    КонецЦикла;
    Модель.Ограничения().ТолькоОдин(РаботникиНаЗадачу);
КонецЦикла;

Связь статуса работника с назначениями. Переменная статуса равна 1 тогда и только тогда, когда работник назначен на какую-либо задачу.

// Ограничение: работник работает тогда и только тогда, когда назначен на задачу
Для Р = 0 По КоличествоРаботников - 1 Цикл
    СуммаЗадач = Модель.Выражения().Сумма(РаботникиЗадач[Р]);
    Модель.Ограничения().ЗначениеРавно(РаботникиРаботают[Р], СуммаЗадач);
КонецЦикла;

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

// Ограничение: разрешенные комбинации для первой бригады (работники 0-3)
СтатусыБригады1 = Новый Массив();
СтатусыБригады1.Добавить(РаботникиРаботают[0]);
СтатусыБригады1.Добавить(РаботникиРаботают[1]);
СтатусыБригады1.Добавить(РаботникиРаботают[2]);
СтатусыБригады1.Добавить(РаботникиРаботают[3]);
Модель.Ограничения().РазрешенныеКомбинации(СтатусыБригады1, КомбинацииБригады1);

// Ограничение: разрешенные комбинации для второй бригады (работники 4-7)
СтатусыБригады2 = Новый Массив();
СтатусыБригады2.Добавить(РаботникиРаботают[4]);
СтатусыБригады2.Добавить(РаботникиРаботают[5]);
СтатусыБригады2.Добавить(РаботникиРаботают[6]);
СтатусыБригады2.Добавить(РаботникиРаботают[7]);
Модель.Ограничения().РазрешенныеКомбинации(СтатусыБригады2, КомбинацииБригады2);

// Ограничение: разрешенные комбинации для третьей бригады (работники 8-11)
СтатусыБригады3 = Новый Массив();
СтатусыБригады3.Добавить(РаботникиРаботают[8]);
СтатусыБригады3.Добавить(РаботникиРаботают[9]);
СтатусыБригады3.Добавить(РаботникиРаботают[10]);
СтатусыБригады3.Добавить(РаботникиРаботают[11]);
Модель.Ограничения().РазрешенныеКомбинации(СтатусыБригады3, КомбинацииБригады3);

Ограничение РазрешенныеКомбинации принимает два параметра:

• Массив булевых переменных (статусы работников бригады)
• Массив разрешённых комбинаций (каждая комбинация — массив из 0 и 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, 76, 75, 70, 50, 74");
ЗатратыНаЗадачу.Добавить("35, 85, 55, 65, 48, 101");
ЗатратыНаЗадачу.Добавить("125, 95, 90, 105, 59, 120");
ЗатратыНаЗадачу.Добавить("45, 110, 95, 115, 104, 83");
ЗатратыНаЗадачу.Добавить("60, 105, 80, 75, 59, 62");
ЗатратыНаЗадачу.Добавить("45, 65, 110, 95, 47, 31");
ЗатратыНаЗадачу.Добавить("38, 51, 107, 41, 69, 99");
ЗатратыНаЗадачу.Добавить("47, 85, 57, 71, 92, 77");
ЗатратыНаЗадачу.Добавить("39, 63, 97, 49, 118, 56");
ЗатратыНаЗадачу.Добавить("47, 101, 71, 60, 88, 109");
ЗатратыНаЗадачу.Добавить("17, 39, 103, 64, 61, 92");
ЗатратыНаЗадачу.Добавить("101, 45, 83, 59, 92, 27");

Затраты = Новый Массив(ЗатратыНаЗадачу.Количество());
Для К = 0 По ЗатратыНаЗадачу.Количество() - 1 Цикл
    Затраты[К] = О2.Утилиты().МассивЧиселИзСтроки(ЗатратыНаЗадачу[К]);
КонецЦикла;

Бригада1 = Новый Массив();
Бригада1.Добавить("0, 0, 1, 1");
Бригада1.Добавить("0, 1, 0, 1");
Бригада1.Добавить("0, 1, 1, 0");
Бригада1.Добавить("1, 1, 0, 0");
Бригада1.Добавить("1, 0, 1, 0");

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

Бригада2 = Новый Массив();
Бригада2.Добавить("0, 0, 1, 1");
Бригада2.Добавить("0, 1, 0, 1");
Бригада2.Добавить("0, 1, 1, 0");
Бригада2.Добавить("1, 1, 0, 0");
Бригада2.Добавить("1, 0, 0, 1");

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

Бригада3 = Новый Массив();
Бригада3.Добавить("0, 0, 1, 1");
Бригада3.Добавить("0, 1, 0, 1");
Бригада3.Добавить("0, 1, 1, 0");
Бригада3.Добавить("1, 0, 1, 0");
Бригада3.Добавить("1, 0, 0, 1");

КомбинацииБригады3 = Новый Массив(Бригада3.Количество());
Для К = 0 По Бригада3.Количество() - 1 Цикл
    КомбинацииБригады3[К] = О2.Утилиты().МассивЧиселИзСтроки(Бригада3[К]);
КонецЦикла;

КоличествоРаботников = Затраты.Количество();
КоличествоЗадач      = Затраты[0].Количество();

// Регистрируем булевы переменные для каждой комбинации (работник, задача)
РаботникиЗадач = Новый Массив(КоличествоРаботников);
Для Р = 0 По КоличествоРаботников - 1 Цикл
    РаботникиЗадач[Р] = Модель.МассивБулевыхПеременных(КоличествоЗадач);
КонецЦикла;

// Регистрируем булевы переменные для статуса работы каждого работника
РаботникиРаботают = Модель.МассивБулевыхПеременных(КоличествоРаботников);

// Ограничение: каждый работник выполняет не более одной задачи
Для Р = 0 По КоличествоРаботников - 1 Цикл
    Модель.Ограничения().НиБолееОдного(РаботникиЗадач[Р]);
КонецЦикла;

// Ограничение: каждая задача выполняется ровно одним работником
Для З = 0 По КоличествоЗадач - 1 Цикл
    РаботникиНаЗадачу = Новый Массив(КоличествоРаботников);
    Для Р = 0 По КоличествоРаботников - 1 Цикл
        РаботникиНаЗадачу[Р] = РаботникиЗадач[Р][З];
    КонецЦикла;
    Модель.Ограничения().ТолькоОдин(РаботникиНаЗадачу);
КонецЦикла;

// Ограничение: работник работает тогда и только тогда, когда назначен на задачу
Для Р = 0 По КоличествоРаботников - 1 Цикл
    СуммаЗадач = Модель.Выражения().Сумма(РаботникиЗадач[Р]);
    Модель.Ограничения().ЗначениеРавно(РаботникиРаботают[Р], СуммаЗадач);
КонецЦикла;

// Ограничение: разрешенные комбинации для первой бригады (работники 0-3)
СтатусыБригады1 = Новый Массив();
СтатусыБригады1.Добавить(РаботникиРаботают[0]);
СтатусыБригады1.Добавить(РаботникиРаботают[1]);
СтатусыБригады1.Добавить(РаботникиРаботают[2]);
СтатусыБригады1.Добавить(РаботникиРаботают[3]);
Модель.Ограничения().РазрешенныеКомбинации(СтатусыБригады1, КомбинацииБригады1);

// Ограничение: разрешенные комбинации для второй бригады (работники 4-7)
СтатусыБригады2 = Новый Массив();
СтатусыБригады2.Добавить(РаботникиРаботают[4]);
СтатусыБригады2.Добавить(РаботникиРаботают[5]);
СтатусыБригады2.Добавить(РаботникиРаботают[6]);
СтатусыБригады2.Добавить(РаботникиРаботают[7]);
Модель.Ограничения().РазрешенныеКомбинации(СтатусыБригады2, КомбинацииБригады2);

// Ограничение: разрешенные комбинации для третьей бригады (работники 8-11)
СтатусыБригады3 = Новый Массив();
СтатусыБригады3.Добавить(РаботникиРаботают[8]);
СтатусыБригады3.Добавить(РаботникиРаботают[9]);
СтатусыБригады3.Добавить(РаботникиРаботают[10]);
СтатусыБригады3.Добавить(РаботникиРаботают[11]);
Модель.Ограничения().РазрешенныеКомбинации(СтатусыБригады3, КомбинацииБригады3);

// Целевая функция: минимизируем общие затраты
ОбщиеЗатраты = Модель.Выражения().СоздатьПостроительВыражений();
Для Р = 0 По КоличествоРаботников - 1 Цикл
    Для З = 0 По КоличествоЗадач - 1 Цикл
        ОбщиеЗатраты.ДобавитьТерм(РаботникиЗадач[Р][З], Затраты[Р][З]);
    КонецЦикла;
КонецЦикла;
Модель.Минимизировать(ОбщиеЗатраты.ПолучитьВыражение());

// Решение модели
Решение = Модель.Решить();

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

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