Problema del conjunto de cobertura

Problema del conjunto de cobertura

El problema del Set Covering , también conocido por sus siglas SCP pertenece a la familia de los problemas no polinomiales duros, es un problema clásico en las Ciencias de la computación, consiste en encontrar las soluciones que minimicen el problema de cubrir un conjunto de necesidades con el menor costo posible. También se puede entender como el problema de encontrar el mínimo de subconjuntos que contengan todos los elementos de un conjunto dado, con el fin de minimizar algún valor.

Contenido

Definición formal

De una forma más formal se puede definir el problema de la cobertura como dado un universo U, una familia S de subconjuntos de U, una cobertura o solución para el problema es una subfamilia {C}\subseteq{S} cuya unión de por resultado el mismo U.

Ejemplo

Figura 1: Ejemplo de set covering para la cobertura de comunas.

Una estación de bomberos tiene la capacidad de cubrir las emergencias tanto de su comuna como de las comunas adyacentes a ella, por ejemplo una estación construida en la comuna 1 (Figura 1) podrá cubrir las emergencias de todo su vecindario, es decir, de la comuna 1, comuna 2 , comuna 3 y comuna 5. Se necesitan construir tantas estaciones de bomberos sean necesarias para cubrir todas las comunas ante posibles emergencias cuidando que todas las comunas estén cubiertas por al menos una estación (una o más) resguardando que la cantidad de estaciones construidas sea el mínimo.


Modelo matemático

Min \sum_{i=1}^{12} x_i

Sujeto a :

x_1+x_2+x_3+x_5 \ge 1

x_2+x_1+x_5 \ge 1

x_3+x_1+x_4 +x_5+x_6+x_7+x_8\ge 1

x_4+x_3+x_5+x_6+x_{11}\ge 1

x_5+x_1+x_2+x_3+x_4+x_{10}+x_{11}\ge 1

x_6+x_3+x_4+x_5+x_8+x_{11}\ge 1

x_7+x_3+x_8+x_{12}\ge 1

x_8+x_3+x_6+x_7+x_9+x_{11}+x_{12}\ge 1

x_9+x_8+x_{10}+x_{11}+x_{12}\ge 1

x_{10}+x_5+x_9+x_{11}\ge 1

x_{11}+x_4+x_5+x_6+x_8+x_9+x_{10}\ge 1

x_{12}+x_7+x_8+x_9\ge 1


X_{i} = \left\{ \begin{array}{l l} 1 &Si \, en \, la \, comuna \, i \, se \, construye \, una \, estacion \, \\ 0 & Si \, no \\ \end{array} \right.

Solución

Una solución para este problema seria construir estaciones en la comuna 1, 11 y 12. Con un total de 3 estaciones construidas se lograría cubrir las necesidades de todas las comunas del problema.


Wikimedia foundation. 2010.

Игры ⚽ Нужен реферат?

Mira otros diccionarios:

  • Problema de la cobertura de vértices — Saltar a navegación, búsqueda En ciencias de la computación, el Problema de la cobertura de vértices es un problema NP completo, que pertenece a los 21 problemas NP completos de Karp. Es muy utilizado en teoría de complejidad computacional para… …   Wikipedia Español

  • Conjunto independiente — El (inesperadamente asimétrico) conjunto de 9 vértices azules es un conjunto independiente maximal para este grafo de 24 vértices. En teoría de grafos, un conjunto independiente o estable es un conjunto de vértices en un grafo tal que ninguno es… …   Wikipedia Español

  • Conjunto Gaitero "Saladillo de Nerio Matheus" (Los Auténticos Gaiteros del Pueblo) — Conjunto Gaitero El Saladillo de Nerio Matheus [[Archivo: |220px]] …   Wikipedia Español

  • Cobertura de aristas — En teoría de Grafos , una covertura de aristas de un grafo es un conjunto de aristas donde cada vertice del grafo es incidente en al menos en una arista del conjunto. En ciencias de la computación, el problema de la cobertura mínima de arista es… …   Wikipedia Español

  • Cobertura de vértices — En matemáticas, en el campo de la teoría de grafos, un covering de un grafo es un conjunto de vértices (o arcos) cuyos elementos son cerrados (adyacentes) a todos los vértices (o nodos) del grafo. Es de especial interés encontrar pequeños… …   Wikipedia Español

  • Medidas para el impulso del sector inmobiliario en España — Las Medidas para el impulso del Sector Inmobiliario en España pretenden atajar la crisis inmobiliaria española de 2008 que supuso la supresión del Ministerio de la Vivienda. A principios de 2011 el Ministerio de Fomento plantea acompañar al… …   Wikipedia Español

  • Herrera del Duque — Para otros usos de este término, véase Herrera (desambiguación). Herrera del Duque …   Wikipedia Español

  • Modelo de cobertura legal — El modelo de cobertura legal, también conocido como modelo de Hempel, modelo de Popper Hempel, teoría de la subsunción[1] o modelo de cobertura legal inferencial,[2] es un intento de capturar los rasgos característicos de las explicación… …   Wikipedia Español

  • Conservación del suelo — Terrazas con cultivos de arroz en China. Conservación del suelo, en la agricultura, la ganadería o la silvicultura, es un conjunto de prácticas aplicadas para promover el uso sustentable del suelo …   Wikipedia Español

  • Historia del registro del sonido — El casete compacto fue el medio más popular para la reproducción y grabación de sonido …   Wikipedia Español

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”