Дискретные
задачи размещения 
Библиотека тестовых задач
Дискретные задачи размещения
|
Задача о
p-медиане с предпочтениями клиентов |
|
В классических моделях размещения производства предполагается, что имеется одно лицо, принимающее решение
(ЛПР). Как правило, это руководитель фирмы, размещающий свои предприятия для обслуживания клиентов. Множество возможных пунктов размещения предприятий I = {1,…, n} и множество клиентов J = {1,…, m} считаются известными. Заданы также производственно–транспортные затраты cij ³ 0 для каждой пары (i, j), iÎI, jÎJ, и число p > 0 открываемых предприятий. Требуется найти подмножество S Ì I , | S | = p открываемых предприятий, которое позволяет обслужить всех клиентов с минимальными суммарными затратами, т.е. найти
Заметим, что при выбранном множестве S открываемых предприятий, каждый клиент обслуживается из наиболее «дешевого» для ЛПР предприятия. Такое положение естественно при централизованном планировании. Однако в рыночных условиях клиенты могут сами выбирать поставщика продукции, исходя из собственных предпочтений.
В этом случае математическая модель может быть представлена как игра двух лиц: ЛПР1 — руководитель фирмы, ЛПР2 — лицо, представляющие интересы клиентов. В этой игре сначала ЛПР1 выбирает подмножество предприятий, затем ЛПР2 выбирает поставщиков для каждого клиента. Игроки неравноправны. Сначала делает ход ЛПР1. Затем, зная это решение, делает ход ЛПР2. Такие игры известны под названием игр Штакельберга [4].
Пусть матрица (dij) задает предпочтения клиентов на множестве предприятий. Если
то j-й клиент предпочитает предприятие i1. Для упрощения модели будем предполагать, что в каждом столбце матрицы dij все элементы различные. В противном случае придется рассматривать оптимистические и пессимистические стратегии и вводить понятия кооперативной и некооперативной игры [2]. Итак, цель ЛПР1 по прежнему состоит в выборе подмножества S Ì I, которое позволяет обслужить всех клиентов с минимальными суммарными затратами, но теперь ЛПР1 вынужден учитывать решение ЛПР2 по выбору поставщиков.
Введем две группы переменных:
ЛПР1:
ЛПР2:
Теперь математическая модель может быть представлена в виде следующей задачи двухуровневого программирования [1, 2, 5]. Найти
при условиях
xi Î {0,1}, iÎI,
где xij*(xi) — оптимальное решение задачи ЛПР2:
при условиях
xij £ xi, iÎI, jÎJ;
xij Î {0,1}, iÎI, jÎJ.
Целевая функция ЛПР1 по-прежнему задает суммарные затраты на обслуживание клиентов. Отличие от классической постановки состоит в том, что теперь множество допустимых решений задается как требованием целочисленности переменных xi, iÎ I (что соответствует условию S Ì I) и ограничением на число открываемых предприятий (| S | = p), так и вспомогательной оптимизационной задачей (задача ЛПР2). При решении этой задачи вектор xi считается известным.
Первые модели размещения производства с предпочтениями клиентов рассматривались в [6]. Существуют различные способы сведения данной двухуровневой задачи к задачам целочисленного линейного программирования [2, 5]. Известно, что поиск оптимального решения сводится к минимизации псевдо-булевой функции общего вида или выбору оптимального набора строк пары матриц [2]. Известны ее полиномиально разрешимые случаи [2], а при условии cij = dij, iÎI, jÎ J двухуровневая задача совпадает с классической задачей о p-медиане.
ЛИТЕРАТУРА
Береснев В.Л. Дискретные задачи размещения и полиномы от булевых переменных. Новосибирск. Изд-во Инст. математики. 2005.
Горбачевская Л.Е. Полиномиально разрешимые и NP-трудные задачи стандартизации. Канд. дисс. Институт математики им. С.Л. Соболева СО РАН. Новосибирск. 1998.
Кочетов Ю.А. Двухуровневые задачи размещения. Труды ИВМиМГ. Серия Информатика. вып. 6. 2006 г.
Мулен Э. Теория игр с примерами из математической экономики. М.: Мир. 1985.
Hansen P., Kochetov Yu., Mladenovic N. Lower bounds for the uncapacitated facility // Proceedings of Discrete Optimization Methods in Production and Logistics (DOM'2004) 2nd International Workshop, Omsk. 2004. P. 50–55.
Hanjoul P., Peeters D. A facility location problem with clients' preference orderings, Regional Science and Urban Economics. 1987. v. 17, P. 451–473.
