Investigacion De operaciones Set-Covering
Enviado por ethan96 • 24 de Mayo de 2017 • Tarea • 7.191 Palabras (29 Páginas) • 550 Visitas
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]
...