02 de octubre de 2017 fundamentos de … 04 (02-10-17).pdf · modelos deterministicos modelos...
TRANSCRIPT
Programación Entera José Luis Quintero 1
FUNDAMENTOS DE
PROGRAMACIÓN ENTERA
Ingeniería en Informática
Ingeniería Industrial
Universidad Católica Andrés Bello
02 de Octubre de 2017
Programación Entera José Luis Quintero 2
1. Investigación de Operaciones ymodelos
2. Características de la ProgramaciónEntera
3. Tipos de modelos de ProgramaciónEntera
4. Software de trabajo
Puntos a tratar
Programación Entera José Luis Quintero 3
DIAGNOSTICO
Planeación de la
Producción
Distribución Asignación de recursos limitados
Inventarios Programación de Actividades
Pronósticos de
Demanda
Medio Ambiente
Análisis de Líneas de
Espera
Analisis de Sistemas de Producción
Información Cuantitativa y Cualitativa del Sistema bajo estudio
Seleccionar el Modelo
Modelos Deterministicos Modelos Estocásticos
Programación Lineal
Soluciones
Reales
Programación Lineal Entera
Soluciones Enteras
Programación Lineal por
metas
Soluciones en orden de prioridad
Programación Dinámica
Soluciones en Etapas continuas
Optimización de Redes
Soluciones
orientadas a la distribución
óptima
Control de Inventarios
Soluciones por etapas (n+1)
Pronósticos
Comportamiento futuro sistema
basado en datos históricos
Teoría de Colas
Determinación de tiempos de
espera y longitud de la cola promedio
Simulación de Sistemas
Estimación de las medidas de desempeño del
sistema modelado
HERRAMIENTAS DE INVESTIGACIÓN DE OPERACIONES
TIPOS DE PROBLEMAS
Problemas vsmodelos
Programación Entera José Luis Quintero 4
SOLUCIÓN AL PROBLEMA DELSISTEMA REAL
SISTEMAREAL
SOLUCIÓNAL MODELO
MODELOCUANTITATIVO
SISTEMA ASUMIDO
JUICIOS YEXPERIENCIAS
VARIABLESRELEVANTES
RELACIONESRELEVANTES
MÉTODODE SOLUCIÓN
INTERPRETACIÓNDECISIONES
Sistema real vs modelos
Programación Entera José Luis Quintero 5
Análisis
IntuiciónSituaciónadministrativa
Modelo Resultados
Decisiones
Mundosimbólico
Mundoreal
Juicio deladministrador
Proceso de construcción de un modelo
Programación Entera José Luis Quintero 6
MODELO
ImplementaciónResultadosDecisión
final
Decisiónóptima
Comparación(+) o ( -)
Ajustes
Proceso de control de un modelo
Programación Entera José Luis Quintero 7
¿Un criterio o varios criterios?
Programación Entera José Luis Quintero 8
1. Investigación de Operaciones ymodelos
2. Características de la ProgramaciónEntera
3. Tipos de modelos de ProgramaciónEntera
4. Software de trabajo
Puntos a tratar
Programación Entera José Luis Quintero 9
• Muchas veces, algunas o todas las variablesde decisión deben restringirse a valoresenteros. Por ejemplo:
a. Número de aeronaves compradas.
b. Número de máquinas que se necesita.
c. Número de viajes que ha realizado un
agente de ventas.
d. La decisión acerca de qué proyectos
van a ejecutarse y qué proyectos no.
Características de la Programación Entera
Programación Entera José Luis Quintero 10
• Los modelos de Programación Lineal Entera(PLE) permiten modelar e incorporar nuevassituaciones de la vida real
• Los PLE son mucho más difíciles de resolverque los modelos de Programación Lineal (PL).
• Si un modelo de PLE se resuelve como unmodelo de PL, se puede obtener una soluciónóptima no entera.
Características de la Programación Entera
Programación Entera José Luis Quintero 11
• Si la solución de un PL es entera, entoncesesa será la solución del PLE.
• Hay problemas que no pueden resolversecon las técnicas actuales por disponibilidadde tiempo del computador o por capacidadde memoria.
Características de la Programación Entera
Programación Entera José Luis Quintero 12
Programación
Entera
Objetivo
SatisfacciónPlaneación
Características de la Programación Entera
Programación Entera José Luis Quintero 13
óptimo
Región factible
Valor de lafunción objetivo
Búsqueda de la solución óptima mediante el uso de métodos
Características de la Programación Entera
Programación Entera José Luis Quintero 14
1. Investigación de Operaciones ymodelos
2. Características de la ProgramaciónEntera
3. Tipos de modelos de ProgramaciónEntera
4. Software de trabajo
Puntos a tratar
Programación Entera José Luis Quintero 15
• Solo de variables enteras, corresponde a unmodelo de programación entera pura.
• Variables enteras y continuas, corresponde aun modelo de programación entera mixta.
• Variables 0-1, corresponde a un modelo deprogramación entera binaria ó 0-1.
Tipos de modelos de Programación Entera
Programación Entera José Luis Quintero 16
• Restricciones y función objetivo lineal,corresponde a un problema deprogramación lineal entera.
• Restricciones y/o función objetivo no lineal,corresponde a un problema deprogramación no lineal entera.
Tipos de modelos de Programación Entera
Programación Entera José Luis Quintero 17
Tipos de modelos de Programación Lineal Entera
Programación Entera José Luis Quintero 18
Tipos de modelos de Programación Lineal Entera
Programación Entera José Luis Quintero 19
Tipos de modelos de Programación Lineal Entera
Programación Entera José Luis Quintero 20
Tipos de modelos de Programación Lineal Entera
Programación Entera José Luis Quintero 21
1. Investigación de Operaciones ymodelos
2. Características de la ProgramaciónEntera
3. Tipos de modelos de ProgramaciónEntera
4. Software de trabajo
Puntos a tratar
Programación Entera José Luis Quintero 22
Criterios para la
función obj.
Formato para los datos deentrada
Tipos de variable
WINQSB
Programación Entera José Luis Quintero 23
Formato de datos de entrada
Max Z = 10 X1 +8X2 Restricciones:
4.5X1 + 1.5X2 <= 306.0X1 + 3.0X2 <= 48 X1, X2 <= 0
Formato matricial
WINQSB
Programación Entera José Luis Quintero 24
Resolver el problema
Si el problema encontró una solución óptima
Informe Combinado
WINQSB
Programación Entera José Luis Quintero 25
Resuelve y muestra los pasos
Tabla Simplex
Iteración 1
Iteración 2
Iteración 3
WINQSB
Programación Entera José Luis Quintero 26
CPLEX 10.0
Programación Entera José Luis Quintero 27
CPLEX 10.0
Programación Entera José Luis Quintero 28
CPLEX 10.0
Programación Entera José Luis Quintero 29
Pensamiento de hoy
“No es lo que no sabemoslo que nos inquieta, es loque sabemos que no es así”.
Will Rogers