Программные продукты и системы

Для решения задачи квадратичного программирования разработаны различные приближенные методы и варианты квадратичного симплекс-метода, основанные на методе Лагранжа. Но приближенные методы не способны дать точное решение, а симплекс-метод требует введения дополнительных переменных и учета нелинейных условий дополнительной нежесткости, что усложняет задачу и увеличивает ее размерность. В литературе описан метод, заключающийся в последовательном решении квадратичной задачи на различных гранях множества ограничений, при этом требуется решать системы линейных уравнений меньшей размерности, чем при использовании симплекс-метода, но большей, чем число переменных целевой функции. В данной работе предложен точный метод решения квадратичной задачи, основанный на решениях систем линейных уравнений, размерность которых не выше числа переменных целевой функции.
Суть метода состоит в том, что задача поиска максимума квадрики на многогранном множестве ограничений сводится к задаче поиска минимального расстояния между точкой безусловного максимума и границей многогранной области ограничений. Для определения расстояния строятся перпендикуляры к граням многогранника, а для уменьшения числа исследуемых граней разработан специальный порядок перебора граней.

Подробное описание дается в статье «Линейное решение задачи квадратичного программирования», автор Татаренко С.И. (Тамбовский государственный технический университет, Тамбов).