ayudantia 4 2003 (1)

Vista previa del material en texto

Métodos de Optimización 
Ayudantía 
 
1.- Problema General de la Producción. (Inventario y Multidimensional) 
 
 Supongamos que se quiere diseñar un plan de producción y de manejo de 
inventario para los próximos T períodos, esto es, determinar la cantidad que se ha de 
producir y la cantidad que se deja en inventario de cada uno de los n posibles productos 
en cada período. Para ello se cuenta con m recursos productivos. La cantidad máxima 
disponible del recurso i en el período t es bit , i = 1,…, m ; t = 1,…, T y la cantidad de 
recurso i que requiere una unidad del producto j para ser fabricado es aij .La demanda 
estimada del producto j en el período t es djt . El inventario del producto j al inicio del 
primer período es Ij0 . El plan debe minimizar los costos de producción y de mantención 
de inventario. El costo unitario de producción del producto j en el período t es cjt y el 
costo unitario de mantención de inventario del producto j en el período t es kjt. 
 
 El plan debe ser tal que no se exceda la cantidad disponible de recursos y que se 
satisfaga la demanda. 
 
Solución: 
 
Variables de decisión: 
 
 El modelo debe ayudar a responder las siguientes preguntas: ¿qué cantidad 
producir de cada producto en cada período? ¿Qué cantidad de producto dejar en 
inventario al final de cada período? Para responder estas preguntas se definen las 
siguientes variables: 
 
xjt = cantidad que se ha de producir del producto j en el período t, j = 1,…,n ; t = 1,…,T 
Ijt = cantidad de inventario del producto j al final del período t, j = 1,…,n ; t = 1,…,T 
 
Restricciones 
 a) Disponibilidad de recursos: 
 bxa itjt
n
j
ij
≤∑
=
*
1
 i = 1,…,m ; t = 1,…,T 
 b) Satisfacción de demanda y Balance de inventario: 
 
 dIxI jtjtjttj =−+−1, j=1,...,n ; t = 1,…,T 
 
 c) No Negatividad de las variables 
 
 0, ≥Ix jtjt j=1,...,n ; t = 1,…,T 
 
Función Objetivo 
 
El costo total es z = costo total de producción + costo total de mantención de inventario 
 
 Min z = ∑ ∑ ∑
= = =
+
T
t
n
j
n
j
jtjtjtjt Ikxc
1 1 1
)**( 
 
2.- Problema del Banquetero 
 
 Un banquetero debe preparar una recepción cada noche de los próximos T días. 
Para ello requiere de rt manteles limpios para cada cena del día t, con t =1,…,T. Para 
proveerse de manteles limpios, puede mandar a lavar manteles sucios, como también 
comprar manteles nuevos, si fuese necesario, disponibles en cantidad ilimitada en el 
mercado. La lavandería tiene dos servicios de lavado: uno rápido, con un costo de c1 
pesos por mantel y uno lento, con un costo de c2 pesos por mantel, con c2<c1. Los 
manteles enviados al servicio rápido están disponibles para la noche siguiente en que 
fueron utilizados, mientras que aquellos enviados al servicio lento, solamente están 
disponibles para la noche subsiguiente. Por otro lado, el precio de compra de un mantel 
nuevo es de c0 pesos, con c0>c1, (pues de los contrario la solución óptima sería 
simplemente utilizar manteles nuevos para cada banquete). Inicialmente, el banquetero 
dispone de un stock de S0 manteles. 
 Establezca un modelo de programación lineal que permita al banquetero 
disponer de manteles limpios para los T banquetes con un mínimo costo. 
 
Solución 
 
Variables de decisión 
Ct : Cantidad de manteles que se comprar para el banquete del día t 
Rt : Cantidad de manteles que se mandar a lavar por servicio rápido el día t 
Lt : Cantidad de manteles que se mandar a lavar por servicio lento el día t 
St : Cantidad de manteles limpios disponibles para el banquete del día t 
 
La función objetivo será minimizar los costos de comprar manteles más los costos de 
mandar a lacar manteles. El banquetero puede incurrir en costos por compra de manteles 
en cada uno de los días del período. Por otro lado, no tiene sentido que el banquetero 
incurra en costos de lavado rápido en el último día del periodo, como tampoco de 
lavado lento en el penúltimo y último día del período, puesto que no necesita manteles 
limpios para los días posteriores al día T. Considerando esto, la función objetivo será: 
 
Min ∑ ∑ ∑
=
−
=
−
=
++
T
t
T
t
T
t
ttt LcRcCc
1
1
1
2
1
210 *** 
 
El primer día el banquetero dispondrá de un stock inicial de S0 manteles limpios, más 
los que puede comprar ese día, de modo que la cantidad total de manteles disponibles 
permita satisfacer la demanda de ese día. 
 
 S1 = S0 +C1 � r1 
 
El segundo día el banquetero dispone de los manteles limpios que puedan sobrar de la 
noche anterior, más los que compra ese mismo día, más los que mandó a lavar al 
servicio rápido el primer día, los que tienen que cubrir la demanda del segundo día. 
 
S2 = S1-r1+C2+R1 � r2 
 
El tercer día el banquetero dispone de los manteles limpios que puedan sobrar de la 
noche anterior, más los que compra ese mismo día, más los que mandó a lavar al 
servicio rápido el primer día, más los que mandó a lavar al servicio lento el primer día, 
los que deben cubrir la demanda del tercer día. 
 
S3 = S2 – r2 + C3 + R2 + L1 � r3 
 
Generalizando para cualquier t tenemos: 
 
St = St-1 – rt-1 + Ct +Rt-1 + Lt-2 � rt t=3,…,T 
 
Ahora, si se elimina la variable de la cantidad de manteles disponibles al inicio de cada 
banquete, la restricción general puede ser expresada como: 
 
∑∑∑∑
−
=
−−
==
≥++−+
2
1
1
1
1
11
t
i
ti
t
i
t
i
i
t
i
i rLRrCS t=3,…,T 
 
Resumiendo, el modelo resultante es: 
 
 Min ∑ ∑ ∑
=
−
=
−
=
++
T
t
T
t
T
t
ttt LcRcCc
1
1
1
2
1
210 *** 
s.a. 
S0 +C1 � r1 
S0 +C1+ C2+R1 –r1 � r2 
∑∑∑∑
−
=
−−
==
≥++−+
2
1
1
1
1
11
t
i
ti
t
i
t
i
i
t
i
i rLRrCS t=3,…,T 
Ct,Rt,Lt � 0 t=1,…,T 
 
 
 
3.- Plan de producción y distribución 
 
Una Empresa que fabrica una línea de N productos químicos, desea establecer un plan 
de producción y de distribución para las próximas T semanas. 
 
La empresa posee K plantas productoras y cada una de ellas es capaz de fabricar todos 
los productos de la línea. Una vez que los productos son fabricados, todos ellos se llevan a las 
bodegas de la planta y allí se mantienen hasta que son despachados a J laboratorios (centros 
de consumos). Para el transporte desde las bodegas hasta los laboratorios se pueden elegir 
entre dos medios de transporte que difieren por la rapidez y el costo. El envío por medio del 
ferrocarril demora 1 semana y por buque, 2 semanas. 
 
Se dispone de la siguiente información : 
 Kk : capacidad semanal de la planta k para producir cualquier producto (lt). 
 Ik : costo de mantener una unidad (lt) de producto en inventario en la bodega de 
la planta k ( $ / (lt x semana)). 
 bn : costo unitario de fabricación del producto n ($/lt). 
 dnj : requerimiento semanal de producto n en el laboratorio j (lt). 
 Hk : capacidad de la bodega k (lt). 
 Ckj1 : costo unitario de transporte desde la bodega k al laboratorio j, si se utiliza 
ferrocarril ($/lt). 
Ckj2 : costo unitario de transporte desde la bodega k al laboratorio j, si se utiliza 
buque ($/lt). 
 
Formule un modelo de programación lineal que apoye la determinación de un plan de 
producción y distribución de mínimo costo total que satisfaga los requerimientos del 
problema. Asuma que los inventarios iniciales son conocidos y que los costos de transporte 
entre las plantas y sus respectivas bodegas es despreciable. 
 
Variables del Modelo. 
 
Xnkt : Cantidad de producto n (lt) producida en la planta k en la semana t ; n = 1,…, 
N; k = 1, …, K; t = 1, …, T. 
Ynkt : Nivel de inventario de producto n (lt) almacenado en la planta k , en la 
semana t; n = 1,…, N; k = 1, …, K; t = 1, …, T. 
Znkjt : Cantidad de producto n (lt) que se envía por ferrocarril desde la planta k 
hasta el laboratorio j, en la semana t ; n = 1,…, N; k = 1, …, K; t = 1, …, T. 
Wnkjt : Cantidad de producto n (lt) que se envía por barco desde la planta k hacia el 
laboratorio j en la semana t; n = 1,…, N; k = 1, …, K; t = 1, …, T.Nota . Suponga que lo que se envía por ferrocarril en la semana t llega dentro 
de 
la misma semana t, mientras que lo que se envía por barco, llega en la semana t+1. 
 
 
 
 
 
 
Costo de Producción: 
 N K T 
 �bn ( � � Xnkt ) 
 n=1 k=1 t=1 
 
Costo de Almacenamiento : 
 K N T 
 �Ik ( � � Ynkt ) 
 k=1 n=1 t=1 
 
Costo de Transporte por Ferrocarril : 
 K J N T 
 � �Ckj1 ( � � Znkjt ) 
 k=1 j=1 n=1 t=1 
 
Costo de Transporte por Barco : 
 K J N T-1 
 � �Ckj2 ( � � Wnkjt ) 
 k=1 j=1 n=1 t=1 
 
Restricciones de Inventario en cada Planta k : 
 J 
Xnkt + Ynk(t-1) - � (Znkt + Wnkjt) = Ynkt , n = 1,…,N ; k = 1, …, K ; t = 1, …, T-1; 
 j=1 
 
J 
XnkT + Ynk(T-1) - � (ZnktT) = YnkT , n = 1,…,N ; k = 1, …, K ; 
 j=1 
 
donde se asume conocidos los inventarios iniciales Ynk0 ; n = 1,…,N ; k = 1, …, K 
 
Restricciones de Demanda: 
 
 K 
 � (Znkjt + Wnkj(t-1)) = dnj , n = 1,…,N ; k = 1, …, K ; t = 1, …, T; 
 k =1 
 
Restricciones de Capacidad de Producción : 
 
 N 
� Xnkt � Kk k = 1, …, K 
n=1 
 
Restricciones de Capacidad de Almacenamiento : 
 
 N 
� Ynkt � Hk k = 1, …, K 
n=1 
 
Restricciones de Signo : 
Xnkt � 0 n = 1,…,N ; k = 1, …, K ; t = 1, …, T 
Ynkt � 0 n = 1,…,N ; k = 1, …, K ; t = 1, …, T 
Znktj � 0 n = 1,…,N ; k = 1, …, K ; t = 1, …, T 
Wnkjt � 0 n = 1,…,N ; k = 1, …, K ; t = 1, …, T-1 
Modelo: 
 N K T K N T K J N T K J N T-1 
Min � � � bn Xnkt + � � � Ik Ynkt + � � � �Ckj1 Znkjt + � � � �Ckj2 Wnkjt 
 n=1 k=1 t=1 k=1 n=1 t=1 k=1 j=1 n=1 t=1 k=1 j=1 t=1 t=1 
 
 
Sujeto a 
 J 
 Xnkt + Ynk(t-1) - � (Znkjt + Wnkjt) = Ynkt 
 j=1 
 
 n = 1,…,N ; k = 1, …, K ; t = 1, …, T-1 
 
 J 
 XnkT + Ynk(T-1) - � (ZnkjT + WnkjT) = YnkT 
 j=1 
 
 n = 1,…,N ; k = 1, …, K 
 
 K 
 � (Znkjt + Wnkj(t-1)) = dnj 
 k=1 
 
 n = 1,…,N ; j = 1, …, J ; t = 1, …, T 
 
 
 N 
� Xnkt � Kk k = 1, …, K 
n=1 
 
 N 
� Ynkt � Hk k = 1, …, K 
n=1 
 
 
 
Xnkt � 0 n = 1,…,N ; k = 1, …, K ; t = 1, …, T 
Ynkt � 0 n = 1,…,N ; k = 1, …, K ; t = 1, …, T 
Znktj � 0 n = 1,…,N ; k = 1, …, K ; t = 1, …, T 
Wnkjt � 0 n = 1,…,N ; k = 1, …, K ; t = 1, …, T-1