Álgebra (71) · Unidad 6 — Algoritmo simplex
Cuando no hay máximo o hay más de uno
Si un indicador es positivo y su columna no tiene ningún coeficiente positivo, no hay pivote: z crece sin tope y no tiene máximo. Si en la tabla final una variable no básica tiene indicador 0, hay otra solución óptima: pivoteando en esa columna se llega a otro vértice con el mismo z, y toda la arista entre los dos es óptima.
La explicación
Tres maneras de terminar
El simplex se frena por una de estas tres razones, y cada una se lee en la tabla:
2. Un indicador positivo cuya columna no tiene ningún coeficiente positivo: no hay fila pivote, y z no tiene máximo.
3. Ningún indicador positivo, pero una no básica con indicador 0: el máximo se alcanza también en otro punto, y la solución no es única.
Cuando no hay pivote: z crece sin tope
Supongamos que la variable que tendría que entrar tiene, en toda su columna, números ≤ 0. Al aumentarla en t, cada básica queda bi − aij·t, y como aij ≤ 0 ninguna baja: todas siguen ≥ 0 por más grande que sea t. Todos esos puntos están en la región, y en ellos z = v + (indicador)·t, que crece tanto como uno quiera.
La conclusión se escribe así: z no tiene máximo en la región (o «no alcanza un máximo»). No es que el máximo sea «infinito», ni que el problema no tenga solución factible: puntos factibles hay de sobra, lo que no hay es uno mejor que todos.
En el dibujo, la región no es acotada y las rectas de nivel se pueden correr para el lado abierto sin salirse nunca. Ojo con la recíproca: una región no acotada no siempre da «sin máximo». Si z crece hacia el lado cerrado, el máximo existe igual, y el simplex lo encuentra.
Un indicador 0 en una no básica: otra solución óptima
En la tabla final, los indicadores de las básicas son 0 siempre: eso no dice nada. Lo que hay que buscar es una no básica con indicador 0. La fila de indicadores dice, por ejemplo, z = 20 − 2s1 + 0·s3: aumentar s3 no cambia z. Si se pivotea en esa columna (con la regla de siempre para la fila) se llega a otro punto esquina con el mismo z.
Y no son sólo dos: todos los puntos del segmento entre los dos vértices P y Q son óptimos, porque z es lineal. Se escriben
En el dibujo pasa cuando la función objetivo es paralela a un lado de la región: la última recta de nivel no toca un vértice solo, se apoya en toda la arista. Por eso la pregunta «¿es única la solución?» se contesta mirando los indicadores de la tabla final.
Para contar: en una tabla con m filas hay m básicas, todas con indicador 0. Si hay más de m indicadores 0, alguno es de una no básica.
Lo mismo, por el método gráfico
Con dos variables conviene hacer las dos cosas. El caso sin máximo es una región abierta con z que crece hacia afuera; el de muchas soluciones, un lado de la región paralelo a las rectas de nivel. Si el simplex y el dibujo no dicen lo mismo, hay un error en las cuentas.
El control que conviene hacer siempre
Si concluís que z no tiene máximo, mostrá puntos factibles con z cada vez más grande: salen de la última tabla, dándole valores a la variable que no pudo entrar. Si concluís que hay otra solución, calculá z en los dos vértices y en el punto medio de la arista: tiene que dar lo mismo en los tres, y los tres tienen que cumplir las restricciones.
Maximizar z = x₁ + 2x₂ sujeta a −x₁ + x₂ ≤ 3 ; x₁ − 2x₂ ≤ 2 ; x₁ ≥ 0, x₂ ≥ 0. Aplicar el método simplex, decidir si se puede seguir pivoteando y sacar conclusiones.
Tabla inicial (x1 x2 │ s1 s2 │ b):
1 −2 │ 0 1 │ 2
─────────────
1 2 │ 0 0 │ z
Primer pivoteo. Entra x2 (indicador 2). En su columna sólo la primera fila tiene coeficiente positivo (la segunda tiene −2 y no pone tope): cociente 3/1 = 3, pivote 1.
F2 + 2F1 → ( −1 0 │ 2 1 │ 8 )
F3 − 2F1 → ( 3 0 │ −2 0 │ z − 6 )
Solución x2 = 3, s2 = 8; z = 6. Queda el indicador 3 de x1.
¿Se puede seguir? La columna de x1 es (−1, −1): ningún coeficiente positivo, no hay cociente que calcular. No se puede pivotear.
Qué quiere decir. Con s1 = 0 y x1 = t, las filas dicen x2 = 3 + t y s2 = 8 + t: para todo t ≥ 0 el punto (t, 3 + t) es factible, y
que crece sin tope. z no tiene máximo en la región.
Por el método gráfico: la región está entre la recta −x1 + x2 = 3 (por arriba) y x1 − 2x2 = 2 (por abajo), con puntos esquina (0, 0), (2, 0) y (0, 3), y se abre hacia arriba y a la derecha. z crece justo hacia ese lado: la recta de nivel se puede correr para siempre.
Control: con t = 10, el punto (10, 13) cumple −10 + 13 = 3 ≤ 3 ✔ y 10 − 26 = −16 ≤ 2 ✔, con z = 36; con t = 100, (100, 103) da z = 306. Ningún valor es el mayor.
Maximizar z = 4x₁ + 2x₂ sujeta a 2x₁ + x₂ ≤ 10 ; x₁ + x₂ ≤ 7 ; x₁ ≤ 4 ; x ≥ 0. Resolver por simplex. ¿Es única la solución? Si no lo es, describir todas las soluciones óptimas.
Tabla inicial (x1 x2 │ s1 s2 s3 │ b): filas ( 2 1 │ 1 0 0 │ 10 ), ( 1 1 │ 0 1 0 │ 7 ), ( 1 0 │ 0 0 1 │ 4 ) e indicadores ( 4 2 │ 0 0 0 │ z ).
Primer pivoteo. Entra x1. Cocientes 10/2 = 5, 7/1 = 7 y 4/1 = 4: fila 3.
( 0 1 │ 0 1 −1 │ 3 )
( 1 0 │ 0 0 1 │ 4 )
( 0 2 │ 0 0 −4 │ z − 16 )
Segundo pivoteo. Entra x2 (indicador 2). Cocientes 2/1 = 2 y 3/1 = 3: fila 1.
( 0 0 │ −1 1 1 │ 1 )
( 1 0 │ 0 0 1 │ 4 )
( 0 0 │ −2 0 0 │ z − 20 )
Ningún indicador positivo: es final, con x1 = 4, x2 = 2 y z = 20.
¿Es única? Las básicas son x2, s2 y x1. Hay cuatro indicadores 0 y tres básicas: el que sobra es el de s3, que es no básica. Hay otra solución óptima.
El otro vértice. Pivoteando en la columna de s3, (−2, 1, 1): cocientes 1/1 = 1 y 4/1 = 4, fila 2. Queda s3 = 1, x1 = 4 − 1 = 3, x2 = 2 + 2·1 = 4, y la esquina sigue en z − 20.
Todas las soluciones: los puntos del segmento entre (4, 2) y (3, 4):
Por qué pasa: z = 4x1 + 2x2 = 2·(2x1 + x2), así que las rectas de nivel son paralelas al lado 2x1 + x2 = 10, y sobre ese lado z = 20.
Control: en (3, 4): 6 + 4 = 10 ✔, 3 + 4 = 7 ✔, 3 ≤ 4 ✔, z = 12 + 8 = 20 ✔. En el punto medio (7/2, 3): z = 14 + 6 = 20 ✔. Los otros vértices, (0, 7) y (4, 0), dan 14 y 16.
Dónde se cae la mayoría
- Seguir buscando pivote en una columna sin coeficientes positivos, o tomar un coeficiente negativo como pivote: no hay fila pivote, y eso ya es la respuesta.
- Concluir que el máximo es infinito, o que el problema no tiene solución: hay puntos factibles, lo que no hay es máximo.
- Contar los ceros de los indicadores de las básicas como «otra solución»: las básicas tienen indicador 0 siempre. Lo que avisa es un 0 en una no básica.
- Dar como respuesta sólo los dos vértices cuando la solución no es única: todo el segmento entre ellos es óptimo.
- Creer que una región no acotada siempre da «sin máximo»: depende de hacia dónde crece z.
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 Cuando no hay máximo o hay más de uno →Los otros temas de la unidad 6
Algoritmo simplex