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.

Óptimo: comparar el objetivo en los vértices

Entre las infinitas combinaciones factibles, ¿cuál deja más beneficio? No hace falta probarlas todas: si la región es un polígono cerrado (incluye su borde) y acotado (no se extiende sin límite), una función lineal alcanza su máximo y su mínimo en algún vértice. Al avanzar por un lado, FF cambia siempre al mismo ritmo, así que en medio del lado nunca hay algo estrictamente mejor que en sus extremos: el máximo se alcanza en un extremo, y si los dos extremos empatan, en todo el lado. Los puntos de dentro tampoco mejoran: desde uno puedes moverte en una dirección en la que FF no baje hasta llegar al borde y, de ahí, seguir por el lado hasta un vértice, sin perder nada (para un mínimo, igual con «no suba»).

En el puesto de bocadillos, F(x,y)=3x+2yF(x,y)=3x+2y es el beneficio, la función objetivo (lo que quieres hacer máximo o mínimo): cada bocadillo de tortilla (x)x\text{)} deja 3 € y cada uno de jamón (y),y\text{),} 2 €. Para evaluarla en un vértice, sustituye xx e yy y conserva los factores 3 y 2.

Haz una tabla con cada vértice y su valor de F.F\text{.} Para un máximo, elige el mayor; para un mínimo, el menor. Responde con las cantidades (el punto) y con el valor de FF y su unidad.

Cómo empezar tu ejercicio

Cuándo usar esta idea: Ya tienes la región y debes maximizar o minimizar una función lineal sobre ella.

Escribe una fila por vértice y sustituye sus dos coordenadas en F,F\text{,} conservando los coeficientes.

Un ejemplo, paso a paso

En un puesto de bocadillos, cada uno de tortilla (xx unidades) deja 3 € y cada uno de jamón (yy unidades) 2 €. Maximiza F=3x+2yF=3x+2y en la región x,y≥0,x,y\ge0\text{,} x≤4,x\le4\text{,} y≤6,y\le6\text{,} x+y≤8.x+y\le8\text{.} Las cantidades son continuas.

Intersección de las restriccionesRegión poligonal con vértices cero cero, cuatro cero, cuatro cuatro, dos seis y cero seis. Las cotas x como máximo cuatro e y como máximo seis forman un rectángulo; la cota x más y como máximo ocho elimina su esquina superior derecha.xy022446688(0,0)(4,0)(4,4)(2,6)(0,6)(4,6), fuerax ≤ 4, y ≤ 6, x + y ≤ 8
La zona verde reúne todas las combinaciones permitidas. El punto marcado (4,4)(4,4) da 3⋅4+2⋅4=20;3\cdot4+2\cdot4=20\text{;} la tabla del ejemplo compara ese beneficio con el de las demás esquinas.
Mira la última columna y quédate con el valor mayor.
Vértice (x,y)(x,y)CuentaF(x,y)F(x,y)
(0,0)(0,0)3⋅0+2⋅03\cdot0+2\cdot00
(4,0)(4,0)3⋅4+2⋅03\cdot4+2\cdot012
(4,4)(4,4)3⋅4+2⋅43\cdot4+2\cdot420
(2,6)(2,6)3⋅2+2⋅63\cdot2+2\cdot618
(0,6)(0,6)3⋅0+2⋅63\cdot0+2\cdot612
  1. Los vértices de la región, ya calculados, son (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{.} Como la región es cerrada y acotada, el máximo está en uno de ellos.
  2. Sustituimos en F=3x+2yF=3x+2y conservando los factores. En (4,4):(4,4)\text{:} F=3⋅4+2⋅4=12+8=20.F=3\cdot4+2\cdot4=12+8=20\text{.}
  3. Hacemos lo mismo en los otros cuatro vértices y recogemos los valores en la tabla.
  4. El mayor valor de la tabla es 20, que corresponde a x=4,x=4\text{,} y=4.y=4\text{.}
  5. Como (4,4)(4,4) tiene coordenadas enteras, vale también para bocadillos enteros: los repartos enteros son un caso particular de los continuos, así que ninguno puede superar 20.

Lo que obtenemos: El máximo es F(4,4)=20F(4,4)=20 €, alcanzado al producir 4 unidades de cada tipo.

Ojo con este error: Elegir el vértice con más cantidad de un producto sin evaluar F:F\text{:} (2,6)(2,6) tiene más jamón que (4,4),(4,4)\text{,} pero deja 18 € frente a 20 €.

Para ir más allá

Si el enunciado exige unidades enteras y la mejor esquina tiene decimales, la solución continua no basta. Hay que buscar la mejor combinación de números enteros que cumpla todos los límites. Redondear las coordenadas no garantiza que se cumplan ni que el resultado sea el mejor.

Este atajo se aplica con seguridad a regiones acotadas. Si la región no lo es, el objetivo podría seguir creciendo (o bajando) sin tope y hay que comprobarlo: mira «Casos especiales».

Ahora prueba la idea

Si el beneficio fuera G=x+4yG=x+4y en la misma región, ¿qué vértice gana entre (4,4)(4,4) y (2,6)?(2,6)\text{?}

Ver la respuesta y el porqué

(2,6),(2,6)\text{,} con G=26G=26 frente a G=20.G=20\text{.}

G(2,6)=2+4⋅6=26G(2,6)=2+4\cdot6=26 y G(4,4)=4+4⋅4=20.G(4,4)=4+4\cdot4=20\text{.} Con otros coeficientes cambia el ganador: hay que evaluar.

Ver los otros bloques