El Algoritmo del Simplex

Conceptos y Principios Básicos

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.
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.

Dado un problema de programación lineal en forma estándar que llamaremos P:
     Minimizar Ctx
Sujeto a
     Ax = b
     x ≥ 0
Donde
\( A \in M_{mxn}, con \, rango(a)=m, \, b\in R^{m}, \, C\in R^{n} \)
Por tanto, m es el número de restricciones (filas de la matriz A o 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. (t, significa la transpuesta de la matriz, no es un exponente).

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

    cj - CBtB-1 aj = cj - CBtyj = cj - zj

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

    zj - cj < 0, con zj = CBt B-1 aj

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

    CNt - CBt B-1 N ≥ 0       (2)
Entonces hay dos posibilidades.

    1)yj = B-1aj ≤ 0 ∀j , entonces podemos construir

    x = w + λ dj, siendo dj = (-B-1aj, ej)t

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

    Adj = 0

por tanto

    x = w + λ dj es también solución factible ∀ λ ≥ 0.

Por otro lado

    Ctx = Ctw + λdj = Ctw + λ(-CtB-1aj) dj = Ctw - λ(zj - cj) → -∞ cuando λ → ∞

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 .

    2) El vector yj = B-1aj 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 + λdj

siendo dj = (-B-1aj ej)t

y siendo λ = min{β/yij : yij > 0}, β = B-1 b.
Con este valor λ, x es solución factible y si por ejemplo

    λ = βj/ yij

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 que

    zj - cj > 0

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

    zj - ck = max (zj - cj), con zj - cj > 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
Queda el problema de obtener estas soluciones, veremos en la sección cálculos del Simplex como el algoritmo del Simplex nos ofrece un cálculo en el cual no es preciso realizar la inversa de la matriz A. A este cálculo se le llama pivotar la matriz y es otro elemento básico 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