Algoritme símplex dual i símplex dual estès

L'algoritme símplex dual i símplex dual estès són dos evolucions de l'algoritme simplex per solucionar problemes de programació lineal sense la utilització de variables artificials. Com molt bé sabem per la resolució de problemes a través de taules necessitem que les variables de folgança formin base canònica però això en moltes ocasions no succeix.

A continuació presentem les característiques del símplex, el símplex dual i el símplex dual estès.

- Símplex:

• Els valors de Vb han de ser positius
• Han de formar base canònica
• Els valors de zi - ci han de ser inadequats a l'òptim

- Símplex dual:

• Han de formar base canònica
• Algun ( o tots ) els valors de Vb han de ser negatius
• El valor de Xji ha ser negatiu
• Els valors de zi - ci han de ser adequats a l'òptim

- Símplex dual estès:

• Han de formar base canònica
• Algun ( o tots ) els valors de Vb han negatius
• Els valors de zi - ci han de ser inadequats a l'òptim

En la resta de casos ens trobarem directament en l'òptim.

Per resoldre l'algoritme símplex dual estès utilitzarem en primera iteració i després d'haver fet entrar la restricció: X1 + X2 + ... + Xn < = > M, aplicarem l'algoritme símplex. Posteriorment i amb la variable artificial fora de la base aplicarem l'algoritme símplex dual.