Material Modelamiento

Universidad de Los Andes Facultad de Ingenier´ ıa
Semestre 2009-1
´ Profesor: Carlos Alarcon, Miguel Carrasco ´ Auxiliar: Diego Moran, Andrea Valle

Un poco m´s sobre modelamiento a
Introducci´n a la Optimizaci´n o o Abril 2009

‘‘Multiplicando’’ variables binarias en un problema de programaci´n lineal entera. o
Suponga que tiene 2 variables binarias x e y, Cxy un par´metro constante yque necesita que aparezca en la a funci´n objetivo o en una restricc´n el t´rmino Cxy · xy, que es claramente una expresi´n no lineal (pues es o o e o una multiplicaci´n de variables). o ¿C´mo se puede escribir esta expresi´n de manera lineal? o o F´cil,observando de que el producto xy puede valer 0 o 1 uno se da cuenta de que basta con crear la variable: a 1, si x = y = 1 0, si no

z= Y lasrestricciones:

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. e

‘‘Multiplicando’’ una variable binaria por una entera o real acotada en un problema de programaci´n lineal entera. o
Suponga que tiene una variable binaria x y una variable entera o real acotaday (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 a o o e Cxy · xy, que es claramente una expresi´n no lineal (pues es una multiplicaci´n de variables). o o ¿C´mo se puede escribir esta expresi´n de manera lineal? o o No es tan f´cil, pero tampoco imposible. Defina la variable real positiva: a z = valor que toma elproductox · y Para que la definici´n tenga sentido, basta agregar las siguientes restricciones: o 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. e

C´mo saber si una variable es mayor o menor que otra en un problema deprogramaci´n o o 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, espec´ ıficamente necesita que aparezca en la funci´n objetivo o en alguna restricc´n o o el t´rmino C, s´lo cuando x > y. e o Veamos c´mo hacer esto. Defina las variables: o 1, si x > y 0, si no

z= Y considere las siguientesrestricciones:

x − y ≤ Mz

−M (1 − z) + 0,5 ≤ x − y Estas restricciones hacen que la variable z tenga el siginicado requerido. As´ para agregar la expresi´n que se necesita basta poner el t´rmino lineal C · z. ı, o e

2

Ejercicio propuesto.
P1.- Considere que Ud. es propietario de una empresa de delivery OptiPizza, en la cual est´n a su cargo a
M trabajadores dedicados a repartir el producto.Inicialmente, la reglamentaci´n horaria estipulaba o 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], a i = 1, . . . , 16, y en esta nueva etapa se propone satisfacer al menos unporcentaje 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 a o a continuas. a) Plantee un modelo de optimizaci´n lineal entero que permita encontrar la cantidad m´ o ınima de turnos y la distribuci´n de empleados por turno que satisfaga la restricci´n de demanda. Por turno o o 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 o hora j, y las variables xj , que indican el n´mero de empleados que entran en la hora j. u b) Dados los malos resultados de la pol´ ı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...