Álgebra (71) · Unidad 6 — Algoritmo simplex
Pivotear hasta la tabla final
Entra la columna del mayor indicador positivo; sale la fila del menor cociente b/a entre los coeficientes positivos de esa columna. Se divide la fila por el pivote, se hacen ceros en el resto de la columna (también en los indicadores) y se repite hasta que no quede ningún indicador positivo.
La explicación
Un pivoteo es un paso de Gauss con dos reglas
Pivotear es hacer que una variable no básica pase a ser básica: su columna se convierte en una columna de la identidad, con operaciones de fila. Lo que el simplex agrega son dos reglas para elegir dónde, y las dos tienen un porqué.
2. La fila: en esa columna, para cada coeficiente positivo aij, el cociente bi / aij. Se elige el menor (si hay empate, el primero). La básica de esa fila es la que sale.
3. Se divide la fila pivote por el pivote aij, para que quede un 1.
4. A cada una de las otras filas, incluida la de indicadores, se le resta la fila pivote multiplicada por el número que tiene en esa columna: Fk − akj·Fi. La columna queda de la identidad.
5. Se lee la nueva solución factible básica y la esquina «z − v». Si queda algún indicador positivo, se vuelve al paso 1; si no, la tabla es final.
Por qué el mayor indicador
El indicador de una no básica dice cuánto sube z por cada unidad que se la aumente. Elegir el mayor es la apuesta de subir lo más rápido posible. Cualquier indicador positivo llevaría al mismo máximo, pero la regla de la práctica es la del mayor, y con ella todos llegan a las mismas tablas.
Por qué el menor cociente, y sólo con los positivos
Cuando la variable que entra crece, cada básica cambia. En la fila i queda básica = bi − aij·(lo que creció). Si aij > 0, esa básica baja y llega a 0 cuando la que entra vale bi / aij: ése es su tope. Si aij ≤ 0, esa básica no baja nunca, y esa fila no pone tope.
Hay que frenar en el primer tope, el menor. Si se elige otro, alguna básica ya pasó por 0 y queda negativa: al pivotear aparece un b negativo en la tabla, que quiere decir que el punto se salió de la región. Es la señal de que se eligió mal la fila.
La esquina «z − v»
La fila de indicadores se opera como cualquier otra. Al restarle cj veces la fila pivote (que en la columna b tiene bi/aij), la esquina pasa de «z» a «z − cj·bi/aij»: z aumentó exactamente lo que ganó la variable que entró. Por eso z nunca baja de un paso al otro.
Con el problema maximizar z = 3x1 + 4x2 sujeta a x1 + 2x2 ≤ 14 ; 3x1 + 2x2 ≤ 18, entra x2 (indicador 4) con cocientes 14/2 = 7 y 18/2 = 9: pivote en la fila 1. La esquina queda z − 4·7 = z − 28.
Cada pivoteo es un salto entre puntos esquina
En el dibujo de la unidad 5, la tabla inicial es el origen, y cada pivoteo mueve el punto a un vértice vecino, siguiendo una arista de la región, a uno donde z es mayor. En el ejemplo: (0, 0) con z = 0 → (0, 7) con z = 28 → (2, 6) con z = 30. El simplex no visita el (6, 0), que da 18: no hace falta.
Tablas que no son la inicial, y un parámetro en la esquina
Si te dan una tabla intermedia, se sigue desde ahí con las mismas reglas: no hace falta saber de qué problema salió. Y si la esquina trae una letra, «z − α», se pivotea igual: la esquina final queda «z − (α + algo)», y el máximo vale α + algo. Si te dicen cuánto tiene que valer el máximo, queda una ecuación en α.
El control que conviene hacer siempre
Después de cada pivoteo: la columna que entró es de la identidad, los b son todos ≥ 0 y la esquina creció (o quedó igual). Al final, reemplazá la solución en el problema original: las restricciones se tienen que cumplir y z tiene que dar lo de la esquina. Si el problema es de ℝ², podés además comparar con la tabla de vértices.
Resolver por el método simplex: maximizar z = 3x₁ + 4x₂ sujeta a x₁ + 2x₂ ≤ 14 ; 3x₁ + 2x₂ ≤ 18 ; x₁ ≥ 0, x₂ ≥ 0. Indicar en cada tabla las básicas, la solución factible básica y el valor de z.
Tabla inicial (x1 x2 │ s1 s2 │ b):
3 2 │ 0 1 │ 18
─────────────
3 4 │ 0 0 │ z
Básicas s1 = 14, s2 = 18; solución (0, 0, 14, 18); z = 0.
Primer pivoteo. Mayor indicador positivo: 4 → entra x2. Cocientes: 14/2 = 7 y 18/2 = 9. El menor es 7: pivote 2, en la fila 1 (sale s1).
F2 − 2F1 → ( 2 0 │ −1 1 │ 4 )
F3 − 4F1 → ( 1 0 │ −2 0 │ z − 28 )
Básicas x2 = 7 y s2 = 4; solución (0, 7, 0, 4); z = 28. No es final: x1 tiene indicador 1.
Segundo pivoteo. Entra x1. Cocientes: 7 / ½ = 14 y 4/2 = 2. El menor es 2: pivote 2, en la fila 2 (sale s2).
F1 − ½F2 → ( 0 1 │ ¾ −¼ │ 6 )
F3 − F2 → ( 0 0 │ −3/2 −½ │ z − 30 )
Básicas x2 = 6 (fila 1) y x1 = 2 (fila 2); s1 = s2 = 0; z = 30. Es final: ningún indicador positivo.
Respuesta: el máximo es z = 30, en (2, 6).
Control: 2 + 12 = 14 ✔, 6 + 12 = 18 ✔, z = 6 + 24 = 30 ✔. Los vértices de la región son (0, 0), (6, 0), (0, 7) y (2, 6), con z = 0, 18, 28 y 30: el mayor es el que dio el simplex.
Dónde se pierde el punto: en el primer pivoteo, tomar el cociente 9. Con pivote en la fila 2, a la fila 1 le queda 14 − 18 = −4 en b: un b negativo es la alarma de que el cociente no era el menor.
Resolver por simplex el problema del tema 6.1: maximizar z = 3x₁ + 2x₂ + 4x₃ sujeta a x₁ + x₂ + 2x₃ ≤ 10 ; 2x₁ + x₂ + x₃ ≤ 14 ; x ≥ 0. Dar el máximo, el punto donde se alcanza y controlarlo.
Tabla inicial (x1 x2 x3 │ s1 s2 │ b):
2 1 1 │ 0 1 │ 14
───────────────
3 2 4 │ 0 0 │ z
Primer pivoteo. Entra x3 (indicador 4). Cocientes 10/2 = 5 y 14/1 = 14: fila 1, pivote 2.
F2 − F1 → ( 3/2 ½ 0 │ −½ 1 │ 9 )
F3 − 4F1 → ( 1 0 0 │ −2 0 │ z − 20 )
Solución x3 = 5, s2 = 9, lo demás 0; z = 20. Queda el indicador 1 de x1.
Segundo pivoteo. Entra x1. Cocientes 5 / ½ = 10 y 9 / (3/2) = 6: fila 2, pivote 3/2.
F1 − ½F2 → ( 0 ⅓ 1 │ ⅔ −⅓ │ 2 )
F3 − F2 → ( 0 −⅓ 0 │ −5/3 −⅔ │ z − 26 )
Ningún indicador positivo: es final. Básicas x3 = 2 (fila 1) y x1 = 6 (fila 2); x2 = 0.
Respuesta: el máximo es z = 26, en (6, 0, 2).
Control: 6 + 0 + 4 = 10 ✔, 12 + 0 + 2 = 14 ✔, z = 18 + 0 + 8 = 26 ✔. En ℝ³ no se dibuja cómodo, pero se pueden listar los puntos esquina: (0, 0, 0), (7, 0, 0), (0, 10, 0), (0, 0, 5), (4, 6, 0) y (6, 0, 2), con z = 0, 21, 20, 20, 24 y 26. El simplex pasó por el origen y por (0, 0, 5), y llegó al mejor sin mirar los otros tres.
Dónde se pierde el punto: en el segundo pivoteo, dividir la fila por 3/2 mal (multiplicar en vez de dividir): la columna de x1 no queda con un 1, y ya no se puede leer la solución.
Dónde se cae la mayoría
- Elegir la columna del indicador más negativo: es la regla de los libros que ponen −c en la última fila. En la convención de la práctica entra el mayor indicador positivo.
- Elegir el mayor cociente en vez del menor: aparece un b negativo al pivotear, que quiere decir que el punto se salió de la región.
- Calcular cocientes con coeficientes negativos o nulos: esas filas no ponen tope y no se miran.
- Olvidarse de operar la fila de indicadores: sin ella no se sabe si la tabla es final, y la esquina no dice el nuevo z.
- Cortar en la primera tabla que parece buena: la tabla es final sólo cuando no queda ningún indicador positivo.
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 Pivotear hasta la tabla final →Dónde entra este tema en el parcial
- Segundo parcial — Las encuestas más baratas, por el dual25 puntos · resuelto paso a paso
Los otros temas de la unidad 6
Algoritmo simplex