Tema3. Programación Lineal PDF

Preview

Summary

Download Tema3. Programación Lineal PDF

Description

PROGRAMACIÓN LINEAL

1. DESI GUALDADES Los números reales no nulos se dividen en dos clases: positivos, que forman el conjunto +, y negativos, que forman el conjunto - . En general, se escribe: a< a> a≤ a≥

b (y se lee a menor que b) si b-a es positivo. b (y se lee a mayor que b) si b-a es negativo. b (y se lee a menor o igual que b) si b-a es positivo o cero. b, si b-a es negativo o cero.

A estas expresiones las llamaremos desigualdades, siendo ab, desigualdades estrictas. Gráficamente, la desigualdad a< b, significa que el punto representativo de a en la recta real, se encuentra a la izquierda del que representa a b . Propiedades de las desigu desigualdades: aldades: 1) Cualquiera que sean a y b , se verifica que a=b, a< b, o a> b.

2) 3) 4) 5) 6) 7) 8)

Si a< b, y b0, y b>0, entonces a+b > 0 Si a 3/2 . La solución sería todo el intervalo (3/2 ,  ). -2x  3  x  -3/2. O sea, la semirrecta (-, -3/2].

MAp II: Tema 3. Programación Lineal - 1

Inecuaciones lineales con dos incó incógnitas: gnitas: Si a, b y c son números reales, cualquiera de las siguientes expresiones se llama inecuación lineal con dos incógnitas: ax + by + c < 0 ,

ax + by + c > 0 ,

ax + by + c  0 ,

ax + by + c  0

Las letras x e y son variables o incógnitas. El conjunto de soluciones viene representado ahora por puntos del plano plano. Si construimos la recta ax+ by + c = 0, observamos que esta divide al plano en tres zonas. En una de ellas es ax+by+c0, y en otra, son los puntos de la recta ax+by+c=0.

La solución puede obtenerse despejando una variable y suponiendo que a la otra se le puede asignar cualquier valor. Por ejemplo: -4x + 2y ≥ 7  2y ≥ 7 + 4x  y ≥ 2x + 7/2 , con x real. Representamos en el plano la recta y = 2x + 7/2, y marcamos gráficamente la solución.

Sistemas de inecuaciones lineales co con n dos incógnitas: En general, un sistema de n inecuaciones lineales con dos incógnitas es de la forma:

  a2 x  b2 y  c 2   .......................  an x  bn y  c n   a 1x  b1 y  c1

(El sentido de la desigualdad puede variar). La solución de estos sistemas será la región formada por los puntos del plano que verifican todas y cada una de las inecuaciones. La intersección de tres o más semiplanos, cuando no sea vacía, es una región poligonal que puede ser cerrada (región de área finita) o no (área infinito).

Por ejemplo: x  y 2  x  2y x 4 y 

   4  2 



 y  2  x  x  y  2  2  1  y     2

1 x 4

MAp II: Tema 3. Programación Lineal - 2

Representando las rectas correspondientes y calculando los puntos de intersección A(0,2), B(2,0) y C(-10,-3), obtenemos la siguiente región del plano como solución del sistema:

3. P R O G R A M A C I Ó N L I N E A L B I D I M E N S I O N A L La Programación lineal es una parte de las Matemáticas cuyo objetivo fundamental es optimizar (maximizar o minimizar, según dependa) una expresión lineal (que puede reflejar beneficios, costes, tiempo...) sometida a una serie de restriccion restricciones es (dinero, recursos, personal disponible, ...) que vienen definidas por inecuaciones lineales. Por ejemplo: Imaginemos que una empresa fabrica dos productos A y B por medio de una máquina y de unos cuantos obreros. Supongamos que el empresario calculó que durante el próximo período podrá disponer de 200 horas de máquina y 300 horas de trabajo. Suponemos también que el empresario sabe cuántas horas necesita para fabricar cada unidad de cada producto y el beneficio que le queda. Para concretar, supongamos que las horas necesarias y el beneficio por unidad (en euros) son los siguientes: Horas-máquina Horas-trabajo Beneficio

A

B

15 10 5

10 25 10

Horas disponibles 200 300

El fabricante se preguntará: ¿Cuántas unidades de cada producto tendré que fabricar para conseguir el máximo beneficio posible sin dejar obreros parados? Este es un problema clásico de Programación lineal, llamado así porque se puede formular utilizando ecuaciones e inecuacións lineales, de la siguiente manera: Sean x, y las unidades que deberían producirse de A y B respectivamente. Entonces: Restricciones: 1ª) 2ª) 3ª) 4ª)

15x + 10y  200 10x + 25y  300 x0 y0 MAp II: Tema 3. Programación Lineal - 3

Beneficio:

B(x,y) = 5x + 10y

De todos los valores de x e y que cumplen las cuatro restricciones, hay que hallar los que proporcionan un valor máximo de B(x,y). Representamos el recinto definido por las restricciones y calculamos los vértices igualando las ecuaciones de las rectas correspondientes: A(0,0) (este vértice es obvio), B(0,12), C(

D(

80 100 ), 11, 11

40 0) . 3,

Sustituimos los valores de los vértices en la función a maximizar B(x, y): B (0,0)=0 € B (0,12)=10⋅12=120 € B(

100 1400 80 80 100 = )=5⋅ +10⋅ =127,27 € 11 11 11, 11 11

B(

40 200 = 66,67 € ,0)= 3 3

El beneficio máximo se obtiene en el vértice C, pero como no se puede fabricar un número decimal de unidades, tendremos que buscar la solución entera más proxima dentro del recinto ABCD. El punto (7,9) cumple dichas condiciones. Por tanto, para conseguir el máximo beneficio posible sin dejar obreros parados habrá que fabricar 7 unidades del producto A y 9 unidades del producto B. Todo problema de Programación lineal con dos variables, se puede reducir a uno de la siguiente forma, llamado problema tipo:

  a 2 x  b 2 y  c2   .......... .......... ..  a n x  bn y  c n   x  0 , y  0  a 1x  b 1 y  c1

(1)

MAp II: Tema 3. Programación Lineal - 4

De todas las soluciones del sistema de inecuaciones lineales, se trata de hallar una que haga máximo (o mínimo) el valor de una función z = px + qy

La función z se llama fun función ción objetivo objetivo. Las inecuacións que forman el sistema (1) se llaman restricciones restricciones. Cada solución del sistema (1) se llama solución factible , y el conjunto de todas ellas es el conjunto factible o región factible. Por último, la solución factible que proporciona valor máximo o mínimo a la función objetivo se denomina solución óptima. Si hay una solución óptima, estará en un vértice del recinto solución. Puede que haya infinitas, y se encontrarán en un lado. Y es posible que no haya solución óptima, pues cuando el recinto es infinito, la función puede crecer o decrecer indefinidamente. Resolución por métodos gráficos: Para hallar gráficamente la solución de un problema de programación lineal de dos variables, es recomendable seguir el proceso siguiente: 1- Se dibuja el recinto limitado por las restricciones del problema. 2- Se representa la recta px+qy=0, que viene dada por la función que hay que optimizar. 3- Se trazan rectas paralelas a esta, pasando por los vértices del recinto, y se observa que en cada una de ellos la función z se hace máxima (o mínima), sin más que tener en cuenta cuál de las rectas tiene mayor o menor ordenada en el origen. Un problema de programación lineal puede tener una solución, infinitas o ninguna, como se puede comprender observando los siguientes ejemplos gráficos: Supongamos que se pretende maximizar la función z: - En el gráfico 1 se observa que la solución es única, pues la función z consigue el máximo en el punto R. - En el gráfico 2 se observa que las soluciones son infinitas, pues la recta asociada a la función z es paralela al lado que maximiza la función. - En el gráfico 3 se puede ver que no hay solución, pues la función z no consigue nunca el máximo, debido la que el recinto no está acotado. Solución única

Infinitas soluciones

No existe solución

MAp II: Tema 3. Programación Lineal - 5

EJERCICIOS 1. En la elaboración de dos tipos de refrescos R 1 y R 2 se emplean (además de agua), dos tipos

de productos A y B. Cada refresco del tipo R 1 contiene 3 g de A y 3 g de B. Y cada refresco del tipo R2 contiene 3 g de A y 6 g de B. Se disponen de 120 g de A y 180 g de B. ¿Cuántos refrescos de cada clase hay que elaborar para obtener un beneficio máximo, sabiendo que con los refrescos R1 se ganan 3 céntimos y con los de R2 se ganan 4 céntimos? ( Sol: 20 refrescos de R1 y 20 de R2)

2. Se desean obtener tres elementos químicos a partir de las sustancias A y B. Un kilo de A contiene 8 g del primer elemento, 1 g del segundo y 2 g del tercero; un kilo de B tiene 4 g del primer elemento, 1 g del segundo y 2 g del tercero. Se desea obtener por lo menos 16 g del primer elemento, las cantidades del segundo y del tercero tienen que ser como mucho 5 g y 20 g respectivamente, y la cantidad de A es como mucho el doble que la de B. Calcula los kilos de A y los de B que se necesitan para que el coste sea mínimo si un kilo de A vale 2 €, y uno de B 10 €. ¿Puede eliminarse alguna restricción? (Sol: 1,6 kg de A y 0,8 kg de B) 3. Las restricciones pesqueras impuestas por la CEE obligan a cierta empresa a pescar como máximo 2000 toneladas de merluza y 2000 toneladas de rape; además, en total, las capturas de estas dos especies no pueden pasar de las 3000 toneladas. Si el precio de la merluza en lonja es de 10 €/kg y el del rape es de 15 €/kg, ¿qué cantidades debe pescar para obtener el máximo beneficio? ( Sol: 1000 ton. de merluza, 2000 ton. de rape) 4. Una compañía fabrica dos modelos de sombreros: Bae y Viz . La fabricación de los sombreros

se realiza en las secciones de moldeado, pintura y montaje. La fabricación de cada modelo Bae requiere 2 horas de moldeado, 3 de pintura y una de montaje. La fabricación del modelo Viz requiere 3 horas de moldeado, 2 de pintura y una de montaje. Las secciones de moldeado y pintura disponen de un máximo de 1500 horas cada mes (cada una), y la de montaje de 600 h. Si el modelo Bae se vende a 100 € y el modelo Viz a 120 €, ¿qué cantidad de sombreros de cada tipo se deben fabricar para maximizar el beneficio? ( Sol: 300 de cada clase) 5.

Una compañía está especializada en la fabricación de palos de hockey y juegos de ajedrez. La fabricación de estos artículos se hace en los puestos de mecanización A, B y C. Cada palo de hockey requiere un proceso de 4 horas de duración en el puesto de mecanización A y de 2 horas en el B. Un juego de ajedrez, por su parte, precisa de 6 horas en el puesto de mecanización A, de 6 en el B y de 1 en el C. El puesto de mecanización A dispone de un máximo de 120 horas mensuales, el B de 72 y el C de 10. Si cada palo de hockey se vende a 20 € y cada juego de ajedrez a 40 €, ¿cuántos palos de hockey y cuántos juegos de ajedrez deberá fabricar mensualmente si la compañía desea maximizar sus beneficios? (Sol: 24 palos de hockey, 4 juegos de ajedrez)

6. En una fábrica de maquetas de aviones se construyen dos tipos de maquetas A y B. La fábrica

está dividida en dos salas: una de montaje y otra de acabado . Para la fabricación de cada modelo A se necesitan 3 horas semanales en la sala de montaje y 3 en la de acabado . La fabricación de cada modelo B requiere 5 horas semanales en la sala de montaje y 3 en la de acabado. La sala de montaje puede estar funcionando como máximo 150 horas a la semana, y la de acabado 120 h. Si el beneficio es de 300 dólares en cada modelo A y de 400 en cada modelo B, ¿cuántos modelos de cada tipo habrá que fabricar cada semana para maximizar los beneficios (suponiendo que se venden todos)? (Sol: 25 de A, 15 de B)

MAp II: Tema 3. Programación Lineal - 6

7. Una empresa produce dos bienes A y B. Tiene dos fábricas y cada una de ellas produce los dos bienes en las cantidades por hora siguientes: Fábrica 1

Fábrica 2

Bien A

10 unidades/hora

20 unidades/hora

Bien B

25 unidades/hora

25 unidades/hora

La empresa recibe un pedido de 300 unidades de A y 500 de B. Los costes de funcionamiento de las dos fábricas son: 100 € por hora para la fábrica 1 y 80 € por hora para la fábrica 2. ¿Cuántas horas debe funcionar cada fábrica para minimizar los costes de la empresa y satisfacer el pedido? (Sol: 0 horas de la fábrica 1, 20 h la fábrica 2)

8. Dibuja el recinto que cumple las siguientes restricciones: x≥0 , y−4≤0 , y−x +1≥0 , y +2 x−5 ≤0 . Localiza el punto del recinto en el que la función objetivo F( x , y )=x + y es máxima. (Sol: ( ½ , 4 )) 9. Los alumnos de un colegio tienen 120 camisetas, 110 pañuelos y 70 gorros. Con el fin de obtener dinero para el viaje de fin de curso, los van a poner a la venta en dos paquetes distintos; por el primero (dos camisetas, un pañuelo y un gorro) cobrarán 6 €; y por el segundo (una camiseta, dos pañuelos y un gorro) 7 €. ¿Cuántos paquetes de cada tipo deberán vender para obtener el máximo beneficio? ( Sol: 30, 40 respect.)

10. Dibuja la región determinada por las inecuaciones x≥0, y≥0, x+y ≤6, 2x+y ≤10, x+y≥3 y maximiza la función z=4x + 3y, sometida a las restricciones dadas por estas inecuaciones. (Sol: (4,2))

11. Una compañía aérea tiene dos aviones A y B para cubrir un determinado trayecto. El avión A debe hacer más veces el trayecto que el avión B, pero no puede superar los 120 viajes. Entre los dos aviones deben hacer 60 o más vuelos, pero no más de 200. En cada vuelo, A consume 900 litros de combustible, y B 700 litros. En cada viaje del avión A la empresa gana 3000 €, y 2000 € por cada viaje del B. a) ¿Cuántos viajes debe hacer cada avión para obtener el máximo de ganancias? b) ¿Cuántos vuelos debe hacer cada avión para que el consumo de combustible sea mínimo? (Sol: a) 31 viajes el A y 29 el B. b) 120 viajes el A y 80 el B) 12. Se desea fabricar dos tipos de bombones que llamaremos A y B. Las cajas del tipo A contienen 1 kg de chocolate y 2 kg de cacao; las de tipo B contienen 2 kg de chocolate, 1 kg de cacao y 1 kg de almendras. Disponemos de 500 kg de chocolate, 400 de cacao y 225 de almendras. Por cada caja del tipo A se ganan 2 € y por cada caja de tipo B, 3€. ¿Cuántas cajas de cada tipo hay que fabricar para que la ganancia sea máxima? (Sol: 100 de A y 200 de B) 13. Un laboratorio fabrica los complejos vitamínicos REVIT y VITAL que se venden a 1,92 € y 2,21 € la caja, respectivamente. La tabla adjunta indica los contenidos en vitaminas A y B por caja de cada producto. El coste de 1 g de vitamina A es de 5 céntimos, y el coste de 1 g de vitamina B es de 12 céntimos. Se disponen de 38 g de vitamina A y 42 g de vitamina B. ¿Cuántas cajas de REVIT y cuántas de VITAL deben fabricarse, para que el beneficio sea máximo? (Sol: 6 cajas de REVIT y 2 de VITAL) REVIT VITAL

A 4g 7g

B 6g 3g

MAp II: Tema 3. Programación Lineal - 7

14. Disponemos de 210000 € para invertir en Bolsa. Nos recomiendan dos tipos de acciones: Las de tipo A que rinden el 10 %, y las de tipo B que rinden el 8 %. Decidimos invertir un máximo de 130000 € en las de tipo A, y como mínimo 6000 € en las de tipo B. Además queremos que la inversión en las de tipo A sea menor o igual que el doble de la inversión en B. ¿Cuál tiene que ser la distribución de la inversión para obtener el máximo interés anual? (Sol: 130000 € en acciones de tipo A y 80000 € en las de tipo B)

15. Una persona tiene 5000 € para invertir en dos tipos de acciones A y B. El tipo A tiene bastante riesgo con un rédito anual del 10%, y el tipo B es bastante seguro con un rédito anual del 7%. Decide invertir como máximo 3000 € en A, y como mínimo 1000 € en B, e invertir en A por lo menos tanto como en B. ¿Cómo debería invertir su dinero para maximizar los intereses anuales? (Sol: 3000 € en acciones de A y 2000 € en las de B) 16. Un fabricante de aviones produce en dos fábricas tres tipos de aparatos A, B y C. Se comprometió a entregar semanalmente a un emirato árabe, 12 aviones del tipo A, 8 del tipo B y 24 del tipo C. Al fabricante le cuesta 120000 € diarios el funcionamiento de la primera fábrica, y 16000 € el de la segunda. La primera fábrica produce, en un día, 6 aviones tipo A, 2 tipo B y 4 tipo C, mientras que la segunda produce, respectivamente, 2, 2 y 12. ¿Cuántos días por semana debe trabajar cada fábrica para, cumpliendo el contrato con el emir, conseguir reducir al máximo los costes de funcionamiento de las fábricas? (Sol: 0 y 6 días, resp.) 17. Doña Filomena quiere adelgazar pero se encuentra demasiado débil. En una farmacia le ofrecen dos compuestos A y B, para que tome una mezcla de ellos en la comida, con las siguientes recomendaciones: - No debe tomar más de 150 g de la mezcla, ni menos de 50 g. - Debe tomar siempre más cantidad, o igual, de A que de B. - No debe incluir más de 100 g de A. Se sabe que 100 g de A contienen 30 mg de vitaminas y 450 calorías, y que 100 g de B contienen 20 mg de vitaminas y 150 calorías. ¿Cuántos gramos debe tomar de cada compuesto para obtener el preparado más rico en vitaminas? ¿Y se quiere obtener el preparado más pobre en calorías? (Sol: El preparado más rico en vitaminas contiene 100 g de A y 50 de B. El más pobre en calorías tiene 25 g de A y 25 de B)

18. Un animal debe tomar diariamente 9 unidades de hidratos de carbono y 8 de grasas, como máximo. En el mercado hay dos marcas de alimentos con la siguiente composición: Marca A B

Hidratos 1 3

Grasas 2 1

Proteínas 3 4

Calcular la cantidad necesaria de cada marca para que tome el mayor número posible de proteínas. (Sol: 3 unidades de A y 2 de B) 19. Los 400 alumnos de un colegio van a ir de excursión. Para eso se contrata el viaje a una empresa que dispone de 8 autobuses con 40 plazas y 10 con 50 plazas, pero sólo de 9 conductores para ese día. Dada la diferente capacidad y calidad, el contrato de cada autobús de los grandes cuesta 80 €, y cada uno de los pequeños, 60 €. ¿Cuántos autobuses de cada clase habrá que alquilar para minimizar los costes? (Sol: 5 de 40 plazas y 4 de 50 plazas) 20. Una compañía fabrica y vende dos modelos de lámparas A y B. Para su fabricación necesita un trabajo manual de 20 minutos para el modelo A y 30 minutos para el B; y un trabajo de máquina de 20 minutos para A, y 10 para B. Dispone para el trabajo manual de 100 horas al

MAp II: Tema 3. Programación Lineal - 8

mes, y para la máquina de 80 horas al mes. Sabiendo que el beneficio por unidad es de 1,5€ y 1 € para A y B, respectivamente, planificar la producción para obtener el máximo beneficio. (Sol: 210 unidades de A y 60 de B)

21. Considerar la función z=3 /2 x+ y en el conjunto: x≥0 , y≥0 , 3 x+2 y −2≥0 , 3 x−4 y−12≤ 0 . Comprobar que esta función consigue el valor mínimo en más de un punto. 22. (Junio 2013) Sea la función f (x , y )=−0,8 x +1,5 y sujeta a las restricciones: x + y ≤10 ; x +2 y ≥ 8 ; 2≤ y ≤ x+6 ; x ≤ 6 . (a) Representa la región R del plano determinado por el conjunto de restricciones y calcula sus vértices. (b) Calcula los puntos de R donde la función alcanza sus valores máximo y mínimo. 23. (Junio 2014) Consideremos el siguiente sistema de inecuaciones: y− x − 2≤ 0 ; y + x− 6 ≤ 0 ; 2 y≥ 5 − x . (a) Representa gráficamente la región factible y calcula sus vértices. (b) Calcula en qué punto o puntos de esa región alcanza los valores máximo y mínimo la función f (x , y )=x +2 y . (c) Responde al apartado anterior si se añade y≥ 0 al sistema de inecuaciones anterior. 24. (Septiembre 2014) (a) Representa la región del plano definida por el sistema de inecuaciones: y +2 x ≤ 6, y ≤ x ,4 y ≥ x−3 , y calcula sus vértices. Justifica si los puntos P(1, –1/2) y Q (1/2,1) pertenecen o no a esta región. (b) Calcula en qué punto o puntos de esta región la función f (x , y )=y + 2 x alcanza el valor máximo. 25. (Junio 2015) Sea R la región del plano determinada por el sistema de inecuaciones 2 x +3 y ≤ 12, −2 ≤ 2 x − y ≤ 4 , y≥ 0 . (a) Representa la región R y calcula sus vértices. Justifica si el punto P(–1/2, 1/2) pertenece o no a la región R. (b) Calcula el punto o puntos de R donde la función f (x , y )=−2 x...