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

Изучается проблема размещения предприятий (средств обслуживания) в условиях конкуренции, когда две фирмы последовательно открывают свои предприятия, а каждый потребитель выбирает открытое предприятие, исходя из своих собственных предпочтений, и приносит доход фирме-лидеру или фирме-последователю. Задача состоит в том, чтобы выбрать размещение предприятий фирмы-лидера так, чтобы с учётом реакции фирмы-последователя и известных предпочтений потребителей получить максимальный доход (прибыль). Даны формулировки рассматриваемых задач в виде задач целочисленного линейного двухуровневого программирования и эквивалентные формулировки в виде задач псевдобулева двухуровневого программирования. Предлагается способ построения верхних оценок значений целевых функций рассматриваемых задач конкурентного размещения. Соответствующий алгоритм состоит в построении вспомогательной псевдобулевой функции, называемой оценочной, и отыскании наименьшего значения этой функции. Для частного случая – задач конкурентного размещения на сети в виде цепи – предлагаются полиномиальные алгоритмы получения оптимальных решений. Приводятся результаты вычислительного эксперимента, позволяющего оценить точность вычисления верхних оценок для задач конкурентного размещения предприятий на цепи. Табл. 1, ил. 1, библиогр. 15.