TNM IO1 Metodo Dual-Simplex

Investigación de Operaciones

Método Dual - Simplex

EMPEZAR

Método Dual -Simplex

Se aplica a problemas optimos, pero no factibles.

Tal caso se reconoce expresando primero las restricciones (≤) como en la forma canónica. La función objetivo puede estar en la forma de maximización o minimización.

+ info

Método Dual - Simplex

Note que un elemento negativo en el lado derecho significa que la variable de holgura correspondiente es negativa.

• Esto significa que el problema comienza óptimo, pero infactible como se requiere en el procedimiento dual – simplex.
• En la iteración donde la solución básica llega a ser factible, esta será la solución factible básica óptima.
• Como en el método simplex regular, el método de solución está basado en las condiciones de factibilidad y optimidad.
• La condición de optimidad garantiza que la solución permanezca siempre óptima, mientras que la condición de factibilidad obliga a las soluciones básicas hacia el espacio factible.

Método Dual SimplexProcedimiento

Paso 3

Paso 2

Paso 1

El Método Dual - Simplex se ilustra con el planteamiento del modelo matemático

• Min Xo = 250 X1 + 325 X2 + 280 X3 + 230 X4 + 335 X5 + 300 X6

• s.a

• X1 + X4 ≥ 35

• X2 + X5 ≥ 85

• X3 + X6 ≥ 22

• X1 + X2 + X3 ≤ 65

• X4 + X5 + X6 ≤ 77

• X1, X2, X3, X4, X5, y X6 no negativas.

Haciendo uso de la propiedad de las desigualdades a que se hizo referencia al inicio del tema método simplex, ponemos las restricciones en la forma (≤).

• Min Xo = 250 X1 + 325 X2 + 280 X3 + 230 X4 + 335 X5 + 300 X6

• s.a

• -X1 - X4 ≤ -35

• -X2 - X5 ≤ -85

• -X3 - X6 ≤ -22

• X1 + X2 + X3 ≤ 65

• X4 + X5 + X6 ≤ 77

• X1, X2, X3, X4, X5, y X6 no negativas.

y pasando el modelo a su forma estándar.

• Min Xo - 250 X1 - 325 X2 - 280 X3 - 230 X4 - 335 X5 - 300 X6 =0

• s.a

• -X1 - X4 ≤ -35

• -X2 - X5 ≤ -85

• -X3 - X6 ≤ -22

• X1 + X2 + X3 ≤ 65

• X4 + X5 + X6 ≤ 77

• X1, X2, X3, X4, X5, y X6 no negativas.

La tabla correspondiente de inicio está dada como:

Continua procedimiento

• La variable de salida será S2 ya que tiene el valor más negativo en la columna de solución, para elegir la variable de entrada dividimos renglón objetivo en lo que respecta a las variables no básicas (resaltado en amarillo) entre el renglón de la variable que se eligió como de salida, a saber.

• La variable de entrada, como el problema es de minimización es el menor cociente positivo, en este caso 325 que corresponde a la variable X2. Y se continua con el procedimiento habitual del simplex.

Continua procedimiento

• El problema aún no es factible, la nueva variable de salida será S1 (más negativa).

• La nueva variable de entrada será X4.

Continua procedimiento

• Siendo esta la tabla óptima de solución con:
• Xo = 42,255
• X1 = 0, X2 = 43, X3 =22, X4 =35, X5 = 42 y X6 = 0

Referencias Bibliográficas

Taha. H. A. (1988). Investigación de operaciones. “Una introducción” Representaciones y servicios de ingeniería, s.a. México.

Después de agregar las variables de holgura y poner el problema en la forma de tabla, si cualquier elemento de la parte derecha (resultado) es negativo, y si la condición de optimidad está satisfecha (para problemas de maximización ya no hay valores negativos en el renglón objetivo y columna de variables no básicas; y para problemas de minimización ya no hay valores positivos) el problema puede resolverse con el método dual – simplex.