Metodo Simplex

PROGRAMACIÓN LINEAL

MÉTODO SIMPLEX PRIMAL paso a paso

El método simplex fue inventado en 1947 por el matemático George Dantzig

Se utiliza para resolver problemas de programación lineal, donde intervienen tres o más variables.

El algebra matricial y el proceso de eliminación de Gauss-Jordan para resolver un sistema de ecuaciones lineales son la base del método simplex

EJERCICIO

Una negocio familiar produce dos tipos de dulces.

El dulce A debe contener en gramos: 6 de leche y 4 de azúcar.

El dulce B debe contener en gramos: 5 de leche y 3 de azúcar.

Cada semana el negocio puede obtener 160 kilos de leche y 100 kilos de azúcar.

Pueden elaborar a lo más 250 k de los dulces. Si obtienen una utilidad de $300 por cada kilo del duce A y $200 por kilo de dulce B ¿Qué cantidades de cada tipo deberán producir a fin de obtener la máxima utilidad?

1. Sacamos la información del problema

Leche azúcar

Dulce A = X 6 4

Dulce B = y 5 3

Materia prima disponible 160 100

Como dice a lo más es una desigualdad menor que y las representamos:

Con las siguientes restricciones éstas están dadas por la máxima cantidad de lo que pueden obtener:

2. Ahora igualamos las variables que tenemos agregando una nueva variable a cada igualdad llamada de holgura

Y la función objetivo

se iguala a cero:

3. Se elabora la tabla simplex como en el método de Gauss- Jordán

Observen la tabla en cada igualdad donde no hay variable se pone cero

1 x 2 y 3 s 4 t 5 v 6 z 7 igual

1 6 5 1 0 0 0 160

R2/4 2 4 3 0 1 0 0 100

3 1 1 0 0 1 0 250

4 -300 -200 0 0 0 1 0

Las variables de holgura toman el valor de 1 así como el de z y quedan en diagonal en la matriz como pueden obsevar.

4. En Gauss se debe hacer uno la C1,1 ( renglón uno columna uno)

En el METODO SIMPLEX PRIMAL la igualdad se va a dividir entre la primer columna y valor más pequeño ese es que se hará uno y se llama renglón pivote. El valor negativo se ignora, no se divide.

El que haremos uno será el del renglón 2, dividiendo todo el renglón entre 4

:

EN UNA NUEVA TABLA COLOCAMOS LOS VALORES OBTENIDOS en el renglón 1 Y LOS DEMÁS RENGLONES SE QUEDAN IGUAL.

1 x 2 y 3 s 4 t 5 v 6 z 7 igual

R1-6R2 1 6 5 1 0 0 0 160

2 1 3/4 0 1/4 0 0 25

R3-R2 3 1 1 0 0 1 0 250

R4 +300R2 4 -300 -200 0 0 0 1 0

5. Igual que en Guas hacemos ceros los renglones que están abajo y arriba del uno.

Ahora, con los valores obtenidos elaboramos otra tabla

1 x 2 y 3 s 4 t 5 v 6 z 7 igual

1 0 1/2 1 3/2 0 0 10

2 1 3/4 0 1/4 0 0 25

3 0 1/4 0 -1/4 1 0 225

4 0 25 0 75 0 1 7500

En el método simplex terminamos las iteraciones cuando en el renglón de z NO QUEDA NINGÚN VALOR NEGATIVO, si quedará valor negativo en el renglón de z iniciamos de nuevo las iteraciones.

CONCLUSIÓN:

EN LA COLUMNA DE “X” VEMOS QUE HAY UN UNO, NOS VAMOS A LA COLUMNA DE IGUALDAD Y VEMOS QUE SU VALOR ES 25, EN LA COLUMNA DE “Y” NO VEMOS NINGÚN UNO, ENTONCES SIGNIFICA QUE NO FABRICARÍAMOS PRODUCTOS “B” Y SOLAMENTE 25 KILOS PRODUCTOS DE “A” CON UN BENEFICIO DE $7500 QUE NOS EL UNO EN LA COLUMNA DE “Z”

...