Алгоритм решения задач бинарного квадратичного программирования методом штрафных функций

Рассматривается обобщение классической задачи квадратичного программирования, когда наряду с линейными ограничениями допускается наличие квадратичных ограничений. Представлен случай, когда переменные могут принимать только бинарные значения — 0 или 1. Подобные задачи важны при выборе оптимальных структур систем, состоящих из большого числа вариантов, и выбор или отказ от выбора отдельных вариантов равносилен значениям 1 или 0 соответствующих бинарных переменных. Описана процедура сведения указанной задачи на основе метода штрафных функций к задаче полиномиального программирования четвертой степени, когда все слагаемые, кроме одного, имеющего четвертую степень, имеют степень не более второй. Решение полученной оптимизационной задачи сведено к решению системы уравнений, содержащих только бинарные переменные. Предложен эвристический рекуррентный алгоритм решения полученной системы уравнений, описаны варианты построения начального варианта решения, а также параметров, используемых в предложенном методе. В процессе сведения использованы классические формулы Кардано для корней кубического уравнения, для практического нахождения которых получены соотношения и описана процедура вычисления. Полученный алгоритм может быть использован также при решении многих задач дискретной математики.