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

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

Dates:

Submitted:	Oct 18, 2024
Accepted:	Nov 1, 2024
Published print:	Dec 30, 2024
Published online:	Dec 30, 2024

Identifiers: No identifiers

Citing: Пока нет цитирований

Altmetrics: