|
Программирование
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. Прикладное значение разработанного алгоритма заключается в его использовании для решения задачи «Формирование оптимального регионального заказа на подготовку профессиональных кадров по учреждениям высшего и среднего образования в Российской Федерации».
Ключевые слова:
нелинейное программирование, целочисленное программирование, численный метод, оптимизация.
Поступила в редакцию: 11.12.2018
Образец цитирования:
V. M. Tat'yankin, A. V. Shitselov, “A numerical method for solving quadratic integer programming problem”, Вестн. ЮУрГУ. Сер. Матем. моделирование и программирование, 12:3 (2019), 130–139
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/vyuru510 https://www.mathnet.ru/rus/vyuru/v12/i3/p130
|
Статистика просмотров: |
Страница аннотации: | 130 | PDF полного текста: | 39 | Список литературы: | 21 |
|