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) 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.
La zona sombreada tiene esquinas, y para optimizar necesitas sus coordenadas exactas. Medirlas con una regla en el dibujo da valores aproximados; resolver un sistema de ecuaciones da el valor exacto.
Una frontera es la recta que sale al cambiar el signo de una condición por =. Un vértice es una esquina de la región: el punto donde se cruzan dos fronteras y que cumple además todas las demás condiciones.
Aquí las fronteras son x=0 e y=0 (de x≥0 e y≥0),x=4,y=6 y x+y=8. Cruza dos de ellas, resuelve el sistema y comprueba el punto en las cinco condiciones. No todo cruce es vértice. Si las dos fronteras son inclinadas, resuelve su sistema por reducción, como en Gauss (hay un ejemplo en «Para ir más allá»).
Cómo empezar tu ejercicio
Cuándo usar esta idea: Piden las coordenadas de las esquinas de la región factible.
Elige dos fronteras que formen esquina, resuelve su sistema y sustituye el punto en las demás condiciones.
Un ejemplo, paso a paso
Calcula todos los vértices de x,y≥0,x≤4,y≤6 y x+y≤8.
Sigue el borde verde: sus esquinas son los cinco vértices factibles. La esquina del rectángulo (4,6) queda fuera porque 4+6>8.
Mira la última columna: los puntos con «no» no son esquinas de la región.
Cruce de
Punto
¿Cumple todo?
x=0 y y=0
(0,0)
sí
x=4 y y=0
(4,0)
sí
x=0 y y=6
(0,6)
sí
x=4 y x+y=8
(4,4)
sí
y=6 y x+y=8
(2,6)
sí
x=4 y y=6
(4,6)
no, 4+6=10>8
y=0 y x+y=8
(8,0)
no, 8>4
x=0 y x+y=8
(0,8)
no, 8>6
Las fronteras son cinco rectas: x=0,y=0,x=4,y=6 y x+y=8. Cada vértice sale del cruce de dos de ellas. Con cinco rectas hay 10 pares, pero 2 son paralelos (x=0 con x=4 e y=0 con y=6) y nunca se cruzan: quedan 8 cruces.
Los cruces que no necesitan cálculo son (0,0) (x=0 con y=0),(4,0) (x=4 con y=0) y (0,6) (x=0 con y=6).
Cruce de x=4 con x+y=8: sustituimos x por 4 y se conserva el resto, 4+y=8. Restamos 4 en ambos miembros: y=4. El punto es (4,4).
Cruce de y=6 con x+y=8: sustituimos y por 6, x+6=8. Restamos 6 en ambos miembros: x=2. El punto es (2,6).
Faltan tres cruces. x=4 con y=6 da (4,6). Con y=0 en x+y=8 queda x+0=8, luego (8,0). Con x=0 queda 0+y=8, luego (0,8). La tabla prueba los ocho cruces en todas las condiciones: solo valen los que no incumplen ninguna.
Lo que obtenemos: Los vértices son (0,0),(4,0),(4,4),(2,6) y (0,6).
Ojo con este error: Leer las coordenadas con una regla sobre el dibujo: la escala engaña y los vértices se calculan.
Para ir más allá
Los ejes x=0 e y=0 son fronteras aquí porque se exige x,y≥0. En un recinto general, un eje solo es frontera si alguna condición lo impone.
Cruce de dos rectas inclinadas. Para x+y=5 y 2x+y=8, resta la primera a la segunda: (2x+y)−(x+y)=8−5, luego x=3. En la primera, 3+y=5, luego y=2. El punto es (3,2). Es vértice si cumple las demás condiciones; por ejemplo, en la región x,y≥0,x+y≤5,2x+y≤8 lo cumple: 3≥0,2≥0,3+2=5≤5 y 2⋅3+2=8≤8.
Ahora prueba la idea
Cruza x=3 con x+y=7. ¿Es vértice de la región que además exige y≤3?
Ver la respuesta y el porqué
El cruce es (3,4) y no es vértice.
Sustituimos x por 3: 3+y=7. Restando 3 en ambos miembros, y=4. Pero 4>3 incumple y≤3, así que el cruce no es una esquina de la región.