Material Modelamiento

Vista previa del material en texto

Universidad de Los Andes
Facultad de Ingenieŕıa
Semestre 2009-1
Profesor: Carlos Alarcón, Miguel Carrasco
Auxiliar: Diego Morán, Andrea Valle
Un poco más sobre modelamiento
Introducción a la Optimización
Abril 2009
‘‘Multiplicando’’ variables binarias en un problema de programación lineal entera.
Suponga que tiene 2 variables binarias x e y, Cxy un parámetro constante y que necesita que aparezca en la
función objetivo o en una restriccón el término Cxy · xy, que es claramente una expresión no lineal (pues es
una multiplicación de variables).
¿Cómo se puede escribir esta expresión de manera lineal?
Fácil,observando de que el producto xy puede valer 0 o 1 uno se da cuenta de que basta con crear la variable:
z =
{
1, si x = y = 1
0, si no
Y las restricciones:
x+ y ≤ 2z
z ≤ x
z ≤ y
De lo anterior la variable z representa exactamente el valor del producto x · y.
Con esto Ud. el término Cxy · xy lo puede escribir como Cxy · z, que es lineal.
‘‘Multiplicando’’ una variable binaria por una entera o real acotada en un problema
de programación lineal entera.
Suponga que tiene una variable binaria x y una variable entera o real acotada y (suponga L ≤ y ≤ U), Cxy
un parámetro constante y que necesita que aparezca en la función objetivo o en una restriccón el término
Cxy · xy, que es claramente una expresión no lineal (pues es una multiplicación de variables).
¿Cómo se puede escribir esta expresión de manera lineal?
No es tan fácil, pero tampoco imposible. Defina la variable real positiva:
z = valor que toma el productox · y
Para que la definición tenga sentido, basta agregar las siguientes restricciones:
z ≤ Ux
y ≤ z + U(1− x)
z + L(1− x) ≤ y
Note que, de las restricciones anteriores, si x = 0, entonces z = 0 y si x = 1, entonces z = y.
Con esto Ud. el término Cxy · xy lo puede escribir como Cxy · z, que es lineal.
Cómo saber si una variable es mayor o menor que otra en un problema de programación
lineal entera.
Suponga que tiene 2 variables enteras x e y tal que −M ≤ x− y ≤M . Suponga que tiene un costo asociado
a que x sea mayor que y, espećıficamente necesita que aparezca en la función objetivo o en alguna restriccón
el término C, sólo cuando x > y.
Veamos cómo hacer esto. Defina las variables:
z =
{
1, si x > y
0, si no
Y considere las siguientes restricciones:
x− y ≤Mz
−M(1− z) + 0,5 ≤ x− y
Estas restricciones hacen que la variable z tenga el siginicado requerido.
Aśı, para agregar la expresión que se necesita basta poner el término lineal C · z.
2
Ejercicio propuesto.
P1.- Considere que Ud. es propietario de una empresa de delivery OptiPizza, en la cual están a su cargo
M trabajadores dedicados a repartir el producto. Inicialmente, la reglamentación horaria estipulaba
trabajar 16 hrs. ininterrumpidas a todos sus empleados. Sin embargo, por normativas superiores se
debe organizar un sistema de turnos que satisfaga un porcentaje de la demanda.
Para tales efectos, la demanda por hora es conocida y está dada por Di [Unidades/hora],
i = 1, . . . , 16, y en esta nueva etapa se propone satisfacer al menos un porcentaje pi ∈ ] 0, 1] de ella.
Además, cada empleado satisface sólo un pedido por hora y no puede trabajar más de 8 horas diarias
continuas.
a) Plantee un modelo de optimización lineal entero que permita encontrar la cantidad mı́nima de
turnos y la distribución de empleados por turno que satisfaga la restricción de demanda. Por turno
se entiende un bloque de 8 horas continuas.
Indicación: Considere las variables yj ∈ {0, 1}, las cuales indican si se inicia o no un turno en la
hora j, y las variables xj , que indican el número de empleados que entran en la hora j.
b) Dados los malos resultados de la poĺıtica anterior, se decide imponer que el 20 % de sus empleados
trabaje horas extra (10 horas en lugar de 8). Formule el modelo para considerar este caso.
Como ninguna de las ideas anteriores le ha funcionado satisfactoriamente Ud. ha decidido redefinir el
concepto de turno. Su propuesta consiste en considerar nuevamente 9 bloques de 8 horas, no necesari-
amente continuos. Para i ∈ {1, . . . , 9}, el bloque i-ésimo comienza en la hora i y las 7 horas restantes
son previamente predefinidas por Ud.
c) Para esta nueva definición de turnos, plantee un modelo de optimización lineal entero que permita
encontrar la cantidad mı́nima de turnos y la distribución de empleados por turno que satisfaga la
restricción de demanda. Suponga que las 8 horas predefinidas para el turno i son t1i, . . . t8i (note
que ti1 = i y que tij > i si j > 1).
Note que el valor óptimo de la parte anterior depende de cómo estén predefinidos los turnos, es decir
de los valores que Ud. elija para los escalares tij .
d) Formule un modelo lineal entero que le permita encontrar los valores de tij , i ∈ {1, . . . , 9}, j ∈
{1, . . . , 8} que minimicen la cantidad de turnos usados.
Suponga para las partes que siguen que ya encontró los valores tij óptimos. Considere que existe un
costo CD1i asociado a dejar demanda insatisfecha en la hora i ∈ {1, . . . , 16} y además se paga un costo
de CD2i por cada pedido insatisfecho. Además, por reglamentaciones del Ministerio del Trabajo, si el
turno i tiene asignado al menos un trabajador y menos de γ trabajadores se debe pagar un costo fijo
de Kγ , y si tiene asignado un número mayor o igual a más de γ se debe pagar por trabajador un costo
de Rγ .
e) Formule un modelo de programación lineal entera que permita encontrar el costo mı́nimo a pagar
por la demanda insatisfecha y la distribución de empleados por turno que satisfaga la restricción
de demanda.
f ) Formule un modelo de programación lineal entera que permita minimizar el costo asociado a
asignar trabajadores a turnos insatisfecha y encontrar la distribución de empleados por turno que
satisfaga la restricción de demanda.
3