Download B - IIT - Universidad Pontificia Comillas

ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
Modelado en optimización
José María Ferrer Caja
Universidad Pontificia Comillas
Optimización
Encontrar el valor que deben tomar las variables del
problema para hacer óptima la función objetivo, y de
forma que se satisfagan las restricciones
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
Modelado en optimización- 1
Componentes de un problema de optimización
Función objetivo
Medida cuantitativa del funcionamiento del sistema que se
desea optimizar (maximizar o minimizar)
Variables
Representan las decisiones que se pueden adoptar y de las
que depende el valor de la función objetivo
Variables de control y de estado
Restricciones
Relaciones que las variables deben satisfacer
Igualdades y desigualdades
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
Modelado en optimización- 2
Clasificación de modelos
Función objetivo
Lineal, cuadrática, no lineal, no diferenciable, multiobjetivo,
estocástica, sin función objetivo
Restricciones
Sin restricciones, lineales, no lineales, no diferenciables,
acotadas, disyuntivas, probabilísticas
Variables
Continuas, enteras, binarias
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
Modelado en optimización- 3
Modelo
Representación simplificada de la realidad,
generalmente de forma matemática, que facilita su
comprensión y el estudio de su comportamiento
Un buen modelo debe mantener un equilibrio entre
sencillez y capacidad de representación
Se requiere una interacción constante entre el
modelador (creador del modelo) y el experto
(conocedor del problema real)
Es a la vez una ciencia y un arte
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
Modelado en optimización- 4
Etapas en el desarrollo de un modelo
Identificación del problema
Especificación matemática y formulación
Resolución
Verificación, validación y refinamiento
Interpretación y análisis de resultados
Implantación, documentación y mantenimiento
El tiempo empleado en realizar correctamente una
etapa facilitará de forma notable las etapas sucesivas
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
Modelado en optimización- 5
Identificación del problema
Recolección de información relevante
Planteamiento general del problema
Qué se quiere optimizar
De qué alternativas se dispone
Qué limitaciones se tienen
Interpretación y traducción a términos precisos de los
datos y elementos del problema
Fase fundamental para que las futuras decisiones
sean útiles
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
Modelado en optimización- 6
Especificación matemática y formulación
Definición en términos matemáticos adecuados de los
elementos del problema
Función objetivo
Variables
Restricciones
Parámetros
Identificación del tipo(s) de modelo general que se
puede aplicar
Formulación clara y elegante
Análisis del tamaño y estructura del problema
formulado
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
Modelado en optimización- 7
Resolución
Elección del tipo de método de solución y de algoritmos
adecuados
Implementación (en un lenguaje informático adecuado)
de los algoritmos elegidos
Obtención de la solución óptima o de soluciones
suficientemente satisfactorias
El tiempo de resolución dependerá de la formulación
propuesta
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
Modelado en optimización- 8
Verificación, validación y refinamiento
Comprobación de coherencia con la realidad
Detección y corrección de errores de codificación
Mejora y ampliación por nuevas necesidades
En la definición
En la formulación
En la implementación
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
Modelado en optimización- 9
Interpretación y análisis de resultados
Análisis de sensibilidad de la solución obtenida, frente a
cambios en los parámetros
Detección de soluciones robustas
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
Modelado en optimización- 10
Implantación, documentación y mantenimiento
Documentación clara, precisa y completa
El código debe estar escrito de forma ordenada y debe
incluir comentarios que faciliten las operaciones de
mantenimiento
Elaboración de un manual de usuario con
especificaciones matemáticas e informáticas
Formación de usuarios
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
Modelado en optimización- 11
Ejemplo de la dieta: Planteamiento
La alimentación diaria de una ternera debe contener al menos:
700 g de proteínas
28 g de calcio
150 mg de vitaminas
Se dispone de pienso y forraje con coste por kg de 30 y 35
céntimos de euro
La composición nutritiva por kg de alimento es:
Proteínas (g)
Calcio (g)
Vitaminas (mg)
Pienso
30
2
10
Forraje
45
1
5
Se trata de determinar la cantidad diaria de cada alimento para
minimizar el coste total de la alimentación
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
Modelado en optimización- 12
Ejemplo de la dieta: Formulación genérica
Índices:
i → tipo de alimento (pienso y forraje)
j → tipo de nutriente (proteínas, calcio y vitaminas)
Parámetros:
bj → cantidad mínima diaria requerida del nutriente j
aij → cantidad de nutriente j por kg de alimento i
ci → coste por kg del alimento i
Variables:
xi → cantidad diaria de alimento i por ternera
Función objetivo:
Restricciones:
min ∑ci xi
xi
i
De satisfacción de la cantidad de nutrientes
De no negatividad x i ≥ 0 ∀ i
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
∑a x
ij
i
≥ bj ∀j
i
Modelado en optimización- 13
Ejemplo de la dieta: Formulación numérica
min 30x 1 + 35x 2
x1 , x 2
30x 1 + 45x 2 ≥ 700
(proteínas)
2x 1 + x 2 ≥ 28
(calcio)
10x 1 + 5x 2 ≥ 150
(vitaminas)
x1 ≥ 0
x2 ≥ 0
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
Modelado en optimización- 14
Modelos generales de optimización:
Programación lineal (LP)
min z = c1x1 + c2x2 + …+ cnxn
T
min c x
s.a
Ax = b
x ≥0
a11x 1 + a12x 2 + … + a1n x n = b1
x
⇔
x ∈ n ,c ∈ n , A ∈ m×n ,b ∈ m
 x 
 1 
 vector de


x =  
  variables
x n 
a

 11 a 1n 

A =  


a m 1 a mn 
am 1x 1 + am 2x 2 + … + amn x n = bm
x 1, x 2 , …, x n ≥ 0
c 
 1  vector de



c =   coeficientes
 
cn  de coste
 b 
 1 
 vector de

matriz de
b =  
  demandas
restricciones
bm 
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
Modelado en optimización- 15
Modelos generales de optimización:
Programación entera (IP)
min cT x + d T y
x
Ax + By = b
x, y ≥ 0
x ∈ n , y ∈ l , c ∈ n , d ∈ l
A ∈ m×n , B ∈ m×l , b ∈ m
Si l = 0 → Programación entera pura (PIP)
Si l > 0 → Programación entera mixta (MIP)
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
Modelado en optimización- 16
Modelos generales de optimización:
Programación binaria (BIP)
min cT x
x
Ax = b
x ≥0
n
x ∈ {0,1} ,c ∈ n , A ∈ m×n ,b ∈ m
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
Modelado en optimización- 17
Modelos generales de optimización:
Programación cuadrática (QP)
1 T
min c x + x Qx
x
2
Ax = b
T
x ≥0
x ∈ n , c ∈ n , A ∈ m×n
Q ∈ n×n , b ∈ m
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
Modelado en optimización- 18
Modelos generales de optimización:
Programación no lineal (NLP)
min f (x )
x
g (x ) = 0
h (x ) ≤ 0
l ≤x ≤u
f : n → g : n → m
h : n → k
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
Modelado en optimización- 19
Modelos generales de optimización:
Programación multiobjetivo
min(f1(x ),..., fk (x ))
x
Ax = b
x ≥0
x ∈ n , c ∈ n , A ∈ m×n , b ∈ m
fi (x ) : n → ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
Modelado en optimización- 20
Modelos generales de optimización: Especiales
Optimización no lineal sin
restricciones
min f (x )
x
f : n → Ajuste no lineal mínimo cuadrático
Problema mixto complementario
(MCP)
xF (x ) = 0
x ∈ n
F : n → n
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
Modelado en optimización- 21
Modelos específicos de programación lineal
y entera
Problema del transporte
Problema del transbordo
Problema de asignación
Problema de la mochila (knapsack)
Problema del recubrimiento (set-covering)
Problema del empaquetado (set-packing)
Problema de la partición (set-partitioning)
Problema del viajante (TSP)
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
Modelado en optimización- 22
Problema del transporte: Definición
Minimizar el coste total de transporte de un producto
desde los orígenes a los destinos, satisfaciendo la
demanda de cada destino sin superar la oferta
disponible en cada origen
a1 1
ai
a
Oferta en el origen i 2
2
am m
1
b1
2
b2 Demanda enj el destino j
n
bn
b
cij
Coste unitario de transporte del origen i al destino j
m
Se supone que la oferta es igual a la demanda:
∑a = ∑b
i
i =1
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
n
j
j =1
Modelado en optimización- 23
Problema del transporte: Formulación
Variables de decisión
xij = unidades transportadas desde el origen i al destino j
min
x ij
m
n
i=1
j=1
∑ ∑c x
ij
ij
s .a
m
∑x
i=1
n
ij
= bj
j = 1,..., n
∑x
j=1
ij
= ai
i = 1,..., m
x ij ≥ 0
i = 1,..., m, j = 1,..., n
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
Modelado en optimización- 24
Problema del transporte: Propiedades
Si
Si
m
∑ a > ∑b
i
i =1
j =1
m
n
i
se añade un sumidero universal con coste nulo
j
∑ a < ∑b
i =1
n
j
se añade una fuente universal con coste elevado
j =1
La matriz de restricciones es totalmente unimodular: todos los
determinantes de las submatrices valen 0, 1 ó -1
Por lo tanto, si los coeficientes de oferta ai y demanda bj son
enteros la solución óptima es un vector entero → x ij∗ ∈ ∀ i, j
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
Modelado en optimización- 25
Problema del transbordo: Definición
Transportar un producto en una red satisfaciendo la
demanda, con el mínimo coste posible
bi → Cantidad de producto disponible en el nodo i
oferta: bi > 0
demanda: bi < 0
transbordo: bi = 0
cij → Coste unitario de transporte del nodo i al nodo j
Se supone que la oferta es igual a la demanda:
m
∑b = 0
i
i =1
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
Modelado en optimización- 26
Problema del transbordo: Formulación
Variables de decisión
xij = unidades transportadas desde el nodo i al nodo j
n
n
min ∑ ∑ cij x ij
x ij
conservación del
flujo
n
∑x
j =1
j ≠i
i =1 j = 1
n
ij
− ∑ x ki = bi
k =1
k ≠i
x ij ≥ 0
Matriz totalmente unimodular:
i = 1, … , n
i, j = 1,..., n , i ≠ j
b i ∈ ∀ i ⇒ x ij∗ ∈ ∀ i , j
El problema del transbordo generaliza al problema del transporte
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
Modelado en optimización- 27
Problema de asignación
Asignar n tareas a n máquinas de forma que el coste
total sea mínimo
cij → Coste de asignar la tarea i a la máquina j
Variables
 1 si se asigna la tarea i a la máquina j
xij = 
si no
0
Formulación
Cada tarea ha de ser
realizada por una
máquina
Cada máquina ha de
realizar una tarea
n
m in
x ij
n
∑ ∑c
i =1
ij
x ij
j =1
n
∑x
ij
= 1
i = 1, … , n
∑x
ij
= 1
j = 1, … , n
j =1
n
i =1
x ij ∈ {0, 1}
∀ i, j
Caso particular del problema del transporte
La restricción xij ∈ {0,1} puede sustituirse por xij ≥ 0
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
Modelado en optimización- 28
Problema de la mochila
Elegir objetos de los n disponibles de forma que el valor
total sea máximo, sin sobrepasar el volumen disponible
cj → Volumen que ocupa el objeto j
vj → Valor del objeto j
b → Volumen total disponible
Variables
Formulación
 1 si se elige el objeto j
xj = 
si no
0
n
max ∑ v j x j
xj
j =1
n
∑c x ≤ b
x ∈ {0,1}
j
j
j =1
j
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
∀j
Modelado en optimización- 29
Problema del recubrimiento
Se dispone de un conjunto de m elementos y una
colección de n subconjuntos
Se desea elegir subconjuntos que cubran todos los
elementos al menos una vez, y con el mínimo coste
cj → Coste del subconjunto j
aij → Indica si el elemento i pertenece al subconjunto j (1 sí, 0 no)
Variables
 1 si se elige el subconjunto j
xj = 
si no
0
Formulación
Cada elemento
seleccionado al
menos una vez
n
min ∑ c j x j
xj
j =1
n
∑ a x ≥ 1 i = 1, …, m
x ∈ {0,1} j = 1, …, n
ij
j
j =1
j
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
Modelado en optimización- 30
Problema del recubrimiento: Ejemplo
Una compañía aérea con base en San Francisco quiere cubrir todos
sus vuelos asignando tres tripulaciones a algunas de las 12
secuencias factibles de vuelos que se indican en la siguiente tabla.
El objetivo es minimizar el coste de la asignación. Los costes de las
diferentes secuencias aparecen en la última fila:
SF – LA
SF – Denver
SF – Seattle
LA – Chicago
LA – SF
Chicago – Denver
Chicago – Seattle
Denver – SF
Denver – Chicago
Seattle – SF
Seattle – LA
Coste (M€)
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
1
1
2
3
4
1
1
1
2
2
3
2
4
2
2
3
4
6
Secuencias
5 6 7
1
1
1
2
3
3
3
4
2
4
2
7 5 7
factibles
8 9 10
1
1
1
3 2
5
4
3
3
5
2
4
2 4
8 9 9
11
12
1
1
3
5
3
4
2
4
8
5
2
9
Modelado en optimización- 31
Problema del recubrimiento: Ejemplo

1 si se asigna la secuencia j


xj = 

0 en cualquier otro caso


Variables:
Formulación:
min 2x1 + 3x 2 + 4x 3 + 6x 4 + 7x 5 + 5x 6 + 7x 7 + 8x 8 + 9x 9 + 9x10 + 8x11 + 9x12
x 1 + x 4 + x 7 + x 10 ≥ 1
(SF-LA)
x 2 + x 5 + x 8 + x 11 ≥ 1
x 3 + x 6 + x 9 + x 12 ≥ 1
(SF-Denver)
(SF-Seattle)
12
∑x
j
=3
(Dispone de tres tripulaciones)
j =1
x j ∈ {0,1} j = 1,...,12
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
x 3 = x 4 = x 11 = 1
x 1 = x 5 = x 12 = 1
Modelado en optimización- 32
Problema del empaquetado
Se dispone de un conjunto de m elementos y una
colección de n subconjuntos
Se desea elegir los subconjuntos que den el máximo
beneficio total, sin que ningún elemento aparezca más
de una vez
cj → Beneficio del subconjunto j
aij → Indica si el elemento i pertenece al subconjunto j (1 sí, 0 no)
Variables
 1 si se elige el subconjunto j
xj = 
si no
0
Formulación
Cada elemento
seleccionado como
mucho una vez
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
n
max ∑ c j x j
xj
j =1
n
∑ a x ≤ 1 i = 1, …, m
x ∈ {0,1} j = 1, …, n
ij
j
j =1
j
Modelado en optimización- 33
Problema de la partición
Análogo al problema del empaquetado, pero
seleccionando exactamente una vez cada elemento
n
max ∑ c j x j
xj
Cada elemento
seleccionado una vez
j =1
n
∑ a x = 1 i = 1, …, m
x ∈ {0,1} j = 1, …, n
ij
j
j =1
j
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
Modelado en optimización- 34
Recubrimiento, partición, empaquetado
RECUBRIMIENTO
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
PARTICIÓN
EMPAQUETADO
Modelado en optimización- 35
Problema del viajante: Formulación 1
Realizar un circuito que pase por n ciudades sin repetir
ninguna (volviendo a la ciudad de partida) de manera
que la distancia (o tiempo o coste) total sea mínima
cij → Distancia de la ciudad i a la ciudad j
Variables:

1 si se va de la ciudad i a la ciudad j


xij = 

0
en otro caso


Formulación:
A cada ciudad se
llega una vez
De cada ciudad se
sale una vez
No se permiten
subciclos
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
min ∑cij xij
xij
i, j
∑x
∑x
∑x
ij
= 1 ∀j = 1,..., n
ij
= 1 ∀i = 1,..., n
ij
≤ card(U ) − 1 ∀U ⊂ {1,…, n},2 ≤ card(U ) ≤ n − 2
i
j
i, j ∈U
xij ∈ {0,1} ∀i, j = 1,..., n
Modelado en optimización- 36
Problema del viajante: Formulación 2
Variables:


1 si se va de la ciudad i a la ciudad j en la etapa k del circuito

xijk = 

0
en otro caso


Formulación:
De cada ciudad se
sale una vez
A cada ciudad se
llega una vez
En cada etapa se
recorre un tramo
En cada etapa se
sale de la ciudad a la
que se ha llegado en
la etapa anterior
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
min ∑ c ij x ijk
x ijk
i , j ,k
∑x
∑x
∑x
∑x
ijk
= 1 ∀ i = 1, ..., n
ijk
= 1 ∀ j = 1, ..., n
ijk
= 1 ∀ k = 1, ..., n
j ,k
i ,k
i, j
i
x ijk
∑x
∈ {0, 1} ∀ i, j , k
ijk
=
jrk + 1
∀ j , k = 1, ..., n
r
= 1, ..., n
Modelado en optimización- 37
Modelado con variables binarias
Conversión de entera a binarias
Disyunciones
Disyunciones por bloques
Cumplimiento de un número de ecuaciones
Selección entre varios valores
Implicaciones entre variables binarias y restricciones
Implicaciones
Relaciones sencillas entre variables binarias
Productos
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
Modelado en optimización- 38
Conversión de entera a binarias
Se quiere descomponer la variable entera x en
variables binarias y1, y2 , …
Se busca una cota superior u
0≤x ≤u
Se determina N tal que
2N ≤ u ≤ 2N +1
La descomposición es
N
x=
i
2
∑ yi
i =0
Se ha de sustituir en el modelo x por dicha expresión,
añadiendo
yi ∈ {0,1} ∀i
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
Modelado en optimización- 39
Tabla de equivalencias lógicas
P→Q
no P ó Q
P↔Q
(P → Q) y (Q → P)
P → (Q y R)
(P → Q) y (P → R)
P → (Q ó R)
(P → Q) ó (P → R)
(P y Q) → R
(P→ R) ó (Q → R)
(P ó Q) → R
(P→ R) y (Q → R)
no (P ó Q)
no P y no Q
no (P y Q)
no P ó no Q
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
Modelado en optimización- 40
Disyunciones
f (x ) ≤ 0
ó
g (x ) ≤ 0 se modela mediante


 f (x ) ≤ M δ
δ ∈ {0,1}


g(x ) ≤ M (1 − δ )


M es suficientemente grande. Lo ideal es que la M de cada
restricción sea la cota más ajustada para cada restricción
La implicación f (x ) > 0 ⇒ g (x ) ≤ 0 es equivalente a
f (x ) ≤ 0 ó
g(x ) ≤ 0
Ejemplo:
3x + 2y − z < 3 ⇒ x − 4y + z ≥ 1
⇔
−3x − 2y + z + 3 > 0 ⇒ −x + 4y − z + 1 ≤ 0
⇔
−3x − 2y + z + 3 ≤ 0 ó − x + 4y − z + 1 ≤ 0
⇔


−3x − 2y + z + 3 ≤ M δ
δ ∈ {0,1}

−
x
+
4
y
−
z
+
1
≤
M
(1
−
δ
)


ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
Modelado en optimización- 41
Disyunciones por bloques



f1(x ) ≤ 0

g1(x ) ≤ 0






f
(
x
)
≤
0
g 2 (x ) ≤ 0


2

ó











fk (x ) ≤ 0
g (x ) ≤ 0





 l


f1(x ) ≤ M δ







 fk (x ) ≤ M δ


g1(x ) ≤ M (1 − δ )







g (x ) ≤ M (1 − δ )

 l
se modela mediante
δ ∈ {0,1}
Este método es apropiado para regiones factibles no convexas
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
Modelado en optimización- 42
Cumplimiento de un número de ecuaciones
Se deben cumplir al menos k de las N ecuaciones:
f1(x 1, …, x n ) ≤ 0
f2 (x 1, …, x n ) ≤ 0
…
fN (x 1, …, x n ) ≤ 0
La formulación sería
f1(x 1, …, x n ) ≤ M δ1
f2 (x 1, …, x n ) ≤ M δ2
fN (x 1, …, x n ) ≤ M δN
N
∑δ
i
= N −k
i =1
δi ∈ {0,1}
∀i = 1, …, N
El caso N = 2, k = 1 equivale a una disyunción
Se procede de forma análoga para bloques de ecuaciones
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
Modelado en optimización- 43
Selección entre varios valores
La función f ha de tomar uno de los valores de la
siguiente lista:

d1




d2


f (x 1, …, x n ) = 





d

 N
La formulación sería
N
f (x 1, …, x n ) = ∑ di δi
i =1
N
∑δ
i
=1
i =1
δi ∈ {0,1}
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
i = 1, …, N
Modelado en optimización- 44
Implicaciones entre variables binarias y
restricciones
δ =1⇒
∑a x
j
j
∑a x
≤b
j
j
j
∑a x
j
∑a x
≤b ⇒ δ = 1
j
j
∑a x
δ = 1 ⇒ ∑ a jx j ≥ b
j
j
≥ b + m(1 − δ )
j
j
j
j
≥ b + ε + (m − ε)δ
j
j
j
∑a x
≤ b + M (1 − δ )
j
≥b ⇒ δ = 1
j
∑a x
j
≤ b − ε + (M + ε)δ
∑a x
j
≤ b + M (1 − δ )
∑a x
j
≥ b + m(1 − δ )
∑a x
j
≥ b + ε + (m − ε)δ ′
∑a x
j
≤ b − ε + (M + ε)δ ′′
j
j
δ =1⇒
∑a x
j
j
j
=b
j
j
j
j
j
∑a x
j
j
j
=b ⇒ δ =1
j
j
j
δ ′ + δ ′′ − δ ≤ 1
Donde
m ≤ ∑ ajx j − b ≤ M
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
y
ε > 0, ε 0
j
Modelado en optimización- 45
Implicaciones
La implicación f (x ) ≤ 0 ⇒ g(x ) ≤ 0 se puede descomponer
como (f (x ) ≤ 0 ⇒ δ = 1) y (δ = 1 ⇒ g(x ) ≤ 0) y aplicar las
relaciones de la transparencia anterior
La doble implicación f (x) ≤ 0 ⇔ g(x ) ≤ 0 se puede
descomponer como (f (x ) ≤ 0 ⇔ δ = 1) y (δ = 1 ⇔ g(x ) ≤ 0) y
aplicar las relaciones de la transparencia anterior
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
Modelado en optimización- 46
Relaciones sencillas entre variables binarias
δ1 = 1 ó δ2 = 1
δ1 + δ2 ≥ 1
δ1 = 1 ⇒ δ2 = 1
δ1 ≤ δ2
δ1 = 1 ⇔ δ2 = 1
δ1 = δ2
δ1 = 1,..., δk = 1 ⇒ δ1' = 1 ó...ó δl' = 1
δ1' + ... + δl' ≥ δ1 + ... + δk − k + 1
N
Al menos k de {δj = 1}
j =1
N
Como mucho k de {δj = 1}
j =1
δ1 + ... + δN ≥ k
δ1 + ... + δN ≤ k
Si en vez de δ = 1 se tiene δ = 0 en la expresión equivalente se sustituye
δ por 1−δ
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
Modelado en optimización- 47
Ejemplo de fabricación: Formulación 1
Si se fabrica alguno de los productos A o B entonces
debe fabricarse también al menos uno de los productos
C, D o E


1 si se fabrica el producto j

δj = 
j ∈ {A, B,C , D, E }

0
si no


δA = 1 ó δB = 1 ⇒ δC = 1 ó δD = 1 ó δE = 1


δA = 1 ⇒ δC = 1 ó δD = 1 ó δE = 1


δ = 1 ⇒ δC = 1 ó δD = 1 ó δE = 1

B


δC + δD + δE ≥ δA


δ + δD + δE ≥ δB

C
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
Modelado en optimización- 48
Ejemplo de fabricación: Formulación 2
δA = 1 ó δB = 1 ⇒ δC = 1 ó δD = 1 ó δE = 1
δA + δB ≥ 1 ⇒ δC + δD + δE ≥ 1


δA + δB ≥ 1 ⇒ δ = 1


δ = 1 ⇒ δC + δD + δE ≥ 1




2δ ≥ δA + δB


δ + δD + δE ≥ δ

C
Hay que añadir las restricciones 0-1 a las variables binarias
Si xj es la cantidad de producto j que se fabrica habría que añadir
(en cualquiera de las formulaciones)
x j ≤ M δ j ∀j
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
Modelado en optimización- 49
Ejemplo de baloncesto: Planteamiento
Un entrenador de baloncesto tiene 9 jugadores, a los que ha
evaluado de 1 a 3 de acuerdo con su manejo de pelota, tiro, rebote
y defensa, según se indica en la tabla adjunta:
Jugador
Posiciones
Manejo de pelota
Tiro
Rebote
Defensa
1
Pívot
2
1
3
3
2
Base
3
3
1
2
3
Pívot, Alero
2
3
2
2
4
Alero, Base
1
3
3
1
5
Pívot, Alero
1
3
1
2
6
Alero, Base
3
1
2
3
7
Pívot, Alero
3
2
2
1
8
Pívot
2
1
3
2
9
Alero
3
3
1
3
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
Modelado en optimización- 50
Ejemplo de baloncesto: Planteamiento
El equipo titular de 5 jugadores debe tener la máxima capacidad
defensiva y satisfacer las siguientes condiciones:
Al menos dos jugadores deben estar en disposición de actuar de
pívot, dos de alero y uno de base
Su nivel medio en el manejo de pelota en tiro y en rebote debe ser
por lo menos 2
Si juega el jugador 3, entonces el jugador 6 no puede jugar
Si juega el jugador 1, también deberá jugar el 4 ó el 5, pero no los
dos a la vez
El jugador 8 ó el 9, pero no los dos a la vez, deben jugar
Formular un programa lineal que facilite la selección del equipo
titular
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
Modelado en optimización- 51
Ejemplo de baloncesto: Formulación
Variables:
1 si se incluye el jugador j en el equipo
x j = 0


en otro caso
j = 1, …, 9
x

1 si se incluye el jugador j en posición k


=
en otro caso
jk 0
j = 3, 4,5,6,7
k = p, a,b (sólo los necesarios)
Función objetivo:
max 3x 1 + 2x 2 + 2x 3 + x 4 + 2x 5 + 3x 6 + x 7 + 2x 8 + 3x 9
Restricciones:
x1 + x 2 + x 3 + x 4 + x 5 + x 6 + x 7 + x 8 + x 9 = 5
5 jugadores en el equipo
x1 + x 3p + x 5p + x 7 p + x 8 ≥ 2
Al menos 2 pívots
x 3a + x 4a + x 5a + x 6a + x 7a + x 9 ≥ 2
Al menos 2 aleros
x 2 + x 4b + x 6b ≥ 1
Al menos 1 base
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
Modelado en optimización- 52
Ejemplo de baloncesto: Formulación


2x 1 + 3x 2 + 2x 3 + x 4 + x 5 + 3x 6 + 3x 7 + 2x 8 + 3x 9 ≥ 10


x + 3x + 3x + 3x + 3x + x + 2x + x + 3x ≥ 10
 1
2
3
4
5
6
7
8
9


3x + x 2 + 2x 3 + 3x 4 + x 5 + 2x 6 + 2x 7 + 3x 8 + x 9 ≥ 10

 1
x3 + x6 ≤ 1
Equivale a x 3 = 1 ⇒ x 6 = 0
x 4 + x 5 ≤ 2 − x1



 x +x ≥x

5
1

 4
x8 + x9 = 1


x 3 p + x 3a − x 3 = 0



x 4a + x 4b − x 4 = 0




x 5 p + x 5a − x 5 = 0


x 6a + x 6b − x 6 = 0




x + x 7a − x 7 = 0


 7p
Nivel medio al menos 2
en manejo, tiro y rebote
Equivalen a x 1 = 1 ⇒ x 4 + x 5 = 1
Deben jugar 8 ó 9, pero no ambos
Coherencia entre puestos para los
jugadores polivalentes
x j , x jk ∈ {0,1} ∀j, k
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
Modelado en optimización- 53
Productos
δ1δ2 = 0
δi ∈ {0,1}
δ1δ2
δi ∈ {0,1}
δ1 + δ2 ≤ 1
δ1 = 0 ó δ2 = 0
Reemplazar δ1δ2 por
δi ∈ {0,1}
δ3
δ3 = 1 ⇔ δ1 = 1 y δ2 = 1
δ3 ≤ δ1
δ3 ≤ δ2
δ3 ≥ δ1 + δ2 − 1
δi ∈ {0,1}
xδ
x ≥0
δ ∈ {0,1}
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
Reemplazar xδ por
δ =0⇒y =0
δ =1⇒y =x
y
y≥0
y ≤ Mδ
y ≤x
y ≥ x + Mδ − M
(donde x ≤ M )
Modelado en optimización- 54
Modelado de funciones objetivo no lineales
Problemas con coste fijo (fixed-charge)
Problemas con costes variables por tramos
Función objetivo minimax o maximin
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
Modelado en optimización- 55
Problemas con coste fijo
Cada variable xj lleva asociado un coste fijo kj y un coste
unitario cj:
0



f j (x j ) = 

k + c jx j

 j
xj > 0
Se introduce una variable binaria yj por cada xj que cumpla


1

yj = 

0


xj > 0
xj = 0
Para ello se añaden restricciones de la forma
y j ∈ {0,1}
xj ≤ M ⋅ yj
xj = 0
xj ≥ 0
(M “grande”)
La función objetivo queda
n
m in
x j ,y j
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
n
∑ f (x
j
j =1
j
) = ∑ (k j y j + c j x j )
j =1
Modelado en optimización- 56
Problemas con costes variables por tramos
La variable x lleva asociados costes c1, c2,…, cN en los
tramos (p0, p1], (p1, p2],…, (pN-1, pN]
Se introducen N variables continuas y N variables binarias de la
siguiente forma


x
x =

0



k
si x ∈ p k −1 , p k 

si no
(


1
δ =

0



k
si x k > 0
xk = 0
En la función objetivo se introduce el sumando
N
cx =
∑c
k
xk
k =1
Se añaden las restricciones
N
∑x
N
k
= x,
k =1
∑δ
k
k =1
( p k −1 + ε )δ k ≤ x k ≤ p k δ k
δ k ∈ {0, 1}
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
=1
∀ k = 1, ..., N
∀ k = 1, ..., N
Modelado en optimización- 57
Función objetivo minimax o maximin
min f (x )
x
Ax = b
siendo
x ≥0
{
f (x ) = max c 1T x + d 1 , c T2 x + d 2 , ..., c Tp x + d p
c 1 , c 2 , ..., c p ∈ n ,
d 1 , d 2 , ..., d p ∈ x ∈ n , A ∈ m×n , b ∈ m
El problema se puede reformular como
min z
z ≥ c1T x + d1
z ≥ cT2 x + d2
z ≥ cTp x + d p
Ax = b
x ≥0
Análogo para función objetivo maximin
ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL
Modelado en optimización- 58
}