Metodo simplex

PROBLEMAS SIN SOLUCIÓN ÓPTIMA
Ejemplo 1

Maximizar z  x1  x 2  s.a. x  3x  9  1 2  2x1  x 2  2    x1 , x 2  0  

 

Maximizar z  x1  x 2  Mx 4  s.a. x  3x  x  x  9  1 2 3 4  2x1  x 2  x 5  2     x1 , x 2 , x 3, x 4 , x 5  0 

 

                              1                      1  x 1  1    2  M+1  ‐5    2  1‐5M  x 2  3  1  3M+1  0  1  0             0                      ‐M                0  x 3  ‐1  0  ‐M  ‐1  0  ‐M 

XB          CB              b 

x4  
1  0  0  1  0  0 

x5  0  1  0  ‐3  1  ‐3M‐1 

x 4          ‐M               9
x5           0               2   Z = ‐9M 

x 4          ‐M               3
X2           1               2   z = 2‐3M 

Segunda tabla La solución factible básica que se obtiene a partir de la segundatabla es óptima (todos los c’i son menores o iguales que cero). x1 = 0, x2 = 2, x3 = 0,  x 4 = 3, x5 = 0   Observa  que  hay  una  variable  artificial  ( x 4 )  que  toma  un  valor  distinto  de  cero:  esto  indica  que EL PROBLEMA INICIAL NO POSEE SOLUCIÓN ÓPTIMA.

1   

Ejemplo 2

Maximizar z  x1  x 2  s.a. x  3x  9  1 2  2 x1  x 2  8    x1 , x 2  0  

 

Maximizar z x1  x 2  M x 4  Mx 6  s.a. x  3x  x  x  9  1 2 3 4  2x1  x 2  x 5  x 6  8     x1 , x 2 , x 3 , x 4 , x 5 , x 6  0 
          0             ‐M             0 
x2  x3 

                                       1                    1 
XB          CB              b  x1 

             ‐M 
x5 

x4  
1  0  0  1/3  ‐1/3 

x6
     0  1  0     0  1  0 

x 4         ‐M              9
 

1  2    3M+1  1/3  5/3 
 

3  1  4M+1  1  0  0    1  0  0 

‐1  0  ‐M  ‐1/3  1/3 

0  ‐1  ‐M  0  ‐1  ‐M    1/5  ‐3/5 

x6          ‐M              8
z = ‐17M  x2             1              3  

x6          ‐M             5 
z = 3‐5M 

5M  2 3

M 1 3
‐2/5  1/5  1/5   

 4M  1 3
2/5  ‐1/5 

x2             1              2   x1             1              3   z = 5 

0  1  0 ‐1/5  3/5 

M 
2 

1 5
 

2/5 

M 
‐1 

2 5
 

X5             0              10   x1             1              9   z = 9 

0  1  0 

5  3  ‐2 

‐2  ‐1  1 

1  0  0 

1  ‐M‐1 

0  ‐M 

Cuarta tabla: No se llega a una solución óptima y sin embargo no se puede continuar con el método porque no se puede aplicar el criterio de salida (entraría x3 pero todos loselementos de dicha columna son menores o iguales que cero, luego no podemos continuar). Esto indica que el problema planteado no tiene solución óptima.

2   

PROBLEMAS CON SOLUCIÓN MÚLTIPLE
Ejemplo 1

 

Maximizar z  2 x1  x 2  s.a. x  3x  9  1 2  2 x1  x 2  8      x1 , x 2  0  
                              2                     1  x1   1  2  2  0  1  0  0  1  0  x 2  3 1  1  5/2  1/2  0  1  0  0 

 Maximizar z  2 x1  x 2 s.a. x  3x  x  9  1 2 3  2 x1  x 2  x 4  8     x1 , x 2 , x3 , x 4  0 
             0                       0               x 3  1  0  0  1  0  0  2/5  ‐1/5  0  x 4  0  1  0  ‐1/2  1/2  ‐1  ‐1/5  3/5  ‐1 

                

XB          CB              b  x3             0                9 x4             0                8    z = 0  x3             0                 5  x1                    2                 4  z = 8  x2               1              2  x1              2               3  z = 8 

Segunda  tabla. La solución factible básica que obtenemos en ella es óptima: x1 = 4, x2 = 0, x3 = 5, x4 = 0.  En ella la función toma el valor 8:  z = 8.   Observa que el nº de ceros en la última fila es mayor que el nº de variables básicas, lo cual indica 

que  el  problema  tiene  multiplicidad  de  soluciones.  Para  buscarlas  seguiremos  aplicando  el  algoritmo  haciendo entrar en la base aquella variable que no es básica y que sin embargo su c’i  es 0, en este caso  x2. De esta forma pasamos a una nueva tabla (la 3ª) y se obtiene otra solución factible básica óptima:  ...