Álgebra (71) · Unidad 6 — Algoritmo simplex
Leer una tabla simplex
En una tabla simplex las básicas son las columnas de la identidad y valen el b de la fila donde tienen su 1; las demás valen 0. La esquina «z − v» dice que z = v, y la tabla es final cuando ningún indicador es positivo.
La explicación
Cada fila es una ecuación
Una tabla simplex no es un dibujo: es un sistema de ecuaciones escrito sin las letras. En un problema con x1, x2 y tres holguras, la fila
Las operaciones del simplex son operaciones de fila, así que cada tabla es un sistema equivalente al inicial: tiene exactamente las mismas soluciones. Lo que cambia es cuáles variables quedan «despejadas».
Básicas y no básicas
Una variable es básica si su columna es una columna de la identidad: un 1 en una fila, 0 en todas las demás, y 0 en la fila de indicadores. Hay exactamente una básica por fila de restricción. Las otras son no básicas.
Con este problema, maximizar z = 2x1 + 3x2 sujeta a x1 + 2x2 ≤ 12 ; x1 + x2 ≤ 8 ; 3x1 + x2 ≤ 18, después de dos pivoteos queda (x1 x2 │ s1 s2 s3 │ b):
1 0 │ −1 2 0 │ 4
0 0 │ 2 −5 1 │ 2
────────────────
0 0 │ −1 −1 0 │ z − 20
La columna de x2 es (1, 0, 0) con 0 abajo: básica, de la fila 1. La de x1 es (0, 1, 0): básica, de la fila 2. La de s3 es (0, 0, 1): básica, de la fila 3. Las de s1 y s2 tienen varios números distintos de 0: no básicas.
La solución factible básica
2. Cada básica vale el b de la fila donde está su 1 (con las no básicas en 0, cada ecuación queda «básica = b»).
3. z es el número que acompaña a z en la esquina: «z − 20» dice z = 20. En la tabla inicial la esquina dice «z», o sea z = 0.
En el ejemplo: x1 = 4, x2 = 4, s3 = 2, s1 = s2 = 0, z = 20. Como los b son todos ≥ 0, la solución es factible: es un punto esquina de la región, el (4, 4).
Las holguras tienen lectura propia. Una holgura no básica vale 0: esa restricción se cumple justo (en un problema de producción, ese recurso se usa entero). Una holgura básica con valor positivo es lo que sobra de ese recurso: acá s3 = 2.
¿Es la tabla final?
La fila de indicadores también es una ecuación. En el ejemplo dice −s1 − s2 = z − 20, o sea
Como en la región todas las variables son ≥ 0, z nunca puede pasar de 20: la tabla es final y 20 es el máximo. En general, si algún indicador es positivo, aumentar esa variable aumenta z y hay que seguir pivoteando; si ninguno es positivo, la tabla es final. Los indicadores de las básicas son siempre 0.
Se miran todos los indicadores, también los de las holguras. Un indicador positivo en la columna de una holgura quiere decir que conviene «despegarse» de esa restricción: la tabla todavía no es final aunque los de las x sean todos ≤ 0.
El control que conviene hacer siempre
Si tenés el problema original, reemplazá la solución en él: 4 + 2·4 = 12 ✔, 4 + 4 = 8 ✔, 3·4 + 4 = 16 = 18 − 2 ✔ (sobran las 2 de s3) y z = 2·4 + 3·4 = 20 ✔. Si sólo tenés la tabla, controlá que haya una básica por fila, que sus indicadores sean 0 y que los b sean todos ≥ 0: un b negativo es un error de cuentas.
La siguiente es una tabla simplex de un problema estándar de maximización con tres variables y tres restricciones (columnas x₁ x₂ x₃ │ s₁ s₂ s₃ │ b): ( 2/3 0 5/3 │ 1 0 −1/3 │ 20 ) ; ( 5/3 0 2/3 │ 0 1 −1/3 │ 30 ) ; ( 1/3 1 1/3 │ 0 0 1/3 │ 20 ) ; indicadores ( 5/3 0 2/3 │ 0 0 −4/3 │ z − 80 ). Determinar las variables básicas y no básicas, la solución factible básica, el valor de z y si la tabla es final.
Las columnas de la identidad: se recorren una por una.
x2: (0, 0, 1), indicador 0 → sí, fila 3
x3: (5/3, 2/3, 1/3) → no
s1: (1, 0, 0), indicador 0 → sí, fila 1
s2: (0, 1, 0), indicador 0 → sí, fila 2
s3: (−1/3, −1/3, 1/3) → no
Básicas: s1, s2 y x2, una por fila. No básicas: x1, x3 y s3.
La solución factible básica: las no básicas en 0 y cada básica igual al b de su fila.
s1 = 20 , s2 = 30 , s3 = 0
Ojo con x2: su 1 está en la tercera fila, así que vale el 20 de esa fila, no el de la primera (que casualmente también es 20: por eso conviene decir siempre de qué fila sale).
El valor de z: la esquina dice «z − 80», así que z = 80.
¿Es final? No: hay dos indicadores positivos, 5/3 (de x1) y 2/3 (de x3). La fila de indicadores dice
y aumentar x1 (o x3) sube z. El próximo pivoteo haría entrar a x1, que tiene el mayor.
Lectura: en esta tabla se fabrican 20 unidades del producto 2 y nada de los otros; la tercera restricción está justa (s3 = 0) y en las otras dos sobra (20 y 30).
Control: una básica por fila ✔, sus indicadores son 0 ✔, los b son 20, 30 y 20, todos ≥ 0 ✔. Y reemplazando en la tercera fila: 0 + 20 + 0 + 0 = 20 ✔.
Una fábrica de jabones artesanales hace tres líneas: de glicerina (x₁), de avena (x₂) y de carbón (x₃), en lotes. Las restricciones son de aceite (2x₁ + x₂ + x₃ ≤ 180), de esencias (x₁ + 2x₂ + 3x₃ ≤ 300) y de horas de moldeado (2x₁ + 2x₂ + x₃ ≤ 240), y la ganancia es z = 6x₁ + 5x₂ + 4x₃ (miles de pesos). Después de tres pivoteos queda la tabla ( 1 0 0 │ 4/5 −1/5 −1/5 │ 36 ) ; ( 0 0 1 │ 2/5 2/5 −3/5 │ 48 ) ; ( 0 1 0 │ −1 0 1 │ 60 ) ; indicadores ( 0 0 0 │ −7/5 −2/5 −7/5 │ z − 708 ). ¿Es final? Leer la respuesta en el contexto y controlarla con el problema original.
¿Es final? Los indicadores son 0, 0, 0 (los de las básicas) y −7/5, −2/5, −7/5: ninguno positivo. Sí, es final.
Las básicas: x1 (su 1 está en la fila 1), x3 (fila 2) y x2 (fila 3). Las holguras son las tres no básicas.
s1 = s2 = s3 = 0 , z = 708
Cuidado con el orden: x3 es básica de la segunda fila y x2 de la tercera, así que x2 = 60 y x3 = 48, no al revés.
En el contexto: conviene hacer 36 lotes de glicerina, 60 de avena y 48 de carbón, y se gana 708 mil pesos. Las tres holguras valen 0: se usan enteros el aceite, las esencias y las horas de moldeado.
Por qué es el máximo: la fila de indicadores dice
y como las holguras son ≥ 0, cualquier otro plan factible da z ≤ 708.
Control con el problema original:
esencias: 36 + 120 + 144 = 300 ✔
moldeado: 72 + 120 + 48 = 240 ✔
z = 216 + 300 + 192 = 708 ✔
Dónde se pierde el punto: leer las básicas por el orden de las columnas y contestar x2 = 48: el control de las esencias lo caza (36 + 96 + 180 = 312 > 300).
Dónde se cae la mayoría
- Tomar como básica una columna que tiene un 1 pero también otros números distintos de 0: tiene que ser una columna de la identidad, con 0 también en la fila de indicadores.
- Leer z con el signo cambiado: «z − 20» quiere decir z = 20, no −20.
- Dar por final una tabla mirando sólo los indicadores de las x: un indicador positivo en una holgura también obliga a seguir.
- Darle a una no básica el número que aparece en su columna: las no básicas valen 0, y los valores se leen sólo en la columna b.
- Leer las básicas en el orden de las columnas: cada básica vale el b de la fila donde está su 1, que no tiene por qué ser la fila con su número.
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 Leer una tabla simplex →Los otros temas de la unidad 6
Algoritmo simplex