1.2. Формализация задачи

– булева переменная, обозначающая, взял ли i-ый работник j-ую задачу.

рейтинг i-го работника.

стоимость i-го работника.

Целевая функция, учитывающая качество выполнения всех заданий:

.

Ограничения:

Суммарная зарплата работников не должна превышать 310 ДЕ:

.

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

.

Каждый человек может взять только одно задание, но не обязан:

.

Это задача линейного программирования, так как целевая функция и ограничения задачи имеют линейную форму. Не имеется управлений и состояний системы.

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

Значение целевой функции необходимо максимизировать, поэтому знак коэффициентов целевой функции меняется на противоположный. Ограничения неравенства задачи являются ограничениями сверху, поэтому их знак не меняется. Присутствуют ограничения типа равенства. В задаче имеем 40 переменных, которые в программе обозначим следующим образом: – это булева переменная, обозначающая, взял ли определённый работник определённую задачу. В зависимости от индекса, получаем следующие переменные:

# mi - булева: взял ли работник задачу.

# m1-4 - первый работник, задачи 1-4;

# m5-8 - второй работник, задачи 1-4;

# и т.д.

Константные значения в задаче:

INEQUALITIES_LIMITS_COUNT = 11

QUALITIES_LIMITS_COUNT = 4

WORKER_COUNT = 10

TASK_COUNT = 4

VAR_COUNT = 40

LOW_SALARY = 60

HIGH_SALARY = 100

# Рейтинг рабочих с 1 по 10

R = [0.85, 0.65, 0.59, 0.65, 0.35, 0.27, 0.65, 0.85, 0.47, 0.39]

# Координаты местонахождения рабочих и задач.

task_x = [6, 19, 12, 4]

task_y = [1, 18, 14, 7]

worker_x = [11, 10, 17, 13, 17, 0, 6, 0, 5, 8]

worker_y = [10, 15, 7, 11, 19, 9, 19, 19, 17, 13]

Задаём коэффициенты целевой функции (для каждого работника одно значение рейтинга для всех задач):

# Задача максимизации - знак переменных меняется.

a = [[-r] * 4 for r in R]

c = list(reduce(lambda a, b: a + b, a))

Задаём ограничения равенства:

# Каждое задание может взять только один человек.

A.append([1, 0, 0, 0] * 10)

A.append([0, 1, 0, 0] * 10)

A.append([0, 0, 1, 0] * 10)

A.append([0, 0, 0, 1] * 10)

Ограничения неравенства:

# Ограничение на суммарную зарплату.

a = [[LOW_SALARY if r < 0.7 else HIGH_SALARY] * 4 for r in R]

G = [list(reduce(lambda a, b: a + b, a))]

# Каждый человек может взять только одно задание.

for i in range(0, 10):

G.append([1 if i*4 <= j < i*4 + 4 else 0 for j in range(VAR_COUNT)])

Приведём левые части матриц ограничений неравенств и равенств (только их части из-за большого размера матриц):

Рисунок 1 – Левая часть матрицы ограничений равенств

Здесь индексы у обозначают следующее: – номер рабочего, – номер задачи. Каждый столбец представляет собой ограничение вида: «Каждое задание должен взять только один человек». Поэтому для каждого ограничения не равны нулю те переменные, у которых второй индекс равен номеру задачи.

Рисунок 2 – Левая часть матрицы ограничений неравенств

Здесь первый столбец — это ограничение на суммарную зарплату работников. Далее – ограничения на количество взятых заданий, которое не должно превышать 1 для каждого рабочего. В каждом столбце не равны нулю переменные, относящиеся к одному конкретному рабочему.

Задаём правые части ограничений:

# Правая часть матрицы ограничений неравенств.

h = [310]

h.extend([1] * (INEQUALITIES_LIMITS_COUNT - 1))

b = [1] * QUALITIES_LIMITS_COUNT

Приведение к матричному типу и решение задачи:

c = matrix(c, tc='d')

G = matrix(G, tc='d')

A = matrix(A, tc='d')

h = matrix(h, tc='d')

b = matrix(b, tc='d')

B = set(range(VAR_COUNT))

status, solution = glpk.ilp(c=c, G=G.T, h=h, A=A.T, b=b, B=B)

Получаем следующие результаты решения:

Рисунок 3 – Результаты решения задачи

Логика полученного решения очевидна: взять одного работника с самым высоким рейтингом и зарплатой 100 ДЕ (больше не получится из-за ограничения на зарплату), и из оставшихся рабочих с зарплатой 60 ДЕ набрать также имеющих наибольший рейтинг.