В
дискретной задаче о -центроиде
рассматривается ситуация, когда две фирмы последовательно
принимают решения о размещении предприятий. Сначала на рынок
выходит первая фирма (Лидер) и открывает
свои предприятий.
Затем, зная это решение, конкурирующая фирма (Конкурент)
открывает собственные предприятий.
Каждый клиент из множества всех открытых предприятий
выбирает одно, согласно собственным предпочтениям. Обслуживание
каждого клиента приносит доход. В зависимости от размещения
предприятий рынок (множество клиентов) как-то делится между
двумя фирмами. Каждая фирма стремится максимизировать свою долю
рынка. Задача состоит в том, чтобы найти множество предприятий
Лидера, позволяющее максимизировать его долю рынка (суммарный
доход).
Подробное описание
математической модели
На
сегодняшний день эффективные методы решения данной задачи неизвестны. Первые
шаги в этом направлении сделаны в [2], где предлагается точная схема
частичного перебора. В [1] исследуется частный случай задачи, когда
Конкурент размещает только одно предприятие. Методы локального поиска
описаны в [3, 4, 7, 8, 11].
Способы построения нижних и верхних оценок приводятся в
[3, 5, 11].
Полиномиальные случаи и результаты по
вычислительной сложности можно найти в [9, 10].
ЛИТЕРАТУРА
[1] F. Plastria, L. Vanhaverbeke. Discrete models for competitive location
with foresight. Computers and Oper. Res. 2008. V. 35, N. 3. P. 683–700.
[2] C.M.C. Rodriguez, J.A.M. Perez. Multiple voting location problems.
European J. Oper. Res. 2008. V.
191, N. 2.
P. 437–453.
[3]
Е.В.
Алексеева, Н.А. Кочетова. Верхние и нижние оценки для конкурентной задачи о
р-медиане // Труды 14 Байкальской международной школы-семинара
"Методы оптимизации и их приложения. Том 1. Северобайкальск.
2008. стр. 563-569
pdf-file 208 Kb
[4] Е.В. Алексеева, А.В. Орлов. Генетический алгоритм для конкурентной задачи о
р-медиане // Труды 14 Байкальской международной школы-семинара
"Методы оптимизации и их приложения". Том 1. Северобайкальск. 2008. стр.
570-585.
pdf-file 469 Kb
[5] Ю.А. Кочетов,
А.В.Кононов, А.В. Плясунов
Конкурентные модели размещения производства
// Журн. вычисл. матем. и матем. физики. 2009.
Т. 49б № 6ю С. 1-17.
pdf-file
338 Kb
[6] S.L. Hakimi. On locating new facilities in a competitive environment.
European J. Oper. Res. 1983. V. 12, P. 29–35.
[7] S. Benati, G. Laporte. Tabu search
algorithms for the (r | Xp)-medianoid and (r|p)-centroid
problems. Location
Science. 1994. V.2, N.2, P. 193-204.
[8] J. Bhadury, H.A. Eiselt, J.H.
Jaramillo. An alternating heuristic for medianoid and centroid problems in
the plane. Computers and Oper. Res. 2003. V. 30. P. 553-565.
[9] H. Noltermeier, J. Spoerhose, H.C.
Wirth. Muliple voting location and single voting location on trees.
European J. Oper. Res. 2007. V. 181. P. 654-667.
[10] J. Spoerhose, H.C. Wirth. (r/p)-Centroid
problems on paths and trees. Tech. Report 441, Inst. Comp. Science,
University of Würzburg, 2008.
[11] E. Alekseeva, N. Kochetova, Yu.
Kochetov, A. Plyasunov. A hybrid memetic algorithm for the competitive p-median
problem.
Proc. of XIII IFAC Symposium on Information Control Problems in Manufacturing
(INCOM '09).
Moscow. 2009.
pdf.file 143 Kb
|
Библиотека тестовых задач