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]

...