PROBLEMAS DE PROGRAMACIN LINEAL
PROBLEMA 5 La compaa de transportes "La perola negra" se ha diversificado introducindose en el sector de la alimentacin, produciendo alimentos mezclados de forma especial. Actualmente ha recibido un pedido de 200 kilogramos como mnimo de una mezcla constituida por dos ingredientes A y B. El primer ingrediente A, le cuesta a la compaa 300 u.m. (unidades monetarias) el kilogramo; el segundo ingrediente le cuesta 800 u.m./kg. La mezcla no puede contener ms del 40% del ingrediente A y debe tener al menos 30% de B. En estas condiciones calcular: a) Cantidad a utilizar de cada ingrediente en las mezcla para minimizar los costes. b) Dentro de qu intervalo podra variar el coste unitario del ingrediente A sin que cambie por ello la solucin ptima? c) Saldra rentable para el proceso de produccin aadir a la mezcla un ingrediente C sabiendo que el coste de ste es de 500 u.m./kg? Raznese. d) Qu pasara si Sanidad impusiese que la cantidad mxima de antioxidante E-XX presente en cada kilogramo de mezcla (por haberse descubierto recientemente que tiene propiedades alucingenas) fuese como mximo de 6 gramos, sabiendo que cada kilogramo de ingrediente A contiene 10 gramos de E-XX y cada kilogramo de B contiene 3 gramos?
SOLUCIN a) Llamando X1: kg. de ingrediente A en la mezcla. X2: kg. de ingrediente B en la mezcla. La funcin de produccin sera: Min S.a. X1 X1 + X2 X2 200 04 (X1+ X2) 03 (X1+ X2) Z = 300X1 + 800X2
X1, X2 0 Sin embargo, dado que se trata de un problema de minimizacin, el mtodo de resolucin buscar que la cantidad de ingredientes fabricada sea lo ms pequea posible, lo justo para que se cumpla la primera restriccin. Por esta razn se puede considerar que la suma de los ingredientes en el ptimo ser de 200 Kg, por lo que el problema se puede expresar de la siguiente manera:
Javier Osorio 1
PROBLEMAS DE PROGRAMACIN LINEAL
Min S.a.
Z = 300X1 + 800X2
X1 + X 2 X1 X2
X1 , X 2 0
200 0,4 200 0,3 200
Que introduciendo variables de holgura quedara: Min S.a. X1 + X 2 X 3 + X4 X1 X2 Xj 0 ( j = 1, ... 5) Vemos que no tenemos base inicial fcilmente identificable, por lo que recurriremos a la utilizacin de variables artificiales y al mtodo de dos fases. 1 Fase: Min S.a. X1 + X 2 X 3 X1 + X4 X2 X5 + X6 + X7 = 200 = 80 = 60 X0 = X6 + X7 X5 = 200 = 80 = 60 Z = 300X1 + 800X2
Xj 0 ( j = 1, ... 7) X6, X7: variables artificiales
Calculamos ahora los valores de la fila cero y de la columna de lado derecho para la primera tabla Simplex.
X 6 200 X B = X 4 = 80 X 60 7 1 1 1 0 0 1 A = 1 0 0 1 0 0 0 1 0 0 1 0
2
0 0 1
Javier Osorio
PROBLEMAS DE PROGRAMACIN LINEAL
X1 X 2 X N = = 0 X3 X5
B = [ a6 , a4 , a7 ]
1 Z1 C1 = C B B 1 a1 C1 = ( 1, 0, 1) 1 0 = 1 0 1 Z 2 C2 = ( 1, 0, 1) 0 0 = 2 1 1 Z 3 C3 = ( 1, 0, 1) 0 0 = 1 0 0 Z5 C5 = ( 1, 0, 1) 0 0 = 1 1 200 Z = C B B 1 b = ( 1, 0, 1) 80 = 260 60 La primera tabla Simplex quedara:
X1 1 1 1 0 X2 2 1 0 1 X3 -1 -1 0 0 X4 0 0 1 0 X5 -1 0 0 -1 X6 0 1 0 0 X7 0 0 0 1 LD 260 200 80 60
X0 X6 X4 X7
Aplicando el algoritmo Simplex:
Z k Ck = 2 ; k = 2 ; X 2 candidato a entrar en la base.
bn = yrk
Min y
1 i m
bi
: yik > 0 = ik
Min {200,60} = 60
Javier Osorio
PROBLEMAS DE PROGRAMACIN LINEAL
X 7 sale de la base; y32 es el pivote. Iterando sucesivamente se obtienen las siguientes tablas:
X0 X6 X4 X2
X1 1 1 1 0
X2 0 0 0 1
X3 -1 -1 0 0
X4 0 0 1 0
X5 1 1 0 -1
X6 0 1 0 0
X7 -2 -1 0 1
LD 140 140 80 60
X0 X6 X1 X2
X1 0 0 1 0
X2 0 0 0 1
X3 -1 -1 0 0
X4 -1 -1 1 0
X5 1 1 0 -1
X6 0 1 0 0
X7 -2 -1 0 1
LD 60 60 80 60
X0 X5 X1 X2
X1 0 0 1 0
X2 0 0 0 1
X3 0 -1 0 -1
X4 0 -1 1 -1
X5 0 1 0 0
X6 -1 1 0 1
X7 -1 -1 0 0
LD 0 60 80 120
Solucin ptima. Se han eliminado las variables artificiales, pasamos a resolver la 2 fase: Min Z= 300X1 + 800X2 (las restricciones permanecen constantes)
1 1 Z3 - C3 = C B B a 3 c3 = ( 0, 300, 800) 0 = 800 1 1 Z4 - C4 = ( 0, 300, 800 ) 1 = -500 1 60 Z = C B B 1 b = ( 0, 300, 800) 80 = 120.000 120 La solucin es ptima de entrada y no hace falta recurrir a la 2 fase:
X1= 80 kg de A X2 = 120 kg de B Z = 120.000 u.m. de coste
Javier Osorio
PROBLEMAS DE PROGRAMACIN LINEAL
La tabla ptima sera:
X1 0 0 1 0 X2 0 0 0 1 X3 -800 -1 0 -1 X4 -500 -1 1 -1 X5 0 1 0 0 LD 120.000 60 80 120
Z X5 X1 X2
b) Intervalo de variacin del coste de A. Se ha de cumplir que: (Z3 - C3) = C B B 1 a 3 C3 0
1 (0, (300+1 ),800 ) 0 0 0; 1 no restringido inferiormente 1
Inferiormente se puede decrementar 1 hasta -, lo cual es fsicamente imposible, pero s puede disminuir el nuevo coste hasta cero, siendo ptima la solucin con C1=0 (Z4 - C4) = C B B 1 a 4 C4 0
1 0, ( 300 + 1 ) , 800 1 0 0 1
300 + 1 - 800 0
1 500
Para 0 C1 300 + 500 la solucin sigue siendo ptima. c) Sale rentable aadir un ingrediente C ? El nuevo problema sera: Min Z= 300X1 + 800X2 + 500X8 S.a.
Javier Osorio
PROBLEMAS DE PROGRAMACIN LINEAL
X 1 + X 2 + X 8 200 80 X1 60 X2
X1, X2, X8 0
X8 : kg. de ingrediente C en la mezcla. Se trata nicamente de estudiar el valor: Z8 - C8 = C B B 1 a8 c8 Siendo: C B = ( 0, 300, 800)
y6
1
y4
y7
1 1 1 De la ltima tabla de la 1 fase. B = 0 1 0 1 1 0
1 1 1 1 1 1 1 a 8 = 0 ; y8 = B a 8 = 0 1 0 0 = 0 1 1 0 0 1 0 1 1 1 1 Z8 - C8 = [ 0, 300, 800] 0 1 0 0 500 = 300 > 0; S es rentable. 1 1 0 0 Incorporamos esta variable a la tabla ptima anterior y calculamos la nueva solucin del problema. La nueva tabla sera:
X1 0 0 1 0 X2 0 0 0 1 X3 -800 -1 0 -1 X4 -500 -1 1 -1 X5 0 1 0 0 X8 300 1 0 1 LD 120.000 60 80 120
Z X5 X1 X2
Iterando aplicando el algoritmo Simplex:
X1 0 0 1 0 X2 0 0 0 1 X3 -500 -1 0 0 X4 -200 -1 1 0
6
Z X8 X1 X2
X5 -300 1 0 -1
X8 0 1 0 0
LD 102.000 60 80 60
Javier Osorio
PROBLEMAS DE PROGRAMACIN LINEAL
X1 = 80 kg. de A X2 = 60 kg. de B X8 = 60 kg. de C Z = 102.000 u.m.
Esta solucin es mejor, en cuanto que se disminuyen los costes.
d) Limitacin de antioxidante presente. Se trata de aadir otra restriccin y comprobar si sta es vinculante o no. 10 X1 + 3X2 6200 Con
X 1 = 80 1080 + 3120 6200 X 2 = 120
1160 1200
Se cumple la desigualdad, luego nuestro proceso est dentro de la ley y no es necesario cambiar la composicin de la mezcla.
Javier Osorio