Побудовано квадратичну оптимізаційну задачу для знаходження максимального k-плекса у неорієнтованому графі. Наведено дві сім'ї функціонально-надлишкових квадратичних обмежень, які отримано за допомогою обмежень Булевої задачі для максимального k-плекса. Досліджено вплив функціонально-надлишкових обмежень на покращення точності Лагранжевих двоїстих оцінок для цільової функції квадратичної задачі. Розроблено алгоритм пошуку всіх максимальних k-плексів та наведено результати тестових експериментів для його реалізації за допомогою програмного пакета GLPK (GNU Linear Programming Kit).