El Método Simplex.

Pablo Antonio Rangel Aguilar                                                                                 TM903

Método Simplex.

Es un método analítico para la solución de problemas de programación lineal en e cual se pueden resolver modelos complejos. Es un método iterativo con el cual se puede mejorar la resolución de cada paso. Este proceso se pude dar por concluido cuando cuando ya no es posible mejorar el valor, es decir se ha alcanzado la solución optima.

Partiendo de la función objetivo en un punto cualquiera, este procedimiento consiste en buscar otro punto que mejore el valor anterior. Se usan los puntos de los vértices de un polígono que constituye la región determinada por la restricciones a las que se encuentra sujeto el problema. Se debe desplazar por los aristas del polígono desde uno de sus vértices hasta uno adyacente que mejore el valor de la función objetivo. El numero de vértices y aristas es finito por o tanto será posible encontrar una solución.

El método Simplex se basa en la siguiente propiedad: si la función objetivo Z no toma su valor máximo en el vértice A, entonces existe una arista que parte de A y a lo largo de la cual el valor de Z aumenta.

Este método solo trabaja con restricciones del problema cuyas inecuaciones sean del tipo "≤" y su coeficiente independiente sea mayor o igual a 0. En caso se aparecer restricciones "≥ o =" será necesario emplear otro método de resolución.

Este método trabaja mediante programación de ecuaciones lineales pero para esto hay que convertir las ecuaciones en variables conocidas como holgura y exceso las cuales juegan un rol fundamental en la creación de matriz identidad base del simplex. Estas variables son representadas por la letra "S" y se suman si las restricciones son  "≤" caso contrario si son "≥".

Optimización.

Condición de parada: cuando en la fila Z no aparece ningún valor negativo.

Condición de entrada a la base: el menor valor negativo en la fila Z (o el de mayor valor absoluto entre los negativos) indica la variable Pj que entra a la base.

Condición de salida de la base: una vez obtenida la variable entrante, la variable que sale se determina mediante el menor cociente P0/Pj de los estrictamente positivos.

Minimización.

Condición de parada: cuando en la fila Z no aparece ningún valor positivo.

Condición de entrada a la base: el mayor valor positivo en la fila Z indica la variable Pj que entra a la base.

Condición de salida de la base: una vez obtenida la variable entrante, la variable que sale se determina mediante el menor cociente de los estrictamente negativos.

Desarrollo del método Simplex.

[pic 1]

Construcción de la tabla.

Las columnas de la tabla estas acomodadas de la siguiente forma: la primer columna de la tabla contiene las variables que se encuentran en la base, es decir las que toman valor para proporcionar una solución. La segunda columna es para los coeficientes que dichas variables tienen en la función objetivo. En la misma tabla se agregan dos filas; la primera donde se reflejaran los coeficientes de las variables de la función objetivo y la otra donde se pondrán los valores de la función objetivo y los costes reducidos.

...