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

Авторы: Кирюхин Е.А.
Опубликовано в выпуске: #5(100)/2025
DOI:
Раздел: Информатика, вычислительная техника и управление | Рубрика: Информационные технологии. Компьютерные технологии. Теория вычислительных машин и систем
Ключевые слова: оптимизационные задачи, задачи дискретной оптимизации, задача коммивояжера, методы решения оптимизационных задач, популяционный алгоритм, надстройка Microsoft Excel «Поиск решения», язык программирования С++
Опубликовано: 17.10.2025

Проанализированы процессы постановки задач дискретной оптимизации и методы их решения. В качестве примера рассмотрена задача коммивояжера. Для постановки ее условия введен ряд определений и классификаций, а затем построена ее математическая модель. На примере данной задачи выполнено сравнение двух распространенных способов решения оптимизационных задач с помощью современных цифровых инструментов. В качестве первого способа рассмотрено решение с использованием надстройки Microsoft Excel «Поиск решения». В качестве второго решения рассмотрена разработка программного продукта, реализующего один из методов решения задач дискретной оптимизации, а именно эволюционную стратегию популяционного алгоритма. Данный метод также был использован и в первом способе решения. Стоит учитывать, что программная реализация такого решения может быть осуществлена на любом современном языке программирования. В статье приведен пример программного решения, разработанного на языке программирования С++. Решение с помощью разработанного программного обеспечения определило оба верных маршрута с равной минимальной длиной для заданных исходных данных, в отличие от решения с использованием надстройки «Поиск решения», которое ввиду специфики своей организации выдало только одно верное решение. На основе результатов сравнения двух решений обоснована целесообразность решения оптимизационных задач путем разбиения условия поставленной задачи на входные и выходные данные с последующим составлением математической модели задачи, в частности, заданием целевой функции и разработкой универсального программного решения на любом современном языке программирования.

Литература

[1] Гашков С.Б. Дискретная математика. Санкт-Петербург, Лань, 2025, 520 с.

[2] Шевляков А.Н. Основы дискретной математики. Омск, ОмГУ, 2020, 98 с.

[3] Белоусов А.И., Ткачев С.Б. Дискретная математика. Москва, Изд-во МГТУ им. Н.Э. Баумана, 2020, вып. 19, 703 с.

[4] Ржевский С.В. Математическое программирование. Санкт-Петербург, Лань, 2022, 608 с.

[5] Рогова Н.В., Старожилова О.В. Математическое программирование. Самара, ПГУТИ, 2024, 177 с.

[6] Борознов В.О. Исследование решения задачи коммивояжера. Вестник Астраханского государственного технического университета. Серия: Управление, вычислительная техника и информатика, 2009, № 2, с. 147–151.

[7] Рахмангулов А.Н., Цыганов А.В., Пикалов В.А., Муравьев Д.С. Математическое моделирование транспортных систем и процессов. Магнитогорск, Изд-во Магнитогорского гос. техн. ун-та, 2021, 190 с.

[8] Перлюк В.В. Методы оптимизации проектных решений. Санкт-Петербург, ГУАП, 2023, 121 с.

[9] Гапанович В.С., Гапанович И.В. Методы решения оптимизационных задач. Тюмень, ТИУ, 2014, 272 с.

[10] Поиск решения в Excel: пример использования функции для решения задачи с неизвестными параметрами. URL: https://exceltut.ru/poisk-resheniya-v-excel-primer-ispolzovaniya-funktsii-dlya-resheniya-zadachi-s-neizvestnymi-parametrami/ (дата обращения 20.03.2025).

[11] Функция Поиск решения в Excel. Включение, пример использования со скриншотами. URL: https://office-guru.ru/excel/funkciya-poisk-resheniya-v-excel-vklyuchenie-primer-ispolzovaniya-so-skrinshotami.html (дата обращения 20.03.2025).