Metodo Dual Simplex

Método Simplex Dual.

El método simplex dual resulta ser una estrategia algorítmica eficiente cuando luego de llevar un modelo de programación lineal a su forma estándar, la aplicación del método simplex no es inmediata o más bien compleja, por ejemplo, puede requerir la utilización del método simplex de 2 fases.

Una aplicación típica del método simplex dual es en la resolución de problemas con una función objetiva de minimización, con restricciones del tipo mayor o igual y donde las variables de decisión son mayores o iguales a cero.

Criterios del simplex en coeficientes del modelo de PL resumido, a los problemas primal y dual.

Enseguida se presenta una comparación funcional del simplex y el dual simplex. 

 Comparación funcional del simplex y el dual simplex.

Criterios del método dual-simplex para el cambio de base.

En el algoritmo dual-simplex aplican los siguientes criterios para cambio de base:

Criterio de factibilidad.- Se aplica en el dual-simplex para determinar, entre las variables básicas, una VS que salga de la base, eligiendo para salir la que corresponda al valor más negativo en la columna de solución. Esto es válido tanto para el objetivo mínimo como para el máximo.

Criterio de optimalidad.- Se aplica en el dual-simplex para determinar, entre las variables no básicas, una VE que entre a la base con el siguiente procedimiento: 

Criterio de Optimalidad en el método dual-simplex.

Elemento Pivote.- Se ubica como pivote al coeficiente que corresponde al cruce del renglón y columna elegidos con los criterios del cambio de base.

Ejemplo:

  

Aplica dual simplex a un PL con 4 restricciones .

Pasos:

1) Consiga infactibilidad en restricciones tipo >=, (multiplique por -1):

2) Arregle la función Z; consiga la matriz I de base, sume holguras H_i, como sigue:

3) Tabule coeficientes y aplique el dual-simplex; elija variables VS, VE y pivote así:

Tablas del Dual-simplex aplicado al ejemplo DUX1.

Ejemplo:

Aplica dual-simplex a un PL con 2 restricciones >= y 1 restricción <= (DUX2).

Pasos:

1) Consiga infactibilidad, multiplique por (-1) en restricción tipo >= como sigue:

2) Arregle el objetivo Z; consiga la solución básica (sume holguras H_i), como sigue:

3) Construya la tabla y aplique el algoritmo dual simplex: