Задача о p-медиане возникает во многих приложениях, например, размещение предприятий бытового обслуживания, складов [1, 2], пунктов автосервиса на дорогах, коммутаторов в телефонной сети и др. [3]. Она отличается от простейшей задачи размещения двумя аспектами в ней не учитываются стоимости на открытие предприятий и есть ограничение на число предприятий, которые могут быть открыты.  Задача о  p-медиане принадлежит классу NP-трудных в сильном смысле задач, поскольку к ней сводится задача о вершинном покрытии.

Рассмотрим множество I = {1,..., n} потенциальных мест открытия предприятий, множество J = {1,..., m} клиентов и
n m матрицу  (g_ij) транспортных затрат на удовлетворение спроса j-го клиента i-м предприятием. Задача о p-медиане заключается в размещении p предприятий из множества I таким образом, чтобы минимизировать общие транспортные затраты на обслуживание всех  клиентов. Запишем ее в виде задачи целочисленного линейного программирования:

 

ЛИТЕРАТУРА

1. Cristofides, N. Graph Theory. An Algorithm Approach. New York: Academic Press. 1975.

2. Hansen, P. and Jaumard, B. Cluster Analysis and Mathematical Programming. Mathematical Programming 79 (1997), p. 191-215.

3. Krarup, J. and Pruzan, P. The simple plant location problem: survey and synthesis. European J. Oper. Res. 12 (1983), N 1, p.36-81.

4. Mirchandani, P. and Francis, R. (eds.) Discrete Location Theory. Wiley-Intersience. 1990.

 

На главную