Распределение офисов между сотрудниками
artpgchОптимизация распределения служебных помещений между сотрудниками
Введение
В данном примере представлено решение задачи оптимального распределения ограниченного ресурса — служебных помещений — между сотрудниками с учётом ряда организационных требований. Критериями оптимизации выступают персональные предпочтения работников, взвешенные по их стажу, а также обязательное условие смежности рабочих мест для двух пар сотрудников, занятых совместными проектами. Задача формализована в виде модели целочисленного линейного программирования с целью максимизации суммарного взвешенного удовлетворения предпочтений при соблюдении всех установленных ограничений.
Распределение помещений
Перед нами стоит задача распределить семь офисных помещений между шестью сотрудниками.
Имена сотрудников: Анна, Артём, Алёна, Антон, Андрей, Анастасия.
Каждый сотрудник получает ровно один кабинет, а в каждом кабинете может находиться не более одного человека. Таким образом, одно помещение неизбежно останется пустым.
Сотрудники могут указывать свои предпочтения по выбору рабочих мест, и эти пожелания учитываются в соответствии с их стажем работы в компании: чем дольше человек работает в компании, тем выше его приоритет.
Планировка помещений неоднородна: часть кабинетов имеет окна, другие — нет, причём одно из окон заметно меньше остальных. Дополнительная сложность заключается в том, что Алёна и Антон часто работают в паре, поэтому их стоит разместить в соседних помещениях. То же самое касается Андрея и Анастасии — их рабочие места также должны быть смежными.
Присоединим необходимые библиотеки и функцию построения планировки.
using JuMP, HiGHS, LinearAlgebra
include("officeassign.jl")
Планировка помещений
Кабинеты 1, 2, 3 и 4 расположены внутри здания — это помещения без окон. Кабинеты 5, 6 и 7 имеют доступ к естественному освещению, однако важно отметить, что окно в кабинете 5 значительно меньше, чем в двух других.
Схема расположения кабинетов:
кабинеты = ["Кабинет 1", "Кабинет 2", "Кабинет 3", "Кабинет 4", "Кабинет 5", "Кабинет 6", "Кабинет 7"];
officeassign(кабинеты)
Постановка задачи
Представим задачу в виде математической модели. Создадим бинарные переменные, которые будут указывать на принадлежность кабинета конкретному сотруднику.
Список имён сотрудников:
имена = ["Анна", "Артём", "Алёна", "Антон", "Андрей", "Анастасия"];
Создадим бинарные переменные, индексированные по номерам кабинетов и именам сотрудников.
модель = Model(HiGHS.Optimizer)
@variable(модель, занимает[i in имена, j in кабинеты],
Int, lower_bound=0, upper_bound=1);
Стаж сотрудников
Необходимо назначить весовые коэффициенты для предпочтений сотрудников в зависимости от их стажа. Таким образом, чем дольше человек работает в компании MathWorks, тем больший вес имеют его пожелания.
Стаж работы сотрудников распределяется следующим образом:
-
Анна — 9 лет
-
Артём — 2 года
-
Алёна — 5 лет
-
Антон — 4 года
-
Андрей — 1,5 года
-
Анастасия — 10 лет
На основе этих данных требуется построить нормированный вектор весовых коэффициентов.
стаж = [9, 2, 5, 4, 1.5, 10];
весовой_вектор = стаж/sum(стаж);
Предпочтения сотрудников
Построим матрицу предпочтений, в которой строки соответствуют кабинетам, а столбцы — сотрудникам. Каждого человека нужно попросить оценить каждый кабинет по шкале таким образом, чтобы сумма всех его оценок (то есть сумма по столбцу) равнялась 100. Чем выше значение, тем более желательным считается данный кабинет для сотрудника. Предпочтения каждого человека представлены в виде вектор-столбца.
Анна = [1, 3, 3, 3, 10, 40, 40];
Артём = [0, 0, 0, 0, 20, 40, 40];
Алёна = [0, 0, 0, 0, 30, 40, 30];
Антон = [0, 0, 0, 10, 10, 40, 50]
Андрей = [3, 4, 1, 2, 10, 40, 40];
Анастасия = [10, 10, 10, 10, 20, 20, 20];
Каждый i-й элемент вектора предпочтений каждого сотрудника показывает, насколько высоко он ценит i-й кабинет.
Таким образом, итоговая матрица предпочтений имеет следующий вид:
матрица_предпочтений = [Анна Артём Алёна Антон Андрей Анастасия]';
Умножим матрицу предпочтений на весовой вектор, чтобы масштабировать столбцы с учетом стажа.
ПМ = zeros(length(имена), length(кабинеты))
for i in 1:length(имена)
for j in 1:length(кабинеты)
ПМ[i, j] = весовой_вектор[i] * матрица_предпочтений[i, j]
end
end
Целевая функция
Цель задачи — максимизировать удовлетворенность предпочтений сотрудников с учетом их стажа. Теперь необходимо создать задачу оптимизации и включить в нее данную целевую функцию.
@objective(модель, Max, sum(занимает[i, j] * ПМ[findfirst(isequal(i), имена), findfirst(isequal(j), кабинеты)]
for i in имена, j in кабинеты));
Ограничения
Первое условие гарантирует, что каждый сотрудник получает ровно один кабинет. Математически это означает, что для каждого человека сумма значений переменной занимает по всем кабинетам должна быть в точности равна единице.
@constraint(модель, ограничение1[i in имена], sum(занимает[i, j] for j in кабинеты) == 1);
Вторая группа условий представляет собой неравенства. Эти ограничения гарантируют, что в каждом кабинете будет находиться не более одного человека.
@constraint(модель, ограничение2[j in кабинеты], sum(занимает[i, j] for i in имена) <= 1);
Требуется, чтобы Алёна и Антон располагались в кабинетах, расстояние между которыми не превышает одного кабинета. Аналогичное условие применяется к Анастасии и Андрею.
Установим ограничения, гарантирующие, что Алёна и Антон будут находиться не дальше, чем через один кабинет друг от друга.
@constraint(модель, ограничение_Алёна_Антон_1, занимает["Алёна","Кабинет 1"] + sum(занимает["Антон", j] for j in кабинеты) - занимает["Антон","Кабинет 2"] <= 1);
@constraint(модель, ограничение_Алёна_Антон_2, занимает["Алёна","Кабинет 2"] + sum(занимает["Антон", j] for j in кабинеты) - занимает["Антон","Кабинет 1"] - занимает["Антон","Кабинет 3"] - занимает["Антон","Кабинет 5"] <= 1);
@constraint(модель, ограничение_Алёна_Антон_3, занимает["Алёна","Кабинет 3"] + sum(занимает["Антон", j] for j in кабинеты) - занимает["Антон","Кабинет 2"] - занимает["Антон","Кабинет 4"] - занимает["Антон","Кабинет 6"] <= 1);
@constraint(модель, ограничение_Алёна_Антон_4, занимает["Алёна","Кабинет 4"] + sum(занимает["Антон", j] for j in кабинеты) - занимает["Антон","Кабинет 3"] - занимает["Антон","Кабинет 7"] <= 1);
@constraint(модель, ограничение_Алёна_Антон_5, занимает["Алёна","Кабинет 5"] + sum(занимает["Антон", j] for j in кабинеты) - занимает["Антон","Кабинет 2"] - занимает["Антон","Кабинет 6"] <= 1);
@constraint(модель, ограничение_Алёна_Антон_6, занимает["Алёна","Кабинет 6"] + sum(занимает["Антон", j] for j in кабинеты) - занимает["Антон","Кабинет 3"] - занимает["Антон","Кабинет 5"] - занимает["Антон","Кабинет 7"] <= 1);
@constraint(модель, ограничение_Алёна_Антон_7, занимает["Алёна","Кабинет 7"] + sum(занимает["Антон", j] for j in кабинеты) - занимает["Антон","Кабинет 4"] - занимает["Антон","Кабинет 6"] <= 1);
Теперь установим ограничения, гарантирующие, что Анастасия и Андрей будут находиться не дальше, чем через один кабинет друг от друга.
@constraint(модель, ограничение_Андрей_Анастасия_1, занимает["Андрей","Кабинет 1"] + sum(занимает["Анастасия", j] for j in кабинеты) - занимает["Анастасия","Кабинет 2"] <= 1);
@constraint(модель, ограничение_Андрей_Анастасия_2, занимает["Андрей","Кабинет 2"] + sum(занимает["Анастасия", j] for j in кабинеты) - занимает["Анастасия","Кабинет 1"] - занимает["Анастасия","Кабинет 3"] - занимает["Анастасия","Кабинет 5"] <= 1);
@constraint(модель, ограничение_Андрей_Анастасия_3, занимает["Андрей","Кабинет 3"] + sum(занимает["Анастасия", j] for j in кабинеты) - занимает["Анастасия","Кабинет 2"] - занимает["Анастасия","Кабинет 4"] - занимает["Анастасия","Кабинет 6"] <= 1);
@constraint(модель, ограничение_Андрей_Анастасия_4, занимает["Андрей","Кабинет 4"] + sum(занимает["Анастасия", j] for j in кабинеты) - занимает["Анастасия","Кабинет 3"] - занимает["Анастасия","Кабинет 7"] <= 1);
@constraint(модель, ограничение_Андрей_Анастасия_5, занимает["Андрей","Кабинет 5"] + sum(занимает["Анастасия", j] for j in кабинеты) - занимает["Анастасия","Кабинет 2"] - занимает["Анастасия","Кабинет 6"] <= 1);
@constraint(модель, ограничение_Андрей_Анастасия_6, занимает["Андрей","Кабинет 6"] + sum(занимает["Анастасия", j] for j in кабинеты) - занимает["Анастасия","Кабинет 3"] - занимает["Анастасия","Кабинет 5"] - занимает["Анастасия","Кабинет 7"] <= 1);
@constraint(модель, ограничение_Андрей_Анастасия_7, занимает["Андрей","Кабинет 7"] + sum(занимает["Анастасия", j] for j in кабинеты) - занимает["Анастасия","Кабинет 4"] - занимает["Анастасия","Кабинет 6"] <= 1);
Решение
Выполним решение задачи оптимизации.
optimize!(модель);
решение = value.(занимает);
значение_функции = objective_value(модель);
статус_выхода = termination_status(модель);
выходные_данные = raw_status(модель);
Визуализация решения
Визуализируем оптимальное распределение служебных помещений между сотрудниками.
число_кабинетов = length(кабинеты);
кабинет = Vector{Vector{String}}(undef, число_кабинетов);
for i=1:число_кабинетов
кабинет[i] = имена[findall(x -> x > 0.5, [решение[имя, кабинеты[i]] for имя in имена])]
end
кто_в_кабинете = copy(кабинеты);
for i=1:число_кабинетов
if isempty(кабинет[i])
кто_в_кабинете[i] = " пусто ";
else
кто_в_кабинете[i] = кабинет[i][1];
end
end
officeassign(кто_в_кабинете);
значение_функции,статус_выхода,выходные_данные
Вывод
В результате решения оптимизационной задачи было получено распределение кабинетов, обеспечивающее максимальное значение целевой функции при полном соблюдении заданных условий. Решение демонстрирует эффективность применения методов математического моделирования для принятия объективных управленческих решений в условиях конфликтующих критериев и ограниченных ресурсов. Использованный подход позволяет формализовать и балансировать как субъективные человеческие предпочтения, так и строгие операционные требования.