Программирование
A numerical method for solving quadratic integer programming problem
[Численный метод решения задачи целочисленного и квадратичного программирования определенного вида]
V. M. Tat'yankin,
A. V. Shitselov Yugra State University, Khanty-Mansiysk, Russian Federation
Аннотация:
Предлагается новый численный метод решения задачи целочисленного программирования квадратичного вида. Алгоритм основан на специальном представлении минимизатора соответствующего целевого функционала. Проблема может быть сведена к специальной задаче с наименьшими квадратами с ограничениями. Для разработанного метода был предложен алгоритм решения задачи целочисленного программирования квадратичного вида. Преимущество представленного алгоритма заключается в невысокой вычислительной сложности, в среднем, которая оценивается в
$O(n\ln(n))$. Данная вычислительная сложность подтверждена экспериментально. Эксперимент заключался в решении задачи при количестве неизвестных
$10, 10^2,\dots, 10^8$. Каждое вычисление производилось
$500$ раз. Разработанный алгоритм состоит из
$3$ шагов. В среднем, в
$83,6\%$ случаях, решение находилось на
$2$ шаге, оставшиеся решения — на
$3$ шаге. Численный эксперимент реализован на языке «Python» и размещeн на сервисе GitHubGist. Прикладное значение разработанного алгоритма заключается в его использовании для решения задачи «Формирование оптимального регионального заказа на подготовку профессиональных кадров по учреждениям высшего и среднего образования в Российской Федерации».
Ключевые слова:
нелинейное программирование, целочисленное программирование, численный метод, оптимизация.
УДК:
519.854.3
MSC: 49M37 Поступила в редакцию: 11.12.2018
Язык публикации: английский
DOI:
10.14529/mmp190311