El Algoritmo del Simplex

Conceptos y Principios Básicos

El Algoritmo del Simplex cuya invención se debe a George Dantzig en 1947 y le valió en 1975 la Medalla Nacional de la ciencia es el principal método para resolver problemas de programación lineal.
El algoritmo del Simplex realiza iteraciones entre el conjunto de puntos extremos del conjunto factible, comprobando en cada uno si se cumple el Criterio de Optimalidad.


Dado un problema de programación lineal en forma estándar que llamaremos P:
Minimizar \( C^t x \)

Sujeto a

\( \begin{matrix} Ax=b \\ x\geqslant 0 \end{matrix} \)

Donde

\( A \in \mathbb M _{mxn}, \, rnk(A)=m ,\,\, b \in R^{m}, \, C \in R^{n}, \,\, n \geqslant m \)
Así, m es el número de restricciones (o número de filas de la matriz A, también es la dimensión del vector b) y n es el número de incógnitas (columnas de la matriz A ó dimensión del vector C).

Si el problema P tiene solución optima finita en xk sabemos, de la Teoría de la Programación Lineal que dicha solución estará entre el conjunto de puntos extremos del conjunto factible, S.

La idea básica del algoritmo del Simplex es realizar iteraciones entre los puntos extremos del conjunto factible x1, x2, ...,xs hasta que se cumpla una cierta condición que se llama "criterio de optimalidad". Si esta condición se cumple en un punto, digamos, xk entonces esa será la solución que estamos buscando.

Teoría en extensión


Dado el problema P, supongamos que tenemos x, punto extremo de S. Este punto extremo será una solución de la forma

\( x=\begin{bmatrix} B^{-1}b \\ 0\end{bmatrix} \).

con B submatriz de A rango m.

Así podemos descomponer A en dos matrices:

\( A=\begin{bmatrix} B \\ N\end{bmatrix} \)

B es como hemos dicho submatriz de A mxm y N es la submatriz de A formada por las n-m filas restantes (recordar que n≥m).

Sea ahora w otro punto de la región factible, S. Entonces

\( Aw = b,\, es\,\,decir \)

\(Bw_{B} + Nw_{N} = b \)

Como B es invertible se tiene

\(w_{B} = B^{-1}b - B^{-1}Nw_{N} \)

Aplicando Ct a w

\( C^{t}w = C_{B}^{t}w_{B} + C_{N}^{t}w_{N} = C_{B}^{t}(B^{-1}b - B^{-1}Nw_{N}) + C_{N}^{t}w_{N} \).

Por ser w, punto de la región factible, sabemos que

    wN ≥ 0, esto implica que si x fuera la solución óptima, se tendría que

\((1) \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,C_{N}^{t}-C_{B}B^{-1}N\, >\, 0\)

Esta es la idea central subyacente algoritmo del simplex a la que nos referíamos antes, también se llama criterio de optimalidad:

criterio de optimalidad del Algoritmo del Simplex


$$ C_{N}^{t}-C_{B}B^{-1}N\, >\, 0 $$
Si se cumple esta condición entonces x será la solución óptima.
La ecuación del criterio de optimalidad tiene como coordenadas

\(c_{j} - C_{B}^{-t}B^{-1}a_{j} = c_{j} - C_{B}^{-t}y_{j} = c_{j} - z_{j} \)

Siendo aj, columna de N.
En Resumen, el criterio de optimalidad es

$$ c_{j} - z_{j} < 0 $$

Supongamos ahora que (1) no se cumple, es decir

\( C_{N}^{t}-C_{B}B^{-1}N\, \geqslant 0 \)
Entonces hay dos posibilidades.

Primera posibilidad



\( y_{j} = B^{-1}a_{j} \leqslant 0, \; \forall j \), entonces podemos construir

\( x= w+\lambda d_{j} \) siendo \( d_{j}=\begin{bmatrix} -B^{-1}a_{j} \\ e_{j} \end{bmatrix} \)

Sabemos que dj es una dirección extrema del conjunto factible S, en particular

\( Ad_{j} = 0 \)

por tanto

\( x= w+\lambda d_{j} \) es también solución factible \( \forall \lambda d_{j} \geqslant 0 \) .

Por otro lado

\( C^{t}x = C^{t} (w+\lambda d_{j} ) = C^{t}w + \lambda(-C^{t}B^{-1}a_{j})d_{j} = C^{t}w - \lambda(z_{j}-c_{j}) \mapsto - \infty \) cuando \( \lambda \mapsto \infty \)

Esto quiere decir que podemos hacer la solución tan pequeña como queramos sin salirnos del conjunto factible S, por tanto estamos en el caso de solución es no acotada .

Segunda posibilidad



El vector \( y_{j} \) tiene alguna componente positiva. Entonces podemos construir otra solución factible (la cual estará también dentro del conjunto de puntos extremos de S) en la que la función es más pequeña.
La nueva solución se construye así

\( x= w+\lambda d_{j} \)

siendo \( d_{j}=\begin{bmatrix} -B^{-1}a_{j} \\ e_{j} \end{bmatrix} \)

y siendo \( \lambda = min \{ \frac {\beta}{y_{ij}}, y_{ij} \geqslant 0, \beta = B^{-1}b \} \)

Con este valor de λ, x es solución factible y si por ejemplo. para un cierto i

\( \lambda = \frac {\beta}{y_{ij}} \) entonces x es la solución básica asociada a la matriz

Entonces x es la solución básica asociada a la matriz

    B, = (a1, a2, ..., ar-1, aj, ar+1, ..., , am )

Es decir, hemos intercambiado un vector por otro (hemos sacado el que estaba en el lugar r y lo hemos sustituído por el que está en el lugar j).

En resumen, construimos una solución a partir de otra.

Observación: si varios índices j, verifican el criterio de optimalidad:

$$ z_{j} - c_{j} > 0 $$

Entonces la operación anterior se realiza sobre el índice k que cumple

$$ z_{k} - c_{k} = max \{ z_{j} - c_{j}, \,\ z_{j} - c_{j} > 0 \} $$

Es decir, se toma el máximo de los positivos de los zj - cj

Resumen del Método Simplex,



Los puntos extremos x0, ..., xs, son las soluciones del sistema

     Bx=b, con B submatriz mxm de rango m de la matriz inicial A.

La solución óptima, si existe debe estar entre estos puntos...

Dado un punto extremo xi de la región factible, probamos si se cumple el criterio de optimalidad en él, en cuyo caso xi es la solución óptima buscada.
En caso contrario, pueden ocurrir dos cosas:
    1) Caso de solución no acotada.
    2) Se puede pasar al punto extremo siguiente y hacer la prueba del criterio de optimalidad para él.
Esta es la idea del algoritmo del simplex, iterar entre los puntos extremos del conjunto factible, los cuales son soluciones de sistemas de ecuaciones tomados a partir de submatrices cuadradas de la matriz de restricciones, hasta que uno de ellos cumpla el criterio de optimalidad

Nos resta aún el problema de cómo obtener estas soluciones, ya veremos en la sección cálculos del Simplex cómo el algoritmo del Simplex nos ofrece un cálculo en el cual no es preciso calcular la inversa de la matriz A. En lugar de eso, se realiza un cálculo llamado "pivotar la matriz" que es la idea básica del algoritmo del Simplex.





Ha sido util? Alguna idea para complementar el texto?



Deja tu post

Comentarios de otros usuarios

mariano reyes:

2016-10-12 14:48:20
muy interesante pagina

davidd:

2015-01-26 21:43:50
Muy buen post. Agadecido por el texto pues se deduce la condición del criterio de optimalidad de manera muy simple. Gracias. Saludos




Deja tu post