Реферат: Рассматривается динамическая задача конкурентного размещения, моделирующая взаимодействие двух соперничающих сторон (Лидера и Последователя), размещающих свои объекты на рассматриваемом горизонте планирования, состоящего из некоторого числа периодов времени. Предполагается, что Лидер открывает свои объекты в начале горизонта планирования и не изменяет это решение внутри горизонта планирования. При этом Последователь может корректировать свое решение в каждом периоде горизонта планирования. Предлагается алгоритм поиска наилучшего решения, построенный на основе вычислительной схемы ветвей и границ. Для вычисления верхних границ используется специальная релаксация исходной двухуровневой задачи, усиленная дополнительными ограничениями. Предлагаются процедуры построения таких ограничений, в которых используются вспомогательные оптимизационные задачи для получения наиболее сильных отсечений. На примере задачи динамического конкурентного размещения на сети с тремя вершинами демонстрируются возможности модели учитывать информацию об изменениях параметров с течением времени. Реализация алгоритма ветвей и границ демонстрирует значительный эффект от использования отсечений, предложенных специально для динамических моделей: верхняя граница вычисляется более точно и сокращается число вершин дерева ветвления.

Библиографическая ссылка: Береснев В.Л. , Мельников А.А.
Алгоритм ветвей, границ и отсечений для неявной динамической задачи конкурентного размещения
Дискретный анализ и исследование операций. 2024. Т.31. №4. С.5–26. DOI: 10.33048/daio.2024.31.814

Даты:

Поступила в редакцию:	18 окт. 2024 г.
Принята к публикации:	1 нояб. 2024 г.
Опубликована в печати:	30 дек. 2024 г.
Опубликована online:	30 дек. 2024 г.

Идентификаторы БД: Нет идентификаторов

Цитирование в БД: Пока нет цитирований

Альметрики: