Том 21, номер 5, 2014 г., Стр. 54-66

УДК 519.87+519.854
Панин А. А., Плясунов А. В.
О сложности двухуровневых задач размещения и ценообразования

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

Ключевые слова: двухуровневая задача, размещение, ценообразование, вычислительная и аппроксимационная сложности, NP-трудность в сильном смысле, AP-сводимость, Poly-APX-полнота.

Панин Артём Александрович ^1,2
Плясунов Александр Владимирович ^1,2
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: arteam1897@gmail.com, apljas@math.nsc.ru

Статья поступила 15 октября 2013 г.
Исправленный вариант — 29 января 2014 г.

Литература

[1] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. - М.:Мир, 1982. - 416 с.

[2] Кочетов Ю. А., Плясунов А. В. Полиномиально разрешимый класс задач двухуровневого линейного программирования // Дискрет. анализ и исслед. операций. Cер. 2. - 1997. - T. 1, №2. - С. 23–33.

[3] Панин А. А., Плясунов А. В. Задача ценообразования. Ч. 1. Точные и приближённые алгоримы решения // Дискрет. анализ и исслед. операций. - 2012. - Т. 19, №2.- С. 31–40.
Panin A. A., Plyasunov A. V. The pricing problem. I: Exact and approximate algorithms // J. Appl. Industr. Math. - 2013. - Vol. 7, N2. - P. 241–251.

[4] Панин А. A., Плясунов А. B. Задача ценообразования. Ч. 2. Вычислительная сложность // Дискрет. анализ и исслед. опер. - 2012. - T. 19, №6. - С. 56–71.
Panin A. A., Plyasunov A. V. The pricing problem. II: Computational complexity // J. Appl. Industr. Math. - 2013. - Vol. 7, N3. - P. 420–430.

[5] Aboolian R., Berman O., Krass D. Competitive facility location model with concave demand // Eur. J. Oper. Res. - 2007. - Vol. 181. - P. 598–619.

[6] Aboolian R., Berman O., Krass D. Optimizing pricing and location decisions for competitive service facilities charging uniform price // J. Oper. Res. Soc. - 2008. - Vol. 59. - P. 1506–1519.

[7] Ausiello G., Crescenzi P., Gambosi G., Kann V., Marchetti-Spaccamela A., Protasi M. Complexity and approximation: combinatorial optimization problems and their aproximability properties. - Berlin: Springer-
Verl., 1999. - 524 p.

[8] Bazgan C., Escoffer B., Paschos V. Th. Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness // Theor. Comput. Sci. - 2005. - Vol. 339. - P. 272–292.

[9] Bouhtou M., Grigoriev A., Van Der Kraaij A. F., Van Hoesel S., Spieksma F., Uetz M. Pricing bridges to cross a river // Naval Res. Logistics. - 2007. - Vol. 54, N4. - P. 411–420.

[10] Crescenzi P., Kann V., Silvestri R., Trevisan L. Structure in approximation classes // SIAM J. Comput. - 1999. - Vol. 28, N5. - P. 1759–1782.

[11] Dasci A., Laporte G. Location and pricing decisions of a multistore monopoly in a spatial market // J. Region. Sci. - 2004. - Vol. 44. - P. 489–515.

[12] Dempe S. J. Foundations of bilevel programming. - Dordrecht: Kluwer Acad. Publ., 2002. - 481 p.

[13] Eiselt H. A., Marianov V. Foundations of location analysis. - New York:
Springer-Verl., 2011. - 510 p.

[14] Grigoriev A., van Loon J., Sviridenko M., Uetz M., Vredeveld T. Optimal bundle pricing with monotonicity constraint // Oper. Res. Lett. - 2008. - Vol. 36, N5. - P. 609–614.

[15] Hanjoul P., Hansen P., Peeters D., Thisse J.-F. Uncapacitated plant location under alternative spatial price policies // Market Sci. - 1990. - Vol. 36. -P. 41–57.

[16] Serra D., ReVelle C. Competitive locations and pricing on networks // Geograph. Anal. - 1999. - Vol. 31. - P. 109–129.

[17] Vives X. Oligopoly pricing: old ideas and new tools. - Cambridge, MA: MIT Press, 1999. - 425 p.