Ejemplos de programación lineal

Vamos a ver un ejm de programación lineal.

Unos grandes almacenes encargan pantalones y chaquetas
a un fabricante.

El fabricante dispone, para la confección, de 750 metros
de tejido de algodón, y 1000 metros de poliéster, cada
pantalón precisa 1 metro de algodón y 2 metros de poliéster,
y cada chaqueta necesita 1.5 metros de algodón y 1 metro
de poliéster.

El precio del pantalón se fija en 50 euros,
el de la chaqueta en 40 euros.

¿Qué número de pantalones y chaquetas debe suministrar
el fabricante a los almacenes para que éstos consigan
un beneficio máximo?

Los pasos que debemos seguir son los siguientes.

1. Elección de las incógnitas

  • x = número de pantalones
  • y = número de chaquetas

2. Función objetivo

Sería la siguiente.

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

3. Restricciones

Vamos a ayudarnos de una tabla.

Pantalón Chaqueta Disponible
Algodón 1 1.5 750
Poliéster 2 1 1000
  • x + 1.5y ≤ 750 -> 2x + 3y = 1500
  • 2x + y ≤ 1000

Como el número de pantalones y chaquetas son números naturales, habrá 2 restricciones más.

  • x ≥ 0
  • y ≥ 0

4. Hallar el conjunto de soluciones factibles

Debemos representar gráficamente 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.

Ejm de programación lineal

Resolvemos gráficamente la inecuación x + 1.5y ≤ 750, para ello tomamos un punto en el plano, por ejm el (0,0)

0 + 1.5*0 ≤ 750

0 ≤ 750, entonces, el punto (0,0) se encuentra en el semiplano donde se cumple la desigualdad. De modo análogo resolvemos 2x + y ≤ 1000

2*0 + 0 ≤ 1000

La zona de intersección de las soluciones de las inecuaciones sería la solución al sistema de inecuaciones, que constituye el conjunto de las soluciones factibles.

Ejm de programación lineal 2

5. Calcular las coordenadas de los vértices del recinto de las soluciones factibles

La solución óptima, si es única, se encuentra en un vértice del recinto. Estas 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)

Ejm de programación lineal 3

6. Calcular el valor de la función objetivo

En la función objetivo sustituimos cada uno de los vértices.

  • f(x,y) = 50x + 40y
  • f(0,500) = 500*0 + 40*500 = 20.000 euros
  • f(500,0) = 50*500 + 40*0 = 25.000 euros
  • f(375,250) = 50*375 + 40*250 = 28750 (máximo)

La solución óptima es fabricar 375 pantalones y 250 chaquetas para obtener un beneficio de 28750 euros.

Solución múltiple

La solución no siempre es única, también podemos encontrarnos con una solución múltiple.

Si la función objetivo del ejercicio anterior hubiese sido

  • f(x,y)= 20x + 30y
  • f(0,500) = 20 · 0 + 30 · 500 = 15 000 € (Máximo)
  • f(500, 0) = 20 · 500 + 30 · 0 = 10 000 €
  • f(375, 250) = 20 · 375 + 30 · 250 = 15 000 € (Máximo)

En este caso, todos los pares, con soluciones enteras del segmento trazado en negro serían máximos.

Solución múltiple

  • f(300, 300)= 20 · 300 + 30 · 300 = 15 000 €     (Máximo)