Институт вычислительной математики и математической геофизики СОРАН

Пятая азиатская международная школа-семинар "Проблемы оптимизации сложных систем"

Кыргызская Республика, г.Бишкек, база "Эдельвейс" Иссык-Кульского Государственного Университета, 12 - 22 августа.
ВАЖНАЯ ИНФОРМАЦИЯ

Тезисы докладов

Стратегия коротких медиан для конкурентной задачи о р-медиане

Кочетова Н.А., Алексеева Е.В.

Институт математики им. С.Л. Соболева СО РАН (Новосибирск)

В конкурентной задаче о $p$-медиане заданы конечные множества клиентов и предприятий. Известна матрица $(g_{ij})$ расстояний между клиентами и предприятиями. Два игрока, Лидер и Конкурент, открывают свои предприятия, стараясь захватить как можно большую часть рынка. Лидер открывает $p$ предприятий первым. Затем Конкурент открывает свои $r$ предприятий. Каждый клиент из открытых $p+r$ предприятий выбирает ближайшее предприятие в качестве своего поставщика. Задача состоит в том, чтобы выбрать за Лидера $p$ предприятий так, чтобы после наилучшего хода Конкурента получить максимальную долю рынка.

Известно, что игнорируя Конкурента и решая за Лидера классическую задачу о $p$-медиане, получаем достаточно хорошее приближенное решение задачи. У такого подхода есть очевидный недостаток: решая задачу о $p$-медиане, Лидер стремится обслужить всех клиентов, несмотря на то, что часть из них неизбежно окажется у Конкурента. Уйдут те клиенты, для которых предприятия Конкурента окажутся ближе предприятий Лидера. Новая стратегия последовательно запрещает использование элементов матрицы $(g_{ij})$, начиная с самых больших. На каждой итерации решается задача о $p$-медиане на незапрещенных элементах матрицы $(g_{ij})$ и наилучшее решение с учетом реакции Конкурента предъявляется в качестве ответа. Такой подход позволяет избавиться от наиболее удаленных клиентов (Камчатки) и еще ближе придвинуть предприятия к основной части клиентов. Приводятся результаты численных экспериментов на тестах из библиотеки {it <<Дискретные задачи размещения>>} (http://math.nsc.ru/AP/benchmarks). Проводится сравнение с другими известными эвристиками и точным решением задачи. Работа выполнена при финансовой поддержке РФФИ (грант 08--07--00037) и АВЦП Рособразования (проект 2.1.1/3235).

Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии
Обратная связь

[Головная страница]
[Конференции]

© 2009, Институт Вычислительной Математики и Математической Геофизики СО РАН, Новосибирск
© 1996-2009, Сибирское отделение Российской академии наук, Новосибирск
Дата последней модификации: 06-Jul-2012 (11:52:52)