Дискретная математика и Математическая кибернетика

Условия эффективной разрешимости квадратичной задачи выбора. Часть 2

В. М. Демиденко

Белорусский государственный экономический университет

Аннотация: В современной терминологии условия классической теоремы Харди, Литлвуда и Полиа о перестановке трех систем гарантируют строгую разрешимость задачи оптимизации билинейной формы с симметрической матрицей Тёплица специального вида. Билинейная форма с указанной матрицей принимает экстремальные значения на подстановках двух видов в зависимости от того, одинаковые или противоположные упорядочения имеют компоненты двух векторов, определяющих значения переменных. В предыдущей части статьи были описаны условия достижения минимума функционала квадратичной задачи выбора на первой из заданных подстановок, обобщающие ряд результатов аналогичного плана для задачи минимизации квадратичной формы и квадратичной задачи о назначениях. В этой части работы рассматриваются условия, накладывание которых на элементы четырех индексной матрицы гарантирует достижение минимума функционала квадратичной задачи выбора на второй под становке, приведенной в теореме о перестановке трех систем. Результаты, представленные в двух частях статьи, на сегодняшний день описывают наиболее широкие классы четырехиндексных матриц, для которых функционал квадратичной задачи выбора принимает экстремальные значения на фиксированных подстановках.

Ключевые слова: Комбинаторная оптимизация; квадратичная задача о назначениях; оптимизация на подстановках; эффективно разрешимые случаи.

УДК: 519.157.2