METODO DUAL SIMPLEX

METODO DUAL SIMPLEX.

Este método se aplica a problemas óptimos pero infactibles. En este caso, las

restricciones se expresan en forma canónica (restricciones ).

La función objetivo puede estar en la forma de maximización o de minimización.

Después de agregar las variables de holgura y de poner el problema en la tabla, si

algún elemento de la parte derecha es negativo y si la condición de optimidad está

satisfecha, el problema puede resolverse por el método dual simplex. Note que un

elemento negativo en el lado derecho significa que el problema comienza óptimo

pero infactible como se requiere en el método dual simplex. En la iteración donde

la solución básica llega a ser factible esta será la solución óptima del problema.

CONDICION DE FACTIBILIDAD.

La variable que sale es la variable básica que tiene el valor más negativo (los

empates se rompen arbitrariamente si todas las variables básicas son no

negativas, el proceso termina y esta última tabla es la solución óptima factible).

CONDICION DE OPTIMIDAD.

La variable que entra se elige entre las variables no básicas como sigue. Tome los

cocientes de los coeficientes de la función objetivo entre los coeficientes

correspondientes a la ecuación asociada a la variable que sale.

Ignore los cocientes asociados a denominadores positivos o cero.

La variable que entra es aquella con el cociente más pequeño si el problema es de

minimizar o el valor absoluto más pequeño si el problema es de maximización

(rompa los empates arbitrariamente). Si los denominadores son ceros o positivos

el problema no tiene ninguna solución factible.

EJERCICIOS RESUELTOS V

INVESTIGACIÓN DE OPERACIONES

Método Simplex Dual

Docente: Juan Carlos Vergara Schmalbach

F.O.

Min. Z = 4X1 + 12X2 + 18X3

S.A.

X1 + 3X3 ≥ 3

2X2 + 2X3 ≥ 5

X1, X2, X3 ≥ 0

S OLUCIÓN 1

PASO 1: Convertir el problema de minimización en uno de maximización. La función

objetivo se multiplica por -1

F.O.

Max. Z = - 4X1 - 12X2 - 18X3

Las restricciones se multiplican por -1

S.A.

- X1 - 3X3 ≤ -3

- 2X2 - 2X3 ≤ -5

X1, X2, X3 ≥ 0

PASO 2: Se convierten las inecuaciones en ecuaciones.

F.O.

Z + 4X1 + 12X2 + 18X3 = 0

S.A.

- X1 - 3X3 + S1 = -3

– 2X2 - 2X3 + S2 = -5

1HILLER, Frederick. "INTRODUCCIÓN A LA INVESTIGACIÓN DE OPERACIONES".

Editorial Mc. Graw Hill. México, 1997. Pág. 265

PASO 3: Se determinan las variables básicas y no básicas.

·Básicas: S1 y S2

·No Básicas: X1, X2 y X3

PASO 4: Elaborar la tabla inicial del simplex

Variable

Básica

Variables

X1 X2 X3 S1 S2

Solución

S1 -1 0 -3 1 0 -3

S2 0 -2 -2 0 1 -5

Z 4 12 18 0 0 0

PASO 5: Determinar la variable que sale (fila pivote)

Es el número más negativo de la solución de las restricciones = fila de S2

PASO 6: Determinar la variable que entra (columna pivote)

Razón = Coeficiente de Z / coeficiente fila pivote.

Razón Mayor = Columna X2 (-12 / 2)

Variable

Básica

Variables

X1 X2 X3 S1 S2

Solución

S1 -1 0 -3 1 0 -3

S2 0 -2 -2 0 1 -5

Z 4 12 18 0 0 0

Razón - -6 -9 - 0

PASO 7: Elaborar la nueva tabla del simplex

a) Nueva fila pivote = Fila pivote / elemento pivote

0 -2 -2 0 1 -5

-2 -2 -2 -2 -2 -2

0 1 1 0 -0,5 2,5

Fila Pivote

Elemento Pivote

Nueva Fila Pivote

b) Nuevas filas = fila anterior - coeficiente de la columna pivote x nueva fila pivote.

Nueva Fila (S1)

-1 0 -3 1 0 -3

0 0 0 0 0 0

0 1 1 0 -0,5 2,5

-1 0 -3 1 0 -3

Nueva Fila (Z)

4 12 18 0 0 0

12 12 12 12 12 12

0 1 1 0 -0,5 2,5

4 0 6 0 6 -30

Nueva

...