Investigacion De operaciones Set-Covering

UNIVERSIDAD AUTÓNOMA DE NUEVO LEÓN.[pic 1][pic 2]

FACULTAD DE INGENIERÍA MECÁNICA Y ELÉCTRICA.

Investigación de operaciones

Producto integrador

Programación entera

Set - Covering

Dra. Jania A. Saucedo Martínez

Alumnos:

Dia: Martes

Fecha: 23/05/2017

INDICE

Contenido

Investigación de operaciones        2

Producto integrador        2

Programación entera        2

Set - Covering        2

Dra. Jania A. Saucedo Martínez        2

Alumnos:        2

Introducción        4

Problema del Set Covering        5

Origen        5

Aplicaciones        5

Otros métodos para su solución        6

Modelo matemático        6

PROBLEMA DE APLICACIÓN DEL SET COVERING        7

Conclusión        23

Bibliografía        23

Introducción

Sabemos que un modelo de Programación Entera es aquel cuya solución óptima tiene sentido solamente si una parte o todas las variables de decisión toman valores restringidos a números enteros, permitiendo agregar en el modelamiento matemático algunos aspectos que quedan fuera del alcance de los modelos de Programación Lineal.

Existen múltiples aplicaciones de modelos de Programación Entera como apoyo para la toma de decisiones.

En este producto integrador, vamos a analizar el método de programación “set covering”, también conocido como problema del conjunto de cobertura.

Se van a mencionar su origen, principales usos y objetivos de aplicación, su modelo matemático, así como la metodología para la solución del problema y sus variantes, identificaremos sus tipos de restricciones, también daremos a conocer sus posibles usos en la vida real, la forma de plantear el problema, así como su definición formal.

Mostraremos un ejemplo con todos los pasos y hasta llegar a la solución, y comprobar en que consiste dicha solución. Y al final concluiremos con la señalización de sus puntos de relevancia.

Problema del Set Covering

El Set Covering además de ser un problema clásico es el mas popular  de los modelos para la localización de instalaciones, que pertenece a la clase NP-Completo, donde la entrada esta dada por varios conjuntos de elementos o datos que tienen algún elemento en común. En general, estos problemas consisten en encontrar un conjunto de necesidades al menor costo posible.

En este problema se tienen que cubrir todas las tareas, aunque se repitan ciertas asignaciones.

En muchos casos, la distancia o tiempo de respuesta entre los clientes y los puntos que prestan los servicios, es decisiva para la satisfacción del cliente.

Este nos ayuda a minimizar el costo de las actividades que en su conjunto cubren

 todas las características al menos una vez.

Origen

Proviene de la Lista de 21 problemas NP-completos de Karp, es una lista de 21 problemas computacionales famosos, que tratan sobre combinatoria y teoría de grafos. Esta lista fue elaborada en 1972 por el informático teórico Richard Karp, en su trabajo seminal "Reducibility Among Combinatorial Problems" (Reducibilidadentre Problemas Combinatorios).

Aplicaciones

Existen muchas aplicaciones de este tipo de problema, siendo las principales la localización de servicios, selección de archivos en un banco de datos, simplificación de expresiones booleanas, balanceo de líneas de producción, entre otros.

1)En esta clase de problemas, varias plantas ofrecen servicios que se traslapan a varias instalaciones. El objetivo es determinar la cantidad minima de plantas que cubren cada instalación. Por ejemplo, se pueden construir plantas de tratamiento de agua en varios lugares, y cada planta sirve a un grupo de ciudades. El traslape ocurre cuando a una ciudad dada le da servicio mas de una planta.

La distancia o tiempo de respuesta entre los clientes y los puntos que prestan los servicios, es decisiva para la satisfacción del cliente. Por ejemplo, si se incendia un edificio, el tiempo de respuesta de una estación de bomberos es vital, ya que si se demora en llegar es posible que el incendio haya consumido por completo el edificio.

Otros métodos para su solución

En el artículo (Itaim, 2005) menciona que dada la dificultad de determinar la solución óptima y el gran tamaño de los problemas reales, es que se han ideado varios algoritmos de solución optima y algoritmos basados en heurística. Presentando asi soluciones optimas involucrando 1000 filas y 10000 columnas.

Modelo matemático

Existen m características y n combinaciones (subconjuntos) de dichas características. La elección de una combinación implica realizar todas las características de la misma. Se trata de minimizar el  costo  total  de  las  combinaciones  elegidas  de  manera que se cubra  o  posea cada  característica  i  al  menos  una  vez. Los datos son C j   costo de elegir  la  combinación  j y la matriz de pertenencia de cada característica  i   a  cada  combinación  j,  denominando las variables[pic 3]

...