Grado en Administración de Empresas
Departamento de Estadı́stica
Asignatura: Optimización y Simulación para la Empresa
Curso: 2011/2012
PRÁCTICA 4: Optimización Entera (2)
1. Localización de plantas y planificación logı́stica
Una de las grandes aplicaciones de la Optimización Entera son los modelos de lo-
calización de centros de servicio y transporte de productos. Se trata de modelos en los
que una compañı́a fabrica un cierto producto en sus plantas y después lo envı́a a los
clientes. Además del coste de transporte, existe un coste fijo adicional por cada planta que
está abierta. En esta práctica veremos un ejemplo de un problema de localización de
plantas con costes fijos y capacidades.
La empresa Mate produce salsa de tomate en cinco plantas diferentes P1,. . . ,P5. La
capacidad de producción anual de cada planta (en toneladas) se da en la Tabla 1. El coste
(en euros) de producir una tonelada de salsa de tomate y enviarlo a cada uno de sus cuatro
clientes (C1,. . . ,C4) aparece en la Tabla 2. Cada cliente tiene una demanda (en toneladas)
dada en la Tabla 3. Además, cada planta operativa (es decir, envı́a alguna cantidad de salsa
de tomate) incurre en un coste fijo anual (en euros) dado en la Tabla 1.
El objetivo de la empresa es minimizar el coste anual de satisfacer las demandas:
necesita determinar qué plantas mantener abiertas ası́ como el plan óptimo de envı́os.
P1 P2 P3 P4 P5
Capacidad 300 200 300 200 400
Coste fijo 35000 45000 40000 42000 40000
Tabla 1: Capacidades y costes operativos de las plantas.
Para resolver este problema, necesitamos conocer: 1) los envı́os de las plantas a los
clientes y 2) qué plantas están operativas (abiertas). En consecuencia, si I = {1, 2, 3, 4} es
el conjunto de clientes y J = {1, 2, 3, 4, 5} es el conjunto de plantas, definimos las siguientes
variables:
xij =“toneladas de salsa de tomate enviadas al cliente i que han sido producidas en
la planta j;
1
Hasta
C1 C2 C3 C4
P1 1180 1160 1190 1200
P2 810 800 850 760
Desde P3 850 830 890 840
P4 770 750 810 780
P5 800 770 820 830
Tabla 2: Costes de producción y transporte.
C1 C2 C3 C4
200 300 200 250
Tabla 3: Demandas de los clientes.
(
1, si la planta j está operativa,
yj =
0, en caso contrario,
i ∈ I, j ∈ J.
Si llamamos cij al coste de enviar al cliente i una tonelada de salsa producida en la
planta j, entonces el coste de producción y envı́o será
4 X
X 5
CP E = cij xij .
i=1 j=1
Por otra parte, si fj es el coste fijo de mantenimiento anual de la planta j cuando ésta
está operativa, el coste fijo total es
5
X
CF = fj y j .
j=1
En consecuencia, el coste total que debemos minimizar es
4 X
X 5 5
X
CT = CP E + CF = cij xij + fj y j .
i=1 j=1 j=1
Ahora debemos modelizar las distintas condiciones del problema.
En primer lugar, cada cliente debe recibir tantas toneladas como demanda:
5
X
xij = di , i ∈ I,
j=1
con d = (200, 300, 200, 250).
2
Por otra parte, ninguna planta puede producir más de su capacidad y solo puede
producir salsa de tomate si está abierta:
4
X
xij ≤ Mj yj , j ∈ J,
i=1
con M = (300, 200, 300, 200, 400).
En consecuencia, el modelo que representa el problema de esta empresa es el siguiente:
4 X 5 5
X X
Min. cij xij + fj y j
i=1 j=1 j=1
X5
s.a xij = di , i ∈ I,
j=1
X4
xij ≤ Mj yj , j ∈ J,
i=1
xij ≥ 0, i ∈ I, j ∈ J,
yj ∈ {0, 1}, j ∈ J.
El modelo puede resolverse fácilmente con Solver. En la imagen podemos ver una
solución óptima. Ten en cuenta que, siendo un problema entero, conviene dar un valor de
0 % a la tolerance en el menú Opciones. De lo contrario, existe el riesgo de que Solver
se detenga en una solución subóptima. Compruébalo resolviendo el problema con el valor
por defecto de una tolerancia del 5 %.
3
2. Ejercicios
1. Contesta las siguientes preguntas sobre el ejemplo:
a) ¿Qué plantas no se utilizan?
b) ¿Están todas las plantas abiertas trabajando a su máxima capacidad?
c) ¿Hay algún cliente que reciba toda su demanda desde una única planta?
d ) ¿Cómo impondrı́as que el cliente 2 debe recibir al menos la mitad de la demanda
desde la planta 3?
2. Abril 2011 Una cadena de supermercados se plantea abrir hasta cuatro nuevos cen-
tros en cuatro ciudades: C1, C2, C3, y C4. Por razones logı́sticas, la cadena no quiere
albergar más de un supermercado en una misma ciudad. Cada posible centro puede
ser construido con uno de entre tres distintos tamaños: pequeño (P), mediano (M)
y grande (G). A continuación se muestra una tabla que contiene los costes de con-
strucción de cada centro en función de su tamaño y el beneficio neto esperado de
cada centro. Tanto los costes como los beneficios están en millones de euros.
Coste Beneficio
C1 C2 C3 C4 C1 C2 C3 C4
P 13 20 12 20 A 6 7 5 8
M 30 40 24 30 B 10 14 9 11
G 39 45 48 55 C 12 17 19 20
La compañı́a tiene un presupuesto de 100 millones de euros.
a) Formula un problema de programación entera que ayude a la compañı́a a decidir
qué centros construye y de qué tamaño de manera que se maximice el beneficio
medio esperado y resuélvelo con ayuda del Solver.
b) ¿Qué restricción hay que añadir al problema anterior si necesariamente tiene que
haber un hipermercado en la ciudad C2?, ¿cómo cambia la solución?
c) ¿Cómo modeları́as la siguiente restricción? se puede construir un hipermercado
pequeño en las ciudades C1, C2 y C3 solamente si se construye ese tamaño en la
ciudad C4. ¿Cómo cambia la solución?
d) ¿Y esta restricción? En total, no puede haber más de dos tipos de tamaño con-
struidos. ¿Cómo cambia la solución?
