Álgebra (71) · Unidad 5 — Programación lineal en ℝ²

Problemas de programación lineal

Un problema de programación lineal se resuelve en tres movimientos: traducir el enunciado a variables, restricciones y función objetivo; hallar los vértices de la región y evaluar; y contestar en el idioma del problema: cuántas unidades de cada cosa y cuánto se gana o se gasta.

Practicar este tema →7 ejercicios que te corrigen paso a paso · gratis, sin cuenta

La explicación

Traducir: la parte que decide el ejercicio

Casi todos los errores de un problema de programación lineal están en el planteo, no en las cuentas. Conviene hacerlo siempre en el mismo orden:

1. Las variables, con su unidad. «x = cantidad de mochilas chicas por semana», no «x = mochilas». Si el enunciado pregunta «cuántas horas», las variables son horas, aunque aparezcan prendas.
2. Las restricciones, una por frase. Cada recurso limitado da una ≤ (lo que se usa no pasa de lo que hay); cada pedido o mínimo da una ≥.
3. La no negatividad: x ≥ 0, y ≥ 0, porque son cantidades.
4. La función objetivo, y si se maximiza o se minimiza.

Un truco para las restricciones de recursos: armá mentalmente una tablita con una fila por recurso y una columna por producto, y en cada casilla lo que usa una unidad. Cada fila es una restricción: x·(lo que usa uno) + y·(lo que usa el otro) ≤ lo que hay.

Las frases que más se traducen mal

«a lo sumo 80» → ≤ 80
«por lo menos 30», «no menos de» → ≥ 30
«entre 40 y 100 en total» → 40 ≤ x + y ≤ 100
«x no supera a y» → x ≤ y
«x es al menos el doble de y» → x ≥ 2y
«x no supera el triple de y» → x ≤ 3y
«al menos un tercio del total es x» → x ≥ (x + y)/3

Las de proporción se pasan con todo de un lado: x ≥ 2y es x − 2y ≥ 0, y x ≥ (x + y)/3 es 3x ≥ x + y, o sea 2x − y ≥ 0. La frontera de todas ellas pasa por el origen. El error más común es darla vuelta: «x es al menos el doble de y» no es y ≥ 2x. Para controlar, poné números: si y = 10, x tiene que ser 20 o más; en x ≥ 2y eso se cumple.

Resolver y contestar

Con el planteo hecho, lo que sigue es lo del tema anterior: los vértices de la región (cortes de dos fronteras que cumplen todo), la tabla de vértices, y el mejor valor. Pero la respuesta no es «x = 40, y = 30»: es «hay que fabricar 40 mochilas chicas y 30 grandes por semana, y se gana $ 270 000». Si se pregunta por el costo, se contesta el costo; si se pregunta por la cantidad de días, los días.

Dos cosas que conviene mirar antes de contestar. Que el óptimo tenga sentido: si las variables son cantidades que no se parten (mochilas, personas), el vértice óptimo tiene que tener coordenadas enteras; en los problemas de práctica están armados para que así sea. Y qué recursos se agotan: en el óptimo, las restricciones que se cumplen con igualdad son las que están «topeadas»; las demás tienen sobrante.

Máximos y mínimos

En los de máximo (ganancia, ingreso, peso transportado) las restricciones suelen ser de recursos (≤) y la región queda cerca del origen, acotada. En los de mínimo (costo, horas, días) suelen ser pedidos (≥), y la región queda lejos del origen, muchas veces no acotada. Ahí no hay problema: el mínimo existe igual, porque el costo crece al alejarse. Lo que no tendría sentido es preguntar el máximo costo de una región no acotada, salvo que alguna restricción la cierre (por ejemplo, un tope de días).

El control que conviene hacer siempre

Reemplazá la respuesta en el enunciado, no en tu sistema: con 40 mochilas chicas y 30 grandes, ¿alcanza la tela? ¿alcanzan las horas? Si alguna frase del enunciado no se cumple, el error está en la traducción. Y compará con un vértice vecino: tiene que dar peor.

Un ejercicio resuelto, paso a paso

Un taller textil fabrica mochilas chicas y grandes. Una chica lleva 1 m de tela y 2 horas de costura; una grande, 2 m de tela y 3 horas. Por semana hay 100 m de tela y 170 horas de costura. Cada chica deja una ganancia de $ 3000 y cada grande, de $ 5000. ¿Cuántas de cada una conviene fabricar para ganar lo más posible?

Variables: x = mochilas chicas por semana, y = mochilas grandes por semana.

Restricciones, una por recurso:

tela: x + 2y ≤ 100
costura: 2x + 3y ≤ 170
x ≥ 0 , y ≥ 0

Objetivo: maximizar z = 3000x + 5000y.

Vértices: (0, 0); en el eje x manda la costura, (85, 0), porque (100, 0) necesitaría 200 horas; en el eje y manda la tela, (0, 50), porque (0, 170/3) necesitaría más de 113 m; y el corte de las dos:

x = 100 − 2y → 2(100 − 2y) + 3y = 170
200 − y = 170 → y = 30 , x = 40

Tabla:

(0, 0) → 0
(85, 0) → 255 000
(40, 30) → 120 000 + 150 000 = 270 000
(0, 50) → 250 000

Respuesta: hay que fabricar 40 mochilas chicas y 30 grandes por semana, y la ganancia es de $ 270 000.

Control en el enunciado: tela, 40 + 60 = 100 m ✔ (se usa toda); costura, 80 + 90 = 170 h ✔ (también). Un vecino, (85, 0), da menos ✔.

Dónde se pierde el punto: armar las restricciones «por producto» en vez de «por recurso», por ejemplo x + 2 ≤ 100: cada restricción tiene que sumar lo que usan las dos mochilas de un mismo recurso.

Y uno del nivel del parcial

Una cadena de heladerías compra por semana dulce de leche común, a $ 900 el kilo, y repostero, a $ 1500 el kilo. Necesita al menos 12 kg de repostero; la común no puede superar el triple de la repostera; y entre las dos tiene que comprar no menos de 40 kg ni más de 100 kg. ¿Cuántos kilos de cada una tiene que comprar para gastar lo menos posible, y cuánto gasta?

Variables: x = kg de común, y = kg de repostero, por semana.

Restricciones:

y ≥ 12
x ≤ 3y → x − 3y ≤ 0
40 ≤ x + y ≤ 100
x ≥ 0

Objetivo: minimizar C = 900x + 1500y.

Vértices: son cinco fronteras (la doble cuenta como dos). Los cortes que cumplen todo:

y = 12 con x + y = 40 → (28, 12)
y = 12 con x = 3y → (36, 12)
x = 3y con x + y = 100 → (75, 25)
x + y = 100 con x = 0 → (0, 100)
x + y = 40 con x = 0 → (0, 40)

El corte de x = 3y con x + y = 40 es (30, 10), que tiene y < 12: queda afuera. Es un pentágono.

Tabla de costos:

(28, 12) → 25 200 + 18 000 = 43 200
(36, 12) → 32 400 + 18 000 = 50 400
(75, 25) → 67 500 + 37 500 = 105 000
(0, 100) → 150 000
(0, 40) → 60 000

Respuesta: tiene que comprar 28 kg de común y 12 kg de repostero, y gasta $ 43 200 por semana.

Control en el enunciado: repostero 12 ≥ 12 ✔; común 28 ≤ 3·12 = 36 ✔; total 40, entre 40 y 100 ✔. Tiene sentido: compra el mínimo total, con lo justo de la cara.

Dónde se pierde el punto: traducir «la común no puede superar el triple de la repostera» como y ≤ 3x. Con eso cambia la región entera y el mínimo sale en otro lado.

Dónde se cae la mayoría

Dar vuelta una proporción: «x es al menos el doble de y» es x ≥ 2y, no y ≥ 2x.
Poner las cantidades de un recurso en la fila equivocada: cada restricción es un recurso, con lo que usa cada producto de ESE recurso.
Contestar «x = 40, y = 30» en vez de responder en el contexto: cuántas de cada cosa y cuánto se gana o se gasta.
Tomar como variables lo que no pregunta el enunciado: si pide horas de cada taller, las variables son horas.
En un problema de mínimo, olvidarse de que la región puede ser no acotada y buscarle un máximo que no existe.

Hasta acá la explicación. La práctica es la otra mitad: 7 ejercicios de este tema, en cuatro niveles, que no te dicen sólo si está bien al final sino que te corrigen en cada paso y te explican por qué. Además trae una animación que muestra la idea en movimiento.

Practicar Problemas de programación lineal →

Dónde entra este tema en el parcial

Segundo parcial — Camperas y buzos25 puntos · resuelto paso a paso

Los otros temas de la unidad 5

Programación lineal en ℝ²

Ver todos los temas de Álgebra (71)