Розв’язання квадратичної задачі про призначення методом локальних оптимумів

Юрій Михайлович Зорін; Сергій Валентинович Подольський

Розв’язання квадратичної задачі про призначення методом локальних оптимумів

Автор(и)

Юрій Михайлович Зорін Національний технічний університет Україні “КПІ”
Сергій Валентинович Подольський EPAM Systems,

Ключові слова:

квадратична задача про призначення, евристичний алгоритм, комбінаторна оптимізація, локальний мінімум

Анотація

У роботі запропоновано евристичний алгоритм розв’язання квадратичної задачі про призначення. На відміну від існую-
чих евристичних алгоритмів, які потребують визначення декількох вхідних параметрів, запропонований алгоритм використовує
лише один параметр і базується на ідеї використання комбінації локальних оптимумів в околі перестановок двох елементів. При
цьому він дозволяє отримати більш якісні розв’язки за дещо менший час в порівнянні з відомими алгоритмами.