El Método simplex

EL METODO SIMPLEXSIMPLEX PRIMAL

YESID ARIZA OSORIOASESORAMIENTO EMPRESARIAL & GESTIONCAPACITACION Y ENTRENAMIENTO


Es una herramienta matemática que resuelve problemas de planeación y programación de operaciones; es decir, resuelve la pregunta sobre cuánto producir de acuerdo a la capacidad operativa y estudios de mercado

Utiliza el modelo de la Programación Lineal, a través de la solución de una matriz, usando el método de eliminación de Gauss Jordan.


METODOLOGIA DE TRABAJOIdentificación de la función objeto y las restricciones

Construcción del modelo de programación lineal de forma estándar

Construcción de un modelo matricial

Solución de la matriz por método de eliminación (Gauss Jordan)

Se obtiene a partir del enunciado del ejercicio y en la práctica, a partir de entrevistas

y/o observación

•Las variables se consideran positivas•Se suman o restan variables básicas o supuestas para eliminar la inecuación•Se asegura que el signo del número al otro lado de la solución sea positivo

Se construye una matriz, generalmente de dos dimensiones, una para las variables básicas incluyendo a Z (Función objeto) y otra para todas las variables

Se utiliza la eliminación identificando en cada iteración la columna de entrada y la ecuación pivote


IDENTIFICACION DE LA FUNCION OBJETO Y LAS RESTRICCIONES

Ejemplo

Maximizar Z= 3X + 2Y, sujeto a:

X+2Y<=62X+Y<=8-X+Y<=1Y<=2

Considere todas las variables positivas


CONSTRUCCION DEL MODELO DE PL USANDO LA FORMA ESTANDAR

Función Objeto

Se debe agrupar las variables de un solo lado de la ecuación, entonces:

Z=3X+2Y, queda como-3X-2Y+Z=0

Inecuaciones

Sumar o restar una variable supuesta teniendo en cuenta el sentido de la inecuación; si es menor que se suma, si es mayor que, se restaDe ser necesario cambiar el signo de toda la igualdad para que el número del otro lado del igual sea positivo

X+2Y<=6X+2Y+S1=6

2X+Y<=82X+Y+S2=8

-X+Y<=1-X+Y+S3=1

Y<=2Y+S4=2


MODELO DE PL USANDO LA FORMA ESTANDAR

Restricciones

Función Objeto -3X-2Y+Z = 0

X+2Y+S1 = 6 2X+Y+S2 = 8 -X+Y+S3 = 1 Y+S4 = 2

Los números después del signo igual, se consideran posibles soluciones, ellos deben colocarse en la casilla correspondiente de la matriz para solucionar el modelo de Simplex

Los números delante de las variables son sus coeficientes


DISEÑO DE LA MATRIZ

Básica Z X Y S1 S2 S3 S4 Solución

Z

S1

S2

S3

S4

Esquema de la matriz


DISEÑO DE LA MATRIZ


Z 1 -3 -2 0 0 0 0 0

S1 0 1 2 1 0 0 0 6

S2 0 2 1 0 1 0 0 8

S3 0 -1 1 0 0 1 0 1

S4 0 0 1 0 0 0 1 2

Se toman los coeficientes de las ecuaciones del modelo de PL de forma estándar y se colocan en su lugar correspondiente de acuerdo con la identificación de las filas y columnas de la matriz


SOLUCION DE LA MATRIZ(Condiciones de optimidad y de factibilidad)

CONDICIÓN MAXIMIZACIÓN MINIMIZACIÓN

Optimidad

La variable entrante es la que tiene el coeficiente mas negativo en la ecuación objeto.

La variable entrante es la que tiene el coeficiente mas positivo en la ecuación objeto.

El empate (dos números iguales, se rompe de manera arbitraria

El nivel óptimo se alcanza cuando los coeficientes No Básicos de la ecuación Z son No Negativos.

El nivel óptimo se alcanza cuando los coeficientes No Básicos de la ecuación Z son No Positivos.

Factibilidad La variable saliente es la variable básica con menor razón positiva entre la solución y el coeficiente en la dirección de la variable entrante.


SOLUCION DE LA MATRIZ(Identificación de Columna de Entrada, Ecuación Pivote y Elemento Pivote)


Z 1 -3 -2 0 0 0 0 0

S1 0 1 2 1 0 0 0 6 6/1=6

S2 0 2 1 0 1 0 0 8 8/2=4

S3 0 -1 1 0 0 1 0 1 1/-1=-1

S4 0 0 1 0 0 0 1 2 2/0=∞

Coeficientes de las variables No Básicas en la función Objeto

Columna de Entrada

Ecuación Pivote; tiene la menor razón positiva Pivote


SOLUCION DE LA MATRIZ(ITERACIONES)

Se utiliza el método de eliminación Gauss Jordan para calcular los nuevos coeficientes, según las siguientes operaciones del cálculo:

Nueva Ecuación Pivote = Ecuación Pivote / Elemento Pivote

Nueva Ecuación = Ecuación anterior – Coeficientes

Columna entrada

Nueva Ecuación

Pivotex




Z

S1

X 0 1 ½ 0 ½ 0 0 4

S3

S4

Utilizamos el cálculo de la nueva Ecuación Pivote, dividimos cada coeficiente entre el elemento pivote, el resultado es:

Note que la variable X pasó a ser básica


Calculamos cualquiera de las ecuaciones de la nueva Iteración, el ejemplo es el cálculo de la primera fila (Ecuación objeto)

Ecuación anterior 1 -3 -2 0 0 0 0 0

Coeficiente Columna Entrada (CCE) -3

Nueva Ecuación Pivote 0 1 1/2 0 1/2 0 0 4

CCE x Nueva Eq. Pivote 0 3 3/2 0 3/2 0 0 12

Nueva Ecuación 1 0 -1/2 0 3/2 0 0 12




Z 1 0 -1/2 0 3/2 0 0 12

S1

X 0 1 ½ 0 ½ 0 0 4

S3

S4

Se escriben los valores en la fila correspondiente de la Matriz (primera fila)



SOLUCION DE LA MATRIZ(SOLUCIÓN)


Z 1 0 0 1/3 4/3 0 0 12+2/3

Y 0 0 1 2/3 -1/3 0 0 4/3

X 0 1 0 -1/3 2/3 0 0 10/3

S3 0 0 0 -1 1 1 0 3

S4 0 0 0 -2/3 1/3 0 1 2/3

Se realizan las Iteraciones que sean necesarias, identificando una y otra vez la Columna de Entrada, la Ecuación Pivote y el elemento pivote, hasta que se cumpla el valor óptimo descrito en la condición de Optimidad. La matriz resultante es la siguiente:


SOLUCION DE LA MATRIZ(SOLUCIÓN)


Z 1 0 0 1/3 4/3 0 0 12+2/3

Y 0 0 1 2/3 -1/3 0 0 4/3

X 0 1 0 -1/3 2/3 0 0 10/3

S3 0 0 0 -1 1 1 0 3

S4 0 0 0 -2/3 1/3 0 1 2/3

La solución es, los valores de X y Y que hacen máxima a Z, son 10/3 y 4/3 respectivamente y el valor máximo de Z es 12 +2/3

Education

El Método simplex