Алгоритм ветвей, границ и отсечений для неявной динамической задачи конкурентного размещения

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