Álgebra (71) · Unidad 5 — Programación lineal en ℝ²
Parámetros en la función objetivo y en la región
Cuando cambian los precios, cambia la inclinación de las curvas de nivel y el óptimo salta de un vértice a otro; justo en el cambio, las curvas son paralelas a un lado y el óptimo es toda la arista. Pedir que el máximo esté en un vértice es pedir que z valga ahí más que en todos los otros vértices: un sistema de desigualdades en el parámetro.
La explicación
Qué cambia cuando cambian los precios
La región sale de las restricciones: los recursos, los pedidos. La función objetivo sale de los precios. Si sube el precio de un producto, la región no se mueve, pero las curvas de nivel se inclinan distinto, y la última que toca la región puede tocarla en otro vértice. Es lo que pasa en la vida real: si las medialunas empiezan a dejar más que las facturas, conviene hacer más medialunas, hasta donde lo permitan los recursos.
Las pendientes deciden
Las curvas de nivel de z = p·x + q·y tienen pendiente −p/q. Cada lado de la región también tiene su pendiente. El óptimo está en el vértice donde la inclinación de las curvas de nivel queda «entre» las de los dos lados que llegan a él. Y cuando las curvas de nivel son paralelas a un lado, la última curva que toca la región lo toca entero: el óptimo es toda la arista.
Por ejemplo, en la región x + y ≤ 8 ; x ≤ 6 ; y ≤ 5 ; x, y ≥ 0 (vértices (0, 0), (6, 0), (6, 2), (3, 5) y (0, 5)), la función z = x + y tiene curvas de nivel de pendiente −1, igual que el lado x + y = 8: su máximo, 8, se alcanza en todo el segmento de (6, 2) a (3, 5). Si x pesa un poco más, el óptimo cae en (6, 2); si pesa un poco menos, en (3, 5).
¿Para qué valores del parámetro el máximo está en un vértice dado?
El método que no falla es algebraico, con la tabla de vértices:
2. Escribí z en cada vértice, en función del parámetro.
3. Pedí que z en el vértice elegido sea mayor o igual que en cada uno de los otros. Cada comparación es una inecuación en el parámetro.
4. La respuesta es la intersección de todas. En los extremos del intervalo hay empate con un vecino: el máximo se alcanza en una arista.
Para un mínimo, lo mismo con «menor o igual». Y si piden el máximo en un vértice y el mínimo en otro, se resuelven las dos listas de condiciones y se intersecan.
En el ejemplo de arriba, con z = αx + y y el máximo en (6, 2): z vale 6α + 2 ahí, 3α + 5 en (3, 5), 5 en (0, 5), 6α en (6, 0) y 0 en el origen. Las condiciones son 6α + 2 ≥ 3α + 5 (o sea α ≥ 1), 6α + 2 ≥ 5 (α ≥ 1/2), 6α + 2 ≥ 6α (siempre) y 6α + 2 ≥ 0 (α ≥ −1/3). Todas juntas: α ≥ 1.
Una condición que fija la función
Si de f = αx + βy sólo se sabe una relación entre los coeficientes (por ejemplo, α + β = 4) y algo sobre el óptimo, hay que juntar las dos cosas. Un empate es una ecuación: «el máximo se alcanza en todo el lado de P a Q» dice f(P) = f(Q). Con esa ecuación y la relación entre α y β se despejan los dos, y la función queda fija: ya se la puede evaluar en cualquier otra región.
Parámetros en las restricciones
Si el parámetro está en una restricción, lo que se mueve es la región. Las preguntas típicas son «para qué valor el punto P es esquina» o «para qué valor P está en la región». Para que P sea esquina tiene que estar sobre dos fronteras: si las restricciones sin parámetro lo tocan una sola vez (o ninguna), la frontera con parámetro tiene que pasar por P, y eso se despeja reemplazando P en la ecuación. Después se verifica que, con esos valores, P cumpla todas las desigualdades.
El control que conviene hacer siempre
Probá un valor del parámetro de adentro de tu respuesta y uno de afuera, y en los dos hacé la tabla de vértices completa: con el de adentro el óptimo tiene que estar donde se pidió, y con el de afuera en otro lado. En un extremo del intervalo, la tabla tiene que mostrar un empate.
Sea R: x + y ≤ 8 ; x ≤ 6 ; y ≤ 5 ; x ≥ 0 ; y ≥ 0, y sea z = αx + y. Hallar todos los valores de α para los que el máximo de z sobre R se alcanza en (6, 2).
Vértices de R: (0, 0), (6, 0), (6, 2) (x = 6 con x + y = 8), (3, 5) (y = 5 con x + y = 8) y (0, 5). No dependen de α.
z en cada vértice:
(6, 0) → 6α
(3, 5) → 3α + 5
(0, 5) → 5
(0, 0) → 0
Las condiciones: z(6, 2) tiene que ser mayor o igual que en cada uno de los otros.
6α + 2 ≥ 3α + 5 → 3α ≥ 3 → α ≥ 1
6α + 2 ≥ 5 → α ≥ 1/2
6α + 2 ≥ 0 → α ≥ −1/3
Respuesta: las cuatro a la vez, α ≥ 1. En α = 1 hay empate con (3, 5): el máximo es toda la arista de (6, 2) a (3, 5). Para α > 1, el máximo está sólo en (6, 2).
Control: con α = 2 (adentro), la tabla da 14, 12, 11, 5, 0: gana (6, 2) ✔. Con α = 1/2 (afuera), da 5, 3, 13/2, 5, 0: gana (3, 5) ✔.
Dónde se pierde el punto: comparar sólo con (6, 0), que es el vecino de abajo: esa condición se cumple siempre y daría «cualquier α». El vecino que pone la cota es el otro, (3, 5).
Sea R: x + a·y ≤ 11 ; b·x − y ≥ 1 ; y ≥ 0. a) Hallar a y b para que (3, 2) sea punto esquina de R. b) Para esos valores, hallar el máximo de z = 2x + 5y en R y el punto donde se alcanza.
a) ¿Sobre qué fronteras puede estar (3, 2)? La única sin parámetro es y = 0, y (3, 2) no está sobre ella. Para ser esquina necesita dos fronteras: tienen que ser las dos con parámetro.
b·x − y = 1 en (3, 2): 3b − 2 = 1 → b = 1
Con a = 4 y b = 1, R es x + 4y ≤ 11 ; x − y ≥ 1 ; y ≥ 0, y (3, 2) cumple las tres (la tercera sin igual): es esquina ✔.
b) Los otros vértices: y = 0 con x − y = 1 da (1, 0); y = 0 con x + 4y = 11 da (11, 0). Es el triángulo de vértices (1, 0), (11, 0) y (3, 2).
z(11, 0) = 22
z(3, 2) = 6 + 10 = 16
El máximo es 22, en (11, 0). No está en el punto del ítem a): que un punto sea esquina no quiere decir que sea el óptimo.
Control: un punto de adentro, (4, 1), cumple 8 ≤ 11 ✔ y 3 ≥ 1 ✔, y da z = 13, menos que 22 ✔.
Dónde se pierde el punto: en a), buscar una sola condición. Con una sola frontera, (3, 2) queda en el medio de un lado, no en una esquina.
Dónde se cae la mayoría
- Comparar z en el vértice elegido sólo con un vecino: hay que compararlo con todos los vértices, o al menos con los dos vecinos y verificar el resto.
- Creer que al cambiar los precios cambia la región: la región sale de las restricciones y no se mueve; lo que cambia es qué vértice gana.
- Tomar la pendiente de las curvas de nivel de z = px + qy como p/q o como q/p: es −p/q.
- En un empate, contestar sólo los dos vértices: el óptimo es toda la arista que los une.
- Hallar el parámetro que pone el punto sobre una frontera y no verificar que, con ese valor, el punto cumpla las demás restricciones.
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 Parámetros en la función objetivo y en la región →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 ℝ²