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 la variable de salida, para ello tomamos el coeficiente más negativo de la columna de solución, esto es válido tanto para casos de Max como de Min.

Puesto que tiene factibilidad dual, se puede aplicar el método dual-simplex.

Hacemos una segunda iteración

Síntesis

Cuando se tiene un caso de Max en el método Dual-Simplex, todo el procedimiento es exactamente igual que si fuera de Min, excepto que al definir la variable de entrada se hacen cocientes cuyos denominadores serán necesariamente negativos tomados de la ecuación pivote y los numeradores serán los números correspondientes en la función objetivo.

Se toman los valores absolutos de los cocientes (prescindiendo de los signos) y se elige, para determinar la variable de entrada, el cociente más próximo a cero.

...