О сложности двухуровневых задач размещения и ценообразования

Рассматриваются двухуровневые частично-целочисленные задачи размещения и ценообразования. Каждая из них определяется оптимизационными задачами верхнего и нижнего уровней, первая из которых описывает выбор размещения и ценообразования, а вторая моделирует реакцию потребителей на решение верхнего уровня. Основные усилия в работе концентрируются вокруг изучения вычислительной сложности двухуровневых задач с разными стратегиями ценообразования: равномерной, фабричной и дискриминационной. Показано, что при любой стратегии ценообразования соответствующая оптимизационная задача NP-трудна в сильном смысле, принадлежит классу Poly-APX и является полной в нём относительно AP-сводимости. Библиогр. 17.