Том 19, номер 5, 2012 г., Стр. 83-100

УДК 519.87+519.854
Плясунов А. В., Панин А. А. 
Задача ценообразования. Часть I. Точные и приближённые алгоритмы решения

Аннотация:
Для исследуемой задачи ценообразования показано, что она NP-трудна в сильном смысле. Для её решения разработаны точные и приближённые алгоритмы, использующие декомпозицию, генетический локальный поиск и поиск с запретами. Приводятся результаты вычислительных экспериментов.
Табл. 3, библиогр. 25.

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

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

Статья поступила 1 июня 2011 г.
Исправленный вариант — 4 июня 2012 г.

Литература

[1] Васильев Ф. П. Методы оптимизации. — М.: Факториал Пресс, 2002. — 829 c.

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

[3] Дементьев В. Т., Шамардин Ю. В. Задача о выборе цен на продукцию при условии обязательного удовлетворения спроса // Дискрет. анализ и исслед. операций. Сер. 2. — 2002. — Т. 9, № 2. — C. 31–40.

[4] Панин А. А. Генетический алгоритм для одной задачи ценообразования // Тр. ИВМиМГ СО РАН. Сер. Информатика. — 2009. — Вып. 9. — С. 190–196.

[5] Плясунов А. В. О вычислительных возможностях метаэвристик // Мат. Росс. конф. «Дискретная оптимизация и исследование операций» (Владивосток, 7–14 сентября 2007 г.). — Новосибирск: Изд-во Ин-та математики, 2007. — С. 61–68.

[6] Плясунов А. А. Гибридные методы решения сложных комбинаторных задач, использующие декомпозицию // Сб. докл. 8-й междунар. конф. «Интеллектуальная обработка информации» (Республика Кипр, Пафос, 17–24 октября, 2010 г.). — М.: МАКС Пресс, 2010. — С. 286–289.

[7] Alekseeva E., Kochetova N., Kochetov Yu., Plyasunov A. A hybrid memetic algorithm for the competitive $p$-median problem // Preprints 13th IFAC Symp. Information Control Problems in Manufacturing. — Moscow, 2009. — P. 1516–1520.

[8] Alekseeva E. V., Kochetova N. A., Kochetov Yu. A., Plyasunov A. V. A heuristic and exact methods for the dicrete ($r|p$)-centroid problem. — Berlin: Springer-Verl., 2010. — P. 11–22. (Leсt. Notes Comput. Sci.; Vol. 6022).

[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, N 4. — P. 411–420.

[10] Chandru V., Hooker J. N. Optimization methods for logical inference. — New York: John Wiley & Sons, 1999. — 365 p.

[11] Dechter R. Constraint processing. — San Francisco: Morgan Kaufmann, 2003. — 481 p.

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

[13] Geoffrion A. V. Generalized Benders decomposition // J. Optimization Theory Appl. — 1972. — Vol. 10, N 4. — P. 237–260.

[14] Gote G., Laughton M. A. Large scale mixed integer programming: Benders-type heuristics // Eur. J. Oper. Res. — 1984. — Vol. 16. — P. 327–333.

[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] Van Hentenryck P., Milano M. Hybrid optimization: the ten years of CPAIOR. — New York: Springer Sci.+Business Media, 2011. — 570 p.

[17] Hooker J. N. Integrated methods for optimization. — New York: Springer Sci.+Business Media, 2007. — 490 p.

[18] Hooker J. N. Logic-based methods for optimization: combining optimization and constraint satisfaction. — New York: Wiley–Intersci., 2000. — 520 p.

[19] Lodi A., Milano M., Toth P. Integration of AI and OR techniques in constraint programming for combinatorial optimization problems. — Berlin: Springer-Verl., 2010. — 369 p. (Lect. Notes Comput. Sci.; Vol. 6140).

[20] Marriott K., Stuckey P. Programming with constraints: an introduction.—Cambridge: The MIT Press, 1998. — 476 p.

[21] McDaniel D., Devine M. A modified Benders partitioning algorithm for mixed integer programming // Manage. Sci. — 1977. — Vol. 24. — P. 312–319.

[22] Mirchandani P. D., Francis R. L. Decomposition methods for facility location problems // Discrete Location Theory. — New York: Wiley & Sons, 1990. — P. 439–478.

[23] Rebeiro C. C., Hansen P. Essays and surveys in metaheuristics. — Boston: Kluwer Acad. Publ., 2002. — 651 p.

[24] Vanderbeck F., Wolsey L. A. Reformulation and decomposition of integer programs. — Montreal: Center Oper. Res. Econometrics, 2009. — Vol. 2188. — 71 p.

[25] Vanderbeck F., Savelsbergh M.W. P. A generic view of Dantzig–Wolfe decomposition for integer programming // Oper. Res. Lett. — 2006. — Vol. 34. — P. 296–306.