Algoritmo Simplex

Algoritmo simplex

El algoritmo del Simplex busca el óptimo de un problema de P.L. recorriendo sólo algunos de los vértices del poliedro que representa el conjunto de soluciones factibles. En cada iteración, al algoritmo se desplaza de un vértice a otro de forma que el valor de la función objetivo mejore con el desplazamiento, esto es, que aumente si el problema es de maximización, o disminuya si el problema es de minimización. La optimización de un P.L. puede dar lugar a cuatro posibles resultados:

a) Alcanzar un óptimo único.

b) Alcanzar un óptimo que no es único (soluciones alternativas o múltiples).

c) Concluir que el problema es no factible, esto es, que no existe ninguna solución que satisfaga simultáneamente todas las restricciones del problema.

d) Concluir que el problema es no acotado, es decir, que el valor de la función objetivo en el óptimo es tan grande como se desee si el problema es de maximización, o tan pequeño como se quiera si el problema es de minimización. El método Simplex alcanza siempre uno de estos resultados en un número finito de iteraciones. En cada iteración se pasa de una solución básica factible a otra, de manera que en el proceso, el valor de la función objetivo mejora en cada iteración. Cuando se determina que no existe ninguna SBF con un mejor valor de la función objetivo que el actual se detiene el proceso puesto que se ha llegado al óptimo.

A continuación se desarrolla el algoritmo del Simplex teniendo en cuenta tres reglas para llegar al óptimo: regla de entrada en la base, regla de salida de la base y test de optimalidad.

4.3.1. Costes reducidos y test de optimalizad.

Sea un P.L. en el que todas las restricciones han sido reducidas a igualdades

mediante las transformaciones adecuadas:

Max(z)=cTX

sujeto a:

Ax = b

x ≤0

A partir de una SBF cualquiera puede realizarse la descomposición:

Z=C_B^T X_B+C_N^T X_N 〖BX〗_B+〖NX〗_N=b

Suponiendo que la matriz B admite inversa, puede despejarse X_(b )en (la ecuación 2 ) de forma que se obtiene:

X_B=B^(-1) b-B^(-1) NX_B y susituyendo

...