El elemento Pivote y cálculos del método del Simplex

La idea básica del Algoritmo del Simplex es, que no necesitamos calcular la inversa de la submatriz B para calcular los puntos extremos de la región factible (recordar que B es una submatriz cuadrada de la matriz de restricciones A y de rango m). En lugar de eso, una serie de cálculos conducen a un elemento de la matriz A, que llamaremos elemento Pivote y que utilizaremos para pasar, de un punto extremo a otro del conjunto factible, probando en cada uno de ellos el criterio de optimalidad, hasta que se produce uno de de estos posibles 4 casos:

Como decíamos, no es preciso invertir la matriz B (recordamos que B es una submatriz cuadrada de A de mxm y de rango m), sino que creamos una tabla para cada iteración del algoritmo en las que los cálculos son mucho más sencillos de hacer que de explicar.

La tabla se construye como sigue:

Base

x1

...

xi

...

xm

Xb

β1

...

βi

...

βm

Cb

Cb1

...

Cbi

...

Cbm

a1	...	ak	...	an
y11	...	y1k	...	y1n
...	...	...	...	...
yi1	...	yik	...	yin
...	...	...	...	...
ym1	...	ymk	...	ymn
z1-c1	...	zk-ck	...	zn-cn

en rojo dejamos ya el elemento pivote yik que explicaremos a continuación

Si existiera una submatriz identidad mxm de A, que llamamos B, las columnas de A que están en B son los índices en la base.

El vector Xb es el punto extremo que nos permite inciar las iteraciones del algoritmo (variables en la base), el vector CB por su parte, está formado por los elementos del vector C que están en ese momento en la base, es para él que calculamos los \( z_{j} - c_{j} \) . Recordamos que \( z_{j} = X_{B}a_{j} \) o también \(z_{j} = C^t_{B}B^{-1}a_{j}\) y que B es en este paso, la matriz identidad, tal como hemos supuesto al principio.

Una vez calculados, se pasa sobre ellos el criterio de optimalidad, es decir vemos si se cumple

\( c_{j} - z_{j} \geq 0, \; \forall j \)

Si se cumple, habríamos terminado, x es el punto óptimo que estamos buscando, en caso contrario tomamos el índice s que hace que

\( s = min \{ c_{j} - z_{j}: \,\ c_{j} - z_{j} < 0 \} \)

Es decir, tomamos como s el índice del mínimo de los negativos de los \( c_{j} - z_{j} \).

Ahora, con este índice s, buscamos el elemento que llamaremos Pivote. Para ello, dividimos cada coordenada i del vector Xb por su coordenada i del vector columna yis y calculamos el mínimo de los positivos, o sea

\( r = min \{ i : \frac {x_i}{y_{is}}, y_{is} \geqslant 0, x = B^{-1}b \} \)

Si el mínimo anterior no existe por ser todos los \( \frac {x_i}{y_{is}} \) negativos, estaríamos en el caso de solución no acotada, tal como hemos visto en la sección El algoritmo del Simplex.

En caso contrario tendremos r, el índice que minimiza los yrs. Este es el elemento llamado elemento Pivote y su importancia es básica para su funcionamiento del Algoritmo del Simplex.


en cuyo caso ya tenemos, s será el nuevo índice de las x que entra en la base y r es el índice de los Xb que sale de la base.

Todo esto ya lo habíamos visto, ahora recalculamos toda la tabla en esta nueva base, para ello calculamos la matriz A de la siguiente manera:

Esta es la base del algoritmo para invertir la matriz de restricciones y de todos los cálculos que haremos aquí.

Es decir, para la fila del pivote los nuevos coeficientes se calculan dividiendo por el pivote, para las otras filas se calcula restando al coeficiente de los yi en la fila del pivote multiplicado por el coeficiente correspondiente a la columna del pivote dividido por el pivote.

Los cálculos son un poco más difíciles de explicar que de entender, veremos al final de esta sección un ejemplo práctico del funcionamiento del algoritmo. Quien lo desee puede pasar directamente a verlo. Por ahora nos ocupamos de los siguientes problemas:

1) ¿Como encontrar una solución primera para que el algoritmo comience las iteraciones?

2) En el caso de que el problema P contenga restricciones de desigualdad ¿Como realizar las operaciones?

3) Alguna de las variables podrían no estar restringidas en signo ¿Como operar en este caso?

4) Podemos tener incompatibilidad o redundancia en las operaciones ¿Que hacer en este caso?

5) ¿Y si en nuestra función objetivo queremos maximizar y no minimizar?

Respuestas a estos problemas
1) La idea es encontrar una submatriz B de A, tal que, reordenando las columnas si es preciso B sea la identidad en mxm, en este caso el propio vector b, es solución para nuestro problema tomando como vectores aquellos cuyas columnas forman la matriz B.

En el caso de que no exista esta matriz identidad B, añadiremos las llamadas variables artificiales y recurrimos al método de las 2 fases.

2) Tendríamos para alguna fila i de la matriz A una restricción de desigualdad

\( \sum_{j=1}^{n}a_{ij}x_j \leq b_i \)

En este caso tenemos definimos una variable de holgura si positiva para que quede como igualdad

\( \sum_{j=1}^{n}a_{ij}x_j + s_i = b_i , \, s_i \geq 0 \)

Y en el caso que tengamos para la fila i

\( \sum_{j=1}^{n}a_{ij}x_j \geq b_i \)

definimos la variable de holgura, también positiva como

\( \sum_{j=1}^{n}a_{ij}x_j - s_i = b_i , \, s_i \geq 0 \)

Así nuestro problema de desigualdades, se traduce en un problema de igualdades.

3)Si para alguna componente i, la variable no está restringida en signo, entonces podemos hacer

\( x_i = x_{i1} - x_{i2}, \, x_{i1},x_{i2} \geq 0 \)

Es decir, descomponermos la variable i en dos variables positivas.

4) En el caso que tengamos incompatibilidad, podemos intentar reformular el problema para que las restricciones sean compatibles, pues incompatibilidad es decir que nuestro problema no se puede resolver.

En el caso de redundancia simplemente podemos desechar las restricciones redundantes y quedarnos con una de ellas solamente.

5) Si tenemos como función objetivo

\( max\sum_{j=1}^{n}C_j x_j \)

Podemos reformular el problema para tener

\( min\sum_{j=1}^{n}C_j (-x_j) \)

Así tenemos, mediante un cambio de variable un problema de minimización (minimizar es lo mismo que (-1). maximizar).

\( max(-x_1+3x_2) \\ \text{ subject to} \\ \left\{ \begin{matrix} -x_1+2x_2 \leq & 6 \\ x_1+x_2 \leq & 5 \\ 2x_1+2x_2 \leq & 10 & \end{matrix}\right. \).

Las restricciones 2 y 3 son la misma, eliminamos una de ellas, así pues tenemos

\( max(-x_1+3x_2) \\ \text{ subject to} \\ \left\{\begin{matrix} -x_1+2x_2 \leq & 6\\ x_1+x_2 \leq & 5 & \end{matrix}\right. \).

Aplicamos el punto 5), es decir maximizar es lo mismo que cambiar de signo y minimizar.

\( min(x_1-3x_2) \\ \text{ subject to} \\ \left\{\begin{matrix} -x_1+2x_2 \leq & 6\\ x_1+x_2 \leq & 5 & \end{matrix}\right. \).

Aplicamos el punto 2) para obtener restricciones de igualdad

\( min(x_1-3x_2+0x_3+0x_4) \\ \text{ subject to} \\ \left\{\begin{matrix} -x_1+2x_2+x_3 = & 6\\ x_1+x_2 + x_4 = & 5 & \end{matrix}\right. \).

Ahora tenemos resuelto el punto 1), pues ya tenemos una submatriz identidad de A, las referentes a las variables x3, x5
Pasamos a construir la tabla y resolver el problema



Tomamos el mínimo de los negativos en zj - cj = -3, ocurre en la variable x2, así entra en la base el índice 2, o sea s=2.

Ahora calculamos el índice que sale de la base, para ello dividimos cada elemento del vector Xbk por su correspondiente en la columna k de la matriz a, es decir, el mínimo de \( \frac{6}{3} = 3\) y de \( \frac{5}{1} = 1\), tomamos el mínimo, así el índice r que sale de la base es el 3 y el elemento pivote es 2

Ya podemos realizar una iteración del algoritmo del simplex, por ejemplo para la fila de la x4

\( \begin{matrix} \frac{3}{2}&=1-(-1)*\frac{1}{2}=1+\frac{1}{2} & =\frac{3}{2}\\ 0&=1-2*\frac{1}{2}=1-1 & =0\\ -\frac{1}{2}&=0-1*\frac{1}{2}&=-\frac{1}{2}\\ 1 &=1-1*\frac{0}{1}= & =1 \end{matrix} \)

Y los mismo para los Xb, símplemente \( 2 = 5 - 1 * \frac{6}{2} = 5 - 3 \)

Veamos como hemos realizado estos cálculos:

1) Para la fila del pivote, simplemente hemos dividido cada coeficiente por el Pivote.
2) Para las otras filas hemos restado a cada uno el coeficiente de la columna del pivote multiplicado por el coeficiente de la fila del pivote y dividido por el pivote, toda la iteración queda



Realizamos ahora otra iteración, ahora el índice que entra es el 1 y sale de la base el índice 4, así tenemos



Ahora se cumple el criterio de optimalidad ya que

zj - cj > 0, ∀j

Así tenemos solución óptima finita En resumen, el algoritmo del simplex pasa de un punto extremo a otro pivotando la matriz de restricciones es decir, haciendo un cambio de base y calculando los coeficientes en la nueva base mediante el elemento pivote.