Clases Ana

Aula virtual

Programación lineal

Hola!

Bienvenid@ a este curso de programación lineal, en el que vamos a ver en qué consiste y cómo se resuelve, mediante un ejemplo.

A por ello, que es sencillo, ya verás.

 

PROGRAMACIÓN LINEAL:

Resolver un problema de programación lineal consiste en optimizar una función lineal, denominada función objetivo , sujeta a una serie de restricciones expresadas mediante inecuaciones lineales.

Este tipo de problemas, vamos a resolverlos por el método gráfico, encontrando lo que vamos a denominar la región factible, que es la región del plano donde estará la solución buscada.

Esta zona puede ser acotada o no y la solución del problema la obtendremos en la frontera de la región factible, así que sacaremos sus vértices y buscaremos cuál es el punto que optimiza la función estudiada.

Para hacer correctamente un problema de programación lineal, seguiremos los siguientes pasos:

  • Sacar las restricciones y la función objetivo del enunciado.
  • Resolver el sistema de inecuaciones formado por las restricciones, por el método gráfico, para hallar la región factible.
  • Obtener los vértices de la región factible.
  • Calcular, de entre los puntos obtenidos y sustituyendo en la función objetivo, cuál de ellos toma el valor máximo o mínimo.

 

Vamos a verlo mejor con un ejemplo:

Un fabricante construye dos tipos de vehículos especiales: Macro y Micro. Un micro se monta en 6 h, mientras que un Macro necesita 10 h. Ambos tipos de vehículos necesitan además 3 h de acabado.

En una semana, la nave de montaje funciona durante 300 h, mientras que la de acabados lo hace durante 120 h. Si

la ganancia es de 1000 euros por vehículo Micro y de 1300 euros por cada vehículo Macro; ¿cuántas unidades de cada tipo es conveniente fabricar para obtener el máximo beneficio?

 

Solución:

1.- Sacamos restricciones del enunciado (si quieres puedes organizar los datos en una tabla)

Tipo vehículos Horas montaje Horas acabado Beneficios
Macro 10 3 1300 €
Micro 6 3 1000 €
Disponibilidad 300 120

 

Ahora expresamos las inecuaciones, siendo x el número de vehículos del tipo Macro y siendo y, el número de vehículos del tipo Micro:

10x+6y\leq 300

3x+3y\leq 120

Como estamos hablando de vehículos, no vamos a dar valores negativos de x ni de y, por lo que las soluciones estarán en el primer cuadrante, ya que serán siempre positivas ó 0. Esto lo expresamos poniendo las inecuaciones siguientes:

x\geq 0

y\geq 0

La función objetivo Z_{o} (x,y) = 1300x+1000y

 

2.- Vamos ahora a resolver este sistema de inecuaciones por el método gráfico. Haremos una tabla de valores para las dos primeras (recomiendo dar los puntos de corte o ceros cruzados)

Para 10x+6y= 300

x y
0 50
30 0

Para ver si la solución está por encima o por debajo de la recta, damos un valor aleatorio y comprobamos si verifica o no la inecuación del enunciado. Recomiendo dar el (0, 0) siempre y cuando la recta no pase por él. En este caso  10x+6y\leq 300, si sustituyo el punto (0, 0) la verifica, puesto que   0\leq 300  , así que la recta mira hacia ese punto, la solución se encuentra por debajo de la recta.

Para 3x+3y= 120

x y
0 40
40 0

 

Comprobamos si verifica o no la inecuación. En este caso  3x+3y\leq 120, si sustituyo el punto (0, 0) la verifica, puesto que 0\leq 120 así que la recta mira hacia ese punto, la solución se encuentra por debajo de la recta también.

Vamos a obtener ahora los vértices de esta región factible, que serían el O (0, 0), punto que no tiene interés puesto que representaría no fabricar nada y evidentemente, esto no reportaría beneficios. El punto A (0, 40), el punto B (30, 0) y el punto C, que corresponde con el corte de ambas rectas y que vamos a calcular resolviendo el sistema de ecuaciones que ambas forman, por el método que queramos y del que se obtiene C (15, 25)

 

El siguiente paso es verificar, de estos puntos de la frontera, cuál es el que maximiza los beneficios. Para ello sustituimos los puntos en la función objetivo Z_{o} (x,y) = 1300x+1000y y decidimos.

 

Para A (0, 40): Z_{o} (0,40) = 1300\cdot 0+1000\cdot 40 = 40000 €

Para B (30, 0): Z_{o} (30,0) = 1300\cdot 30+1000\cdot 0 = 39000 €

Para C (15, 25): Z_{o} (15,25) = 1300\cdot 15+1000\cdot 25 = 44500 €

 

Aquí se observa perfectamente que el punto que da máximos beneficios es el C. Así que la solución al este ejercicio sería indicar que, para que la empresa obtenga máximos beneficios debería fabricar 14 vehículos del tipo Macro y 25 vehículos del tipo Micro, obteniendo así el máximo beneficio de 44500 euros.

 

Qué te ha parecido, sencillo, verdad? Venga, pues te dejo unos cuantos ejercicios en la pestaña de materiales, para que compruebes por ti mism@ lo sencillo que es. A tope!

Insert math as
Block
Inline
Additional settings
Formula color
Text color
#333333
Type math using LaTeX
Preview
\({}\)
Nothing to preview
Insert
Scroll al inicio