ENTENDER ANTES DE CALCULAR

Programación lineal: elegir sin saltarse los límites

Con 12 kg de arroz puedes preparar muchos repartos de paquetes. Primero se descartan los que no caben; después se compara cuál da más beneficio o menos coste.

La idea del bloque y los conocimientos previos
Empieza por esta idea

Cada punto (x,y)(x,y) del dibujo es un reparto de dos cantidades. Las restricciones marcan qué puntos están permitidos y la función objetivo dice cuál de ellos es el mejor.

Recta de nivel: deslizar el objetivo hasta el último punto de la región

Si el objetivo es F=3x+2y,F=3x+2y\text{,} ¿qué combinaciones dejan el mismo beneficio, por ejemplo 12 €? Las que cumplen 3x+2y=12:3x+2y=12\text{:} forman una recta, la recta de nivel F=12.F=12\text{.} Cada valor kk de FF tiene la suya, y todas son paralelas.

Despeja y:y\text{:} y=k2−32x.y=\dfrac k2-\dfrac32x\text{.} Todas tienen pendiente −32,-\dfrac32\text{,} y k2\dfrac k2 es su altura en x=0.x=0\text{.} Como los dos coeficientes son positivos, al crecer kk la recta queda más arriba y a la derecha. En general, con F=ax+by,F=ax+by\text{,} FF crece hacia donde apunta (a,b):(a,b)\text{:} a la derecha si a>0a>0 (a la izquierda si a<0)a<0\text{)} y arriba si b>0b>0 (abajo si b<0).b<0\text{).}

Para maximizar, desliza la recta en el sentido en que FF crece, siempre paralela, hasta que esté a punto de salir de la región. El último punto que toca es el óptimo (en una región con esquinas, un vértice). Para minimizar, haz lo mismo en el sentido contrario, hacia donde FF baja.

Si la recta de nivel es paralela a un lado y ese lado es lo último que toca, todo él es óptimo («Casos especiales»); si lo toca antes, no (con F=x+yF=x+y el mínimo está en (0,0)).(0,0)\text{).}

Cómo empezar tu ejercicio

Cuándo usar esta idea: Piden resolver «gráficamente», «dibujar y justificar», o ver en el dibujo dónde está el óptimo sin calcular todos los vértices.

Dibuja la región y una recta de nivel, por ejemplo la de F=0.F=0\text{.} Mira hacia dónde crece FF (hacia (a,b))(a,b)\text{)} y desliza la recta en ese sentido para maximizar, o al contrario para minimizar.

Un ejemplo, paso a paso

Con xx unidades de un producto e yy de otro, el beneficio es F=3x+2yF=3x+2y euros. Maximiza FF en la región de vértices (0,0),(0,0)\text{,} (4,0),(4,0)\text{,} (4,4),(4,4)\text{,} (2,6)(2,6) y (0,6),(0,6)\text{,} deslizando rectas de nivel.

Rectas de nivel de F = 3x + 2y sobre la región factibleRegión factible de cinco vértices: cero cero, cuatro cero, cuatro cuatro, dos seis y cero seis. Tres rectas paralelas muestran los puntos con el mismo valor de F igual a tres x más dos y: F igual a 6 y F igual a 12 en azul discontinuo, y F igual a 20 en naranja, que toca la región solo en el vértice cuatro cuatro. Una flecha gris indica la dirección en que F crece, hacia arriba y a la derecha.24682468xyF = 6F = 12F = 20(4, 4)F crece
Cada recta de trazos agrupa las combinaciones con el mismo beneficio: 3x+2y=63x+2y=6 y 3x+2y=12.3x+2y=12\text{.} Son paralelas y se alejan del origen al crecer FF (flecha). La naranja, 3x+2y=20,3x+2y=20\text{,} es la última que toca la región, en (4,4):(4,4)\text{:} con un valor mayor, la recta ya no pasa por ningún punto permitido.
Al crecer kk la recta se aleja del origen; mira cuándo deja de tocar la región.
RectaCorta los ejes en¿Toca la región?
F=12F=12(0,6)(0,6) y (4,0)(4,0)Sí, la atraviesa
F=20F=20(0,10)(0,10) y (203,0)\left(\frac{20}3,0\right)Solo en (4,4)(4,4)
F=22F=22(0,11)(0,11) y (223,0)\left(\frac{22}3,0\right)No
  1. La recta de nivel F=kF=k es 3x+2y=k,3x+2y=k\text{,} pendiente −32-\dfrac32 para todo kk y altura k2\dfrac k2 en x=0.x=0\text{.}
  2. Dibuja dos: con k=6k=6 pasa por (0,3)(0,3) y (2,0);(2,0)\text{;} con k=12,k=12\text{,} por (0,6)(0,6) y (4,0),(4,0)\text{,} y atraviesa la región: todos sus puntos dejan 12 €.
  3. Como a=3a=3 y b=2b=2 son positivos, FF crece hacia arriba y a la derecha. Deslizamos la recta en ese sentido, siempre paralela, hasta que casi sale.
  4. Lo último que toca es el vértice (4,4):(4,4)\text{:} F=3⋅4+2⋅4=20.F=3\cdot4+2\cdot4=20\text{.} Con k>20k>20 ya no toca la región.
  5. Comprobación: los otros vértices dan 0,0\text{,} 12,12\text{,} 1818 y 12,12\text{,} todos menores que 20.

Lo que obtenemos: El máximo es F(4,4)=20F(4,4)=20 €, con 4 unidades de cada producto, igual que al comparar vértices.

Ahora, los símbolos en palabras

a, ba,\ b
Coeficientes de xx y de yy en el objetivo F=ax+byF=ax+by (aquí a=3a=3 y b=2),b=2\text{),} no las constantes de las restricciones.
kk
Un valor concreto de F.F\text{.} La recta ax+by=kax+by=k reúne todas las combinaciones que dan k.k\text{.}
−ab-\dfrac ab
Pendiente de todas las rectas de nivel de F:F\text{:} no depende de k.k\text{.} Si b=0b=0 la recta es vertical, x=k/a.x=k/a\text{.}
ax+by=k ⟹ y=kb−abxax+by=k\ \Longrightarrow\ y=\dfrac kb-\dfrac abx(b≠0)(b\neq0)

Quédate con esto: Maximizar es empujar la recta de nivel, en el sentido en que FF crece, hasta el último punto de la región; minimizar, en el sentido contrario.

Ojo con este error: Deslizar siempre «hacia arriba»: el sentido depende de los signos de los coeficientes. Con F=x−y,F=x-y\text{,} las rectas son y=x−ky=x-k y FF crece al ir hacia abajo y a la derecha.

Para ir más allá

Las rectas de nivel son perpendiculares a la dirección (a,b),(a,b)\text{,} en la que FF crece más deprisa.

Si la región no tiene límite y la recta de nivel puede avanzar sin dejar de tocarla, no hay máximo: el objetivo crece sin tope.

Ahora prueba la idea

En la misma región, minimiza H=y−xH=y-x deslizando rectas de nivel. ¿En qué vértice se alcanza y cuánto vale?

Ver la respuesta y el porqué

En (4,0),(4,0)\text{,} con H=−4.H=-4\text{.}

Con a=−1a=-1 y b=1,b=1\text{,} HH crece hacia la izquierda y arriba; para minimizar se desliza la recta y=x+ky=x+k hacia la derecha y abajo. Lo último que toca es (4,0),(4,0)\text{,} con k=0−4=−4.k=0-4=-4\text{.} Los vértices dan 0,0\text{,} −4,-4\text{,} 0,0\text{,} 44 y 6.6\text{.}

Ver los otros bloques