P-Centro

Modelos de Localización de varios Centros Problema del p-centro
Localización de centros de servicio, 2006-2007

Índice
1. Formulación general 2. Resolución en un espacio de localización discreto3. Resolución en una red 4. Resolución en el plano 2 2 3 3

1

1.

Formulación general

El objetivo del problema del p-centro, es encontrar Yp = {y1 , y2, ..., yp } ⊂ S de manera que lamáxima distancia ponderada de los usuarios a Yp sea lo menos posible. Así, la formulación general del problema se puede expresar como: Min T (Yp ) = m´x wi di (Yp ) : Yp ⊂ S . a
1≤i≤n

donde Yp∗ y T ∗representan la solución y valor óptimo, respectivamente. Nuevamente, la obtención de los valores óptimos por enumeración será descartado.

2.

Resolución en un espacio de localización discretoSea S = {1, 2, ..., m} el conjunto de posibles localizaciones. Dado un valor t ∈ R, queremos determinar el menor conjunto de localizaciones Y = {y1 , y2 , ..., yk } tales que wi di (Y ) ≤ t, para todo i∈ I = {1, 2, ..., n}. Problema de cubrimiento (Qt ). El problema de cubrimiento, se puede plantear como un modelo de programación lineal, donde las variables binarias son: yj = y aij = y la funciónobjetivo es:
m

1 si se localiza un centro en j, 0 si no,

1 si wi dij ≤ t, 0 si no.

(Qt )

Min
j=1 m

yj aij yj ≥ 1, ∀i ∈ I
j=1

s.a

yj ∈ {0, 1}, ∀j.
∗ Sea yt una solución óptima,entonces resulta lo siguiente: m

T ≤ t si, y solo si,
j=1

∗

∗ yy (j) ≤ p,

∗ ∗ donde yt (j) es la componente j-´sima del vector yt . e

2

Algoritmo 1(Búsqueda Dicotómica) Paso 1:Comenzar con un intervalo inicial de incertidumbre [t, t], tal que t ≤ T ∗ ≤ t. Paso 2: Tomar tm =
t+t , 2

el punto medio del intervalo.

Paso 3: Resolver (Qtm ) entonces: (i) Si v(Qtm ) ≤ p,entonces hacer t = tm y repetir el paso 2, hasta que |t − t| < ǫ. (ii) Si v(Qtm ) > p, entonces hacer t = tm y repetir el paso 2, hasta que |t − t| < ǫ.

3.

Resolución en una red
Si el espacio de...