Simplex Dual I.O

SIMPLEX-DUAL

Se aplica a problemas que tienen factibilidad dual inicial, es decir, que son óptimos pero infactibles simples.

La factibilidad dual se reconoce expresando las restricciones en la forma canónica (£ ). La función objetivo puede ser de maximización o minimización. Condiciones:

Factibilidad

La variable de salida es la variable básica que tiene el valor más negativo, en caso de empate procedemos de forma arbitraria, y si todas las variables básicas son no negativas, el proceso finaliza y la solución factible óptima se encuentra.

Optimalidad

La variable de entrada es seleccionada de las variables no básicas, se hacen cocientes cuyos denominadores serán necesariamente negativos y se toman de la ecuación pivote. Los numeradores serán los números correspondientes en la función objetivo.

Se escoge el cociente más próximo a 0 para minimización. No toma en cuenta cocientes asociados con denominadores positivos o ceros. Y si todos los denominadores son 0 o positivos, el problema no tiene solución factible, los empate se deciden arbitrariamente.

Ejemplo:

Min Z = 2X1 + X2

S.A

3X1 + X2 ³ 3

4X1 + 3X2 ³ 6

X1 + 2X2 ³ 3

X1, X2 ³ 0

1er Paso: Ponemos las restricciones en forma canónica

Min Z = 2X1 + X2

S.A

-3X1 - X2 £ -3

-4X1 - 3X2 £ -6

- X1 - 2X2 £ -3

X1, X2 ³ 0

2º Paso: Agregamos holguras positivas

Min Z = 2X1 + X2

S.A

-3X1 - X2 + S1 = -3

-4X1 - 3X2 +S2 = -6

- X1 - 2X2 +S3 = -3

X1, X2 ³ 0

3er Paso: Igualamos a 0 la función objetivo

Z - 2X1 - X2 = 0

Como tiene factibilidad dual se puede aplicar el método dual-simplex.

Hacemos la primera iteración

Definimos

...