El algoritmo símplex: conceptos, teoremas fundamentales y funcionamiento

1. La pregunta

El tema 15 resolvió un problema evaluando cuatro vértices. Con 10 variables y 10 restricciones, el número de vértices posibles pasa de 180 000. Con 20 y 20, de 130 000 millones. Enumerarlos es imposible.

Hace falta un método que recorra solo los vértices prometedores, que sepa cuándo parar, y que garantice que el punto en el que para es el óptimo. Eso es el símplex, y lleva desde 1947 siendo el algoritmo más usado de la investigación operativa.

2. Intuición

Estás en una esquina del poliedro factible y quieres llegar a la mejor. No conoces el mapa entero, pero desde cada esquina ves las aristas que salen de ella.

El método es sencillo de enunciar:

1. Mira todas las aristas que salen de tu esquina.
2. Si alguna sube (mejora el objetivo), recórrela hasta la siguiente esquina.
3. Si ninguna sube, has terminado: estás en el óptimo.

El paso 3 es el que sorprende y el que hay que creerse: en un poliedro convexo, si desde una esquina no se puede mejorar yendo a ninguna vecina, entonces no hay ningún punto mejor en todo el conjunto. En un terreno con entrantes eso sería falso —podrías estar en una cima secundaria—, pero la convexidad demostrada en el tema 9 lo impide. Es la convexidad lo que convierte un método local en uno global.

Lo que queda es traducir «esquina» y «arista» a álgebra, para poder hacerlo con números sin dibujar nada. Y ahí la clave es: en una esquina, algunas variables valen cero y otras no. Moverse por una arista es hacer que una variable que valía cero empiece a crecer, hasta que otra se anula. Ese intercambio se llama pivotar, y es exactamente una operación de Gauss del tema 8.

3. Formalización

Forma estándar

El símplex exige el problema escrito así:

$$\max z={\mathbf{c}}^{\top }\mathbf{x}\text{s.a.}\mathbf{Ax}=\mathbf{b},\mathbf{x}\ge 0,\mathbf{b}\ge 0$$

con igualdades. Las desigualdades se convierten añadiendo variables:

Restricción original	Se convierte en	Variable añadida
$a^{\top }\mathbf{x}\le b$	$a^{\top }\mathbf{x}+s=b$	holgura $s\ge 0$
$a^{\top }\mathbf{x}\ge b$	$a^{\top }\mathbf{x}-e=b$	excedente $e\ge 0$

La variable de holgura $s_i$ tiene lectura directa: es el recurso $i$ que sobra. Si en el óptimo $s_i=0$, ese recurso está agotado.

Las variables de holgura entran en la función objetivo con coeficiente cero: lo que sobra no aporta beneficio.

Si algún $b_i$ es negativo, se multiplica esa restricción por $-1$ (lo que invierte el sentido de la desigualdad). Si tras convertir hace falta un punto de partida factible que no existe, hay que recurrir a variables artificiales y al método de las dos fases, que es el tema 17.

Soluciones básicas

Con $m$ restricciones y $n$ variables ($n>m$), el sistema $\mathbf{Ax}=\mathbf{b}$ está indeterminado. Se elige un conjunto de $m$ variables —las básicas— y se fijan las $n-m$ restantes —las no básicas— a cero. Resolviendo el sistema resultante se obtiene una solución básica.

Si además todas las variables básicas salen $\ge 0$, es una solución básica factible.

Teorema fundamental (versión algebraica). Las soluciones básicas factibles se corresponden exactamente con los vértices del poliedro factible.

Este teorema es el puente entre la geometría del tema 9 y el álgebra del símplex: buscar vértices es elegir qué variables son básicas.

El número de posibilidades es $\left(\genfrac{}{}{0ex}{}{n}{m}\right)$, y de ahí la explosión combinatoria. El símplex no las prueba todas: salta de una a otra mejorando siempre.

La tabla del símplex

Se organiza todo en una tabla. Con las variables en las columnas, una fila por restricción y una fila final para el objetivo:

$$\begin{array}{cccccc}\text{Baˊsica}& x_1& \cdots & x_n& s_1\cdots s_m& b\\ s_1& a_{11}& \cdots & a_{1n}& 1\cdots 0& b_1\\ ⋮& & & & & ⋮\\ s_m& a_{m1}& \cdots & a_{mn}& 0\cdots 1& b_m\\ z& -c_1& \cdots & -c_n& 0\cdots 0& 0\end{array}$$

La fila $z$ contiene los costes reducidos, escritos habitualmente como $z_j-c_j$. Con la disposición de arriba, la fila objetivo lleva los $-c_j$ al inicio porque procede de escribir $z-{\mathbf{c}}^{\top }\mathbf{x}=0$.

Convenio de este sitio: se trabaja con la fila $z_j-c_j$, de modo que un valor negativo indica que esa variable, al entrar, mejora el objetivo en un problema de máximo.

Las cinco reglas del algoritmo

1. Punto de partida. Con todas las restricciones de tipo $\le$ y $\mathbf{b}\ge 0$, las variables de holgura forman una base factible inmediata: $\mathbf{x}=0$, $\mathbf{s}=\mathbf{b}$. Corresponde al origen, y significa «no producir nada».

2. Criterio de entrada. Entra en la base la variable con el $z_j-c_j$ más negativo. Es la que más mejora el objetivo por unidad. (Cualquier negativo serviría; elegir el más negativo es la regla de Dantzig, y suele converger antes.)

3. Criterio de salida: la razón mínima. Sea $x_k$ la variable entrante y $a_{ik}$ su columna. Se calcula, solo para los $a_{ik}>0$:

$$\theta =\underset{i}{\min }\left\{\frac{b_i}{a_{ik}}:a_{ik}>0\right\}$$

La fila que alcanza el mínimo determina la variable que sale.

Por qué solo los positivos. La variable entrante crece; las básicas cambian según $b_i-\theta a_{ik}$. Si $a_{ik}\le 0$, esa básica no disminuye y nunca se hará negativa: no impone límite. El límite lo ponen las que sí decrecen, y la primera en llegar a cero marca hasta dónde se puede avanzar sin salirse de la región.

Si ninguna $a_{ik}$ es positiva, la variable entrante puede crecer indefinidamente: el problema es no acotado.

4. Pivotar. El elemento en el cruce de la columna entrante y la fila saliente es el pivote. Mediante operaciones de Gauss se convierte en 1 y se hacen ceros en el resto de su columna, incluida la fila $z$. Es exactamente Gauss-Jordan.

5. Criterio de parada. Cuando todos los $z_j-c_j\ge 0$, la solución actual es óptima. Ninguna variable no básica mejora el objetivo al entrar.

Para problemas de mínimo se puede minimizar $-z$ y aplicar lo mismo, que es lo más seguro para no confundir signos.

Lectura de la tabla final

• El valor de $z$ está en la esquina inferior derecha.
• Las variables básicas toman el valor de su fila en la columna $b$.
• Las no básicas valen cero.
• Los $z_j-c_j$ de las columnas de holgura son los precios sombra de las restricciones, que es lo que desarrollará el tema 18.

4. Ejemplo económico resuelto

Problema. Resolvemos por símplex la carpintería del tema 15, simplificada sin el compromiso contractual:

$$\max z=70x_1+50x_2$$ $$\text{s.a.}4x_1+3x_2\le 240,2x_1+x_2\le 100,x_1,x_2\ge 0$$

Paso 1. Forma estándar. Añadimos holguras $s_1$ (horas de carpintería sobrantes) y $s_2$ (horas de acabado sobrantes):

$$4x_1+3x_2+s_1=240$$ $$2x_1+x_2+s_2=100$$

Paso 2. Tabla inicial. Base $\{s_1,s_2\}$, es decir, el vértice $(0,0)$: no producir nada.

$$\begin{array}{cccccc}\text{Base}& x_1& x_2& s_1& s_2& b\\ s_1& 4& 3& 1& 0& 240\\ s_2& 2& 1& 0& 1& 100\\ z_j-c_j& -70& -50& 0& 0& 0\end{array}$$

Paso 3. Primera iteración.

Entra: el más negativo de la fila $z$ es $-70$, columna $x_1$. Entra $x_1$.

Sale: razones con los coeficientes positivos de la columna $x_1$:

$$\frac{240}{4}=60\frac{100}{2}=50\leftarrow \text{mıˊnimo}$$

Sale $s_2$. El pivote es el 2 de la fila $s_2$.

Pivotar. Dividimos la fila $s_2$ entre 2:

$$\text{nueva }{F}_2:(1,0,5,0,0,5\mid 50)$$

Hacemos ceros en la columna $x_1$:

$$F_1\leftarrow F_1-4F_2^{\prime }:(4-4,3-2,1-0,0-2\mid 240-200)=(0,1,1,-2\mid 40)$$ $$F_z\leftarrow F_z+70F_2^{\prime }:(-70+70,-50+35,0,35\mid 0+3500)=(0,-15,0,35\mid 3500)$$ $$\begin{array}{cccccc}\text{Base}& x_1& x_2& s_1& s_2& b\\ s_1& 0& 1& 1& -2& 40\\ x_1& 1& 0,5& 0& 0,5& 50\\ z_j-c_j& 0& -15& 0& 35& 3500\end{array}$$

Estamos en el vértice $(50,0)$ con $z=3500$. Aún hay un negativo.

Paso 4. Segunda iteración.

Entra: $-15$, columna $x_2$. Entra $x_2$.

Sale: razones con coeficientes positivos:

$$\frac{40}{1}=40\leftarrow \text{mıˊnimo}\frac{50}{0,5}=100$$

Sale $s_1$. Pivote: el 1 de la fila $s_1$, columna $x_2$.

Pivotar. La fila $s_1$ ya tiene un 1 en el pivote, se queda igual:

$$\text{nueva }{F}_1:(0,1,1,-2\mid 40)$$ $$F_2\leftarrow F_2-0,5F_1^{\prime }:(1,0,-0,5,0,5+1\mid 50-20)=(1,0,-0,5,1,5\mid 30)$$ $$F_z\leftarrow F_z+15F_1^{\prime }:(0,0,15,35-30\mid 3500+600)=(0,0,15,5\mid 4100)$$ $$\begin{array}{cccccc}\text{Base}& x_1& x_2& s_1& s_2& b\\ x_2& 0& 1& 1& -2& 40\\ x_1& 1& 0& -0,5& 1,5& 30\\ z_j-c_j& 0& 0& 15& 5& 4100\end{array}$$

Paso 5. Parada. Todos los $z_j-c_j\ge 0$: óptimo alcanzado.

Paso 6. Leer la solución.

$$x_1^{\ast }=30\text{ mesas},x_2^{\ast }=40\text{ estanterıˊas}$$ $$s_1^{\ast }=0,s_2^{\ast }=0\text{(no baˊsicas)}$$ $$z^{\ast }=4100\text{ €}$$

Coincide exactamente con el resultado gráfico del tema 15, como tenía que ser.

Paso 7. Leer lo que el método gráfico no daba. Los valores de la fila $z$ bajo las columnas de holgura:

$$z_{s_1}-c_{s_1}=15,z_{s_2}-c_{s_2}=5$$

Estos son los precios sombra. Una hora más de carpintería aumentaría el beneficio en 15 €; una hora más de acabado, en 5 €. La empresa debería pagar hasta 15 € por una hora extra de carpintería y no más de 5 por una de acabado.

Comprobación: con 241 horas de carpintería, rehaciendo el sistema $4x_1+3x_2=241$, $2x_1+x_2=100$ sale $x_1=29,5$, $x_2=41$ y $z=2065+2050=4115=4100+15✓$.

El camino recorrido. El símplex visitó tres vértices: $(0,0)\to (50,0)\to (30,40)$. El método gráfico había evaluado cuatro. Con problemas grandes, la diferencia entre recorrer unos pocos vértices y enumerarlos todos es la diferencia entre resolver y no resolver.

5. Errores típicos

Aplicar el símplex sin pasar a forma estándar. Hacen falta igualdades y $\mathbf{b}\ge 0$. Con desigualdades sin holguras, la tabla no significa nada.

Calcular la razón mínima con coeficientes negativos o nulos. Solo entran en el cociente los $a_{ik}>0$. Incluir un negativo da una razón negativa que parece el mínimo y saca de la región factible.

Olvidar actualizar la fila $z$ al pivotar. Es una fila más y hay que hacer cero en ella la columna entrante. Si no, el criterio de parada nunca se cumple correctamente.

Confundir el criterio de parada según el convenio de signos. Con la fila $z_j-c_j$, en un problema de máximo se para cuando todos son $\ge 0$. Con la otra convención (fila con los $c_j$ directamente) la regla se invierte. Elegir un convenio y no cambiarlo.

Leer mal la solución final. Las variables no básicas valen cero, aunque su columna tenga números. Solo las básicas toman el valor de la columna $b$.

Olvidar interpretar las holguras. $s_i=0$ significa recurso agotado; $s_i>0$, recurso sobrante. Es información valiosa que suele quedarse sin leer.

No comprobar la solución. Sustituir en las restricciones originales y recalcular $z$ cuesta un minuto y detecta cualquier error de pivotaje.

6. Ejercicios

Ejercicio 1 · Pasar a forma estándar

básico

Escribe en forma estándar:

$$\max z=5x_1+3x_2\text{s.a.}2x_1+x_2\le 40,x_1+3x_2\le 30,x_1,x_2\ge 0$$

y escribe la tabla inicial.

Ver solución

Se añade una holgura por restricción:

$$2x_1+x_2+s_1=40$$$$x_1+3x_2+s_2=30$$

con $x_1,x_2,s_1,s_2\ge 0$, y la función objetivo sin cambios (las holguras entran con coeficiente 0).

$$\begin{array}{cccccc}\text{Base}& x_1& x_2& s_1& s_2& b\\ s_1& 2& 1& 1& 0& 40\\ s_2& 1& 3& 0& 1& 30\\ z_j-c_j& -5& -3& 0& 0& 0\end{array}$$

La base inicial es $\{s_1,s_2\}$ con $s_1=40$, $s_2=30$, y corresponde al vértice $(0,0)$: no producir nada y que sobre todo el recurso.

Ejercicio 2 · Una iteración completa

básico

Realiza la primera iteración del ejercicio 1.

Ver solución

Entra: el más negativo es $-5$, columna $x_1$.

Sale: razones con coeficientes positivos de la columna $x_1$:

$$\frac{40}{2}=20\leftarrow \frac{30}{1}=30$$

Sale $s_1$. Pivote: el 2 en la fila $s_1$, columna $x_1$.

Pivotar. Fila del pivote entre 2:

$$F_1^{\prime }:(1,0,5,0,5,0\mid 20)$$$$F_2\leftarrow F_2-1\cdot F_1^{\prime }:(0,2,5,-0,5,1\mid 10)$$$$F_z\leftarrow F_z+5F_1^{\prime }:(0,-0,5,2,5,0\mid 100)$$$$\begin{array}{cccccc}\text{Base}& x_1& x_2& s_1& s_2& b\\ x_1& 1& 0,5& 0,5& 0& 20\\ s_2& 0& 2,5& -0,5& 1& 10\\ z_j-c_j& 0& -0,5& 2,5& 0& 100\end{array}$$

Solución actual: $x_1=20$, $x_2=0$, $z=100$. Aún no es óptima: queda un $z_j-c_j$ negativo ($-0,5$ en $x_2$), así que hay que seguir iterando.

Ejercicio 3 · Símplex completo con tres variables

medio

Resuelve:

$$\max z=3x_1+2x_2+4x_3$$$$\text{s.a.}{x}_1+x_2+2x_3\le 40,2x_1+x_2+x_3\le 30,x_j\ge 0$$

Ver solución

Tabla inicial.

$$\begin{array}{ccccccc}\text{Base}& x_1& x_2& x_3& s_1& s_2& b\\ s_1& 1& 1& 2& 1& 0& 40\\ s_2& 2& 1& 1& 0& 1& 30\\ z_j-c_j& -3& -2& -4& 0& 0& 0\end{array}$$

Iteración 1. Entra $x_3$ ($-4$, el más negativo). Razones: $40/2=20\leftarrow$, $30/1=30$. Sale $s_1$. Pivote: 2.

$$F_1^{\prime }:(0,5,0,5,1,0,5,0\mid 20)$$$$F_2\leftarrow F_2-F_1^{\prime }:(1,5,0,5,0,-0,5,1\mid 10)$$$$F_z\leftarrow F_z+4F_1^{\prime }:(-1,0,0,2,0\mid 80)$$$$\begin{array}{ccccccc}\text{Base}& x_1& x_2& x_3& s_1& s_2& b\\ x_3& 0,5& 0,5& 1& 0,5& 0& 20\\ s_2& 1,5& 0,5& 0& -0,5& 1& 10\\ z_j-c_j& -1& 0& 0& 2& 0& 80\end{array}$$

Iteración 2. Entra $x_1$ ($-1$). Razones: $20/0,5=40$, $10/1,5=6,67\leftarrow$. Sale $s_2$. Pivote: 1,5.

$$F_2^{\prime }:(1,0,333,0,-0,333,0,667\mid 6,667)$$$$F_1\leftarrow F_1-0,5F_2^{\prime }:(0,0,333,1,0,667,-0,333\mid 16,667)$$$$F_z\leftarrow F_z+F_2^{\prime }:(0,0,333,0,1,667,0,667\mid 86,667)$$$$\begin{array}{ccccccc}\text{Base}& x_1& x_2& x_3& s_1& s_2& b\\ x_3& 0& 0,333& 1& 0,667& -0,333& 16,667\\ x_1& 1& 0,333& 0& -0,333& 0,667& 6,667\\ z_j-c_j& 0& 0,333& 0& 1,667& 0,667& 86,667\end{array}$$

Todos los $z_j-c_j\ge 0$: óptimo.

$$x_1^{\ast }=6,67,x_2^{\ast }=0,x_3^{\ast }=16,67,z^{\ast }=86,67$$

Comprobación en las restricciones originales:

$$6,67+0+2(16,67)=6,67+33,33=40✓$$$$2(6,67)+0+16,67=13,33+16,67=30✓$$$$z=3(6,67)+4(16,67)=20+66,67=86,67✓$$

Interpretación. El producto 2 no se fabrica ($x_2=0$): su margen de 2 € no compensa lo que consume de unos recursos que valen 1,667 y 0,667 € por unidad. De hecho su coste reducido, 0,333, dice exactamente cuánto habría que subirle el margen para que entrara en el plan: de 2 a 2,33 €.

Ejercicio 4 · ¿Es no acotado? Diagnóstico correcto

avanzado

Intenta resolver por símplex:

$$\max z=2x_1+3x_2\text{s.a.}{x}_1-x_2\le 4,-x_1+2x_2\le 6,x_1,x_2\ge 0$$

Explica qué ocurre y qué significa.

Ver solución

Tabla inicial.

$$\begin{array}{cccccc}\text{Base}& x_1& x_2& s_1& s_2& b\\ s_1& 1& -1& 1& 0& 4\\ s_2& -1& 2& 0& 1& 6\\ z_j-c_j& -2& -3& 0& 0& 0\end{array}$$

Iteración 1. Entra $x_2$ ($-3$). Razones solo con positivos: en la columna $x_2$ los coeficientes son $-1$ y $2$; solo el segundo es positivo:

$$\frac{6}{2}=3\leftarrow$$

Sale $s_2$. Pivote: 2.

$$F_2^{\prime }:(-0,5,1,0,0,5\mid 3)$$$$F_1\leftarrow F_1+F_2^{\prime }:(0,5,0,1,0,5\mid 7)$$$$F_z\leftarrow F_z+3F_2^{\prime }:(-3,5,0,0,1,5\mid 9)$$$$\begin{array}{cccccc}\text{Base}& x_1& x_2& s_1& s_2& b\\ s_1& 0,5& 0& 1& 0,5& 7\\ x_2& -0,5& 1& 0& 0,5& 3\\ z_j-c_j& -3,5& 0& 0& 1,5& 9\end{array}$$

Iteración 2. Entra $x_1$ ($-3,5$). Razones: la columna $x_1$ tiene coeficientes $0,5$ y $-0,5$. Solo el primero es positivo:

$$\frac{7}{0,5}=14\leftarrow$$

Sale $s_1$. Pivote: 0,5.

$$F_1^{\prime }:(1,0,2,1\mid 14)$$$$F_2\leftarrow F_2+0,5F_1^{\prime }:(0,1,1,1\mid 10)$$$$F_z\leftarrow F_z+3,5F_1^{\prime }:(0,0,7,5\mid 58)$$$$\begin{array}{cccccc}\text{Base}& x_1& x_2& s_1& s_2& b\\ x_1& 1& 0& 2& 1& 14\\ x_2& 0& 1& 1& 1& 10\\ z_j-c_j& 0& 0& 7& 5& 58\end{array}$$

Todos los $z_j-c_j\ge 0$: el símplex termina con $x_1=14$, $x_2=10$, $z=58$.

Comprobación: $14-10=4\le 4✓$; $-14+20=6\le 6✓$.

Entonces, ¿dónde estaba el problema? En que este problema sí es acotado, pese a que la región lo parezca por los coeficientes negativos. Comprobémoslo: para poder crecer desde el óptimo en una dirección $(d_1,d_2)\ge 0$ haría falta $d_1-d_2\le 0$ y $-d_1+2d_2\le 0$, es decir, $d_2\ge d_1$ y $d_2\le d_1/2$. Con $d_1>0$ es imposible. La región está acotada en la dirección de crecimiento.

Cuándo sí habría sido no acotado. Basta cambiar la segunda restricción a $-x_1+2x_2\ge 6$, o eliminarla. Con solo $x_1-x_2\le 4$, la columna de $x_2$ en la tabla sería $(-1)$: ningún coeficiente positivo, no se podría calcular la razón mínima, y $x_2$ podría crecer indefinidamente aumentando $z$ sin límite.

La regla que hay que retener: el problema es no acotado cuando la variable entrante tiene todos los coeficientes de su columna $\le 0$. Ahí el algoritmo se detiene y devuelve «no acotado», no una solución.

Qué significa en la práctica. Un problema real nunca es no acotado: siempre hay algún límite. Si el modelo lo es, falta una restricción —capacidad, demanda máxima, presupuesto—. El diagnóstico correcto no es cambiar de método, es revisar la formulación, tal como se vio en el ejercicio 4 del tema 15.

7. Qué desbloquea

Necesitas antes:

• Sistemas de ecuaciones lineales y método de Gauss — tema 8
• Investigación operativa: formulación de problemas lineales y resolución gráfica — tema 15

Te abre la puerta a:

• Tipología de soluciones, degeneración y método de las dos fases — tema 17
• Dualidad: formulación del dual, relaciones e interpretación económica — tema 18

8. Recursos externos

• OCW UPV/EHU — Investigación Operativa. Programación Lineal. El método símplex con todos los detalles de tabla y pivotaje, y colección de problemas resueltos al final del tema.
• OCW Unizar — Modelos de Investigación Operativa. Incluye scripts de apoyo para practicar la entrada y salida de variables: muy útiles para automatizar la parte mecánica y concentrarse en los criterios.
• OCW Unizar — vídeos de matemáticas básicas, sección de programación lineal. Vídeos concretos sobre el funcionamiento del símplex paso a paso.
• LINDO. Resolver el mismo problema a mano y con LINDO, y comparar la tabla final, es la mejor forma de verificar que se domina el método.