1.3. Решение задачи
Значение целевой функции необходимо минимизировать, поэтому знак коэффициентов целевой функции не меняется. Все ограничения задачи являются ограничениями снизу, что требует описания их в программе с обратным знаком. Ограничений типа равенства нет, задавать их не требуется. В задаче имеем 42 переменные, которые в программе обозначим следующим образом: – количество постоянных работников, заступающих на работу в определенный день. То есть, человек, которые начинают работать в этот день и работают еще следующие 4 дня. – количество временных работников, которые были наняты в определённый день, в определённую из 4 смен и работают только в течение неё. В зависимости от индекса, получаем следующие переменные:
Кол-во постоянных работников:
# x1-7 - пон-воскр, утренняя смена;
# x8-14 - пон-воскр, вечерняя смена.
# Кол-во почасовых рабочих:
# y1-7 - пон-воскр, первая четверть рабочего дня;
# y8-14 - пон-воскр, вторая;
# y15-21 - третья;
# y22-28 - четвертая.
Константные значения в задаче:
CONSTRAINT_COUNT = 70
X_COUNT = 14
Y_COUNT = 28
VAR_COUNT = 42
WORKER_SALARY = 54400
FREELANCER_SALARY = 6720
Зададим коэффициенты целевой функции:
# Задача минимазации - знак переменных не меняется.
c = [WORKER_SALARY] * X_COUNT
c.extend([FREELANCER_SALARY] * Y_COUNT)
Ограничения на минимальное количество работников: в каждый день, в определенную смену, будут работать те люди, которые заступили на работу в этот день, или в предыдущие 4, а также дополнительно нанятые временные рабочие. Учитывая это, зададим матрицу ограничений программно:
G = []
# Условия на занятость в течение недели.
# k - смена: утренняя или вечерняя.
for s in range(2):
# i - день недели.
for i in range(7):
constraint = [0] * VAR_COUNT
# Ставим 1 на месте постоянных рабочих:
# j + 3 - дни, в которые заступили рабочие, которые будут
# работать в i день;
# 7 * s - учитывает смену.
for j in range(5):
constraint[(i + j + 3) % 7 + 7 * s] = -1 # Ограничение снизу
# Теперь на месте временных.
one_quart = constraint.copy()
# Одно условие: почасовой рабочий выходит в одну четверть.
one_quart[X_COUNT * (s + 1) + i] = -1
G.append(one_quart)
# Второе условие: почасовой рабочий выходит в другую четверть.
second_quart = constraint.copy()
second_quart[X_COUNT * (s + 1) + i + 7] = -1
G.append(second_quart)
# Условия на неотрицательность количества рабочих.
for i in range(VAR_COUNT):
constraint = [0] * VAR_COUNT
constraint[i] = -1 # Ограничение снизу
G.append(constraint)
Так как матрица ограничений очень большая, приведем только ее часть:
Рисунок 1 – Матрица ограничений
Пояснения на примере: первый столбец задает ограничения на количество работников в понедельник во временной промежуток с 7:00 до 11:00. В данном случае не равны нулю следующие переменные: – количество постоянных работников утренней смены, заступающих на работу в понедельник, четверг, пятницу, субботу и воскресенье соответственно, а также – количество временных работников в данный отрезок времени. Следующий столбец – тоже понедельник, но время с 11:00 до 15:00. Затем идет вторник и так далее вплоть до 15 столбца, с которого начинается вечерняя смена (два отрезка: с 15:00 до 19:00 и с 19:00 до 23:00). Таким образом, ограничения были заданы правильно.
Правая часть ограничений:
h = [-8, -8, -6, -5, -6, -5, -5, -6, -7, -8, -9, -8, -6, -5,
-7, -6, -4, -5, -4, -4, -6, -7, -8, -9, -7, -6, -4, -4]
h.extend([0] * VAR_COUNT)
Преобразование к типу matrix:
c = matrix(c, tc='d')
G = matrix(G, tc='d')
h = matrix(h, tc='d')
Решение задачи целочисленного линейного программирования:
status, solution = glpk.ilp(c, G.T, h, I=set(range(VAR_COUNT)))
Получаем следующие результаты решения:
Рисунок 2 – Результаты решения
Стоимость всех рабочих в месяц составила 977280 рублей. Количество постоянных работников равно 15, временных – 24.
Итого, получаем оптимальный план занятости работников (с плюсом указано кол-во временных работников, с минусом – количество незадействованных пост. рабочих):
Таблица 2 – Оптимальная занятость работников в течение недели
День недели |
7:00 – 11:00 |
11:00 – 15:00 |
15:00 – 19:00 |
19:00 – 23:00 |
Понедельник |
5 +3 |
5 +3 |
6 +1 |
6 |
Вторник |
5 +1 |
5 |
4 |
4 +1 |
Среда |
5 +1 |
5 |
4 |
4 |
Четверг |
8 -3 |
8 -2 |
6 |
6 +1 |
Пятница |
6 +1 |
6 +2 |
7 +1 |
7 +2 |
Суббота |
8 +1 |
8 |
4 +3 |
4 +2 |
Воскресенье |
5 +1 |
5 |
4 |
4 |