Álgebra (71) · Unidad 6 — Algoritmo simplex
El problema estándar de maximización y la tabla inicial
El simplex resuelve problemas de máximo con restricciones «≤», términos independientes no negativos y variables no negativas. Se agrega una holgura por restricción —lo que le falta para llegar al tope— y se arma la tabla inicial, que representa el origen: las holguras son las básicas y z vale 0.
La explicación
Por qué hace falta otro método
En la unidad 5 un problema de programación lineal con dos variables se resolvía dibujando la región de factibilidad y evaluando la función objetivo en los puntos esquina. Con tres variables ya no se puede dibujar cómodo, y con cuatro no se puede dibujar. Además la cantidad de puntos esquina crece muy rápido: con 3 variables y 3 restricciones hay que probar hasta 20 combinaciones de fronteras para encontrarlos todos.
El método simplex no los prueba todos. Arranca en un punto esquina (el origen), y en cada paso se mueve a un punto esquina vecino en el que z es mayor. Cuando desde donde está no hay forma de aumentar z, se frena: ése es el máximo. Todo se hace con operaciones de fila sobre una tabla, las mismas de Gauss.
El problema estándar de maximización
El simplex, tal como se ve en la materia, trabaja sobre un problema con esta forma exacta:
sujeta a A·X ≤ b, con bi ≥ 0 para todo i
x1 ≥ 0, …, xn ≥ 0
Tres condiciones, y las tres se chequean antes de empezar: es un máximo; todas las restricciones son ≤ con el término independiente mayor o igual que 0; y todas las variables son no negativas. Los coeficientes de z y los de A sí pueden ser negativos: z = 2x1 − x2 + 3x3 está permitido.
A veces una restricción viene disfrazada. −2x1 + x2 ≥ −5 no parece de la forma, pero multiplicando los dos miembros por −1 (que da vuelta la desigualdad) queda 2x1 − x2 ≤ 5, que sí lo es. En cambio x1 + x2 ≥ 6 no se arregla así: al multiplicar por −1 el término queda −6 < 0. Los mínimos, las cotas como x1 ≥ 4 y las restricciones «≥» se llevan a esta forma en los temas 6.5, 6.6 y 6.8.
Las variables de holgura
El simplex trabaja con igualdades, así que a cada restricción «≤» se le suma una variable nueva que mide lo que le falta para llegar al tope:
s1 = 10 − (x1 + x2 + 2x3) ≥ 0
La holgura dice dónde está el punto respecto de esa restricción: s > 0, se cumple con margen (en un problema de producción, sobra recurso); s = 0, se cumple justo (el punto está sobre la recta o el plano frontera); s < 0, no se cumple: el punto está fuera de la región. Por eso se pide s ≥ 0, igual que a las x.
Va una holgura por cada restricción «≤», y ninguna para las condiciones xi ≥ 0.
La tabla simplex inicial
Con n variables y m restricciones, la tabla tiene m filas de restricciones y abajo la fila de indicadores; las columnas son las n de las x, las m de las holguras y la de b. En la práctica se separan con dos rayas verticales (entre las x y las holguras, y antes de b) y no se escribe fila de títulos: se sobreentiende el orden x1, …, xn, s1, …, sm.
2. La fila de indicadores son los coeficientes de z con su signo, ceros debajo de las holguras, y en la esquina «z».
3. El bloque de las holguras queda formado por la identidad.
Ojo con el paso 2: hay libros (sobre todo en inglés) que ponen −c en la última fila y eligen «el más negativo». La convención de esta materia es la otra: la fila arranca siendo c, y después se elige el mayor indicador positivo. Mezclarlas es el error que más confunde.
Qué solución representa la tabla inicial
Las columnas de la identidad son las de las variables básicas: al principio, las holguras. Las demás son no básicas y valen 0. La solución factible básica se lee así: no básicas en 0 y cada básica igual al b de la fila donde tiene su 1.
Es el origen, que es un punto esquina porque b ≥ 0 (por eso se pide). Todavía no se produjo nada y sobra todo.
Cada indicador positivo avisa que conviene aumentar esa variable: con c3 = 4, cada unidad de x3 suma 4 a z. ¿Hasta cuánto puede crecer? Hasta que la primera holgura llegue a 0: en cada fila con coeficiente positivo en esa columna, el tope es bi / ai3, y manda el menor. Ése es el primer paso del simplex, que se ve entero en 6.3.
El control que conviene hacer siempre
Contá las columnas: tienen que ser n + m + 1. Mirá que el bloque de las holguras sea la identidad, que los b sean todos ≥ 0 y que cada indicador tenga el mismo signo que el coeficiente de z. Y reemplazá la solución inicial en cada ecuación con holgura: 0 + 0 + 0 + s1 = b1 ✔.
Maximizar z = 3x₁ + 2x₂ + 4x₃ sujeta a x₁ + x₂ + 2x₃ ≤ 10 ; 2x₁ + x₂ + x₃ ≤ 14 ; x₁ ≥ 0, x₂ ≥ 0, x₃ ≥ 0. Plantear el sistema con holguras, armar la tabla simplex inicial, decir qué solución representa y qué variable conviene aumentar primero.
¿Es estándar? Es un máximo, las dos restricciones son ≤ con términos 10 y 14 (no negativos) y las tres variables son no negativas. Sí.
El sistema con holguras: una por restricción.
2x1 + x2 + x3 + s2 = 14
xi ≥ 0 , sj ≥ 0
La tabla inicial (columnas x1, x2, x3 │ s1, s2 │ b):
2 1 1 │ 0 1 │ 14
───────────────
3 2 4 │ 0 0 │ z
Son 3 + 2 + 1 = 6 columnas, la identidad está debajo de s1 y s2, y los indicadores son 3, 2 y 4: los coeficientes de z con su signo.
La solución que representa: básicas s1 = 10 y s2 = 14; no básicas x1 = x2 = x3 = 0; z = 0. Es el punto esquina (0, 0, 0).
Qué conviene aumentar: los tres indicadores son positivos, así que aumentar cualquiera sube z. El mayor es el 4, de x3: cada unidad de x3 suma 4. Con x1 = x2 = 0 las holguras quedan
s2 = 14 − x3 ≥ 0 → x3 ≤ 14
Manda el menor: x3 puede crecer hasta 5, y ahí z = 20. Los topes son bi / ai3 = 10/2 y 14/1.
Control: el punto (0, 0, 5) cumple 0 + 0 + 10 = 10 ≤ 10 ✔ y 0 + 0 + 5 = 5 ≤ 14 ✔, y es otro punto esquina: está sobre la primera frontera y sobre dos planos coordenados.
Dónde se pierde el punto: en tomar el tope más grande. Con x3 = 14 la primera holgura daría 10 − 28 = −18: el punto se sale de la región.
Un taller de marroquinería fabrica billeteras, cinturones y carteras. Una billetera lleva 2 dm² de cuero y 20 minutos de costura; un cinturón, 3 dm² y 10 minutos; una cartera, 8 dm² y 40 minutos. Esta semana hay 280 dm² de cuero y 1200 minutos de costura, y los cinturones no pueden superar en más de 30 a las billeteras. La ganancia es de 9, 6 y 25 miles de pesos por billetera, cinturón y cartera. Plantear el problema estándar de maximización, armar la tabla inicial y decir qué variable conviene aumentar primero y hasta cuánto.
Las variables: x1 billeteras, x2 cinturones y x3 carteras por semana, todas ≥ 0. La ganancia, en miles de pesos, es z = 9x1 + 6x2 + 25x3.
Las restricciones:
costura: 20x1 + 10x2 + 40x3 ≤ 1200
x2 ≤ x1 + 30
La de costura se puede dividir por 10 (un número positivo no cambia la desigualdad): 2x1 + x2 + 4x3 ≤ 120. La última hay que ordenarla con las variables a la izquierda: −x1 + x2 ≤ 30. «No superar en más de 30» quiere decir que x2 puede llegar a x1 + 30, no más.
¿Es estándar? Máximo, tres restricciones ≤ con términos 280, 120 y 30, todos ≥ 0, y variables no negativas: sí. El coeficiente −1 de x1 no molesta.
La tabla inicial (x1 x2 x3 │ s1 s2 s3 │ b):
2 1 4 │ 0 1 0 │ 120
−1 1 0 │ 0 0 1 │ 30
────────────────
9 6 25 │ 0 0 0 │ z
La solución que representa: no se fabrica nada (x = 0), sobran los 280 dm² de cuero y los 1200 minutos de costura, la tercera restricción tiene margen 30, y z = 0.
Qué conviene aumentar: el mayor indicador positivo es 25, el de las carteras. Con x1 = x2 = 0, el cuero deja hacer hasta 280/8 = 35 carteras y la costura hasta 120/4 = 30. La tercera fila tiene 0 en esa columna: las carteras no la afectan. Manda el menor: hasta 30 carteras, lo que frena la costura. Ahí z = 25·30 = 750 miles de pesos.
Control: 30 carteras usan 240 dm² de cuero (≤ 280 ✔) y 1200 minutos de costura (justo el total ✔), y 0 ≤ 0 + 30 ✔.
Dónde se pierde el punto: escribir la tercera restricción como x1 − x2 ≤ 30 (al revés), o dividir por 10 sólo el primer miembro de la de costura.
Dónde se cae la mayoría
- Poner −c en la fila de indicadores (la convención de los libros en inglés): en la de la práctica la fila arranca siendo los coeficientes de z con su signo.
- Agregar una holgura por cada variable, o también para x ≥ 0: va una por cada restricción «≤», y la no negatividad no lleva.
- Arrancar con una restricción de término negativo, como x₁ − x₂ ≤ −3: el origen no la cumple y la tabla no representa un punto de la región. No es estándar.
- Leer la solución inicial al revés, dándoles a las x los valores de b: en la tabla inicial las básicas son las holguras y las x valen 0.
- Multiplicar una restricción por −1 sin dar vuelta la desigualdad, o cambiándole el signo sólo a un término.
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 El problema estándar de maximización y la tabla inicial →Los otros temas de la unidad 6
Algoritmo simplex