Metodo Simplex, Investigation de operaciones

METODO SIMPLEX

• El método simplex analiza solo soluciones factibles de los vértices
• El método simplex es un algoritmo iterativo (un procedimiento de solución sistemática) que repite una serie de pasos, hasta que obtiene el resultado.

Iniciación

[pic 1]

Prueba de optimilidad [pic 2][pic 3]

                        [pic 4]

                             No

Iteración[pic 5]

    Si

Termina

Ejemplo del Simplex  ≤

Max Z = 3 X1  +  5 X2

Sujeto a   X1                        ≤    4          

                            X2               ≤      12          

            3 X1  +  2 X2             ≤     18        

1º Paso: las restricciones factibles de desigualdad se convierten en igualdad.

Max Z        = 3 X1  +  5 X2

Sujeto a            X1                      =  4                                      

                                      X2            =  12                      

                      3 X1  +  2 X2           =  18                        

2º paso: se introducen las variables de holguras (S), Al introducir las variables de holgura se dice que el modelo se ha aumentado

Max Z = 3 X1  +  5 X2

Sujeto a   X1                 +   S1                          =  4          Ec(1)

                            X2                     +   S2              =  12         Ec(2)

             3 X1  +  2 X2                                 + S3    =  18         Ec(3)

S1 =  S2   = S3 = 0, acompañadas del signo +, coeficiente 1

.3º Paso: se aumenta la función objetivo:

Max Z = 3 X1  +  5 X2 - 0 S1  - 0 S2   - 0 S3

Las variables de holgura están acompañadas del signo -, coeficiente 0

4º Paso: la función objetivo se hace cero:

Max Z - 3 X1  -  5 X2 + 0 S1  +  0 S2   + 0 S3  = 0       Ec(0)

5º paso: tabular: iteración 0

Variables iniciales:  Variables decisión (X1,  X2),  Variables Básicas (Z, S1,  S2,  S3)

[pic 6]

[pic 7]

 [pic 14][pic 15]

1. Hay que determinar la variable entrante, la que tiene el coeficiente negativo más alto (X2).  Luego se coloca un recuadro debajo del coeficiente y se llama columna pivote.  

b. La variable saliente se busca por el cociente mínimo. Se divide los coeficientes del lado derecho entre los coeficientes de la columna pivote (siempre debe ser mayor que cero) y se selecciona el mínimo valor, esa sería la variable saliente.

Iteración 1[pic 16]

[pic 17]

1. X2 sustituye a S2. Luego se divide el renglón pivote entre en número pivote, para obtener el valor se X2.

c. el valor de Z1, se calcula así:   Z0  +  5 X2,    5, es el coeficiente de intercepción de Z y X2  siempre en el cálculo de Z se suma

1. el valor se S1,1 = S1,0  -  0 X2, 0 es el coeficiente de intercepción de S1,0  , y X2

e. el valor de S3,1  = S3,0  -   2 X2,  2 es el coeficiente de intercepción de S3,0  , y X2

f. nueva variable entrante X1 , variable saliente S3

nota: cuando el valor en la columna pivote es positivo (+), para hallar el valor de la nueva variable se resta (-), sin embargo cuando el valor es negativo (-) se suma (+)

iteración 2

...