2.1 Решение задачи с учетом расстояний
Модифицируем рейтинг рабочего в зависимости от того, как далеко он находится от задачи, по следующей формуле:
где
– это расстояние между задачей и рабочим,
вычисляемое по формуле Евклида, а
– старый рейтинг рабочего. Данная
формула позволяет расстоянию внести
существенный вклад в рейтинг, но при
этом новое значение рейтинга остается
в пределах изначальной задачи.
Теперь значение рейтинга у каждого рабочего различается для разных задач:
# Пересчет коэффициентов целевой функции, где учитывается расстояние
# от задания до работника.
new_R = []
for i in range(WORKER_COUNT):
for j in range(TASK_COUNT):
# Задача максимизации - знак переменных меняется.
new_R.append(-recalculate_raiting(R[i], task_coor[j], worker_coor[i]))
Функция, пересчитывающая рейтинг:
def recalculate_raiting(r, task_coor, worker_coor):
x1, y1 = task_coor
x2, y2 = worker_coor
length = sqrt(pow(x2 - x1, 2) + pow(y2 - y1, 2))
return round(1 - log10(length) + r, 2)
Результаты решения:
Рисунок 4 – Результаты решения задачи с модифицированным рейтингом
Состав рабочих (по сравнению с предыдущим решением) поменялся только на одного человека: был 7-ой работник, стал 5-ый. Но только у одного рабочего номер задачи остался тем же. Проанализируем решение с помощью рисунка:
Рисунок 5 – Местонахождение рабочих и заданий
Синими точками обозначены рабочие с зарплатой 60 ДЕ (с оранжевым ободом – имеющие наибольший начальный рейтинг среди остальных с такой зарплатой), ярко-зеленым – с зарплатой 100 ДЕ. Красными крестиками – задания, линия от рабочего к заданию означает, что он взял эту задачу.
Как видно из рисунка, предпочтение все равно отдается рабочим с большим изначальным рейтингом. Несмотря на то, что 6-ой рабочий находится ближе к задачам №1 и №4, выгоднее их распределить между 1-ым и 4-ым работниками (забавное совпадение). С оставшимися задачами всё очевидно.
Заключение
В результате решения задачи был получен оптимальный план наиболее выгодного распределения задач среди рабочих для максимизации рейтинга. Решение первого этапа задания очевидно. Решение второго с учетом введенной функции демонстрирует, что меньшее расстояние не всегда компенсирует небольшой изначальный рейтинг рабочего, потому задания в основном также распределяются среди рабочих с высоким начальным рейтингом.
Список использованных источников
1. Пономарев А.В. Решение задач линейного программирования с использованием GNU Octave, GLPK и Python // Теория принятия решений – тематический сайт. URL: https://avponomarev.bitbucket.io/LP_tutorial.pdf (дата обращения: 30.04.2023).
2. Таха Хемди А. Введение в исследование операций. 7-е издание. М.: Издательский дом "Вильямс", 2005. - 912 с.
3. ГОСТ 7.32–2001. Межгосударственный стандарт. Отчет о научно-исследовательской работе. Структура и правила оформления. М.: Изд-во стандартов, 2001.