El Elemento Pivote y los Cálculos del Método del Simplex

Conceptos y Principios Básicos

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 de la matriz de restricciones A), 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:

Salidas posibles del algoritmo del Simplex y del método de las dos fases


1) El criterio de optimalidad se cumple en un único punto, en este caso tenemos solución optima finita. Ejemplo aquí

2) El criterio de optimalidad se cumple, pero hay infinitos puntos que también lo cumplen, este es el caso de infinitas soluciones. Ejemplo aquí

3) En las iteraciones llegamos al caso de solución no acotada. Ejemplo aquí

4) No podemos continuar el algoritmo y no hemos alcanzado el criterio de optimalidad. Las restricciones son incompatibles, en este caso el problema no tiene solución. Ejemplo aquí

Teoría en extensión

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 seria B, el vector Xb sería el punto extremo que nos permite inciar las iteraciones del algoritmo estaria formado por los elementos del vector C, es para él que calculamos los zj - cj. (Recordamos que zj = Xbiyi,j o también

zj = CBt B-1 aj (notar que B es, en este paso, la matriz identidad.)


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

     zj - cj <0, ∀j

En caso de que no se cumpla, tomamos el índice k de los j que hace que

    zk - ck = max(zj - cj), tales que zj - cj >0

es decir, tomamos el supremo de los positivos en los zj - cj.
Ahora, con este índice k, buscamos el elemento que llamaremos Pivote. Para ello, dividimos cada coordenada i del vector Xb por su coordenada i del vector columna yik y calculamos el mínimo de los positivos, o sea

    yik = min {i: βi/yik, yik>0 }, siendo los βi coordenadas del vector Xb

Si el mínimo anterior fuera -1 (es decir, ninguno es positivo), estaríamos en el caso de solución no acotada, pues ello indicaría que para todo índice i

    βi/yik ≤ 0

y estaríamos en el caso de solución no acotada como hemos visto en la sección El algoritmo del Simplex.

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

Elemento Pivote del Algoritmo del Simplex


Se llama Elemento Pivote del Algoritmo del Simplex a aquel de los yik de la matriz de restricciones cuyos índices i y k cumplen

k = max(zj - cj), tal que zj - cj >0

i = min {i: βi/y ik, y ik>0 }


en cuyo caso ya tenemos, k será el nuevo índice de las x que entra en la base e i es el índice de los Xb que sale de la base.
Ahora recalculamos toda la tabla en esta nueva base, para ello calculamos la matriz A de la siguiente manera

Cálculo de la matriz de restricciones en la nueva base


y'sj = ysj - (ysk * ysj)/yik
y'ij = yij/yik

Esta es la base del algoritmo para invertir la matriz de restricciones.

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

Veremos al final de esta sección un ejemplo práctico del funcionamiento del algoritmo. Tenemos los siguientes problemas:
1) ¿Como encontrar una solución primera para que el algoritmo comience las iteraciones? Esto es equivalente a encontrar una submatriz identidad mxm de A.

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, recurrimos al método de las 2 fases.

2) Tendríamos para alguna fila i de la matriz A

En este caso tenemos definimos una variable de holgura

Y en el caso que tengamos para la fila i, definimos la variable de holgura

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

    xi = xi1 - xi2 con xi1, xi2 ≥0

4) En el caso que tengamos incompatibilidad, podemos intentar reformular el problema para que las restricciones sean compatibles, pues incompatibilidad es lo mismo que 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

Podemos reformular el problema para tener

Así, tenemos la regla que "maximizar una variable es lo mismo que cambiar de signo esa variable y minimizar esa variable".

Ejemplo Práctico

    Max(- x1 + 3x2)
    -x1 + x2 ≤6
    x1 + x2 ≤5
    2x1 + 2x2 ≤10

Aplicamos el punto 3) para las restricciones 2 y 3, ambas son la misma, eliminamos una de ellas, así pues tenemos

    Max(- x1 + 3x2)
    -x1 + x2 ≤6
    x1 + x2 ≤5

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

    Min(x1 - 3x2)
    -x1 + x2 ≤6
    x1 + x2 ≤5

Aplicamos el punto 2)

    Min(x1 - 3x2 + 0x3 + 0x4)
    -x1 + x2 + x3 = 6
    x1 + x2 + x4 = 5

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

Tomamos el mínimo de los positivos en zj - cj
En nuestro caso, 3 se da para la variable y2, así entra en la base el índice 2, o sea k=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 6/2 y de 5/1     min (6/2, 5/1) = 3 , el índice que sale de la base es el 3 y el elemento pivote es 2
Ya podemos realizar una iteración del algoritmo del simplex, queda así
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, por ejemplo

    3/2 = 1 - (-1) * 1/2 = 1 + 1/2
    0 = 1 - 2 * 1/2 = 1 - 1
    -1/2 = 0 - 1 * 1/2 = 0 - 1/2
    1 = 1 - 1 * 0/1 = 1 - 0

3) Y los mismo para los Xb, símplemente 2 = 5 - 1 * 6/2 = 5 - 3

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
x1 = 4/3
x2 = 11/3
Lo que da una optimización para la función objetivo de
s = 12/3 - 11/3 = 1/3
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.





Ha sido util? Alguna idea para complementar el texto?



Deja tu post

Comentarios de otros usuarios





Deja tu post