Ejercicios de programación lineal II

 1. Disponemos de 210.000 euros
para invertir en bolsa. Nos recomiendan dos tipos de acciones.
Las del tipo A, que rinden el 10% y las del tipo B, que rinden el
8%. Decidimos invertir un máximo de 130.000 euros en las
del tipo A y como mínimo 60.000 en las del tipo B.
Además queremos que la inversión en las del tipo A
sea menor 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?

Solución

Es un problema de programación lineal.

Llamamos x a la cantidad que invertimos en
acciones de tipo A

Llamamos y a la cantidad que invertimos en
acciones de tipo B

  
                                           210000              
0,1x+0,08y

Condiciones que deben cumplirse
(restricciones):

R1   

  R2   

  R3   

  R4       

Dibujamos las rectas auxiliares asociadas a las
restricciones para conseguir la región factible (conjunto
de puntos que cumplen esas condiciones)

         r1
                                         
 r2 (paralela a OY) 
       
        
   r3(paralela a
OX)                          
r4

La región factible es la pintada de amarillo, de
vértices A, B, C, D y E

A(0, 60000), B(120000, 60000), C(130000, 65000),
D(130000, 80000) y E(0, 210000)

La función objetivo es;

F(x, y)= 0,1x+0,08y

 Si dibujamos la curva F(x, y) =0 (en rojo) y la
desplazamos se puede comprobar gráficamente que el
vértice  mas alejado es el D, y por tanto es la
solución óptima.

Comprobarlo analíticamente (es decir comprobar
que el valor máximo de la función
objetivo,  F,  se alcanza en el vértice
D)

2. En una pastelería se hacen dos tipos de
tartas: Vienesa y Real. Cada tarta Vienesa necesita un cuarto de
relleno por cada Kg. de bizcocho y produce un beneficio de 250
Pts, mientras que una tarta Real necesita medio Kg. de relleno
por cada Kg. de bizcocho y produce 400 Ptas. de beneficio. En la
pastelería se pueden hacer diariamente hasta 150 Kg. de
bizcocho y 50 Kg. de relleno, aunque por problemas de maquinaria
no pueden hacer mas de 125 tartas de cada tipo.
¿Cuántas tartas Vienesas y cuantas Reales deben
vender al día para que sea máximo el
beneficio?

Solución

En primer lugar hacemos una tabla para organizar los
datos:

 Función objetivo (hay que obtener su
máximo):  f(x, y)=250x+ 400y

Sujeta a las siguientes condiciones (restricciones del
problema):

Consideramos las rectas auxiliares a las restricciones y
dibujamos la región factible:

Para    0.25x+0.50y=50, ó  x +
2y=200

Para   x + y =150

La otras dos son paralelas a los ejes

Al eje OY    x=125

Al eje Ox      y
=125

Y las otras restricciones (x e y mayor o igual a cero)
nos indican que las soluciones deben estar en el primer
cuadrante

La región factible la hemos coloreado de
amarillo:

Encontremos los vértices:

El  O(0,0), el  A(125, 0) y
el  D(0, 100) se encuentran directamente (son las
intersecciones con los ejes coordenados)

Se observa que la restricción y es redundante (es decir
"sobra")

Resolviendo el sistema:

por reducción obtenemos y=50, x=100

Otro  vértice es el punto  C(100,
50)

Y el último  vértice que nos falta se
obtiene resolviendo el sistema:

X+y=150

X=125

Cuya solución es: X=125,  Y=25 
B(125, 25)

Los vértices de la región son O(0,0),
A(125,0), B(125,25) y C(100,50) y D(0,100),

Si dibujamos el vector de  dirección de la
función objetivo f(x, y)=250x+ 400y Haciendo 250x+ 400y
=0,   y=-(250/400)x=-125x/200

Se ve gráficamente que la solución es el
punto (100, 50), ya que es el vértice mas alejado (el
último que nos encontramos al desplazar la rectas
250x+400y=0 )

Lo comprobamos con el método analítico, es
decir usando el teorema que dice que si existe solución
única debe hallarse en uno de los
vértices

La unción objetivo era:  f(x, y)=250x+400y,
sustituyendo en los vértices obtenemos

f(125,0)=31.250

f(125,25)=31.250+10.000=41.250

f(100,50)=25.000+20.000=45.000

f(0,100)=40.000

El máximo beneficio es 45.000 y se obtiene en el
punto (100, 50)

Conclusión:  se tienen que vender 100 tartas
vienesas y 50 tartas reales.

3. Una escuela prepara una excursión para
400 alumnos. La empresa de transporte tiene 8 autocares de 40
plazas y 10 autocares de 50 plazas, pero solo dispone de 9
conductores. El alquiler de un autocar grande cuesta 80 euros y
el de uno pequeño, 60 euros. Calcular cuantos de cada tipo
hay que utilizar para que la excursión resulte lo mas
económica posible para la escuela.

Solución

Es un problema de programación lineal, en este
caso lo que queremos es hacer mínima la función
objetivo.

Llamamos x al nº de autocares de 40 plazas e
y al nº de autocares de 50 plazas que alquila la
escuela.

Entonces se tiene   x , y

Como sólo hay 9 conductores se verifica que: x
+y

Como tienen que caber 400 alumnos se debe de
verificar:

40x +50 y que simplificada quedaría 4 x +5
y

Por lo tanto las restricciones que nos van a
permitir calcular la  región factible (conjunto de
puntos solución donde se cumplen todas las condiciones)
son

La función objetivo es F(x, y)= 60x+
80y

Dibujamos las rectas auxiliares,

r1                           
r2                        
r3                         
r4

Así como la de que corresponde a F(x, y)=0 que se
dibuja en rojo.

Teniendo en cuenta las restricciones ( la de 
R4  es la parte de arriba  y que la R3 es la parte de
abajo), se encuentra la región factible. En el dibujo es
la parte amarilla.

Los vértices son (0, 8), (0, 9) y el (5,
4), este último es el punto de intersección de
las rectas r3 y r4

 por reducción

restando ambas ecuaciones se tiene x =5 y
sustituyendo en la 1ª ecuación, y
=4

Resolviendo gráficamente se llega a que el punto
(5, 4) es la solución del problema.  La
solución óptima .

Comprobarlo sustituyendo en F(x, y) todos los
vértices y que este es el que da menor valor
(método analítico).

4. Una compañía posee dos minas: la mina A
produce cada día 1 tonelada de hierro de alta calidad, 3
toneladas de calidad media y 5 de baja calidad. La mina B produce
cada día 2 toneladas de cada una de las tres calidades. La
compañía necesita al menos 80 toneladas de mineral
de alta calidad, 160 toneladas de calidad media y 200 de baja
calidad. Sabiendo que el coste diario de la operación es
de 2000 euros en cada mina ¿cuántos días
debe trabajar cada mina  para que el coste sea
mínimo?.

Solución

Organizamos los datos en una tabla:

La función objetivo C(x, y)=2000x +
2000y

Las restricciones son:

La región factible la obtenemos dibujando las
rectas auxiliares: r1x + 2y=80, r2 3x + 2y= 160 y r35x + 2y=200 en
el primer cuadrante  y considerando la región no
acotada que determina el sistema de restricciones:

Los vértices son los puntos A(0, 100), B(20, 50),
C(40, 20), D(80, 0), que se encuentran al resolver el sistema que
determinan dos a dos las rectas auxiliares y (y que estén
dentro de la región factible).

r1 r2
que nos da el punto (40, 20)
(comprobarlo)

r2
r3 que nos da el punto (20,
50)

r1
r3  no hace falta calcularlo pues queda fuera de la
región factible.

En la gráfica se aprecia que el primer punto que
se alcanza al desplazar la recta C(x, y)=0 es el (40, 20). Luego
la solución es trabajar 40 días en la mina A y 20
en la B. (método gráfico)

Lo comprobamos  aplicando el método
analítico:

C(0, 100)=2000.100=200000

C(20, 50)=2000.20+2000.50=40000 + 100000=
140000

C(40, 20)= 2000. 40+2000.20=80000 +
40000= 120000    coste mínimo

C(80, 0)= 2000.80 =160000

5. Se va a organizar una planta de un taller de
automóviles donde van a trabajar electricistas y
mecánicos. Por necesidades de mercado, es necesario que
haya mayor o igual número de mecánicos que de
electricistas y que el número de mecánicos no
supere al doble que el de electricistas. En total hay disponibles
30 electricistas y 20 mecánicos. El beneficio de la
empresa por jornada es de 250 euros por electricista y 200 euros
por mecánico. ¿Cuántos trabajadores de cada
clase deben elegirse para obtener el máximo beneficio y
cual es este?

Sea   

 x = nº electricistas

y = nº mecánicos

La función objetivo

f (x, y)=250x+ 200y ,  las restricciones

La región factible sería para estas
restricciones:

Se aprecia gráficamente (línea en rojo)
que la solución óptima está en el punto (20,
20).

Por tanto:

20 electricistas y 20 mecánicos dan el
máximo beneficio, y este es 9000 euros, ya que f(x, y)
=250.20+200.20=9000

6. Para recorrer un determinado trayecto, una
compañía aérea desea ofertar, a lo sumo,
5000 plazas de dos tipos: T(turista) y P(primera). La ganancia
correspondiente a cada plaza de tipo T es de 30 euros, mientras
que la ganancia del tipo P es de 40 euros.

El número de plazas tipo T no puede exceder de
4500 y el del tipo P, debe ser, como máximo, la tercera
parte de las del tipo T que se oferten.

Calcular cuántas tienen  que ofertarse de
cada clase para que las ganancias sean máximas.

Solución

Sea x el nº que se ofertan de tipo T, y el nº
que se ofertan de tipo P.

La función objetivo es:

f(x, y)=30x +40y

Las restricciones:

La región factible:

Los vértices, A(0, 5000), B(3750, 1250), C(4500,
500) y D(4500, 0) (comprueba el punto B resolviendo el sistema
correspondiente)

El método gráfico nos da que el punto
solución es el B (3750, 1250)

Comprueba los resultados usando el método
analítico (sustituyendo los puntos vértices en f y
viendo q el máximo valor se obtiene en B)

Autor:

Pablo Turmero