Álgebra (71) · Unidad 5 — Programación lineal en ℝ²
Función objetivo y curvas de nivel: máximo y mínimo
Las curvas de nivel de z = ax + by son rectas paralelas, y al correrlas en un sentido z crece. Si la región es un polígono, el máximo y el mínimo están en vértices: alcanza con una tabla de vértices. Si no es acotada, hay que mirar hacia dónde se escapa la región: puede que no haya máximo, o mínimo, o ninguno de los dos.
La explicación
La función objetivo
En un problema de programación lineal hay algo que se quiere hacer lo más grande posible (una ganancia, un ingreso) o lo más chico posible (un costo, un tiempo). Casi siempre es una función lineal de las dos variables:
Se llama función objetivo, y el problema completo se escribe «maximizar (o minimizar) z sujeta a» las restricciones. Si un kiosco gana $ 300 por alfajor y $ 200 por gaseosa, la ganancia es z = 300x + 200y.
Curvas de nivel
Los puntos donde z vale un número fijo k forman la curva de nivel z = k, que es la recta a·x + b·y = k. Por ejemplo, para z = 3x + 2y, la curva de nivel z = 12 es la recta que pasa por (4, 0) y (0, 6): todos los puntos de esa recta dan 12. Tres cosas que hay que tener claras:
- Todas las curvas de nivel de una misma z son rectas paralelas, porque sólo cambia el término independiente: tienen todas pendiente −a/b (si b ≠ 0; si b = 0 son todas verticales).
- Al correr la recta, z cambia de a poco: en un sentido crece y en el otro decrece. Para saber cuál es cuál alcanza con dibujar dos curvas, por ejemplo z = 0 y z = 12, y mirar hacia dónde quedó la de 12.
- Que la curva z = k toque la región quiere decir que hay algún punto factible donde z vale k.
La idea del método gráfico
Buscar el máximo de z en la región es buscar el mayor k para el que la recta z = k todavía toca la región. Si la recta se va corriendo en el sentido en que z crece, el último contacto con la región es en un borde: un vértice, o un lado entero si el lado es paralelo a las curvas de nivel. Por eso:
1. Hallá todos los vértices.
2. Calculá z en cada uno: es la tabla de vértices.
3. El mayor valor de la tabla es el máximo y el menor es el mínimo. Siempre existen los dos.
4. Si el máximo se repite en dos vértices vecinos, se alcanza en todo el lado que los une (la arista), no sólo en los dos puntos.
En un polígono no hace falta dibujar ninguna curva de nivel: la tabla alcanza. Pero hay que tener todos los vértices, porque si falta uno la tabla puede mentir.
Regiones no acotadas
Si la región se escapa hacia algún lado, la tabla ya no alcanza: puede que z crezca sin tope por el lado abierto. Hay que mirar las curvas de nivel, o «caminar» por el borde que se escapa:
- si al avanzar por la región hacia el lado abierto z crece sin límite, no hay máximo;
- si decrece sin límite, no hay mínimo;
- puede pasar una de las dos cosas, las dos, o ninguna; y en lo que sí existe, se alcanza en un vértice (o en una arista).
Por ejemplo, si la región contiene todos los puntos (0, t) con t ≥ 3, sobre ellos z = 2x + 3y vale 3t, que crece sin tope: z no tiene máximo. Y si en algún vértice z es más chica que en todos los demás y z crece hacia los dos lados por donde la región se abre, ese vértice es el mínimo.
¿En cuál de dos puntos?
Una pregunta típica: «una función lineal alcanza su máximo en A o en B; decidir en cuál». Antes de hacer cuentas, fijate si los dos están en la región. Un punto que no cumple las restricciones no puede ser el máximo, cualquiera sea la función.
El control que conviene hacer siempre
Tomá un punto de adentro de la región y calculá z: tiene que dar entre el mínimo y el máximo que encontraste. Si da más que tu máximo, te falta un vértice en la tabla. Y en una región no acotada, evaluá z en un punto lejano del lado abierto: si da más que tu «máximo», el máximo no existe.
Hallar el máximo y el mínimo de z = 2x − y en la región R: x + y ≤ 7 ; x − y ≤ 3 ; x ≥ 0 ; y ≥ 1, e indicar dónde se alcanzan.
Planteo: primero ver si R es acotada. x ≥ 0 e y ≥ 1 la dejan arriba a la derecha, y x + y ≤ 7 la cierra: es un polígono, así que alcanza con la tabla de vértices.
Los vértices:
y = 1 con x − y = 3 → (4, 1)
x − y = 3 con x + y = 7 → (5, 2)
x + y = 7 con x = 0 → (0, 7)
El tercero sale sumando: 2x = 10, x = 5, y = 2. Los cuatro cumplen todas las restricciones.
La tabla de vértices:
(4, 1) → z = 8 − 1 = 7
(5, 2) → z = 10 − 2 = 8
(0, 7) → z = 0 − 7 = −7
Respuesta: el máximo es z = 8, en (5, 2), y el mínimo es z = −7, en (0, 7).
Control: un punto de adentro, (2, 3), da z = 1, que está entre −7 y 8 ✔. Y tiene sentido: z premia la x y castiga la y, así que el máximo está abajo a la derecha y el mínimo arriba a la izquierda.
Dónde se pierde el punto: olvidarse el vértice (4, 1), que sale de una restricción (y ≥ 1) que no es de las «grandes». Acá no cambia la respuesta, pero en otra función podría ser el máximo.
Sea R: x + 2y ≥ 6 ; 3x + y ≥ 8 ; x ≥ 0 ; y ≥ 0. a) Hallar los puntos esquina de R. b) Determinar, si existen, el máximo y el mínimo de f = 5x + 4y en R. c) Lo mismo para g = x − 2y.
a) Esquinas. Las dos primeras son ≥ y no contienen al origen: R está «afuera», lejos del origen, y no es acotada. Los cortes que sirven:
x + 2y = 6 con 3x + y = 8 → (2, 2)
y = 0 con x + 2y = 6 → (6, 0)
Para (2, 2): x = 6 − 2y, 18 − 6y + y = 8, y = 2. Los cortes (0, 3) y (8/3, 0) caen afuera: (0, 3) da 3 < 8 en la segunda, y (8/3, 0) da 8/3 < 6 en la primera.
b) f = 5x + 4y. Tabla: f(0, 8) = 32, f(2, 2) = 18, f(6, 0) = 30. Pero R no es acotada, así que hay que mirar el lado abierto. Por el eje y, los puntos (0, t) con t ≥ 8 están en R y dan f = 4t, que crece sin tope: f no tiene máximo. Como f tiene los dos coeficientes positivos, alejarse del origen la hace crecer por cualquier lado: el mínimo es 18, en (2, 2).
c) g = x − 2y. Por el eje x, (t, 0) con t ≥ 6 da g = t, que crece sin tope: no hay máximo. Por el eje y, (0, t) con t ≥ 8 da g = −2t, que decrece sin tope: no hay mínimo. g no tiene ni máximo ni mínimo, aunque la tabla de vértices dé números (−16, −2 y 6).
Control: en b), un punto de R como (3, 3) da f = 27 ≥ 18 ✔. En c), (100, 0) está en R y da g = 100, más que cualquier valor de la tabla ✔.
Dónde se pierde el punto: contestar «el máximo de f es 32, en (0, 8)» sacándolo de la tabla. En una región no acotada la tabla sólo sirve para el sentido en que z no se escapa.
Dónde se cae la mayoría
- Hacer la tabla de vértices en una región no acotada y dar como máximo el mayor valor de la tabla: si z crece por el lado abierto, no hay máximo.
- Olvidarse un vértice en la tabla: el máximo puede estar justo en el que falta.
- Decir que el máximo está sólo en dos puntos cuando se repite en dos vértices vecinos: está en toda la arista que los une.
- Elegir como óptimo un punto que no está en la región: primero hay que ver que cumpla las restricciones.
- Confundir el sentido en que crece z con un coeficiente negativo: en z = 2x − y, subir hace bajar a z.
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 Función objetivo y curvas de nivel: máximo y mínimo →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 ℝ²