Metodo Simplex

INSTITUTO TECNOLOGICO DE PUEBLA
2012
METODO SIMPLEX
ALFONSO REYES ARVIZU LEONARDO GARCIA ROSALES

ING. EN GESTION EMPRESARIAL

METODO SIMPLEX
Como sabemos, el método simplex es un algoritmo iterativo que iniciando en una solución básica factible pero no óptima, genera soluciones básicas factibles cada vez mejores hasta encontrar la solución óptima (sí esta existe).Nótese que la base de su lógica es mantener la factibilidad, mientras busca la optimalidad. Pero surge la posibilidad de usar otro esquema igualmente iterativo, que como contraparte del simplex, comienza en una solución básica óptima, pero no factible y mantiene la inmejorabilidad mientras busca la factibilidad. Con este procedimiento se llega igualmente a la solución óptima.
El nuevo algoritmofue desarrollo en 1954 por C. E. Lemke y se conoce con el nombre de Método Dual-Simplex. A continuación se presenta su estructura y un ejemplo para ilustrar su aplicación.
La aplicación del método simplex presupone que se tiene un sistema de restricciones lineales formado sólo por ecuaciones lineales. Esta transformación puede ser llevada a cabo de una forma muy simple introduciendo algunasvariables adicionales, las cuales se denominan variables de holgura. Estas variables se definen una para cada restricción y si la misma tiene el signo ≤ la variable de holgura se adiciona y el signo fuera ≥ la variable de holgura se restara.
Luego que se tiene un problema de Programación Lineal estándar, es decir, todas las restricciones tienen signos de igualdad es necesario determinar la soluciónbásica factible inicial (S.B.F.I).
Dado un sistema de m ecuaciones lineales con n variables (AX=b) con m<n y rango r(A)=m. Si escogemos cualquier matriz no singular de orden mxm y si todas las (n-m) variables no asociadas con estas columnas de la matriz son iguales a cero, entonces la solución al sistema de ecuaciones resultante es llamada una solución básica. Como la matriz A consta de ncolumnas se puede definir la matriz B formada por m columnas linealmente independientes de A, esta matriz la llamaremos matriz básica. Con las (n-m) columnas restantes de A se puede construir otra matriz que se denominará matriz no básica y la denotaremos por W. Entonces puede escribirse la matriz A de la siguiente manera: A = (B, W).
Las variables que forman parte de la matriz B se llaman variablesbásicas (XB) y las que forman parte de la matriz W se llaman variables no básica.( XW ), entonces el vector X está conformado por el conjunto de variables básicas y no básicas, es decir, X = (XB, XW).

Entonces el sistema de restricciones del problema de Programación Lineal AX=b puede escribirse de la forma siguiente: AX=BXB + WXW = b. Si asumimos que las variables no básicas tomarán valor cero, laexpresión anterior quedaría BXB =b. La expresión XB = B-1 b que se obtiene a partir de la anterior, permitiría calcular la solución básica factible inicial.
El método simplex se desarrolla en la tabla simplex. Cada iteración requiere de una tabla.
En la primera columna se escribirán los coeficientes de la función objetivo correspondiente a las variables básicas, escribiendo en la segunda columnadichas variables. La tercera columna indica los valores que toman las variables básicas en la solución que se está representando mediante la tabla simplex. El resto de la columnas representan los vectores Pj correspondientes a cada uno de los vectores aj de la matriz A (Pj es el vector coordenado de cada vector aj respecto a la base considerada). En la última fila de la tabla aparecen los valoresZj -Cj correspondiente a cada vector aj. Los coeficientes Zj se determinan utilizando la siguiente expresión: Zj =CBPj

Un empate al elegir la variable que sale se rompe arbitrariamente. El problema ocurre en la siguiente iteración donde los valores de una o más variables básicas llegan a ser cero, en cuyo caso se dice que la solución es degenerada. En este punto no existe la seguridad de...