ПОИСК РЕШЕНИЯ ЗАДАЧИ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ С ПОМОЩЬЮ ИТЕРАТИВНОГО ОКРУГЛЕНИЯ КООРДИНАТ (2023)

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

Тип: Статья
Автор (ы): Матвеев Юрий Николаевич, Иванов Алексей Викторович
Ключевые фразы: ПОКООРДИНАТНЫЙ СПУСК, оптимизация, ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ, ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ, математическое программирование

Идентификаторы и классификаторы

УДК
004.021. Алгоритмы
eLIBRARY ID
60033806
Текстовый фрагмент статьи