Introducción a la Introducción a la OptimizaciónOptimización
Álvaro Baíllo Moreno
Introducción a la Optimización - 1
• Concepto de optimización.• Áreas de estudio:
– Programación lineal.– Programación lineal entera.– Programación no lineal.– Programación dinámica.
ContenidoContenido
Introducción a la Optimización - 2
• Tenemos la responsabilidad de gestionar un sistema:– Economía de un país.– Proceso de fabricación.– Negocio de transporte.– Equipo de personas.
• La situación del sistema se caracteriza mediante variables de estado:– Describen totalmente la situación del sistema en un instante t.– Economía de un país: Inflación, PIB...– Proceso de fabricación: Unidades de producto terminado,
unidades disponibles de materia prima...– Negocio de transporte: Unidades disponibles en los almacenes
de origen, unidades demandadas en cada destino...– Equipo de personas: Personas que trabajan en cada turno...
Punto de partida: el sistemaPunto de partida: el sistema
Introducción a la Optimización - 3
• Las decisiones se denominan variables de control:– Economía de un país: Tipos de interés, política fiscal...– Proceso de fabricación: Unidades de producto a fabricar...– Negocio de transporte: Unidades a transportar desde cada
almacén de origen a cada destino...– Equipo de personas: Personas que entran a trabajar en cada
hora...• El sistema debe verificar ciertas restricciones:
– Economía de un país: Inflación y déficit público limitados...– Proceso de fabricación: Límite del almacén de producto
terminado...– Negocio de transporte: Número máximo de unidades en cada
trayecto...– Equipo de personas: Número máximo de horas de trabajo
seguidas...
Problema: tomar decisionesProblema: tomar decisiones
Introducción a la Optimización - 4
• Normalmente existen múltiples soluciones para las que el sistema verifica las restricciones:– Se denominan soluciones factibles.
• Es necesario establecer criterios que permitan ordenar las soluciones de mejor a peor.– Se puede definir una función objetivo que valore
cuantitativamente la bondad de una cierta solución.
Objetivo: identificar las decisiones Objetivo: identificar las decisiones óptimasóptimas
Introducción a la Optimización - 5
• Múltiples funciones objetivo: OptimizaciOptimizacióón n multicriteriomulticriterio– No hay coincidencia del óptimo para los diferentes objetivos.
•• No existe funciNo existe funcióón objetivon objetivo– Sistema de ecuaciones (no) lineales.– Encontrar una solución factible.
• No existen restricciones: OptimizaciOptimizacióón sin n sin restriccionesrestricciones– Determinar el mínimo de un función.
Optimización: casos particularesOptimización: casos particulares
Introducción a la Optimización - 6
• Programación lineal (LP):– Se utiliza en situaciones que pueden representarse utilizando:
• Expresiones lineales: que no incluyan productos de variables.• Variables continuas.
– Existen algoritmos de resolución muy potentes que permiten abordar problemas de gran tamaño:
• > 106 variables, > 106 restricciones.– La teoría de la dualidad permite:
• Interpretar económicamente los resultados obtenidos.• Analizar el impacto económico de las restricciones.• Obtener una nueva solución óptima de forma sencilla ante
pequeñas variaciones de la situación.– Siempre que se pueda, interesa adoptar este enfoque.
Optimización: áreas de estudioOptimización: áreas de estudio
Introducción a la Optimización - 7
• Programación lineal entera (MIP, MLIP):– Se utiliza en situaciones que pueden representarse utilizando:
• Expresiones lineales: que no incluyan productos de variables.• Variables continuas.• Variables enteras para representar niveles discretos de decisión.• Variables binarias para representar decisiones alternativas, etc.
– Con este enfoque se puede plantear prácticamente cualquier problema, pero...
– ...el tamaño de los problemas que se puede resolver es menor:
• ~ 104 variables, ~ 104 restricciones.– Sólo debe utilizarse cuando no sea posible el enfoque LP.
Optimización: áreas de estudioOptimización: áreas de estudio
Introducción a la Optimización - 8
• Programación no lineal (NLP):– Se utiliza en situaciones que deben representarse utilizando:
• Expresiones no lineales: como productos de variables.• Variables continuas.
– En general es difícil garantizar que la solución obtenida es la óptima:
• La programación cuadrática es una excepción.– La interpretación económica de la formulación suele ser
interesante pero...– ...los algoritmos de resolución son poco potentes.– Es posible abordar sólo problemas de pequeño tamaño.– Normalmente es posible reformularlos como problemas MLIP.
Optimización: áreas de estudioOptimización: áreas de estudio
Introducción a la Optimización - 9
• Programación dinámica (DP):– Estudia problemas en los que las decisiones se toman en
varias etapas.• El estado del sistema en cada etapa se define completamente con
las variables de estado.• Las decisiones de cada etapa determinan el estado del sistema en
etapas posteriores.– Para abordar estos problemas se discretiza el abanico de
estados que el sistema puede tener en cada etapa.– La estrategia de solución se basa en el principio de
Bellman:
Optimización: áreas de estudioOptimización: áreas de estudio
Una política óptima se caracteriza por que, independientemente del estado inicial y de la decisión inicial, las decisiones restantes deben constituir una política óptima
con respecto al estado resultante de la primera decisión
Modelos y modeladoModelos y modelado
Álvaro Baíllo Moreno
Introducción a la Optimización - 11
Esquema teóricoEsquema teórico, generalmente en forma matemáticamatemática, de un sistema o de una realidad compleja (por ejemplo, la evolución económica de un país), que se elabora para facilitar su comprensiónfacilitar su comprensión y y el estudio estudio de su comportamiento.
Diccionario de la lengua española. Real Academia Española.
ModeloModelo
Introducción a la Optimización - 12
• Representación de una realidad: –– Compleja:Compleja: Puede involucrar equipo multidisciplinar.–– Precisa:Precisa: Formulada mediante expresiones matemáticas.–– Simplificada:Simplificada:
• Las simplificaciones introducidas son válidas en un cierto ámbito de utilización del modelo: no debe usarse fuera de ese ámbito.
• Permiten mantener un equilibrio entre representación detallada ycapacidad de obtener resultados numéricos.
• En el ámbito de la Investigación Operativa (IO):– Son herramientas de ayuda a la toma de decisiones.decisiones.
ModeloModelo
Introducción a la Optimización - 13
• Interacción entre dos agentes:
Proceso de modeladoProceso de modelado
Experto: •Conoce el sistema de estudio.
•Quiere introducir mejoras.•Desea asesoramiento para tomar decisiones.
ExpertoExperto: : •Conoce el sistema de estudio.
•Quiere introducir mejoras.•Desea asesoramiento para tomar decisiones.
Modelador:•Especifica y desarrolla el modelo que permite orientar esa toma de decisiones.
•Dos vertientes:–Ciencia
• Análisis y detección de relaciones entre datos• Suposiciones y aproximaciones a los problemas• Algoritmos específicos de solución
–Arte• Visión o interpretación de la realidad• Estilo en modelo y documentación• Elegancia y simplicidad en desarrollo• Uso de creativo de herramientas
ModeladorModelador::•Especifica y desarrolla el modelo que permite orientar esa toma de decisiones.
•Dos vertientes:––CienciaCiencia
• Análisis y detección de relaciones entre datos• Suposiciones y aproximaciones a los problemas• Algoritmos específicos de solución
––ArteArte• Visión o interpretación de la realidad• Estilo en modelo y documentación• Elegancia y simplicidad en desarrollo• Uso de creativo de herramientas
Introducción a la Optimización - 14
• Diálogo entre modelador y experto:– Entrevistas.– Conocimiento mutuo.– Manejo de un lenguaje común:
• El modelador se familiariza con el sistema de estudio.• El experto se familiariza con las técnicas de modelado.
– Especificación de objetivos comunes:• Acuerdo en la metodología y en los recursos.
• Descripción del comportamiento del sistema:– Identificación de variables de estado y de control.– Identificación de restricciones.– Identificación de posibles objetivos (económicos, de
rendimiento, etc.)– Proporciona una primera aproximación al problema.
Proceso de modeladoProceso de modelado
Introducción a la Optimización - 15
• Formulación de hipótesis y simplificaciones– Ayudan a comprender mejor el problema. – Permiten que el problema sea tratable computacionalmente.– Es necesario valorar el impacto que pueden suponer en el
resultado.• Desarrollo de modelos reducidos o prototipos:
– Permiten hacer pruebas iniciales y comprobar si el planteamiento es adecuado.
• Organización de la información disponible– Identificar la información relevante para el problema.– Recopilación de información: tarea costosa.– Creación de un sistema de información: e.g. base de datos.– Parámetros desconocidos: estimaciones.– Parámetros inciertos: representación de la estocasticidad.
Proceso de modeladoProceso de modelado
Introducción a la Optimización - 16
• Primera versión del modelo:– Definición de una función objetivofunción objetivo.– Especificación de las variablesvariables del problema, junto con sus
límites.– Especificación de los datos de entrada o parámetrosparámetros.– Incorporación de los parámetros estocásticosparámetros estocásticos, mediante un
equivalente determinista o mediante una representación de su distribución de probabilidad.
– Formulación de las relaciones existentes entre variables y parámetros: restriccionesrestricciones.
– Análisis de tamaño y estructuratamaño y estructura del problema– Identificación de tipo de problematipo de problema (LP, MLIP, NLP, DP)– Énfasis en precisión y belleza en la formulación.
Proceso de modeladoProceso de modelado
Introducción a la Optimización - 17
• Codificación:– Selección de un lenguaje de programación o de modelado
adecuado.– Desarrollo de un interfaz con el sistema de información.
• Técnica de resolución:– Selección de un algoritmo de obtención de solución óptima,
cuasióptima o, al menos, satisfactoria.– Detección de soluciones cuasióptimas atractivas.– Evaluación de diferentes métodos de solución.– Diferentes implantaciones del algoritmo elegido.
Proceso de modeladoProceso de modelado
Introducción a la Optimización - 18
•• Verificación:Verificación:– Comparación entre el código implantado y el modelo.– Eliminación de errores en codificación.– Técnicas:
• Probar con problemas de pequeño tamaño: prototipos.• Mantener algunas variables como constantes o eliminarlas.• Reforzar o relajar restricciones.• Eliminar la aleatoriedad de los elementos estocásticos.
•• Validación:Validación:– Comparación de la salida del modelo con el sistema.– Comprobar validez de simplificaciones adoptadas.– Comprobación de adaptación a la realidad.
•• Refinamiento:Refinamiento:– Ampliación en el modelado por nuevas necesidades.
Proceso de modeladoProceso de modelado
Introducción a la Optimización - 19
•• Interpretación de los resultados:Interpretación de los resultados:– Análisis de sensibilidad en parámetros de entrada.– Robustez de la solución óptima.
•• Implantación, documentación y mantenimiento:Implantación, documentación y mantenimiento:– Etapa fundamental para el éxito de un modelo.– Documentación clara, precisa y completa.– Manual de usuario con especificación técnica funcional,
matemática e informática.– Formación de posibles usuarios.
Proceso de modeladoProceso de modelado
Modelado en programación Modelado en programación lineallineal
Álvaro Baíllo Moreno
Introducción a la Optimización - 21
• Motivación con un ejemplo.• Problema del transporte.• Problema de asignación de tareas.• Problema de transbordo.• Problema del camino más corto.• Resolución de problemas de la biblioteca.
ContenidoContenido
Introducción a la Optimización - 22
• La empresa LP monta dos tipos de tarjetas electrónicas, A y B, que se utilizan para el mismo tipo de aplicaciones:– La tarjeta A es de mejor calidad que la B, y por ello:
• El precio que LP recibe por cada tarjeta tipo A, PA, es mayor que el precio que paga por cada tarjeta tipo B, PB.
• El tiempo de mano de obra que requiere el montaje de A, TA, es mayor que el tiempo de mano de obra que requiere B, TB.
– Las tarjetas que se pueden vender son limitadas:• Como mucho se pueden vender D tarjetas de cualquiera de los
dos tipos.– La empresa LP cuenta con N empleados para el montaje de
las tarjetas, cada uno de los cuales trabaja 8 h diarias.
Ejemplo LP1: Montaje de tarjetasEjemplo LP1: Montaje de tarjetas
Introducción a la Optimización - 23
• La empresa LP quiere saber el número de tarjetas de tipo A y B que tiene que montar, XA y XB, para:– maximizar sus ingresos,– vendiendo como mucho D tarjetas,– y respetando la restricción de tiempo impuesta por la mano de
obra.
Ejemplo LP1: Montaje de tarjetasEjemplo LP1: Montaje de tarjetasFormulación del problemaFormulación del problema
maxs.a: , 8 , , 0.
A A B B
A B
A A B B
A B
P X P X
X X DT X T X NX X
+
+ ≤+ ≤≥
Introducción a la Optimización - 24
maxs.a: , 8 , , 0.
A A B B
A B
A A B B
A B
P X P X
X X DT X T X NX X
+
+ ≤+ ≤≥
• Ejemplo LP1: – Los recursos escasos son la mano de obra y la demanda.
La programación lineal como método La programación lineal como método para asignar recursos escasospara asignar recursos escasos
Recurso escaso 1: demanda
Restricciones adicionales que deben cumplirse: cotas
Criterio para asignar los recursos escasos
Recurso escaso 2: mano de obra
Introducción a la Optimización - 25
• ¿Qué variable de control nos interesa?
El problema del transporteEl problema del transporte
Función objetivoFunción objetivo::Minimizar el coste total de transporte de un cierto producto desde los orígenes a los destinos
RestriccionesRestricciones::Satisfacer la demanda de cada destinoNo superar la oferta disponible en cada origen
m orígenesai: oferta del producto en el origen i
n destinosbj: demanda del producto en el destino j
cij: coste de llevar el producto de i a j
Introducción a la Optimización - 26
• Formulación del problema:
El problema del transporteEl problema del transporte
1 1
1
1
min
s.a: , ,
, ,
0, , .
ij
m n
ij ijx i j
n
ij ij
m
ij ji
ij
c x
x a i
x b j
x i j
= =
=
=
= ∀
= ∀
≥ ∀
∑∑
∑
∑
Oferta disponible en cada origen i
Demanda en cada destino j
Cantidades positivas
Cantidad transportada desde i hasta j
Introducción a la Optimización - 27
• En la formulación anterior se ha supuesto que la oferta es igual a la demanda:
• Si la oferta es mayor que la demanda:– Se añade un sumidero con coste de transporte nulo.
• Si la demanda es menor que la oferta:– Se añade una fuente universal con coste muy elevado.
El problema del transporteEl problema del transporte
1 1
m n
i ji j
a b= =
=∑ ∑
1 1
m n
i ji j
a b= =
>∑ ∑
1 1
m n
i ji j
a b= =
<∑ ∑
Introducción a la Optimización - 28
• Estructura del problema:
El problema del transporteEl problema del transporte
1...11
"...""
1...11
1...11
1...11
"
1...11
1...11
xmn...xm2xm1...x2n...x22x21x1n...x12x11
m restricciones de oferta
n restricciones de demanda
n×m variables
Introducción a la Optimización - 29
• La matriz de restricciones es unimodular:– Toda submatriz cuadrada tiene determinante 0, 1 ó –1.
• Si la oferta en todos los orígenes, ai, y la demanda en todos los destinos, bj, toman valores enteros:– El valor de todas las variables xij en la solución óptima es
entero, sin necesidad de utilizar un algoritmo de programación lineal entera.
El problema del transporteEl problema del transporte
Introducción a la Optimización - 30
• Consideramos el problema de asignar n tareas a npersonas (o máquinas) para realizarlas:– cij es el coste que supone la realización de la tarea i por la
persona j.– El objetivo es minimizar el coste de realización de las tareas.– ¿Variable de control?– ¿Función objetivo?– Cada persona realiza una tarea. ¿Formulación?– Cada tarea es realizada por una persona. ¿Formulación?
El problema de asignación de tareasEl problema de asignación de tareas
Introducción a la Optimización - 31
El problema de asignación de tareasEl problema de asignación de tareas
1 1
1
1
min
s.a: 1, ,
1, ,
0, , .
ij
m n
ij ijx i j
n
ijj
m
iji
ij
c x
x i
x j
x i j
= =
=
=
= ∀
= ∀
≥ ∀
∑∑
∑
∑
Cada tarea i, una persona
Cada persona, juna tarea
Asignaciones positivas
= 1 si la persona ihace la tarea j
= 0 en otro caso
Introducción a la Optimización - 32
• Es una extensión del problema del transporte.• En este caso todos los nodos de la red admiten
entrada y salida de producto:– No se distingue entre nodos origen y destino: todos son
iguales.– En lugar de distinguir entre oferta y demanda se define la
oferta neta de cada nodo i, bi (puede ser positiva, negativa o nula).
– Suponemos que la oferta de producto es igual a la demandade producto en el conjunto de la red.
– Sigue habiendo un coste de transporte desde cada nodo ihasta cada nodo j de la red: cij
El problema de El problema de transbordotransbordo
Introducción a la Optimización - 33
• ¿Cómo se formularía este problema?
El problema de El problema de transbordotransbordo
1 1
1 1
min
s.a: , ,
0, , .
ij
m n
ij ijx i j
n n
ij ki ij k
ij
c x
x x b i
x i j
= =
= =
− = ∀
≥ ∀
∑∑
∑ ∑ Balance del flujo en cada nodo i
Esta formulación es general y puede ser aplicada a los dos
modelos vistos anteriormente.
Introducción a la Optimización - 34
• Se desea determinar el camino más corto para llegar del origen al destino en la red de la figura:
• ¿Cómo lo plantearíais?
El problema del camino más cortoEl problema del camino más corto
0
1
3
2
4
6
5
7
8
1
12
1
12
4
3
314
2
1
2
1
1
Introducción a la Optimización - 35
El problema del camino más cortoEl problema del camino más corto
8 8
0 0
8 8
0 0
0
8
min
s.a: , ,
0, , ,
1, 1, 0, 1,...,7
ijij ij
x i j
ij ki ij k
ij
i
c x
x x b i
x i j
bbb i
= =
= =
− = ∀
≥ ∀
== −
= =
∑∑
∑ ∑
Introducción a la Optimización - 36
• Ayuda en emergencias.• Transporte de electrodomésticos.• Logística.• Producción e inventario.
Problemas de la biblioteca de problemasProblemas de la biblioteca de problemas
Modelado en Programación Modelado en Programación LinealLineal
Formulación en GAMSFormulación en GAMS
Álvaro Baíllo Moreno
Introducción a la Optimización - 38
• Formulación del problema.• Descripción del código en GAMS.• Análisis de la salida de GAMS.
ContenidoContenido
Introducción a la Optimización - 39
• La empresa LP monta dos tipos de tarjetas electrónicas, A y B, que se utilizan para el mismo tipo de aplicaciones:– La tarjeta A es de mejor calidad que la B, y por ello:
• El precio que LP recibe por cada tarjeta tipo A, PA, es mayor que el precio que paga por cada tarjeta tipo B, PB.
• El tiempo de mano de obra que requiere el montaje de A, TA, es mayor que el tiempo de mano de obra que requiere B, TB.
– Las tarjetas que se pueden vender son limitadas:• Como mucho se pueden vender D tarjetas de cualquiera de los
dos tipos.– La empresa LP cuenta con N empleados para el montaje de
las tarjetas, cada uno de los cuales trabaja 8 h diarias.
Ejemplo LP1: Montaje de tarjetasEjemplo LP1: Montaje de tarjetas
Introducción a la Optimización - 40
• La empresa LP quiere saber el número de tarjetas de tipo A y B que tiene que montar, XA y XB, para:– maximizar sus ingresos,– vendiendo como mucho D tarjetas,– y respetando la restricción de tiempo impuesta por la mano de
obra.
Ejemplo LP1: Montaje de tarjetasEjemplo LP1: Montaje de tarjetasFormulación del problemaFormulación del problema
maxs.a: , 8 , , 0.
A A B B
A B
A A B B
A B
P X P X
X X DT X T X NX X
+
+ ≤+ ≤≥
Introducción a la Optimización - 41
0
2
4
6
8
10
12
14
16
18
0 2 4 6 8 10 12 14 16 18
PA=3, PB=2, TA=4h, TB=2h, D=12, N=4
Ejemplo LP1: Montaje de tarjetasEjemplo LP1: Montaje de tarjetasCaso numéricoCaso numérico
Introducción a la Optimización - 42
0
2
4
6
8
10
12
14
16
18
0 2 4 6 8 10 12 14 16 18
Recta isobeneficio correspondiente a PT3= 28
Ejemplo LP1: Montaje de tarjetasEjemplo LP1: Montaje de tarjetasCaso numéricoCaso numérico
Introducción a la Optimización - 43
Ejemplo LP1: Montaje de tarjetasEjemplo LP1: Montaje de tarjetasCaso numérico con GAMS: códigoCaso numérico con GAMS: código
Introducción a la Optimización - 44
Ejemplo LP1: Montaje de tarjetasEjemplo LP1: Montaje de tarjetasCaso numérico con GAMS: códigoCaso numérico con GAMS: código
Introducción a la Optimización - 45
Ejemplo LP1: Montaje de tarjetasEjemplo LP1: Montaje de tarjetasCaso numérico con GAMS: códigoCaso numérico con GAMS: código
Introducción a la Optimización - 46
Ejemplo LP1: Montaje de tarjetasEjemplo LP1: Montaje de tarjetasCaso numérico con GAMS: códigoCaso numérico con GAMS: código
Introducción a la Optimización - 47
Ejemplo LP1: Montaje de tarjetasEjemplo LP1: Montaje de tarjetasCaso numérico con GAMS: códigoCaso numérico con GAMS: código
Introducción a la Optimización - 48
Ejemplo LP1: Montaje de tarjetasEjemplo LP1: Montaje de tarjetasCaso numérico con GAMS: códigoCaso numérico con GAMS: código
Introducción a la Optimización - 49
Ejemplo LP1: Montaje de tarjetasEjemplo LP1: Montaje de tarjetasCaso numérico con GAMS: códigoCaso numérico con GAMS: código
Introducción a la Optimización - 50
Ejemplo LP1: Montaje de tarjetasEjemplo LP1: Montaje de tarjetasCaso numérico con GAMS: salidaCaso numérico con GAMS: salida
•Detalle de las ecuaciones:–Cada ecuación se desarrolla en detalle.
–A la izquierda quedan todas las variables.
–A la derecha están los términos constantes.
–Se indica el valor inicial del lado de la izquierda (Left Hand Side, LHS) en función del valor inicial de las variables (por defecto son nulas).
–Se indica la infactibilidad inicialde cada ecuación (INFES).
•Detalle de las ecuaciones:–Cada ecuación se desarrolla en detalle.
–A la izquierda quedan todas las variables.
–A la derecha están los términos constantes.
–Se indica el valor inicial del lado de la izquierda (Left Hand Side, LHS) en función del valor inicial de las variables (por defecto son nulas).
–Se indica la infactibilidad inicialde cada ecuación (INFES).
Introducción a la Optimización - 51
Ejemplo LP1: Montaje de tarjetasEjemplo LP1: Montaje de tarjetasCaso numérico con GAMS: salidaCaso numérico con GAMS: salida
•Para cada variable se indica:–Su cota inferior (.LO), su valor inicial (.L) y su cota superior (.UP)
• Si una variable X no está acotada inferiormente: X.LO = -INF
• Si una variable no está acotada superiormente: X.UP = +INF
–Sus coeficientes en cada una de las ecuaciones del problema:
• Ejemplo: el coeficiente de x(A) en la ecuación ING es -3.
•Para cada variable se indica:–Su cota inferior (.LO), su valor inicial (.L) y su cota superior (.UP)
• Si una variable X no está acotada inferiormente: X.LO = -INF
• Si una variable no está acotada superiormente: X.UP = +INF
–Sus coeficientes en cada una de las ecuaciones del problema:
• Ejemplo: el coeficiente de x(A) en la ecuación ING es -3.
Introducción a la Optimización - 52
Ejemplo LP1: Montaje de tarjetasEjemplo LP1: Montaje de tarjetasCaso numérico con GAMS: salidaCaso numérico con GAMS: salida
•Estadísticas del modelo:–Ecuaciones:
• Bloques (3): ING, DMT, TMP.• Ecuaciones individuales (3).
–Variables:• Bloques (2): z, x(i).• Variables individuales(3).
–Elementos no nulos de la matriz de restricciones (7).
•Estadísticas del modelo:–Ecuaciones:
• Bloques (3): ING, DMT, TMP.• Ecuaciones individuales (3).
–Variables:• Bloques (2): z, x(i).• Variables individuales(3).
–Elementos no nulos de la matriz de restricciones (7).
Introducción a la Optimización - 53
Ejemplo LP1: Montaje de tarjetasEjemplo LP1: Montaje de tarjetasCaso numérico con GAMS: salidaCaso numérico con GAMS: salida
•Resumen de la solución:–Nombre del modelo: LP1–Variable objetivo: z–Tipo de modelo: LP–Dirección: maximización–Optimizador: CPLEX–Línea de la instrucción SOLVE: 41–Estado del optimizador: 1 (Normal)–Estado del modelo: 1 (Óptimo)–Valor de la función objetivo: 27.–Tiempo de CPU
• Utilizado (Resource Usage): 0.410 s.• Límite: 1000 s.
–Iteraciones:• Contadas (Iteration count): 2.• Límite: 10000 iteraciones.
•Resumen de la solución:–Nombre del modelo: LP1–Variable objetivo: z–Tipo de modelo: LP–Dirección: maximización–Optimizador: CPLEX–Línea de la instrucción SOLVE: 41–Estado del optimizador: 1 (Normal)–Estado del modelo: 1 (Óptimo)–Valor de la función objetivo: 27.–Tiempo de CPU
• Utilizado (Resource Usage): 0.410 s.• Límite: 1000 s.
–Iteraciones:• Contadas (Iteration count): 2.• Límite: 10000 iteraciones.
Introducción a la Optimización - 54
Ejemplo LP1: Montaje de tarjetasEjemplo LP1: Montaje de tarjetasCaso numérico con GAMS: salidaCaso numérico con GAMS: salida
•Detalle de la solución:–Valor de la función objetivo: 27.–Valor (LEVEL), cotas (LOWER, UPPER) y valor marginal (MARGINAL) de cada ecuación:
• Ejemplo: DMT LOWER -INFLEVEL 11UPPER 11MARGINAL 1
•Detalle de la solución:–Valor de la función objetivo: 27.–Valor (LEVEL), cotas (LOWER, UPPER) y valor marginal (MARGINAL) de cada ecuación:
• Ejemplo: DMT LOWER -INFLEVEL 11UPPER 11MARGINAL 1
Introducción a la Optimización - 55
Ejemplo LP1: Montaje de tarjetasEjemplo LP1: Montaje de tarjetasCaso numérico con GAMS: salidaCaso numérico con GAMS: salida
•Detalle de la solución:–Valor (LEVEL), cotas (LOWER, UPPER) y valor marginal (MARGINAL) de cada variable:
• Ejemplo: X(A): LOWER 0LEVEL 5UPPER +INFMARGINAL 0
•Detalle de la solución:–Valor (LEVEL), cotas (LOWER, UPPER) y valor marginal (MARGINAL) de cada variable:
• Ejemplo: X(A): LOWER 0LEVEL 5UPPER +INFMARGINAL 0
Introducción a la Optimización - 56
Ejemplo LP1: Montaje de tarjetasEjemplo LP1: Montaje de tarjetasCaso numérico con GAMS: salidaCaso numérico con GAMS: salida
•Informe de la solución:–Informa acerca de problemas de infactibilidad o de no acotación.
•Informe de la solución:–Informa acerca de problemas de infactibilidad o de no acotación.
Modelado en programación Modelado en programación lineal enteralineal entera
Álvaro Baíllo Moreno
Introducción a la Optimización - 58
• Problemas MILP característicos:– Recubrimiento.– Empaquetado.– Partición.– Mochila.– Problema del viajante.
• Modelado con variables enteras y binarias:– Modelado de cantidades indivisibles.– Modelado de restricciones especiales. – Modelado de decisiones discretas.– Modelado de implicaciones.– Modelado de proposiciones lógicas.– Modelado de productos de variables binarias.
ContenidoContenido
Introducción a la Optimización - 59
• Vamos a ver algunos modelos MILP que han sido muy estudiados.
• Con ello se pretende:– Hacer una introducción al modelado MILP.– Ilustrar la importancia del modelado:
• En problemas sencillos para que su representación sea sencilla.• En problemas complejos para que su representación sea correcta.
– Describir algunas estructuras tipo que se suelen presentar con más frecuencia de los que parece.
Modelos MILP característicosModelos MILP característicos
Introducción a la Optimización - 60
• Consideremos un conjunto S de personas:– Por ejemplo: S={1, 2, ..., 5}– Utilizamos el índice i para representar las personas: i =1, ..., 5.
• Supongamos que queremos organizar a estas personas en varios equipos:– El conjunto de equipos posibles es S– Por ejemplo: S = {{1, 2}, {4, 5}, {1, 3, 5}, {2, 4, 5}, {1}, {3}}– Utilizamos el índice j para representar los equipos: j =1, ..., 6.– Cada equipo j tiene un coste cj:
c1 = 1, c2 = 1, c3 = 1, c4 = 1, c5 = 1, c6 = 1.
• Queremos elegir los equipos que permiten tener ocupadas a todas las personas con coste mínimo.– No importa que una misma persona esté en dos equipos.
Problema de recubrimiento Problema de recubrimiento ((Set coveringSet covering))
Introducción a la Optimización - 61
• Hay múltiples soluciones factibles, pero sólo un óptimo:
Problema de recubrimiento Problema de recubrimiento ((Set coveringSet covering))
1 2
34
5
1 2
34
5
1 2
34
5
1 2
34
5
1 2
34
5
Introducción a la Optimización - 62
Problema de recubrimiento Problema de recubrimiento ((Set coveringSet covering))• Para formular el problema definimos una matriz cuyos
elementos aij indican si la persona i está en el equipo j:aij = 1 si la persona i está en el equipo j.aij = 0 en caso contrario.
• La formulación es:
{ }
1
1
min
s.a: 1, ,
0,1 , .
j
m
j jx j
m
ij jj
j
c x
a x i
x j
=
=
≥ ∀
∈ ∀
∑
∑Cada persona i en al menos un equipo.
Variables binarias
Coste de los equipos formados
Introducción a la Optimización - 63
• Consideremos un conjunto S de personas:– Por ejemplo: S={1, 2, ..., 5}– Utilizamos el índice i para representar las personas: i =1, ..., 5.
• Supongamos que queremos organizar a estas personas en varios equipos:– El conjunto de equipos posibles es S– Por ejemplo: S = {{1, 2}, {4, 5}, {1, 3, 5}, {2, 4, 5}, {1}, {3}}– Utilizamos el índice j para representar los equipos: j =1, ..., 6.– Cada equipo j tiene un beneficio cj:
c1 = 1, c2 = 1, c3 = 1, c4 = 1, c5 = 1, c6 = 1.
• Queremos elegir los equipos que proporcionan beneficio máximo sin que exista solape.– No importa que una persona no esté en ningún equipo.
Problema de empaquetado Problema de empaquetado ((Set packingSet packing))
Introducción a la Optimización - 64
• Hay múltiples soluciones factibles, pero sólo un óptimo:
Problema de empaquetado Problema de empaquetado ((Set packingSet packing))
1 2
34
5
1 2
34
5
1 2
34
5
1 2
34
5
1 2
34
5
Introducción a la Optimización - 65
Problema de empaquetado Problema de empaquetado ((Set packingSet packing))• La formulación es:
{ }
1
1
max
s.a: 1, ,
0,1 , .
j
m
j jx j
m
ij jj
j
c x
a x i
x j
=
=
≤ ∀
∈ ∀
∑
∑Cada persona i en sólo un equipo.
Variables binarias
Beneficio de los equipos formados
Introducción a la Optimización - 66
• Consideremos un conjunto S de personas:– Por ejemplo: S={1, 2, ..., 5}– Utilizamos el índice i para representar las personas: i =1, ..., 5.
• Supongamos que queremos organizar a estas personas en varios equipos:– El conjunto de equipos posibles es S– Por ejemplo: S = {{1, 2}, {4, 5}, {1, 3, 5}, {2, 4, 5}, {1}, {3}}– Utilizamos el índice j para representar los equipos: j =1, ..., 6.– Cada equipo j tiene un beneficio cj:
c1 = 1, c2 = 1, c3 = 1, c4 = 1, c5 = 1, c6 = 1.
• Queremos elegir los equipos que proporcionan beneficio máximo de forma que cada persona esté en un equipo y sólo un equipo.
Problema de partición Problema de partición ((Set partitioningSet partitioning))
Introducción a la Optimización - 67
• Hay múltiples soluciones factibles, pero sólo un óptimo:
Problema de partición Problema de partición ((Set partitioningSet partitioning))
1 2
34
5
1 2
34
5
1 2
34
5
Introducción a la Optimización - 68
Problema de partición Problema de partición ((Set partitioningSet partitioning))• La formulación es:
{ }
1
1
max
s.a: 1, ,
0,1 , .
j
m
j jx j
m
ij jj
j
c x
a x i
x j
=
=
= ∀
∈ ∀
∑
∑Cada persona i en uno y sólo un equipo.
Variables binarias
Beneficio de los equipos formados
Introducción a la Optimización - 69
• Supongamos una empresa que puede elegir entre nproyectos.
• Cada proyecto j (j=1,...,n) tiene un coste cj y supone un beneficio rj.
• La empresa tiene un presupuesto máximo de b.• El problema consiste en elegir aquellos proyectos que
maximizan el beneficio respetando la restricción del presupuesto.
Problema de la mochila Problema de la mochila ((KnapsackKnapsack))
Introducción a la Optimización - 70
• Formulación:
• Aplicaciones:– Asignación de presupuestos.– Organización de un almacén.– ...
Problema de la mochila Problema de la mochila ((KnapsackKnapsack))
{ }
1
1
max
s.a: ,
0,1 , .
j
m
j jx j
m
j jj
j
r x
c x b
x j
=
=
≤
∈ ∀
∑
∑Restricción de presupuesto
Variables binarias
Beneficio de los proyectos elegidos
Introducción a la Optimización - 71
• Objetivo:– Hacer un recorrido que pase por n ciudades sin repetir
ninguna y volviendo a la ciudad de partida, de manera que la distancia total recorrida sea mínima.
• En este problema se tienen varias dificultades:– ¿Cuál es la variable de control?– ¿Cómo se garantiza que por cada ciudad se pasa sólo una
vez?– ¿Cómo se impide que haya bucles incompletos?
• Vamos a ir respondiendo a cada una de estas preguntas.
Problema del viajante Problema del viajante ((TravelingTraveling salesmansalesman))
Introducción a la Optimización - 72
• Variable de control:– Vamos a utilizar los índices i e j para referirnos a las ciudades.
• i: ciudad origen.• j: ciudad destino.
– La variable de control es xij:
– La distancia entre dos ciudades i e j viene dada por cij.
Problema del viajante Problema del viajante ((TravelingTraveling salesmansalesman))
1 0ij
i jx =
si se va de la ciudad a la ciudaden otro caso
Introducción a la Optimización - 73
• Formulación incompleta del problema:
Problema del viajante Problema del viajante ((TravelingTraveling salesmansalesman))
{ }
min
1, ,
1, ,
0,1 .
ijij ijx i j i
iji j
ijj i
ij
c x
x j
x i
x
≠
≠
≠
= ∀
= ∀
∈
∑∑
∑
∑
Cada ciudad j es destino de uno y sólo un tramo
Distancia recorrida
Cada ciudad j es origen de uno y sólo un tramo
Variables binarias
Introducción a la Optimización - 74
• Es necesario añadir restricciones adicionales para evitar soluciones formadas por dos o más recorridos:
Problema del viajante Problema del viajante ((TravelingTraveling salesmansalesman))
1
23
4
5
6 7
8
1
23
4
5
6 7
8
Introducción a la Optimización - 75
• Formulación 1:– Consiste en añadir un conjunto de variables enteras:
– Y se añaden las siguientes restricciones:
– Vamos a particularizar estas restricciones para uno de los recorridos incompletos de la transparencia anterior (5 - 7 - 8):
– Las restricciones no se cumplen en caso de recorridos incompletos, luego impiden la presencia de éstos.
Problema del viajante Problema del viajante ((TravelingTraveling salesmansalesman))
, 2,...,iu i n∈ =
( 1) 2, 1, , 1i j iju u n x n i j i j− + − ⋅ ≤ − ∀ > ∀ ≠ >
5 7 57
7 8 78 57 78 85
8 5 85
7 67 6 7 7 7 18 21 18!7 6
u u xu u x x x xu u x
− + ⋅ ≤ − + ⋅ ≤ ⇒ ⋅ + ⋅ + ⋅ ≤ ⇒ ≤− + ⋅ ≤ Sumamos las restricciones
Introducción a la Optimización - 76
• Formulación 1:– Vamos a probar en el caso de un recorrido completo:
Problema del viajante Problema del viajante ((TravelingTraveling salesmansalesman))
3 2 13
2 5 25
5 8 58
8 7 87
7 6 76
6 4 64
7 67 67 67 67 67 6
u u xu u xu u xu u xu u xu u x
− + ⋅ ≤− + ⋅ ≤
− + ⋅ ≤− + ⋅ ≤
− + ⋅ ≤− + ⋅ ≤
Sumamos las restricciones
3 4 13 25 58 87 76 647 7 7 7 7 7 36u u x x x x x x− + ⋅ + ⋅ + ⋅ + ⋅ + ⋅ + ⋅ ≤
4 3 6u u≥ +
Consideramos sólo las restricciones correspondientes a recorridos i → j que se hacen (xij = 1)
1
23
4
5
6 7
81
23
4
5
6 7
8
Introducción a la Optimización - 77
• Formulación 1:– Si en lugar de sumar seis restricciones sumamos sólo cinco:
– Este procedimiento añade casi tantas restricciones como parejas de ciudades.
Problema del viajante Problema del viajante ((TravelingTraveling salesmansalesman))
3 2 13
2 5 25
5 8 58
8 7 87
7 6 76
7 67 67 67 67 6
u u xu u xu u xu u xu u x
− + ⋅ ≤
− + ⋅ ≤
− + ⋅ ≤
− + ⋅ ≤
− + ⋅ ≤Sumamos las restricciones
6 3 5u u≥ +
1
23
4
5
6 7
81
23
4
5
6 7
8
En definitiva, la variable uiindica el orden en que se ha visitado la ciudad i.
Introducción a la Optimización - 78
• Formulación 2:– Consideramos todos los subconjuntos de más de 2 y de menos
de n–2 ciudades que no contienen a la ciudad 1.– Añadimos una restricción para cada uno de estos subconjuntos
U que impida que en él se forme un bucle:
donde Card(U) es el cardinal del subconjunto U (número de elementos de U).
– Con este método estamos añadiendo del orden de 2nrestricciones.
– Por ejemplo, para n = 8 tendríamos que añadir restricciones.
– Al eliminar los bucles de 2 y 3 ciudades estamos eliminando también los de 5 y 6 ciudades.
Problema del viajante Problema del viajante ((TravelingTraveling salesmansalesman))
{ },
Card( ) 1 1,..., 2 Card( ) 2iji j U
x U U n U n∈
≤ − ∀ ⊂ ≤ ≤ −∑
7 7 72 3 4
+ +
Introducción a la Optimización - 79
• Formulación 3:– Cambiamos la elección de la variable de control:
• i: ciudad origen.• j: ciudad destino.• k: tramo de recorrido.
– La variable de control es xijk:
Problema del viajante Problema del viajante ((TravelingTraveling salesmansalesman))
1 0ijk
i j kx
=
si se va de la ciudad a la ciudad en el tramo de recorridoen otro caso
Introducción a la Optimización - 80
• Formulación 3:
Problema del viajante Problema del viajante ((TravelingTraveling salesmansalesman))
{ }
1
min
1, ,
1, ,
1, ,
, , ,
0,1 .
ijkij ijkx i j i k
ijki j k
ijkj i k
ijki j i
ijk jrki j r j
ijk
c x
x j
x i
x k
x x j k
x
≠
≠
≠
≠
+≠ ≠
= ∀
= ∀
= ∀
= ∀
∈
∑∑∑
∑∑
∑∑
∑∑
∑ ∑
Cada ciudad j es destino de uno y sólo un tramo
Distancia recorrida
Cada ciudad j es origen de uno y sólo un tramo
Variables binarias
En cada tramo k sólo un recorrido
Si j es destino del tramo kentonces es origen del k+1.
Introducción a la Optimización - 81
• El uso de variables enteras o binarias aumenta considerablemente las posibilidades de modelado respecto a la programación lineal:– Modelado de cantidades discretas (e.g. número de personas
que se asignan a una tarea).– Modelado de decisiones que implican un coste fijo o de
arranque:• Adquirir o no un activo (un edificio, una máquina, etc.)• Poner en marcha un proceso.
– Modelado de decisiones que posibilitan la toma de otras decisiones:
• La compra de un determinado aparato (variable binaria) permite después tomar decisiones relativas a su operación.
– Modelado de restricciones no lineales y no convexas.– Modelado de implicaciones y de condiciones lógicas.
Modelado con variables enteras o Modelado con variables enteras o binariasbinarias
Introducción a la Optimización - 82
maxs.a: , 8 , , 0.
A A B B
A B
A A B B
A B
P X P X
X X DT X T X NX X
+
+ ≤+ ≤≥
• Ejemplo LP1: – Supongamos que queremos que el número de tarjetas
montadas sea siempre entero (no se pueden dejar tarjetas a medio montar para el día siguiente):
Modelado de cantidades discretasModelado de cantidades discretas
Recurso escaso 1: demanda
Restricciones adicionales que deben cumplirse: cotas
Criterio para asignar los recursos escasos
Recurso escaso 2: mano de obra
Introducción a la Optimización - 83
0
2
4
6
8
10
12
14
16
18
0 2 4 6 8 10 12 14 16 18
• Ejemplo LP1: PA=3, PB=2, TA=4h, TB=2h, D=12, N=4
Modelado de cantidades discretasModelado de cantidades discretas
Región factible en la versión LP
Restricción de tiempo de mano de obra
Restricción de demanda
Soluciones factibles en la versión MILP
Introducción a la Optimización - 84
• Coste fijo: Ejemplo CF– Comparación entre la compra de un coche de gasolina, un
coche diésel y la alternativa de utilizar coches de alquiler:
Modelado de decisiones que implican un Modelado de decisiones que implican un coste fijo o de arranquecoste fijo o de arranque
Número de kilómetros
Coste (Euros)
Alquiler (sin coste fijo)
gasolina
diésel
Coste fijo de la opción
gasolina
Coste fijo de la opción diésel
Introducción a la Optimización - 85
• Ejemplo CF– Cada decisión i implica dos costes:
• Coste fijo de adquisición: fi
• Coste variable por kilómetro recorrido: vi
– Utilizamos dos variables:• Elección de la alternativa i: xi∈{0,1}• Distancia recorrida si se elige la alternativa i: yi
Modelado de Modelado de decisiones que posibilitandecisiones que posibilitan la la toma de toma de otras decisionesotras decisiones::
{ }
min
s.a: ,
, , , 0,1 .
i i i ii
ii
i i
i
i
f x v y
y d
y x d iy ix
+
≥
≤ ∀∈ ∀
∈
∑
∑
Coste variable asociado a la alternativa i
Coste fijo asociado a la alternativa i
Distancia mínima que se espera recorrer
Relación entre la distancia recorrida y la elección de la alternativa
Introducción a la Optimización - 86
• Ejemplo CF– La decisión de inversión (xi) viene condicionada por el uso que
se vaya a dar a esa inversión (yi)
Modelado de Modelado de decisiones que posibilitandecisiones que posibilitan la la toma de toma de otras decisionesotras decisiones::
Número de kilómetros
Coste (Euros)
Interesa la opción de alquilar
d1 d2
Interesa la opción gasolinaInteresa la opción diésel
d3
Introducción a la Optimización - 87
• Consideremos el problema de maximizar y sabiendo que el valor de y tiene que encontrarse en la región factible de la figura:
Modelado de restricciones no lineales y Modelado de restricciones no lineales y no convexasno convexas
y
x
a 1x+b
1
a 2x+b 2
a3 x+b
3
x*
y*Región factible
Introducción a la Optimización - 88
• Este problema se puede formular en forma LP por ser la región factible convexa:
Modelado de restricciones no lineales y Modelado de restricciones no lineales y no convexasno convexas
1 1
2 2
3 3
maxs.a: , , , , ,
0.
y
y a x by a x by a x bx yx
≤ +≤ +≤ +∈
≥
Introducción a la Optimización - 89
• Ahora consideremos el mismo problema pero con una región no convexa:
Modelado de restricciones no lineales y Modelado de restricciones no lineales y no convexasno convexas
y
x
a 1x+b
1
a 3x+b
3
a4 x+b
4
x*
y*Región factible
a2 x+b
2
Introducción a la Optimización - 90
• No es posible dar una formulación LP para este problema:
Modelado de restricciones no lineales y Modelado de restricciones no lineales y no convexasno convexas
1 1
2 2
3 3
4 4
maxs.a: , , , , , , 0.
y
y a x by a x by a x by a x bx yx
≤ +≤ +≤ +≤ +∈
≥
y
x
a 1x+b
1
a 3x+b
3
a4 x+b
4
x*
y*
a2 x+b
2
Introducción a la Optimización - 91
• En esta situación hay que dividir la región no convexa en regiones convexas y utilizar variables binarias para seleccionar la región convexa.
Modelado de restricciones no lineales y Modelado de restricciones no lineales y no convexasno convexas
y
x
a 1x+b
1
a 3x+b
3
a4 x+b
4
xl
y*
Región 1
u = 0
a2 x+b
2
Región 2
u = 1
Introducción a la Optimización - 92
• Formulamos el problema de la siguiente manera:
Modelado de restricciones no lineales y Modelado de restricciones no lineales y no convexasno convexas
( )( )
( )
{ }
1 1 1 3 2 3
2 1 2 4 2 4
1
2
1 2
maxs.a: 1 ,
1 ,
0 1 ,
, , , , 0,1 .
l
l
y
y a x b u a x b u
y a x b u a x b u
x x u
x u x xux x yu
≤ + − + +
≤ + − + +
≤ ≤ −
≤ ≤∈
∈
Región 1 Región 2
Región 1
Región 2
Introducción a la Optimización - 93
• Si u=0:
Modelado de restricciones no lineales y Modelado de restricciones no lineales y no convexasno convexas
1 1 1 3 2
2 1 2 4 2
1
2
1 2
maxs.a: , ,
0 , 0 0, , , .
l
y
y a x b a xy a x b a x
x xx
x x y
≤ + +
≤ + +≤ ≤≤ ≤
∈ Forzamos que x2=0
Estamos en la
Región 1
Introducción a la Optimización - 94
• Si u=1:
Modelado de restricciones no lineales y Modelado de restricciones no lineales y no convexasno convexas
1 1 3 2 3
2 1 4 2 4
1
2
1 2
maxs.a: , ,
0 0,
, , , .
l
y
y a x a x by a x a x b
x
x x xx x y
≤ + +≤ + +≤ ≤
≤ ≤
∈
Forzamos que x1=0
Estamos en la
Región 2
Introducción a la Optimización - 95
• Las variables binarias se pueden utilizar cuando se quiere modelar que el cumplimiento de una condición implica el cumplimiento de otra:
• Ejemplos:– Si una variable supera un cierto valor entonces una restricción
debe cumplirse.– Si una restricción no se verifica entonces otra debe verificarse.
• Las variables binarias se utilizan para:– Detectar el cumplimento de restricciones.– Forzar el cumplimiento de restricciones.
Modelado de implicacionesModelado de implicaciones
A se cumple ⇒ B se cumple
Variables binarias como indicadores
Introducción a la Optimización - 96
• Ejemplo 1:
– M es un valor positivo grande y m un valor negativo pequeño.– x puede tomar cualquier valor entre m y M– δ es una variable binaria.– Veamos qué ocurre para cada uno de los posibles valores de δ:
• δ = 0 obliga a que x ≤ 0:• δ = 1 no obliga a nada.
– Por otro lado, el valor de x también influye sobre el valor de δ:• x > 0 obliga a que δ = 1:• x ≤ 0 no obliga a nada.
Modelado de implicacionesModelado de implicaciones
x Mδ≤
0 1x δ> ⇒ =
0 0xδ = ⇒ ≤
0 Mm
Introducción a la Optimización - 97
– Es interesante comprobar que con la expresión x ≤ Mδ hemos conseguido representar dos implicaciones:
– En realidad estas dos implicaciones son la misma, si se tiene en cuenta que:
– La posibilidad de representar implicaciones utilizando expresiones matemáticas es importante, porque en programación matemática no es posible utilizar bucles IF ... THEN ...
Modelado de implicacionesModelado de implicaciones
IF δ = 0 THEN x ≤ 0
IF x > 0 THEN δ = 1
A B B A⇒ ⇒equivale a
Introducción a la Optimización - 98
• Ejemplo 2:
– M es un valor positivo grande y m un valor negativo pequeño.– x puede tomar cualquier valor entre m y M– δ es una variable binaria.– Veamos qué ocurre para cada uno de los posibles valores de δ:
• δ = 0 obliga a que x ≥ 0:• δ = 1 no obliga a nada.
– Por otro lado, el valor de x también influye sobre el valor de δ:• x < 0 obliga a que δ = 1:• x ≥ 0 no obliga a nada.
Modelado de implicacionesModelado de implicaciones
x mδ≥
0 1x δ< ⇒ =
0 0xδ = ⇒ ≥
0 Mm
Introducción a la Optimización - 99
– Con la expresión x ≤ mδ hemos conseguido representar dos implicaciones:
– Nuevamente, estas dos implicaciones son la misma, si se tiene en cuenta que:
Modelado de implicacionesModelado de implicaciones
IF δ = 0 THEN x ≥ 0
IF x < 0 THEN δ = 1
A B B A⇒ ⇒equivale a
Introducción a la Optimización - 100
• Resumen de lo que sabemos hacer hasta ahora:
Modelado de implicacionesModelado de implicaciones
IF δ = 0 THEN x ≤ 0
IF x > 0 THEN δ = 1
IF δ = 0 THEN x ≥ 0
IF x < 0 THEN δ = 1
x Mδ≤
x mδ≥
Introducción a la Optimización - 101
• Vamos a estudiar cuatro casos distintos a partir de la restricción:
• Supondremos que siempre se verifican las siguientes condiciones:
Modelado de implicacionesModelado de implicaciones
j jj
a x b≤∑
j jj
a x b M− ≤∑
j jj
a x b m− ≥∑
Suponemos que M es un valor positivo “muy grande”.
Suponemos que m es un valor negativo “muy pequeño”.
Introducción a la Optimización - 102
• Caso 1 (≤)
– Dicho de otra manera:
– La formulación es:
de modo que hay dos situaciones posibles:
Modelado de implicacionesModelado de implicaciones
1 j jj
a x bδ = ⇒ ≤∑
( )1j jj
a x b Mδ− ≤ −∑
1 j jj
a x bδ = ⇒ ≤∑
0 j jj
a x b Mδ = ⇒ ≤ +∑ No pasa nada: se cumple siempre.
Forzamos el cumplimiento de la restricción.
1 j jj
a x bδ = ≤∑IF THEN
Introducción a la Optimización - 103
– Como en los ejemplos anteriores, la formulación
además de modelar la implicación
también modela la implicación:
Modelado de implicacionesModelado de implicaciones
( )1j jj
a x b Mδ− ≤ −∑
0j jj
a x b δ> =∑IF THEN
1 j jj
a x bδ = ≤∑IF THEN
Introducción a la Optimización - 104
– Veamos una particularización:
– La formulación correspondiente es:
– Obsérvese la similitud con el Ejemplo 1 visto anteriormente.
Modelado de implicacionesModelado de implicaciones
1 0xδ = ≤IF THEN
( )1x Mδ≤ −
Introducción a la Optimización - 105
• Caso 2 (≥)
– Dicho de otra manera:
– La formulación es:
de modo que hay dos situaciones posibles:
Modelado de implicacionesModelado de implicaciones
1 j jj
a x bδ = ≥∑IF THEN
1 j jj
a x bδ = ⇒ ≥∑
( )1j jj
a x b mδ− ≥ −∑
1 j jj
a x bδ = ⇒ ≥∑
0 j jj
a x b mδ = ⇒ ≥ +∑ No pasa nada: se cumple siempre.
Forzamos el cumplimiento de la restricción.
Introducción a la Optimización - 106
– Como en los ejemplos anteriores, la formulación
además de modelar la implicación
también modela la implicación:
Modelado de implicacionesModelado de implicaciones
0j jj
a x b δ< =∑IF THEN
( )1j jj
a x b mδ− ≥ −∑
1 j jj
a x bδ = ≥∑IF THEN
Introducción a la Optimización - 107
– Veamos una particularización:
– La formulación correspondiente es:
– Obsérvese la similitud con el Ejemplo 2 visto anteriormente.
Modelado de implicacionesModelado de implicaciones
1 0xδ = ≥IF THEN
( )1x mδ≥ −
Introducción a la Optimización - 108
• Caso 3 (≥)
dicho de otra manera:
– Sabiendo que las dos expresiones siguientes son equivalentes:
convertimos la implicación en otra:
que a su vez equivale a:
Modelado de implicacionesModelado de implicaciones
1 0j j j jj j
a x b a x bδ δ≥ ⇒ = = ⇒ <∑ ∑equivale a
0 j jj
a x bδ ε= ⇒ ≤ −∑
1j jj
a x b δ≥ ⇒ =∑
A B B A⇒ ⇒equivale a
1j jj
a x b δ≥ =∑IF THEN
Introducción a la Optimización - 109
– Hemos llegado a una implicación similar a la del Caso 1.– La diferencia es que en lugar de estamos
manejando la expresión – Por este motivo, en lugar de M hay que manejar M + ε.– La formulación de esta implicación es:
de modo que hay dos situaciones posibles:
Modelado de implicacionesModelado de implicaciones
( )j jj
a x b Mε δ ε− + ≤ +∑
1 j jj
a x b Mδ = ⇒ ≤ +∑
0 j jj
a x bδ ε= ⇒ ≤ −∑
No pasa nada: se cumple siempre.
Forzamos el cumplimiento de la restricción.
j jja x b ε− +∑
j jja x b−∑
Introducción a la Optimización - 110
– Como en los ejemplos anteriores, la formulación
además de modelar la implicación
también modela la implicación:
Modelado de implicacionesModelado de implicaciones
0 j jj
a x bδ = <∑IF THEN
( )j jj
a x b Mε δ ε− + ≤ +∑
1j jj
a x b δ≥ =∑IF THEN
Introducción a la Optimización - 111
– Veamos una particularización:
– La formulación correspondiente es:
Modelado de implicacionesModelado de implicaciones
0 1x δ≥ =IF THEN
( )x Mε δ ε+ ≤ +
Introducción a la Optimización - 112
• Caso 4 (≤)
dicho de otra manera:
– Sabiendo que las dos expresiones siguientes son equivalentes:
convertimos la implicación en otra:
que a su vez equivale a:
Modelado de implicacionesModelado de implicaciones
1j jj
a x b δ≤ =∑IF THEN
1j jj
a x b δ≤ ⇒ =∑
A B B A⇒ ⇒equivale a
1 0j j j jj j
a x b a x bδ δ≤ ⇒ = = ⇒ >∑ ∑equivale a
0 j jj
a x bδ ε= ⇒ ≥ +∑
Introducción a la Optimización - 113
– Hemos llegado a una implicación similar a la del Caso 1.– La diferencia es que en lugar de estamos
manejando la expresión – Por este motivo, en lugar de m hay que manejar m – ε.– La formulación de esta implicación es:
de modo que hay dos situaciones posibles:
Modelado de implicacionesModelado de implicaciones
( )j jj
a x b mε δ ε− − ≥ −∑
1 j jj
a x b mδ = ⇒ ≥ +∑
0 j jj
a x bδ ε= ⇒ ≥ +∑
No pasa nada: se cumple siempre.
Forzamos el cumplimiento de la restricción.
j jja x b ε− −∑
j jja x b−∑
Introducción a la Optimización - 114
– Como en los ejemplos anteriores, la formulación
además de modelar la implicación
también modela la implicación:
Modelado de implicacionesModelado de implicaciones
( )j jj
a x b mε δ ε− − ≥ −∑
1j jj
a x b δ≤ =∑IF THEN
0 j jj
a x bδ = >∑IF THEN
Introducción a la Optimización - 115
– Veamos una particularización:
– La formulación correspondiente es:
Modelado de implicacionesModelado de implicaciones
0 1x δ≤ =IF THEN
( )x mε δ ε− ≥ −
Introducción a la Optimización - 116
• Caso 5 (=)
dicho de otra manera:
– Este caso es una combinación de los casos 1 y 2.– La formulación es:
– δ = 1 fuerza el cumplimiento de las dos restricciones simultáneamente.
Modelado de implicacionesModelado de implicaciones
1 j jj
a x bδ = ⇒ =∑
( )
( )
1
1
j jj
j jj
a x b M
a x b m
δ
δ
− ≤ −
− ≥ −
∑
∑
1 j jj
a x bδ = =∑IF THEN
Introducción a la Optimización - 117
• Caso 6 (=)
dicho de otra manera:
– Este caso es una combinación de los casos 3 y 4.– Con una variable δ1 detectamos el cumplimiento del caso 3:
– Con otra variable δ2 detectamos el cumplimiento del caso 4:
Modelado de implicacionesModelado de implicaciones
1j jj
a x b δ= ⇒ =∑
( )1j jj
a x b Mε δ ε− + ≤ +∑
( )2j jj
a x b mε δ ε− − ≥ −∑
1j jj
a x b δ= =∑IF THEN
Introducción a la Optimización - 118
– Hacemos que δ = 1 detecte que δ1 = 1 y que δ2 = 1:
– La formulación completa es:
Modelado de implicacionesModelado de implicaciones
1 2 1δ δ δ≥ + −
( )
( )
1
2
1 2 1
j jj
j jj
a x b M
a x b m
ε δ ε
ε δ ε
δ δ δ
− + ≤ +
− − ≥ −
≥ + −
∑
∑
Estamos modelando una proposición lógica:
Si δ1 = 1 y δ2 = 1 entonces δ = 1
Introducción a la Optimización - 119
Modelado de implicaciones: ResumenModelado de implicaciones: Resumen
1 j jj
a x bδ = ≤∑IF THEN
1 j jj
a x bδ = ≥∑IF THEN
1j jj
a x b δ≥ =∑IF THEN
1j jj
a x b δ≤ =∑IF THEN
1 j jj
a x bδ = =∑IF THEN
1j jj
a x b δ= =∑IF THEN
( )1j jj
a x b Mδ− ≤ −∑
( )1j jj
a x b mδ− ≥ −∑
( )
( )
1
1
j jj
j jj
a x b M
a x b m
δ
δ
− ≤ −
− ≥ −
∑
∑
( )j jj
a x b Mε δ ε− + ≤ +∑
( )j jj
a x b mε δ ε− − ≥ −∑
( )
( )
1
2
1 2 1
j jj
j jj
a x b M
a x b m
ε δ ε
ε δ ε
δ δ δ
− + ≤ +
− − ≥ −
≥ + −
∑
∑
Introducción a la Optimización - 120
• Caso 1:
Modelado de dobles implicacionesModelado de dobles implicaciones
1 j jj
a x bδ = ≤∑IF THEN
1j jj
a x b δ≤ =∑IF THEN
( )1j jj
a x b Mδ− ≤ −∑
( )j jj
a x b mε δ ε− − ≥ −∑1 j j
j
a x bδ = ⇔ ≤∑
j jj
a x b M− ≤∑
0j jj
a x b ε− − ≥∑0δ = ⇒
No pasa nada: se cumple siempre.
Equivale a lo que queríamos
1j jj
a x b δ≤ ⇒ =∑
0j jj
a x b− ≤∑
j jj
a x b m− ≥∑1δ = ⇒
Lo que queríamos.
No pasa nada: se cumple siempre.
1 j jj
a x bδ = ⇔ ≤∑
Introducción a la Optimización - 121
• Caso 2:
Modelado de dobles implicacionesModelado de dobles implicaciones
1 j jj
a x bδ = ≥∑IF THEN
1j jj
a x b δ≥ =∑IF THEN 1 j j
j
a x bδ = ⇔ ≥∑
0j jj
a x b ε− + ≤∑0δ = ⇒
No pasa nada: se cumple siempre.
Equivale a lo que queríamos
1j jj
a x b δ≥ ⇒ =∑
0j jj
a x b− ≥∑
j jj
a x b M− ≤∑1δ = ⇒
Lo que queríamos.
No pasa nada: se cumple siempre.
1 j jj
a x bδ = ⇔ ≥∑
( )1j jj
a x b mδ− ≥ −∑
( )j jj
a x b Mε δ ε− + ≤ +∑
j jj
a x b m− ≥∑
Introducción a la Optimización - 122
• Hemos visto cómo expresar implicaciones entre restricciones y variables binarias:– Ya somos capaces de formular matemáticamente las
expresiones:“si se cumple esta restricción entonces δ debe valer 1”.“si δ vale 1 entonces debe cumplirse esta restricción ”.“esta restricción se cumple si y sólo si δ vale 1”.
– En general, somos capaces de detectar el cumplimiento de una restricción con variables binarias.
• Ahora nos planteamos la posibilidad de establecer relaciones lógicas entre dos o más restricciones.
• Al cumplimiento de una restricción lo llamaremos proposición:– Ejemplo de proposición: “se verifica que “
Modelado de proposiciones lógicasModelado de proposiciones lógicas
j jj
a x b≥∑
Introducción a la Optimización - 123
• Consideremos que tenemos dos proposiciones, X1 y X2.– Supongamos que queremos modelar dos situaciones:
• Al menos una de las dos proposiciones debe ser cierta.• Las dos proposiciones deben ser ciertas.
– Para modelar estas situaciones, a cada proposición le asignamos una variable binaria de manera que:
– Si queremos que se cumpla al menos una de las dos restricciones:
– Si queremos que se cumplan las dos:
Modelado de proposiciones lógicas Modelado de proposiciones lógicas sencillassencillas
1 2 1 2 1X X δ δ+ ≥o equivale a
1 2 1 21, 1X X δ δ= =y equivale a
1 11 Xδ = ⇒ es cierta 2 21 Xδ = ⇒ es cierta
Introducción a la Optimización - 124
• Consideremos que tenemos dos proposiciones, X1 y X2.– Supongamos que queremos modelar la situación:
• Si X1 es cierta entonces X2 debe serlo.– A cada proposición le asignamos una variable binaria de
manera que:
– La situación se modela entonces:
Modelado de proposiciones lógicas Modelado de proposiciones lógicas sencillassencillas
1 2 1 2 0X X δ δ⇒ − ≤equivale a
1 1 1X δ⇒ = es cierta 2 21 Xδ = ⇒ es cierta
Introducción a la Optimización - 125
• Consideremos que tenemos dos proposiciones, X1 y X2.– Supongamos que queremos modelar la situación:
• X1 es cierta si y sólo si X2 es cierta.– A cada proposición le asignamos una variable binaria de
manera que:
– La situación se modela entonces:
Modelado de proposiciones lógicas Modelado de proposiciones lógicas sencillassencillas
1 2 1 2 0X X δ δ⇔ − =equivale a
1 1 1X δ⇔ = es cierta 2 21 Xδ = ⇔ es cierta
Introducción a la Optimización - 126
• Ejemplo:– Si se fabrica el producto A o B (o ambos) entonces debe
fabricarse también al menos uno de los productos C, D o E.Xi proposición: se fabrica el producto iδi=1 variable binaria asociada al cumplimiento de la proposición i
Xi⇔δi=1– Esta situación se modela como sigue:
δA + δB ≥ 1 ⇒ δC + δD + δE ≥ 1– Añadimos una variable binaria intermedia δ para obtener una
doble implicación:δA + δB ≥ 1 ⇒ δ = 1 ⇒ δC + δD + δE ≥ 1
– Veamos cómo se modela cada una de estas implicacionesδA + δB ≥ 1 ⇒ δ = 1 ≡ δA + δB – 2δ ≤ 0δ = 1 ⇒ δC + δD + δE ≥ 1 ≡ – δC – δD – δE + δ ≤ 0
Modelado de proposiciones lógicas Modelado de proposiciones lógicas complejascomplejas
Introducción a la Optimización - 127
– Formulación alternativa:
equivale a δA ≥ 1 → δC + δD + δE ≥ 1δB ≥ 1 → δC + δD + δE ≥ 1δA ≥ 1 → δ = 1 → δC + δD + δE ≥ 1δB ≥ 1 → δ = 1 → δC + δD + δE ≥ 1
– Formulación:Xi ≤ δi
δA – δ ≤ 0δB – δ ≤ 0– δC – δD – δE + δ ≤ 0
Modelado de proposiciones lógicas Modelado de proposiciones lógicas complejascomplejas
( o ) ( o o )A B C D EX X X X X→
{ }0,1iδ ∈
{ }0,1δ ∈
Introducción a la Optimización - 128
Productos con variables binariasProductos con variables binarias
Reemplazar xδ por y
δ3 =1 ↔ δ1 =1 y δ2 =1δ1 δ2 = δ3
δ1 = 0 ó δ2 = 0δ1 δ2 = 0
{ }
1 2
1 1
2 2
111
, 0,1i i
δ δδ δδ δδ δ
′ ′+ ≥′+ =′+ =
′∈
{ }
1 3
2 3
1 2 3
001
0,1i
δ δδ δ
δ δ δ
δ
− + ≤− + ≤+ − ≤
∈
{ }00,1
xxδ
δ≥
∈0 01
yy x
δδ= → == → =
0
0
yy M
x yx y M M
x M
δ
δ
≥≤
− + ≤− + ≤≤
Introducción a la Optimización - 129
• Construcción de almacenes.• Gestión de autobuses.• Adquisición de camiones.• Planificación del Metro.• Oficina de correos.• Abastecimiento.• Adquisición de máquinas troqueladoras.• Secuenciación de trabajos en una máquina.• Producción II.
Problemas de la biblioteca de problemasProblemas de la biblioteca de problemas