informИнформатикаInformatics1816-03012617-6963UIIP NASBinform-557Research ArticleМАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕMATHEMATICAL MODELINGАЛГОРИТМЫ РЕШЕНИЯ МНОГОМЕРНОЙ ЗАДАЧИ О НАЗНАЧЕНИЯХКарпукА. А.Научно-исследовательский институт средств автоматизацииBelarus20083110201802(18)513Copyright © Карпук А.А., 20182018Карпук А.А.Карпук А.А.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://inf.grid.by/jour/article/view/557

Рассматривается многомерная задача о назначениях, полученная из классической задачи о назначениях при дополнительных предположениях, что одного претендента можно назначить на несколько должностей и любое подмножество должностей может оказаться занятым претендентами, несовместимыми между собой на этих должностях. Показывается, что NP-трудная многомерная задача о назначениях сводится к задаче поиска в n-дольном взвешенном гиперграфе максимального полного подгиперграфа, имеющего минимальную сумму весов вершин и ребер. Предлагаются жадные алгоритмы решения задачи и алгоритмы локального поиска в окрестности начального решения.

ReferencesКарпук, А.А. Задача оптимизации использования радиочастотного ресурса при присвоении частот радиолиниям / А.А. Карпук // Информатика. – 2006. – № 4 (12). – С. 5–13.Карпук, А.А. Задача оптимизации использования радиочастотного ресурса при присвоении частот радиолиниям / А.А. Карпук // Информатика. – 2006. – № 4 (12). – С. 5–13.Сергеев, С.И. Квадратичная задача назначения / С.И. Сергеев // Автоматика и телемеханика. – 1999. – № 8. – С. 127–147.Сергеев, С.И. Квадратичная задача назначения / С.И. Сергеев // Автоматика и телемеханика. – 1999. – № 8. – С. 127–147.Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. – М.: Мир, 1982. – 416 с.Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. – М.: Мир, 1982. – 416 с.Ахо, А. Структуры данных и алгоритмы / А. Ахо, Д. Хопкрофт, Д. Ульман. – М.: Издательский дом «Вильямс», 2000. – 384 с.Ахо, А. Структуры данных и алгоритмы / А. Ахо, Д. Хопкрофт, Д. Ульман. – М.: Издательский дом «Вильямс», 2000. – 384 с.Кочетов, Ю.А. Вероятностные методы локального поиска для задач дискретной оптимизации / Ю.А. Кочетов // Дискретная математика и ее приложения: сб. лекций молодежных и научных школ по дискретной математике и ее приложениям. – М.: МГУ, 2001. – С. 87–117.Кочетов, Ю.А. Вероятностные методы локального поиска для задач дискретной оптимизации / Ю.А. Кочетов // Дискретная математика и ее приложения: сб. лекций молодежных и научных школ по дискретной математике и ее приложениям. – М.: МГУ, 2001. – С. 87–117.Special software for electromagnetic compatibility simulation and frequency assignment to radio sets of fixed-mobile radio communication systems / V. Voloshin [et al.] // Proc. 4th European Symposium on electromagnetic compatibility. – Brugge, 2000. – Vol. 2. – P. 119–122.Special software for electromagnetic compatibility simulation and frequency assignment to radio sets of fixed-mobile radio communication systems / V. Voloshin [et al.] // Proc. 4th European Symposium on electromagnetic compatibility. – Brugge, 2000. – Vol. 2. – P. 119–122.Карпук, А.А. Задача о назначениях с учетом коллизий / А.А. Карпук // Информационный бюллетень Ассоциации математического программирования: тез. докл. конф. «Математическое программирование и приложения». – Екатеринбург: УрО РАН, 2007. – № 11. – С. 178.Карпук, А.А. Задача о назначениях с учетом коллизий / А.А. Карпук // Информационный бюллетень Ассоциации математического программирования: тез. докл. конф. «Математическое программирование и приложения». – Екатеринбург: УрО РАН, 2007. – № 11. – С. 178.

The authors declare that there are no conflicts of interest present.