calculo.cc

Resolución gráfica del problema de programación lineal

  1. Dada la función objetivo f(x,y) = ax + by se representa la recta la recta ax + by = 0.

  2. Se trazan rectas paralelas a ax + by = 0 (ax + by = k ) que pasen por los vértices de la región factible. Estas líneas se llaman líneas de nivel.

  3. Teniendo en cuenta el signo de b en la función objetivo, se verifica que:
    • Si b > 0, el valor máximo, si existe, se alcanza en el vértice cuya línea de nivel tiene mayor ordenada en el origen (el valor y para x = 0) y el valor mínimo, si existe, será aquel cuya recta de nivel tenga una ordenada en el origen menor.
    • Si b < 0, el valor máximo, si existe, se alcanza en el vértice cuya línea de nivel tiene menor ordenada en el origen (el valor y para x = 0) y el valor mínimo, si existe, será aquel cuya recta de nivel tenga una ordenada en el origen mayor.
  4. Calculamos el vértice o los vértices elegidos en el paso anterior.
f(x,y) = ax + by Maximizar Minimizar
b > 0 El máximo es, si existe, el vértice cuya línea de nivel tiene mayor ordenada en el origen El mínimo es, si existe, el vértice cuya línea de nivel tiene menor ordenada en el origen
b < 0 El máximo es, si existe, el vértice cuya línea de nivel tiene menor ordenada en el origen El mínimo es, si existe, el vértice cuya línea de nivel recta tiene mayor ordenada en el origen

Posibles resultados en un problema de máximo

Posibles resultados en problema de máximo Gráfica

Solución única en un vértice: R

Solución múltiple:

Todos los puntos del segmento RQ

No hay solución:

No hay máximo, ya que la región no está acotada superiormente.

Posibles resultados en un problema de mínimo

Posibles resultados en problema de mínimo Gráfica

Solución única en un vértice: T

Solución múltiple:

Todos los puntos del segmento PT

No hay solución:

No hay máximo, ya que la región no está acotada inferiormente

Ejemplo de aplicación del método gráfico:

Resuelve de forma gráfica el siguiente problema de programación lineal:
Máximo y mínimo de F(x,y) = 12x + 4y sujeta a:


Seguimos los pasos del método gráfico:

  1. Se representa la recta 3 x + y = 0 (que es la misma que la recta 12x + 4y = 0).

  2. Se trazan rectas paralelas a esta recta que pasen por cada uno de los vértices de la región factible. Tras los dos primeros pasos obtenemos la siguiente representación gráfica:




  3. Para la función F(x,y) = 3x + y = 0, tenemos que b > 0.
    • Para maximizar la función bastará con tomar el vértice por el cual pasa la paralela a la recta 3x + y = 0 con mayor ordenada en el origen. Dicho vértice es el vértice B. Por tanto la función alcanza su máximo en el vértice B.
    • Para minimizar la función bastará con tomar el vértice por el cual pasa la paralela a la recta 3x + y = 0 con menor ordenada en el origen. Dicho vértice es el vértice D. Por tanto la función alcanza su mínimo en el vértice D.
  4. Calculamos los vértices elegidos en el paso anterior:



Ejemplo de aplicación del método gráfico:

Un orfebre fabrica dos tipos de joyas:

La unidad de tipo A se hace con 1 g de oro y 1,5 g de plata y se vende a 25€. La de tipo B se vende a 30 € y lleva 1,5 g de oro y 1 g de plata. Si solo se dispone de 750 g de cada metal, ¿cuántas joyas ha de fabricar de cada tipo para obtener el máximo beneficio?

Empezamos por traducir al lenguaje de la programación lineal el enunciado del problema.

  • Llamamos x a la cantidad de joyas del tipo A.
  • Llamamos y a la cantidad de joyas del tipo B.

Queremos maximizar el beneficio, es decir, la función que nos permite calcular el dinero obtenido de la venta de las joyas. Dicha función es
F(x,y) = 25 x + 30 y

Las restricciones del problema son:

Teniendo todo esto en cuenta podemos pasar a la resolución del problema mediante el método gráfico:

  1. Se representa la recta:    25x + 30y = 0.

  2. Se trazan rectas paralelas a esta recta que pasen por cada uno de los vértices de la región factible. Tras los dos primeros pasos obtenemos la siguiente representación gráfica:




  3. Para la recta 25 x + 30 y = 0, tenemos que b > 0. Como queremos maximizar la función bastará con tomar el vértice por el cual pasa la paralela a 25 x + 30 y = 0 con mayor ordenada en el origen. Dicho vértice es el vértice C. Por tanto la función alcanza su máximo en el vértice C.

  4. Calculamos el vértice elegido en el paso anterior.



    El vértice que maximiza la función es el vértice C. Por tanto habría que fabricar 300 joyas de cada uno de los tipos y, como F(300,300) = 16500, se venderían por 16500 €.

izquierda
         arriba