Журнал Белорусского государственного университета: Математика, информатика, Iss 1, Pp 45-58 (2024)

комбинаторная оптимизация, квадратичная задача о назначениях, оптимизация на подстановках, строгая разрешимость задач, Mathematics, QA1-939

Описан класс четырехиндексных вещественных матриц, для которых гарантирована эффективная разрешимость квадратичной задачи выбора – достижение экстремальных значений ее функционала на одной из подстановок специального вида, приведенных в классической теореме Харди, Литлвуда и Полиа о перестановке трех систем. Условия, определяющие введенный класс матриц, обобщают все ранее предложенные условия, накладываемые на вид матриц и гарантирующие строгую разрешимость задач минимизации билинейной формы на декартовом произведении симметрической группы (условия теоремы о перестановке трех систем), квадратичной формы на симметрической группе, а также результаты аналогичного плана, полученные для квадратичной задачи о назначениях.