p r og r a m a c i n li n e a l
La programacin lineal da respuesta a situaciones en las que se exige maximizar o minimizar funciones que se encuentran sujetas a determinadas limitaciones, que llamaremos restricciones. Su empleo es frecuente en aplicaciones de la industria, la economa, la estrategia militar, etc. Funcin objetivo En esencia la programacin lineal consiste en optimizar (maximizar o minimizar) una funcin objetivo , que es una funcin lineal de varias variables: f(x,y) = ax + by. Restricciones La funcin objetivo est sujeta a una serie de restricciones, expresadas por inecuaciones lineales:
a1x + b1y c1 a2x + b2y c2 ... ... ... anx + bny cn
Cada desigualdad del sistema de restricciones determina un semiplano.
Solucin factible El conjunto interseccin, de todos los semiplanos formados por las restricciones, determina un recinto, acotado o no, que recibe el nombre de regin de validez o zona de soluciones factibles .
Solucin ptima El conjunto de los vrtices del recinto se denomina conjunto de soluciones factibles bsicas y el vrtice donde se presenta la solucin ptima se llama solucin mxima (o mnima segn el caso).
Valor del programa lineal El valor que toma la funcin objetivo en el vrtice de solucin ptima se llama valor del programa lineal.
P a s o s p a r a r e s o l v e r u n p r ob l e ma d e p r og r a ma c i n l i n e a l
1. Elegir las incgnitas. 2. Escribir la funcin objetivo en funcin de los datos del problema. 3. Escribir las restricciones en forma de sistema de inecuaciones. 4. Averiguar el conjunto de soluciones factibles representando
restricciones. 5. Calcular las coordenadas de los vrtices del recinto pocos). 6. Calcular el valor de la funcin objetivo en cada uno de ellos presenta el valor mximo o mnimo segn nos pida cuenta aqu la posible no existencia de solucin si el recinto no
grficamente
las
de soluciones factibles (si son de los vrtices para ver en cul el problema (hay que tener en est acotado).
E j e m p l o s d e p r og r a m a c i n l in ea l
Unos grandes almacenes encargan a un fabricante pantalones y chaquetas deportivas. El fabricante dispone para la confeccin de 750 m de tejido de algodn y 1000 m de tejido de polister. Cada pantaln precisa 1 m de algodn y 2 m de polister. Para cada chaqueta se necesitan 1.5 m de algodn y 1 m de polister. El precio del pantaln se fija en 50 y el de la chaqueta en 40 . Qu nmero de pantalones y chaquetas debe suministrar el fabricante a los almacenes para que stos consigan una venta mxima? 1Eleccin de las incgnitas. x = nmero de pantalones y = nmero de chaquetas 2Funcin objetivo f(x,y)= 50x + 40y 3Restricciones Para escribir las restricciones vamos a ayudarnos de una tabla:
pantalones chaquetas disponible algodn polister 1 2 1,5 1 750 1000
tendremos dos
x + 1.5y 750 2x+3y1500 2x + y 1000 Como el nmero de pantalones y chaquetas son nmeros naturales, restricciones ms: x 0 y 0 4 Hallar el conjunto de soluciones factibles Tenemos que representar grficamente las restricciones. Al ser x 0 e y 0, trabajaremos en el primer cuadrante. Representamos las rectas, a partir de sus puntos de corte con los ejes.
Resolvemos grficamente la inecuacin: 2x +3y 1500, para ello tomamos un punto del plano, por ejemplo e l (0,0). 20 + 30 1 500 Como 0 1 500 entonces el punto (0,0) se encuentra en el semiplano donde se cumple la desigualdad. De modo anlogo resolvemos 2x + y 1000. 20 + 0 1 000 La zona de interseccin de las soluciones de las inecuaciones sera la solucin al sistema de inecuaciones, que constituye el conjunto de las soluciones factibles.
5 Calcular las coordenadas de los vrtices del recinto de las soluciones factibles.
La solucin ptima, si es nica, se encuentra en un vrtice del recinto. Es tas son las soluciones a los sistemas: 2x + 3y = 1500; x = 0 (0, 500) 2x + y = 1000; y = 0 (500, 0) 2x + 3y =1500; 2x + y = 1000 (375, 250)
6 Calcular el valor de la funcin objetivo En la funcin objetivo sustituimos cada uno de los vrtices. f(x, y) = 50x + 40y f(0, 500) = 500 + 40500 = 20000 f(500, 0) = 50500 + 400 = 25000 f(375, 250) = 50375 + 40250 = 28750 Mximo La solucin ptima es fabricar 375 pantalones y 250 chaquetas para obtener un beneficio de 28750 . La solucin no siempre es nica, tambin podemos encontrarnos con una solucin mltiple. Ejemplo Si la funcin objetivo del ejercicio anterior hubiese sido: f(x,y)= 20x + 30y f(0,500) = 200 + 30500 = 15000 Mximo f(500, 0) = 20500 + 300 = 10000 f(375, 250) = 20375 + 30250 = 15000 Mximo En este caso todos los pares, con soluciones enteras, del segmento trazado en negro seran mximos.
f(300, 300)= 20300 + 30300 = 15000 Mximo
empresa de transportes tiene dos tipos de camiones, los del tipo A con un espacio refrigerado de 20 m3 y un espacio no refrigerado de 40 m 3. Los del tipo B, con igual cubicaje total, al 50% de refrigerado y no refrigerado. La contratan para el transporte de 3 000 m 3 de producto que necesita refrigeracin y 4 000 m 3 de otro que no la necesita. El coste por kilmetro de un camin del tipo A es de 30 y el B de 40 . Cuntos camiones de cada tipo ha de utilizar para que el coste total sea mnimo?
1Una
P r o b l e m a s d e p r o g r a ma c i n l in e a l
1Eleccin de las incgnitas.
x = camiones de tipo A y = camiones de tipo B 2Funcin objetivo f(x,y) = 30x + 40y 3Restricciones A Refrigerado No refrigerado 40 B 20 30 Total 30 3 000 4 000
20x + 30y 3 000 40x + 30y 4 000 x 0 y 0 4 Hallar el conjunto de soluciones factibles
5 Calcular las coordenadas de los vrtices del recinto de las soluciones factibles.
6 Calcular el valor de la funcin objetivo
f(0, 400/3) = 30 0 + 40 400/3 = 5 333.332 f(150, 0) = 30 150 + 40 0 = 4 500 Como x e y han de ser nmeros naturales redondeamos el valor de y. f(50, 67) = 30 50 + 40 67 = 4180 Mnimo El coste mnimo son 4 180 para A = 50 yz B = 67.
2Una escuela prepara una excursin autobuses de 40 plazas y 10 de 50 plazas, autocar grande cuesta 800 y el de uno tipo hay que utilizar para que la excursin
1Eleccin de las incgnitas.
x = autobuses pequeos y = autobuses grandes 2Funcin objetivo f(x, y) = 600x + 800y 3Restricciones 40x + 50y 400 x + y 9
para 400 alumnos. La empresa de transporte tiene 8 pero slo dispone de 9 conductores. El alquiler de un pequeo 600 . Calcular cuntos autobuses de cada resulte lo ms econmica posible para la escuela.
x 0 y 0 4 Hallar el conjunto de soluciones factibles
5 Calcular las coordenadas de los vrtices del recinto de las soluciones factibles.
6 Calcular el valor de la funcin objetivo
f(0, 8) = 600 0 + 800 8 = 6 400 f(0, 9) = 600 0 + 800 9 = 7 200 f(5, 4) = 6 00 5 + 800 4 = 6 200 Mnimo El coste mnimo es de 6 200 , y se consigue 4 autobuses grandes y 5 pequeos .
L o s d a t o s e s t n c a m b i a d o s s o l o en l a p r eg u n ta 1 , en l a 3 y 4 en v ez d e e u r o s s on s o l e s E j e r c i c i o s r e su e lt o s d e p r og r a m a c i n l in e a l 1
Una compaa fabrica y venden dos modelos de lmpara L 1 y L2. Para su fabricacin se necesita un trabajo manual de 20 minutos para el modelo L 1 y de 50 minutos para el L 2; y un trabajo de mquina de 40 min para L1 y de 10 minutos para L 2. Se dispone para el trabajo manual de 100 horas al mes y para la mquina 80 horas al mes. Sabiendo que el benefici o por unidad es de 15 y 10 soles para L1 y L2, respectivamente, planificar la produccin para obtener el mximo beneficio.
E j e r c i c i o s r e su e lt o s d e p r og r a m a c i n l in e a l 3
En una granja de pollos se da una dieta, para engordar, con una composicin mnima de 15 unidades de una sustancia A y otras 15 de una sustancia B. En el mercado slo se encuentra dos clases de compuestos: el tipo X con una composicin de una unidad de A y 5 de B, y el otro tipo, Y, con una composicin de cinco unidades de A y una de B. El precio del tipo X es de 10 soles y del tipo Y es de 30 . Qu cantidades se han de comprar de cada tipo para cubrir las necesidades con un coste mnimo?
E j e r c i c i o s r e su e lt o s d e p r og r a m a c i n l in e a l 4
Se dispone de 600 g de un determinado frmaco para elaborar pastillas grandes y pequeas. Las grandes pesan 40 g y las pequeas 30 g. Se necesitan al menos tres pastillas grandes, y al menos el doble de pequeas que de las grandes. Cada pastilla grande proporciona un bene ficio de 2 s/. y la pequea de 1 s/ . Cuntas pastillas se han de elaborar de cada clase para que el beneficio sea mximo?
E j e r c i c i o s r e su e lt o s d e p r og r a m a c i n l in e a l 1
Una compaa fabrica y venden dos modelos de lmpara L 1 y L2. Para su fabricacin se necesita un trabajo manual de 20 minutos para el modelo L1 y de 30 minutos para el L 2; y un trabajo de mquina para L 1 y de 10 minutos para L 2. Se dispone para el trabajo manual de 100 horas al mes y para la mquina 80 horas al mes. Sabiendo que el beneficio por unidad es de 15 y 10 euros para L1 y L2, respectivamente, planificar la produccin para obtener el mximo beneficio.
1Eleccin de las incgnitas.
x = n de lmparas L1 y = n de lmparas L 2 2Funcin objetivo f(x, y) = 15x + 10y 3Restricciones Pasamos los tiempos a horas 20 min = 1/3 h 30 min = 1/2 h 10 min = 1/6 h Para escribir las restricciones vamos a ayudarnos de una tabla: L1 L2 Tiempo Manual 1/3 1/2 100 Mquina 1/3 1/6 80 1/3x + 1/2y 100 1/3x + 1/6y 80 Como el nmero de lmparas son nmeros naturales, tendremos dos restricciones ms: x 0 y 0 4 Hallar el conjunto de soluciones factibles Tenemos que representar grficamente las restricciones. Al ser x 0 e y 0, trabajaremos en el primer cuadrante. Representamos las rectas, a partir de sus puntos de corte con lo s ejes. Resolvemos grficamente la inecuacin: 1/3 x + 1/2 y 100; para ello tomamos un punto del plano, por ejemplo el (0,0). 1/30 + 1/20 100 1/30 + 1/60 80 La zona de interseccin de las soluciones de las inecuaciones sera la solucin al siste ma de inecuaciones, que constituye el conjunto de las soluciones factibles.
5 Calcular las coordenadas de los vrtices del recinto
de las soluciones factibles. La solucin ptima si es nica se encuentra en un vrtice del recinto. stos son las soluciones a los sistemas: 1/3x + 1/2y = 100; x = 0 (0, 200) 1/3x + 1/6y = 80; y = 0(240, 0) 1/3x + 1/2y = 100; 1/3x + 1/6y = 80(210, 60)
6 Calcular el valor de la funcin objetivo
En la funcin objetivo sustituimos cada uno de los vrtices. f(x, y) = 15x + 10y f(0, 200) = 150 + 10200 = 2 000 f(240, 0 ) = 15240 + 100 = 3 600 f(210, 60) = 15210 + 1060 = 3 750 Mximo La solucin ptima es fabricar 210 del modelo L 1 y 60 del modelo L1 para obtener un beneficio de 3 750 .
E j e r c i c i o s r e su e lt o s d e p r og r a m a c i n l in e a l 3
En una granja de pollos se da una dieta, para engordar, con una composicin mnima de 15 unidades de una sustancia A y otras 15 de una sustancia B. En el mercado slo se encuentra dos clases de compuestos: el tipo X con una composicin de una unidad de A y 5 de B, y el otro tipo, Y, con una composicin de cinco unidades de A y una de B. El precio del tipo X es de 10 euros y del tipo Y es de 30 . Qu cantidades se han de comprar de cada tipo para cubrir las necesidades con un coste mnimo? 1Eleccin de las incgnitas. x = X y = Y 2Funcin objetivo f(x,y) = 10x + 30y 3Restricciones X A B Y 1 5 Mnimo 5 15 1 15
x + 5y 15 5x + y 15 x 0 y 0 4 Hallar el conjunto de soluciones factibles
5 Calcular las coordenadas de los vrtices del recinto de las soluciones factibles.
6 Calcular el valor de la funcin objetivo
f(0, 15) = 10 0 + 30 15 = 450 f(15, 0) = 10 15 + 30 0 = 150 f(5/2, 5/2) = 10 5/2 + 30 5/2 = 100 Mnimo El coste mnimo son 100 para X = 5/2 e Y = 5/2.
E j e r c i c i o s r e su e lt o s d e p r og r a m a c i n l in e a l 4
Se dispone de 600 g de un determinado frmaco para elaborar pastillas grandes y pequeas. Las grandes pesan 40 g y las pequeas 30 g. Se necesitan al menos tres pastillas grandes, y al menos el doble de pequeas que de las grandes. Cada pastilla grande pro porciona un beneficio de 2 y la pequea de 1 . Cuntas pastillas se han de elaborar de cada clase para que el beneficio sea mximo? 1Eleccin de las incgnitas. x = Pastillas grandes y = Pastillas pequeas 2Funcin objetivo f(x, y) = 2x + y 3Restricciones 40x + 30y 600 x 3 y 2x x 0 y 0 4 Hallar el conjunto de soluciones factibles
5 Calcular las coordenadas de los vrtices del recinto de las soluciones factibles.
6 Calcular el valor de la funcin objetivo
f(x, y)= 2 f(x, y)= 2 f(x, y)= 2 El mximo pequeas . 3 + 16 = 22 3 + 6 = 12 6 + 12 = 24 Mximo beneficio es de 24 , y se obtiene fabricando 6 pastillas grandes y 12
E j e r c i c i o s r e su e lt o s d e p r og r a m a c i n l in e a l 2
Con el comienzo del curso se va a lanzar unas ofertas de material escolar. Unos almacenes quieren ofrecer 600 cuadernos, 500 carpetas y 400 bolgrafos para la oferta, empaquetndolo de dos formas distintas; en el primer bloque pondr 2 cuadernos, 1 carpeta y 2 bolgrafos; en el segundo, pondrn 3 cuadernos, 1 carpeta y 1 bolgrafo. Los precios de cada paquete sern 6.5 y 7 , respectivamente. Cuntos paquetes le conviene poner de cada tipo para obtener el mximo beneficio? 1Eleccin de las incgnitas. x = P1 y = P2 2Funcin objetivo f(x, y) = 6.5x + 7y 3Restricciones P1 Cuadernos Carpetas Bolgrafos P2 2 1 2 Disponibles 3 600 1 500 1 400
2x + 3y 600 x + y 500 2x + y 400 x 0 y 0 4 Hallar el conjunto de soluciones factibles
5 Calcular las coordenadas de los vrtices del recinto de las soluciones factibles.
6 Calcular el valor de la funcin objetivo
f(x,y)= 6.5 f(x,y)= 6.5 f(x,y)= 6.5 La solucin 200 + 7 0 = 0 + 7 200 = 150 + 7 100 ptima son 150 1300 1 400 = 1 675 Mximo P1 y 100 P2 con la que se obtienen 1 675
E j e r c i c i o s r e su e lt o s d e p r og r a m a c i n l in e a l
Unos grandes almacenes desean liquidar 200 camisas y 100 pantalones de la temporada anterior. Para ello lanzan, dos ofertas, A y B. La oferta A consiste en un lote de una camisa y un pantaln, que se venden a 30 ; la oferta B consiste en un lote de tres c amisas y un pantaln, que se vende a 50 . No se desea ofrecer menos de 20 lotes de la oferta A ni menos de 10 de la B. Cuntos lotes ha de vender de cada tipo para maximizar la ganancia?
1Eleccin de las incgnitas.
x = n de lotes de A y = n de lotes de B 2Funcin objetivo f(x, y) = 30x + 50y 3Restricciones
A C a m i s a1 s
B Mnimo 3 200
Pantalon 1 es 1 100
x x x y + 3y 200 + y 100 20 10 4 Hallar el conjunto de soluciones factibles
5 Calcular las coordenadas de los vrtices del recinto de las soluciones factibles.
6 Calcular el valor de la funcin objetivo
f(x, f(x, f(x, f(x, Con y) = 30 y) = 30 y) = 30 y) = 30 50 lotes 20 90 20 50 de + 50 + 50 + 50 + 50 cada 10 10 60 50 tipo = 1100 = 3200 = 3600 = 4000 Mximo se obtiene una ganancia mxima de 4000 .