23
Modelos de Programación Entera - Heurísticas Optimización de Operaciones Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería Industrial – Pontificia Universidad Javeriana Sede Bogotá

Modelos de Programación Entera - Heurísticas Optimización de Operaciones Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería

Embed Size (px)

Citation preview

Page 1: Modelos de Programación Entera - Heurísticas Optimización de Operaciones Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería

Modelos de Programación Entera - Heurísticas

Optimización de Operaciones

Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería Industrial – Pontificia Universidad Javeriana Sede Bogotá

Page 2: Modelos de Programación Entera - Heurísticas Optimización de Operaciones Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería

Matriz de Distancias Indica el valor de distancia (costo, flujo), entre dos locaciones. Es común

que se utilice la distancia “rectilínea”, en vez de la euclidiana para garantizar la linealidad del modelo.

Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería Industrial – Pontificia Universidad Javeriana Sede Bogotá

Page 3: Modelos de Programación Entera - Heurísticas Optimización de Operaciones Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería

Optimización de la cadena de abastecimiento La administración de la cadena de abastecimiento abarca múltiples procesos

y operaciones que transforman las materias primas en productos y los distribuyen a través de los canales de ventas al detalle. En este caso, las variables de decisión consisten en cuánto producir (o comprar), en cada locación, y cuánto enviar por cada nodo disponible con el fin de satisfacer las demandas proyectadas.

Costos Logísticos Costos de Producción Costos de Transporte Costos Fijos Costos Transaccionales Costos de logística inversa

Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería Industrial – Pontificia Universidad Javeriana Sede Bogotá

Page 4: Modelos de Programación Entera - Heurísticas Optimización de Operaciones Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería

Características de un modelo de Cadena de Suministro Objetivos

Maximizar los ingresos globales de los stakeholders. Minimizar los costos logísticos, Incrementar el flujo que circula por los nodos, Minimizar la probabilidad de generar faltantes. Disminuir los tiempos de entrega.

Restricciones Capacidad física de cada nodo. Demanda del consumidor (Push - Pull). Tiempos de procesamiento y envío. Capacidad de las rutas de transporte. Niveles de Inventario.

Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería Industrial – Pontificia Universidad Javeriana Sede Bogotá

Page 5: Modelos de Programación Entera - Heurísticas Optimización de Operaciones Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería

Modelo S- Proveedores, P- Proceso, C- Clientes.

M – Producción, F –Terminación, W- Bodegas.

xi decisión de utilización de locación o máquina i

rkij cantidad de producto k a enviar desde

i a j.

ci costo de crear la locación i o adquirir máquina i.

qkij costo de transportar el producto k

desde i a j.

rkj requisitos de producción del producto

k en el nodo j.

mj capacidad de la locación j

Restricción de nodos.

Restricción de demanda.

Restricción de capacidad de producción o abastecimiento.

Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería Industrial – Pontificia Universidad Javeriana Sede Bogotá

Page 6: Modelos de Programación Entera - Heurísticas Optimización de Operaciones Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería

Interpretación de la solución

Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería Industrial – Pontificia Universidad Javeriana Sede Bogotá

Page 7: Modelos de Programación Entera - Heurísticas Optimización de Operaciones Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería

Distribución de Planta Es un concepto relacionado con la disposición de las máquinas, los departamentos,

las estaciones de trabajo, las áreas de almacenamiento, los pasillos y los espacios comunes dentro de una instalación productiva propuesta o ya existente . La finalidad fundamental de la distribución en planta consiste en organizar estos elementos de manera que se asegure la fluidez del flujo de trabajo, materiales, personas e información a través del sistema productivo. 

Variables Involucradas Distancias entre estaciones. Flujo de estaciones. Tiempos de Transporte. Áreas disponibles.

Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería Industrial – Pontificia Universidad Javeriana Sede Bogotá

Page 8: Modelos de Programación Entera - Heurísticas Optimización de Operaciones Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería

Características del modelo Función Objetivo

Utilización del espacio Utilización de equipos Minimizar costo de flujo Minimizar distancias Minimizar tiempos muertos Importancia relativa de cercanía

Restricciones Traslape de áreas Restricción de área mínima por departamento Zonas prohibidas y Zonas específicas Comunicación de departamentos Pérdida de rutas peatonales

Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería Industrial – Pontificia Universidad Javeriana Sede Bogotá

Page 9: Modelos de Programación Entera - Heurísticas Optimización de Operaciones Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería

Modelo

Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería Industrial – Pontificia Universidad Javeriana Sede Bogotá

Page 10: Modelos de Programación Entera - Heurísticas Optimización de Operaciones Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería

Interpretación de la solución

Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería Industrial – Pontificia Universidad Javeriana Sede Bogotá

Page 11: Modelos de Programación Entera - Heurísticas Optimización de Operaciones Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería

Heurísticas Consiste en una manera de buscar la solución de un

problema mediante métodos no rigurosos, implementando técnicas empíricas. Su objetivo es encontrar buenas soluciones (No óptimas) en tiempo razonable

El método consiste en generar candidatos de soluciones posibles de acuerdo a un patrón dado; luego los candidatos son sometidos a pruebas de acuerdo a un criterio que caracteriza a la solución. Si un candidato no es aceptado, se genera otro; y los pasos dados con el candidato anterior no se consideran

Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería Industrial – Pontificia Universidad Javeriana Sede Bogotá

Page 12: Modelos de Programación Entera - Heurísticas Optimización de Operaciones Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería

¿Cuándo usar Héurísticas? Tiempos de ejecución inaceptables para ciertos problemas.

(Especialmente problemas MIP)

Encontrar un modelo matemático exacto es muy complicado.

No es absolutamente necesario encontrar la solución óptima.

Page 13: Modelos de Programación Entera - Heurísticas Optimización de Operaciones Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería

Clasificación de Problemas

Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería Industrial – Pontificia Universidad Javeriana Sede Bogotá

Page 14: Modelos de Programación Entera - Heurísticas Optimización de Operaciones Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería

Heurística del vecino más cercano

Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería Industrial – Pontificia Universidad Javeriana Sede Bogotá

Page 15: Modelos de Programación Entera - Heurísticas Optimización de Operaciones Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería

Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería Industrial – Pontificia Universidad Javeriana Sede Bogotá

Ejemplo

Page 16: Modelos de Programación Entera - Heurísticas Optimización de Operaciones Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería

Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería Industrial – Pontificia Universidad Javeriana Sede Bogotá

Ejemplo

Page 17: Modelos de Programación Entera - Heurísticas Optimización de Operaciones Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería

Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería Industrial – Pontificia Universidad Javeriana Sede Bogotá

Ejemplo

Page 18: Modelos de Programación Entera - Heurísticas Optimización de Operaciones Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería

Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería Industrial – Pontificia Universidad Javeriana Sede Bogotá

Ejemplo

Page 19: Modelos de Programación Entera - Heurísticas Optimización de Operaciones Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería

Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería Industrial – Pontificia Universidad Javeriana Sede Bogotá

Ejemplo

Page 20: Modelos de Programación Entera - Heurísticas Optimización de Operaciones Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería

Teoría de la complejidad computacional Medición del desempeño de un algoritmo

Análisis empírico: El objetivo es estimar como los algoritmos se comportan en la practica mediante pruebas con diferentes instancias y tamaños.

Análisis del caso promedio: El objetivo es estimar el número esperado de pasos de acuerdo al tamaño. Se escoge una función de probabilidad y se emplea el análisis estadístico.

Análisis del peor caso: Se dan los limites superiores para el algoritmo.

Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería Industrial – Pontificia Universidad Javeriana Sede Bogotá

Page 21: Modelos de Programación Entera - Heurísticas Optimización de Operaciones Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería

Complejidad del Problema del agente viajero

Si un computador se tardara 3 microsegundos en calcular la distancia de cada ruta y se busca solucionar el problema por FUERZA BRUTA.

Para 10 ciudades tardaría un poco más de 3 segundos Para 11 ciudades tardaría poco más de 30 segundos. Para 20 ciudades tardaría 77,246 años en resolverlo.

Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería Industrial – Pontificia Universidad Javeriana Sede Bogotá

Page 22: Modelos de Programación Entera - Heurísticas Optimización de Operaciones Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería

Desempeño Garantizado y Número de Iteraciones del Vecino más cercano

El método es de orden O(n2), es decir el número de iteraciones requeridas no es mayor a n2

2

1)(

2log

2

1

óptimo circuito del longitud

heurística lacon circuito del longitud n

Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería Industrial – Pontificia Universidad Javeriana Sede Bogotá

Page 23: Modelos de Programación Entera - Heurísticas Optimización de Operaciones Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería

Ejercicio Juan vive en ciudad 1. Es dueño de agencias de seguros en

cinco ciudades. Todos los meses de diciembre visita cada una de sus agencias. La distancia entre cada agencia (en km) se indica en la tabla. ¿Qué orden debe seguir al visitar sus agencias que minimice la distancia total recorrida?

CIUDAD 1 2 3 4 5

1 0 132 217 164 58

2 132 0 290 201 79

3 217 290 0 113 303

4 164 201 113 0 196

5 58 79 303 196 0

Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería Industrial – Pontificia Universidad Javeriana Sede Bogotá