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 x
k 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 x
1, x
2, ...,x
s
hasta que se cumpla una cierta condición que se llama "criterio de optimalidad". Si esta condición se cumple en un punto, digamos, x
k
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} \)\( = C_B^tx_B + C_{N}^{t}w_{N} - C^tB^{-1}Nw_{N} \)
Por ser w, punto de la región factible, sabemos que
wN ≥ 0, esto implica que si el punto inicial x, fuera la solución óptima, se tendría que
\((1) \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,C_{N}^{t}-C^t_{B}B^{-1}N\, \geq \, 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^t_{B}B^{-1}N\, \geq\, 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^t_{B}B^{-1}a_{j} = c_{j} - X_{B} a_{j} = c_{j} - z_{j} \)
Siendo a
j, columna de N.
En Resumen, el criterio de optimalidad es en coordenadas
$$ c_{j} - z_{j} \geq 0 $$
Supongamos ahora que (1) no se cumple, es decir
\( C_{N}^{t}-C_{B}B^{-1}N\, < 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 d
j 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.
Determinamos el indice s que cumpla
\( s = min \{ k: \,\ c_{k} - z_{k} < 0 \} \)
Es decir, tomamos como s el índice del mínimo de los negativos de los \( c_{k} - z_{k} \).
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_{s} \)
siendo \( d_{s}=\begin{bmatrix} -B^{-1}a_{s} \\ e_{s} \end{bmatrix} \)
y siendo \( \lambda = min \{ \frac {x_i}{y_{is}}, y_{is} \geqslant 0, x = B^{-1}b \} \)
Con este valor de λ, x es solución factible y si por ejemplo. para un cierto r
\( \lambda = \frac {x_r}{y_{rs}} \)
Entonces x es la solución básica asociada a la matriz
\( B' = (a_1, a_2, ..., a_{r-1},a_s,a_{r+1},...,a_m) \)
s: índice que entra en la base.
r: índice que sale de la base.
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 s).
En resumen, construimos una solución a partir de otra.
Nos resta ahora hacer el cambio de base para obtener la matriz A y los nuevo \(c_j-z_j \). Eso lo veremos en la sección
cálculos del Simplex.
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, pasando de uno a otro mediante un cambio de base ya que estos puntos
son soluciones de sistemas de ecuaciones tomados a partir de submatrices cuadradas de la matriz de restricciones. Las iteraciones paran cuando uno de ellos cumpla el criterio de optimalidad.
