Control Systems and Computers, N6, 2019, Статья 2
https://doi.org/10.15407/csc.2019.06.021
Нагірна А.Н. Квадратична задача на множині сполучень та метод її розв’язання. Control Systems and Computers. 2019. № 6. C. 21-27.
УДК 364.2:331; 681.513
Нагорная А.Н., кандидат физико-математических наук, доцент, Национальный университет «Киево-Могилянская академия», ул. Сковорода, 2, Киев, 04070, Украина naghirnaalla@ukr.net
Квадратичная задача на множестве сочетаний и
метод ее решения
Введение. При моделировании различного рода процессов и явлений в разных сферах деятельности, довольно часто применяются модели, представляющие собой квадратичные задачи условной оптимизации. Особого внимания заслуживают модели таких задач, рассмотренных на комбинаторных множествах, в частности, сочетаний. Не смотря на простоту представления, данного типа задачи, являются громоздкими, с вычислительной точки зрения. По этому, возникает необходимость в построении новых методов и алгоритм решения.
Целью данной статьи является представления метода решения квадратичной задачи с дополнительными ограничениями на множестве сочетаний. Данный метод позволяет за конечное число шагов найти оптимальное решение сформулированной задачи. Использование данного метода показано на числовом примере.
Методы. Метод решения задачи с квадратичной функцией цели на множестве сочетаний.
Результаты. Сформулирована оптимизационная задача на комбинаторном множестве сочетаний с квадратичной функцией цели и дополнительными ограничениями. Предложен метод ее решения, который заключается в нахождении опорных решений, с использованием свойств множества сочетаний, а также нахождении приростов ограничений и функции цели. Представлен пример решения задачи с использованием предложенного метода.
Выводы. Предложенный метод можно использовать для решения задач условной оптимизации с квадратичной функцией цели на комбинаторном множестве сочетаний.
Загрузить полный текст в PDF (українською).
Ключевые слова: оптимизация, квадратичная задача, квадратичная функция, множество сочетаний, прирост функции цели, прирост дополнительного ограничения, опорное решение, оптимальное решение.
Поступила 03.12.2019
