MÉTODO SIMPLEX MINIMIZACION

HISTORIA

Este famosísimo método fue creado en el año de 1947 por el estadounidense George Bernard Dantzig y el ruso Leonid Vitalievich Kantorovich, con el ánimo de crear un algoritmo capaz de solucionar problemas de m restricciones y n variables.

TEORÍA DEL MÉTODO SIMPLEX

EL MÉTODO SIMPLEX

Es un procedimiento general para encontrar la solución óptima a problemas de

Programación Lineal. Este método logra la solución óptima en un número finito de

Pasos, la demostración de esto es lo que se pretende realizar.

Héctor Martínez Rubín Celis

EL MÉTODO SIMPLEX

El método Simplex es un método secuencial de optimización, es un procedimiento iterativo que permite ir mejorando la solución a cada paso. El proceso concluye cuando no es posible seguir mejorando más dicha solución.

Ing. Napoleón Castro

MÉTODO SIMPLEX

El método Simplex es un procedimiento iterativo que permite mejorar la solución de la función objetivo en cada paso. El proceso concluye cuando no es posible continuar mejorando dicho valor, es decir, se ha alcanzado la solución óptima (el mayor o menor valor posible, según el caso, para el que se satisfacen todas las restricciones).

Será necesario tener en cuenta que el método Simplex únicamente trabaja con restricciones del problema cuyas inecuaciones sean del tipo "≤" (menor o igual) y sus coeficientes independientes sean mayores o iguales a 0. Por tanto habrá que estandarizar las restricciones para que cumplan estos requisitos antes de iniciar el algoritmo del Simplex. En caso de que después de éste proceso aparezcan restricciones del tipo "≥" (mayor o igual) o "=" (igualdad), o no se puedan cambiar, será necesario emplear otros métodos de resolución, siendo el más común el método de las Dos Fases.

RESTRICCIONES DEL MÉTODO SIMPLEX

Tipo de desigualdad	Tipo de variable que aparece
≥	- holgura + artificial
=	+ artificial
≤	+ holgura

• Restricción de tipo "≤"

Para normalizar una restricción con una desigualdad del tipo "≤", hay que añadir una nueva variable, llamada variable de holgura xs (con la condición de no negatividad: xs ≥ 0). Esta nueva variable aparece con coeficiente cero en la función objetivo, y sumando en la ecuación correspondiente (que ahora sí será una identidad matemática o ecuación de igualdad).

                                     

             Restricción de tipo "≥"

En caso de una desigualdad del tipo "≥", también hay que añadir una nueva variable llamada variable de exceso xs (con la condición de no negatividad: xs ≥ 0). Esta nueva variable aparece con coeficiente cero en la función objetivo, y restando en la ecuación correspondiente.

Surge ahora un problema con la condición de no negatividad con esta nueva variable del problema. Las inecuaciones que contengan una desigualdad de tipo "≥" quedarían:

            Restricción de tipo "="

Al contrario de lo que cabría pensar, para las restricciones de tipo "=" (aunque ya son identidades) también es necesario agregar variables artificiales xr. Como en el caso anterior, su coeficiente será cero en la función objetivo y aparecerá sumando en la restricción correspondiente.

VARIABLES DEL MÉTODO SIMPLEX

VARIABLE ARTIFICIAL

Una variable artificial es un truco matemático para convertir inecuaciones ">=" en ecuaciones, o cuando aparecen igualdades en el problema original, la característica principal de estas variables es que no deben formar parte de la solución, dado que no representan recursos. El objetivo fundamental de estas variables es la formación de la matriz identidad.

 Estas variables se representa por la letra "A", siempre se suman a las restricciones, su coeficiente es M por esto se le denomina Método de la M grande, donde M significa un número demasiado grande muy poco atractivo para la función objetivo

VARIABLE  DE  HOLGURA

Variables de holgura o excedente. Son variables que se agregan a la restricción para que la relación de la restricción sea de igualdad (representa el valor que le hace falta al lado izquierdo para ser igual al lado derecho). Ambos tipos de variables tienen que cumplir con la restricción de no negatividad

LA VARIABLE QUE ENTRA 

Cuando una variable se vuelve básica, es decir, entra en la base, comienza a formar parte de la solución. Observando los costes reducidos en la fila Z, se decide que entra a la base la variable de la columna en la que éste sea el de menor valor 

LA VARIABLE QUE SALE 

Una vez obtenida la variable entrante, se determina que sale de la base la variable que se encuentre en aquella fila cuyo cociente P0/Pj sea el menor de los estrictamente positivos 

                                                                  ELEMENTO PIVOTE

El elemento pivote de la tabla queda marcado por la intersección entre la columna de la variable entrante y la fila de la variable saliente.