Saltar al contenido
El bit perdido
Newsletter

Calculadora de programación lineal paso a paso (método de los vértices)

Resuelve problemas de programación lineal con dos variables paso a paso: rectas frontera, región factible dibujada, vértices exactos, valor de la función objetivo en cada uno y máximo o mínimo, con los casos de óptimo en un segmento y región no acotada.

Escribe <= o ≤, >= o ≥. No olvides x >= 0 e y >= 0 si las variables no pueden ser negativas.

Ejemplos:

Ejemplo resuelto paso a paso

Coste mínimo (región no acotada)

min⁡f=375 en (5, 1)\min f = 375 \text{ en } (5,\ 1)
Región factible no acotada con vértices A (10, 0), B (5, 1), C (2, 4), D (0, 8).

  1. 1El planteamiento

    Queremos minimizar la función objetivo sujeta a las restricciones.

    f(x,y)=60x+75y{x+y≥62x+y≥8x+5y≥10x≥0y≥0f(x, y) = 60x + 75y \qquad \begin{cases} x + y \ge 6 \\ 2x + y \ge 8 \\ x + 5y \ge 10 \\ x \ge 0 \\ y \ge 0 \end{cases}

  2. 2Las rectas frontera

    Cambiamos cada desigualdad por una igualdad y buscamos dos puntos de cada recta. Para saber qué lado vale, probamos un punto, por ejemplo el origen. x+y=6x + y = 6 pasa por (0, 6)(0,\ 6) y (6, 0)(6,\ 0); vale el semiplano que no contiene al origen. 2x+y=82x + y = 8 pasa por (0, 8)(0,\ 8) y (4, 0)(4,\ 0); vale el semiplano que no contiene al origen. x+5y=10x + 5y = 10 pasa por (0, 2)(0,\ 2) y (10, 0)(10,\ 0); vale el semiplano que no contiene al origen. x≥0x \ge 0 e y≥0y \ge 0: el primer cuadrante.

  3. 3Los vértices de la región factible

    Cortamos las rectas dos a dos y nos quedamos con los puntos que cumplen todas las restricciones. La región no está acotada.

    A=(10, 0)(x+5y=10, y=0)B=(5, 1)(x+y=6, x+5y=10)C=(2, 4)(x+y=6, 2x+y=8)D=(0, 8)(2x+y=8, x=0)\begin{aligned} A &= (10,\ 0) && (x + 5y = 10,\ y = 0) \\ B &= (5,\ 1) && (x + y = 6,\ x + 5y = 10) \\ C &= (2,\ 4) && (x + y = 6,\ 2x + y = 8) \\ D &= (0,\ 8) && (2x + y = 8,\ x = 0) \end{aligned}

  4. 4La función objetivo en cada vértice

    Si hay óptimo, está en un vértice (o en todo un lado). Evaluamos ff en cada uno.

    f(A)=60⋅10+75⋅0=600f(B)=60⋅5+75⋅1=375f(C)=60⋅2+75⋅4=420f(D)=60⋅0+75⋅8=600\begin{aligned} f(A) &= 60\cdot 10 + 75\cdot 0 = 600 \\ f(B) &= 60\cdot 5 + 75\cdot 1 = 375 \\ f(C) &= 60\cdot 2 + 75\cdot 4 = 420 \\ f(D) &= 60\cdot 0 + 75\cdot 8 = 600 \end{aligned}

  5. 5El mínimo existe

    Aunque la región no está acotada, en las direcciones en que se extiende la función no decrece: al desplazar las rectas de nivel f(x,y)=kf(x, y) = k para disminuir kk, salen de la región por un vértice. Por eso el mínimo existe y está en un vértice.

  6. 6El mínimo

    El mínimo se alcanza en el vértice BB.

    min⁡f=f(5, 1)=375\min f = f(5,\ 1) = 375

El método de los vértices

Un problema de programación lineal con dos variables pide el máximo o el mínimo de una función f(x,y)=ax+byf(x,y)=ax+by entre los puntos que cumplen unas restricciones (desigualdades lineales). Se resuelve así:

  1. Plantear: elegir las variables, escribir la función objetivo y las restricciones (sin olvidar x≥0x\ge0, y≥0y\ge0 si no pueden ser negativas).
  2. Dibujar cada recta frontera y quedarse con el semiplano que cumple la desigualdad: la intersección es la región factible.
  3. Calcular los vértices: cortes de dos rectas que cumplen todas las restricciones.
  4. Evaluar ff en cada vértice: si la región está acotada, el mayor valor es el máximo y el menor, el mínimo. Si no lo está, hay que comprobar antes que el óptimo existe.

Un ejemplo completo

Una fábrica hace mesas (xx) y sillas (yy). Cada mesa da 3 € de beneficio y cada silla, 2 €. Hay 4 horas de montaje (una hora por pieza, sea mesa o silla) y 6 de barnizado (una hora por mesa y tres por silla). ¿Cuántas de cada conviene hacer?

Maximizamos f(x,y)=3x+2yf(x,y)=3x+2y con x+y≤4x+y\le4, x+3y≤6x+3y\le6, x≥0x\ge0, y≥0y\ge0. Los vértices son (0,0)(0,0), (4,0)(4,0), (3,1)(3,1) y (0,2)(0,2), y

f(0,0)=0,f(4,0)=12,f(3,1)=11,f(0,2)=4.f(0,0)=0,\quad f(4,0)=12,\quad f(3,1)=11,\quad f(0,2)=4.

El máximo es 1212 €, con 4 mesas y ninguna silla.

Errores típicos

  • Olvidar x≥0x\ge0, y≥0y\ge0: la región cambia y aparecen vértices con valores negativos.
  • Coger el semiplano equivocado: hay que comprobarlo con un punto, no a ojo.
  • Dar como vértice un corte que no cumple todas las restricciones.
  • Buscar el máximo en una región no acotada sin comprobar que existe.
  • Olvidar que las soluciones deben ser enteras cuando se cuentan piezas o personas: si el vértice óptimo no tiene coordenadas enteras, hay que decirlo y buscar el mejor punto entero de la región.

Preguntas frecuentes

¿Qué es la región factible?

Es el conjunto de puntos (x, y) que cumplen todas las restricciones a la vez. Cada restricción es un semiplano, y la región factible es su intersección: un polígono (acotado o no).

¿Por qué el óptimo está en un vértice?

Porque la función objetivo es lineal: sus rectas de nivel son paralelas, y al desplazarlas para mejorar el valor, la última que toca la región lo hace en un vértice (o en todo un lado si es paralela a él).

¿Qué pasa si dos vértices dan el mismo valor?

Si son el máximo (o el mínimo), el óptimo se alcanza en todos los puntos del segmento que los une: hay infinitas soluciones.

¿Puedo escribir < en lugar de ≤?

Sí, pero la calculadora trata < como ≤ (y > como ≥) y lo avisa: con una desigualdad estricta la frontera no es de la región, y si el óptimo cae en ella, no se alcanzaría. En la PAU las restricciones se escriben con ≤ y ≥.

¿Y si la región no está acotada?

Puede haber óptimo o no. Si la función mejora sin límite al avanzar por la región, no hay máximo (o mínimo). Por ejemplo, un coste con coeficientes positivos se puede minimizar en una región no acotada hacia arriba, pero no maximizar. Si las rectas de nivel son paralelas a un borde que no termina, el óptimo se alcanza en toda una semirrecta.

¿Cómo sé de qué lado está el semiplano?

Se prueba un punto que no esté en la recta, normalmente el origen: si cumple la desigualdad, el semiplano es el que lo contiene.

Otras herramientas