Álgebra (71) · Unidad 6 — Algoritmo simplex
Problemas de maximización y cambio de variables
Un problema con tres o más variables se plantea igual que en el plano —variables con su unidad, una restricción por recurso o condición, la función objetivo— y se resuelve con la tabla. Las frases «no supera en más de…» y «al menos el doble de…» se pasan a la forma «≤» con término ≥ 0, y una cota como x₁ ≥ 3 se saca con el cambio y₁ = x₁ − 3.
La explicación
Plantear, como en la unidad 5, pero sin dibujo
El planteo es el mismo que en programación lineal en ℝ²; lo que cambia es que con tres variables no hay dibujo que ayude, así que cada restricción tiene que salir del texto.
2. Una restricción por recurso (lo que usa cada unidad de cada producto ≤ lo que hay) y una por cada condición del enunciado.
3. La función objetivo: lo que se gana (o se cobra) por cada unidad, sumado.
4. Revisar que quede estándar: todo «≤», términos ≥ 0. Recién ahí se arma la tabla.
Porcentajes: multiplicar para sacar las comas
Si un producto lleva 60 % de un insumo, cada kilo usa 0,6 kg: 0,6x1 + 0,5x2 + 0,2x3 ≤ 160. Multiplicar por 10 los dos miembros no cambia la restricción y deja la tabla sin comas: 6x1 + 5x2 + 2x3 ≤ 1600. Lo único que cambia es la lectura de la holgura: en esa fila, s = 200 son 20 kg que sobran.
Las frases que más se toman
x1 ≤ 2x2 + 10 → x1 − 2x2 ≤ 10
«x2 no supera en más de 12 a x1»
x2 ≤ x1 + 12 → −x1 + x2 ≤ 12
«x1 es al menos el doble de x2»
x1 ≥ 2x2 → −x1 + 2x2 ≤ 0
La última es un «≥», pero como el término independiente es 0, pasando todo de un lado queda un «≤» con término 0, que sí es estándar (0 ≥ 0). Lo mismo con «no puede ser más de la mitad del total». En cambio «al menos 20 unidades» (x1 ≥ 20) no se arregla así: ése va por el dual, en 6.8.
Una restricción con término 0 trae una sorpresa en el simplex: su cociente puede dar 0, y entonces se pivotea en esa fila y z no sube en ese paso. No es un error: la base cambia, el punto sigue siendo el mismo, y en el pivoteo siguiente z ya aumenta.
Cotas inferiores: el cambio de variables
Si el enunciado pide x1 ≥ 3 (un pedido mínimo, un compromiso), el problema no es estándar: el origen no es factible. Se arregla corriendo el origen.
2. Reemplazá en cada restricción y pasá los números a la derecha: x1 + x2 ≤ 14 con x1 ≥ 3 y x2 ≥ 2 queda y1 + y2 ≤ 14 − 3 − 2 = 9.
3. Reemplazá en z: aparece un número suelto. z = 4x1 + 3x2 = 4y1 + 3y2 + 18. Se maximiza la parte con variables; el 18 se suma al final.
4. Resolvé el estándar en las y, y volvé a las variables originales: x1 = y1 + 3, x2 = y2 + 2, y z = zy + 18.
Si al reemplazar algún término independiente queda negativo, el problema nuevo no es estándar (y a lo mejor ni tiene solución factible): revisá las cuentas antes de seguir.
La respuesta va en el contexto
La tabla final da números; el problema pide decisiones. «x1 = 100» se contesta «conviene armar 100 kg del Clásico», con el ingreso en pesos y, si importa, qué recurso sobra. Si hubo cambio de variables, la respuesta es en las x, no en las y.
El control que conviene hacer siempre
Reemplazá la respuesta en el enunciado original, no en el planteo: cada recurso usado tiene que ser ≤ lo disponible, cada condición se tiene que cumplir con las palabras del texto («¿impuestos supera en más de 12 a auditoría?»), y el ingreso tiene que coincidir con la esquina de la tabla final (más la constante, si hubo cambio de variables).
Una tostaduría arma tres blends de café en grano: el Clásico (60 % colombiano y 40 % brasileño), el Suave (50 % colombiano y 50 % brasileño) y el Fuerte (20 % colombiano, 40 % brasileño y 40 % robusta). Tiene en stock 160 kg de colombiano, 200 kg de brasileño y 160 kg de robusta, y vende el kilo a 9, 8 y 14 miles de pesos. ¿Cuántos kilos de cada blend conviene armar para que el ingreso sea máximo?
Variables: x1, x2, x3 = kilos de Clásico, Suave y Fuerte, todos ≥ 0.
Restricciones, una por café, multiplicadas por 10 para sacar las comas (la de robusta, además, dividida por 4):
brasileño: 4x1 + 5x2 + 4x3 ≤ 2000
robusta: x3 ≤ 400
Objetivo: maximizar z = 9x1 + 8x2 + 14x3 (miles de pesos). Es estándar.
Primer pivoteo. Entra x3 (indicador 14). Cocientes 1600/2 = 800, 2000/4 = 500 y 400/1 = 400: fila 3. A la fila 1 se le resta 2F3, a la 2, 4F3, y a los indicadores, 14F3:
( 4 5 0 │ 0 1 −4 │ 400 )
( 0 0 1 │ 0 0 1 │ 400 )
( 9 8 0 │ 0 0 −14 │ z − 5600 )
Segundo pivoteo. Entra x1 (indicador 9). Cocientes 800/6 ≈ 133 y 400/4 = 100: fila 2, pivote 4.
( 1 5/4 0 │ 0 1/4 −1 │ 100 )
( 0 0 1 │ 0 0 1 │ 400 )
( 0 −13/4 0 │ 0 −9/4 −5 │ z − 6500 )
Ningún indicador positivo: es final. Básicas s1 = 200, x1 = 100, x3 = 400; x2 = 0.
Respuesta: conviene armar 100 kg de Clásico, nada de Suave y 400 kg de Fuerte, con un ingreso de 6500 miles de pesos. Se usan enteros el brasileño y la robusta; del colombiano sobran s1 = 200 décimos de kilo, o sea 20 kg (la fila estaba multiplicada por 10).
Control con el enunciado: colombiano 0,6·100 + 0,2·400 = 60 + 80 = 140 ≤ 160 ✔ (sobran 20); brasileño 40 + 160 = 200 ✔; robusta 0,4·400 = 160 ✔; ingreso 900 + 5600 = 6500 ✔.
Dónde se pierde el punto: leer s1 = 200 como «sobran 200 kg» sin acordarse de que la fila se multiplicó por 10; o escribir los porcentajes por fila de blend en vez de por fila de café (cada restricción es un café: suma lo que cada blend usa de ese café).
Un taller arma bicicletas urbanas (x₁) y plegables (x₂). Esta semana tiene 14 cuadros (cada bicicleta usa uno) y 22 horas de armado (una urbana lleva 2 horas y una plegable, 1), y ya tiene encargadas al menos 3 urbanas y al menos 2 plegables. La ganancia es de 4 y 3 decenas de miles de pesos por bicicleta. ¿Cuántas de cada una conviene armar?
El planteo: maximizar z = 4x1 + 3x2 sujeta a x1 + x2 ≤ 14 ; 2x1 + x2 ≤ 22 ; x1 ≥ 3 ; x2 ≥ 2. No es estándar: las cotas son 3 y 2, no 0.
El cambio de variables: y1 = x1 − 3 y y2 = x2 − 2, las dos ≥ 0.
2(y1 + 3) + (y2 + 2) ≤ 22 → 2y1 + y2 ≤ 14
z = 4y1 + 3y2 + 12 + 6 = 4y1 + 3y2 + 18
Se maximiza zy = 4y1 + 3y2 con esas dos restricciones: ése sí es estándar.
El simplex: entra y1 (indicador 4), cocientes 9 y 14/2 = 7: fila 2. Queda y1 = 7, zy = 28, y a y2 le queda el indicador 3 − 2 = 1. Entra y2: en su columna hay ½ y ½, cocientes 2 / ½ = 4 y 7 / ½ = 14: fila 1. Tabla final:
( 1 0 │ −1 1 │ 5 )
( 0 0 │ −2 −1 │ zy − 32 )
y2 = 4, y1 = 5, zy = 32.
Volver a las variables originales: x1 = 5 + 3 = 8, x2 = 4 + 2 = 6, z = 32 + 18 = 50.
Respuesta: conviene armar 8 urbanas y 6 plegables, y se ganan 50 decenas de miles de pesos (500 mil). Se usan los 14 cuadros y las 22 horas.
Control con el enunciado: 8 + 6 = 14 ✔, 16 + 6 = 22 ✔, 8 ≥ 3 ✔, 6 ≥ 2 ✔, z = 32 + 18 = 50 ✔. Por los vértices de la región original: (3, 2) da 18, (10, 2) da 46, (8, 6) da 50 y (3, 11) da 45.
Dónde se pierde el punto: contestar y1 = 5 e y2 = 4, o z = 32, olvidándose de volver a las x y de sumar el 18.
Dónde se cae la mayoría
- Traducir «x₁ no supera en más de 10 al doble de x₂» como x₁ + 10 ≤ 2x₂: se escribe x₁ ≤ 2x₂ + 10, o sea x₁ − 2x₂ ≤ 10.
- Creer que «al menos el doble» no es estándar: x₁ ≥ 2x₂ se escribe −x₁ + 2x₂ ≤ 0, con término 0, y entra en la tabla.
- En el cambio de variables, olvidarse de restar la cota en cada restricción, o de sumar la constante que aparece en z al final.
- Contestar en las y después de un cambio de variables: la respuesta es x₁ = y₁ + 3.
- Asustarse con un cociente 0: se pivotea igual, z no cambia en ese paso y sube en el siguiente.
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 maximización y cambio de variables →Los otros temas de la unidad 6
Algoritmo simplex