Álgebra (71) · Unidad 6 — Algoritmo simplex
Minimizar con el simplex
En una región estándar (restricciones «≤» con término ≥ 0 y variables ≥ 0), minimizar f es maximizar −f: se arma la tabla con los coeficientes de −f, se resuelve el máximo, y el mínimo de f es el opuesto de ese máximo, en el mismo punto.
La explicación
El mínimo de f es el máximo de −f, cambiado de signo
El simplex de la materia sólo sabe maximizar. Para minimizar se usa una idea simple: si en un punto f es lo más chica posible, en ese mismo punto −f es lo más grande posible, y sus valores son opuestos.
y se alcanzan en el mismo punto
Con números: si en la región f toma los valores 0, 6, −10 y −9 en los puntos esquina, −f toma 0, −6, 10 y 9. El mayor de −f es 10, en el mismo punto donde f vale −10, que es su menor valor.
El procedimiento
2. Llamá g = −f y cambiale el signo a todos los coeficientes: si f = x1 − 3x2, entonces g = −x1 + 3x2.
3. Armá la tabla con los indicadores de g y resolvé el máximo con las reglas de siempre.
4. La esquina final dice «g − v»: el máximo de g es v, así que el mínimo de f es −v, en el mismo punto.
El paso 4 es donde más se pierden puntos. La tabla termina diciendo un número positivo, y la respuesta del mínimo tiene el signo cambiado. Conviene escribir las dos cosas: «máx g = 10, entonces mín f = −10».
Qué dicen los indicadores
En la tabla de g, un indicador positivo es una variable que, al aumentar, hace bajar f. Por eso en f = x1 − 3x2 entra primero x2: cada unidad de x2 baja f en 3.
Un caso que se resuelve sin pivotear: si todos los coeficientes de f son ≥ 0, los de g son ≤ 0 y la tabla inicial ya es final. El mínimo es 0, en el origen: tiene sentido, porque f no puede ser negativa si todas las variables son ≥ 0 y sus coeficientes también.
En ℝ², el mismo problema por el método gráfico
Con dos variables conviene controlar con la tabla de puntos esquina, como en la unidad 5: se evalúa f en cada uno y se busca el menor. Las rectas de nivel de f se corren en el sentido en que f baja, que es el sentido en que −f sube; el último punto de la región que tocan es el mínimo. La misma región sirve para el máximo de f: es el vértice del otro extremo.
Por ejemplo, minimizar f = x1 − 3x2 sujeta a x1 + x2 ≤ 6 ; −x1 + 2x2 ≤ 6. Los puntos esquina son (0, 0), (6, 0), (2, 4) y (0, 3), con f = 0, 6, −10 y −9. El mínimo es −10, en (2, 4), y el máximo 6, en (6, 0).
El control que conviene hacer siempre
Reemplazá el punto en f (la original, no en g): tiene que dar el mínimo que contestaste, con su signo. Si el problema es de ℝ², evaluá f en los otros puntos esquina y fijate que ninguno dé menos. Y si te da un mínimo positivo cuando f tiene coeficientes negativos, desconfiá: casi seguro te olvidaste de cambiar el signo al final, o al principio.
Minimizar f = x₁ − 3x₂ sujeta a x₁ + x₂ ≤ 6 ; −x₁ + 2x₂ ≤ 6 ; x₁ ≥ 0, x₂ ≥ 0, convirtiéndolo en un problema estándar de maximización. Controlar con el método gráfico.
¿Región estándar? Dos «≤» con términos 6 y 6, variables ≥ 0: sí.
Pasar a máximo: g = −f = −x1 + 3x2. Tabla inicial:
−1 2 │ 0 1 │ 6
─────────────
−1 3 │ 0 0 │ g
Primer pivoteo. Entra x2 (indicador 3). Cocientes 6/1 = 6 y 6/2 = 3: fila 2, pivote 2.
( −½ 1 │ 0 ½ │ 3 )
( ½ 0 │ 0 −3/2 │ g − 9 )
g = 9 en (0, 3). Queda el indicador ½ de x1.
Segundo pivoteo. Entra x1. Sólo la primera fila tiene coeficiente positivo: cociente 3 / (3/2) = 2, pivote 3/2.
( 0 1 │ ⅓ ⅓ │ 4 )
( 0 0 │ −⅓ −4/3 │ g − 10 )
Es final: máx g = 10, en x1 = 2, x2 = 4.
Respuesta: mín f = −10, en (2, 4).
Control por el método gráfico: los puntos esquina son (0, 0), (6, 0), (2, 4) y (0, 3).
f(2, 4) = 2 − 12 = −10 , f(0, 3) = −9
El menor es −10, en (2, 4) ✔. De paso, el máximo de f es 6, en (6, 0).
Dónde se pierde el punto: contestar «el mínimo es 10» leyendo la esquina de la tabla de g. El control en f lo caza: f(2, 4) = −10.
Minimizar f = −4x₁ + x₂ − 5x₃ sujeta a x₁ + x₂ + 2x₃ ≤ 15 ; x₁ + x₂ + x₃ ≤ 8 ; x₁, x₂, x₃ ≥ 0, pasándolo a un problema de maximización y resolviéndolo con el simplex. Dar el valor mínimo de f y dónde se alcanza.
Pasar a máximo: g = −f = 4x1 − x2 + 5x3. Ojo con x2: su coeficiente en f es +1, así que en g es −1.
1 1 1 │ 0 1 │ 8
───────────────
4 −1 5 │ 0 0 │ g
Primer pivoteo. Entra x3 (5). Cocientes 15/2 = 7,5 y 8/1 = 8: fila 1, pivote 2.
( ½ ½ 0 │ −½ 1 │ ½ )
( 3/2 −7/2 0 │ −5/2 0 │ g − 75/2 )
g = 75/2 = 37,5. Queda el indicador 3/2 de x1.
Segundo pivoteo. Entra x1. Cocientes (15/2) / ½ = 15 y ½ / ½ = 1: fila 2, pivote ½.
( 1 1 0 │ −1 2 │ 1 )
( 0 −5 0 │ −1 −3 │ g − 39 )
Final: máx g = 39, con x3 = 7, x1 = 1, x2 = 0.
Respuesta: mín f = −39, en (1, 0, 7).
Control: 1 + 0 + 14 = 15 ✔, 1 + 0 + 7 = 8 ✔, f = −4 + 0 − 35 = −39 ✔. Tiene sentido que x2 quede en 0: en f suma, así que para minimizar no conviene usarla.
Dónde se pierde el punto: pasar f a g cambiando el signo sólo a los negativos (quedaría g = 4x1 + x2 + 5x3, otro problema), o contestar mín f = 39.
Dónde se cae la mayoría
- Contestar el máximo de −f como si fuera el mínimo de f: si la tabla final dice «g − 10», el mínimo de f es −10, no 10.
- Cambiarle el signo sólo a algunos coeficientes de f al pasar a −f: se cambian todos.
- Armar la tabla con los coeficientes de f y elegir el indicador más negativo: en esta materia se maximiza −f con la regla de siempre.
- Usar este método con restricciones «≥»: la región tiene que ser estándar. Los mínimos con «≥» se hacen por el dual.
- Dar el punto en las variables de otra tabla, o evaluar el control en −f en vez de en f.
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 Minimizar con el simplex →Los otros temas de la unidad 6
Algoritmo simplex