Ingeniería Industrial

Método dual simplex

Asignatura: Investigación de Operaciones I

Docente: Flora Alicia González Jiménez
Integrantes:
Medina Rentería Anahí
Robles Gómez José
Rodríguez Lerma Laura
Zapata Medina Hispania

Cd. Victoria Tamaulipas a 11 de marzo, 2020.

Introducción

Es claro que para cualquier problema de programación lineal los zj-cj son completamente
independientes del vector de limitaciones bi. Consecuentemente, el conjunto de
soluciones básicas a Ax = b con zj-cj ≥ 0 para toda j, depende únicamente de las aj y de
las cj , pero no de b (para un problema de Maximización). En general, no toda solución
básica factible con todas las zj-cj ≥ 0 será optima. La observación realizada presenta una
interesante posibilidad. Si se pudiera iniciar con alguna solución básica, pero no factible a
un problema dado de programación lineal que tenga todos los zj-cj ≥0, entonces
considerando que ninguna base debe ser repetida, una solución optima a el problema de
programación lineal será obtenida en un numero finito de pasos. Esto es lo que
precisamente el algoritmo Dual-Simplex hace. El hecho de que se mantienen todos los zj-
cj ≥0 en cada paso y que no importa la factibilidad de las soluciones básicas (del vector de
limitaciones bi ) sugiere que la Teoría de Dualidad debe ayudar en el desarrollo de tal
algoritmo. Debido a que no siempre es fácil iniciar utilizando este algoritmo ya que no
tiene la aplicabilidad general que tiene el usual método Simplex. Sin embargo, este puede
ser usado en ciertos casos para eliminar la necesidad de utilizar la fase I y la consecuente
introducción de las variables artificiales. Este algoritmo debido a Lemke, ha sido llamado
Dual-Simplex debido a que los criterios seguidos para introducir y sacar el vector son
aquellos seguidos para el problema Dual en lugar de los del problema primo
 Método Dual Simplex

Se puede considerar que el método simplex dual es la imagen en un espejo del

método simplex. El método símplex trata directamente con soluciones básicas
subóptimas y se mueve hacia la solución óptima al tratar de satisfacer la prueba
de optimalidad. Por el contrario, el método símplex dual maneja en forma directa
soluciones básicas superóptimas y se mueve hacia la solución óptima cuando
trata de alcanzar la factibilidad. Aún más, el método dual simplex trata un
problema como si se aplicara el método símplex a su problema dual de manera
simultánea. Si se hacen complementarias sus soluciones básicas iniciales, los dos
métodos se mueven en una secuencia completa y obtienen soluciones básicas
complementarias en cada iteración.

El método simplex dual es muy útil en algunas situaciones especiales. Lo normal

es que sea más fácil encontrar una solución inicial básica factible que una solución
inicial básica superóptima, aunque en ocasiones es necesario introducir muchas
variables artificiales para construir, en una forma simulada, una solución inicial
básica factible. En esos casos puede ser más sencillo comenzar con una solución
básica superóptima y aplicar el método simplex dual. Todavía más, puede ser que
se re quieran menos iteraciones cuando no se tienen que hacer cero tantas
variables artificiales.

Otra aplicación de primordial importancia del método simplex dual es su

asociación con el análisis de sensibilidad. Supóngase que se ha obtenido una
solución óptima por el método simplex pero que es necesario (o de interés para el
análisis de sensibilidad) hacer cambios menores al modelo. Si la solución básica
óptima que se tenía ya no es factible (pero todavía satisface la prueba de
optimalidad), se puede aplicar de inmediato el método simplex dual a partir de esta
solución básica superóptima. Con la aplicación del método simplex dual por lo
general se llega a la nueva solución óptima mucho más rápidamente que si se
resuelve el nuevo problema desde el principio con el método simplex.
Las reglas para el método simplex dual son muy parecidas a las del método
simplex. De hecho, una vez que se inician, la única diferencia entre ellos es el
criterio para elegir las variables básicas que entran y salen y la regla para detener
el algoritmo. Para dar inicio al método símplex dual todos los coeficientes en la
ecuación (0) deben ser no negativos (de manera que la solución básica sea
superóptima). Las soluciones básicas serán no factibles (excepto la última) sólo
porque algunas variables son negativas. El método continúa haciendo que el valor
de la función objetivo disminuya, y conserva siempre coeficientes no negativos en
la ecuación (0), hasta que todas las variables sean no negativas. En este
momento la solución básica es factible (satisface todas las ecuaciones) y, por
tanto, es óptima según el criterio del método simplex de coeficientes no negativos
en la ecuación (0). A continuación se resumirán los detalles del método simplex
dual.

Resumen del método simplex dual

Paso inicial: Se introducen las variables de holgura necesarias para construir un

conjunto de ecuaciones que describan el problema. Se encuentra una solución
básica tal que los coeficientes de la ecuación (0) sean ceros para las variables
básicas y no negativos para las variables no básicas. Se lleva a cabo la prueba de
optimalidad.

Paso iterativo:

 Parte 1. Se determina la variable básica que sale, seleccionando aquella

que tenga el valor negativo más grande.

 Parte 2. Se determina la variable básica entrante: se elige aquella cuyo

coeficiente en la ecuación (0) llegue primero a cero al agregar a la ecuación
 cero un múltiplo creciente de la ecuación que contiene a la variable básica
que sale. Esta elección se hace examinado las variables no básicas con
coeficientes negativos en esa ecuación (la que contiene la variable básica
que sale) y escogiendo la que tiene el cociente más pequeño dado por el
coeficiente de la ecuación (0) entre el valor absoluto del coeficiente en esta
ecuación.

 Parte 3. Se determina la nueva solución básica: se comienza con el

conjunto actual de ecuaciones y se despejan las variables básicas en
términos de las no básicas mediante el método de eliminación de Gauss-
Jordan. Cuando las variables no básicas se hacen cero, cada variable
básica (y Z) es igual al nuevo va dolor del lado derecho de la ecuación en la
que aparece (con coeficiente +¿ 1).

Prueba de factibilidad: se determina si la solución es factible (y por tanto óptima) al

verificar que todas las variables básicas sean no negativas. Si es así, esta
solución es factible y el algoritmo se detiene. De otra manera, se siguen las
instrucciones del paso iterativo.

Para comprender bien el método simplex dual se debe entender que hace lo
mismo que haría el método simplex si se aplica a las soluciones básicas
complementarias en el problema dual. (De hecho, ésta fue la motivación para
construirlo así.) La parte 1, que determina la variable básica que sale, es
equivalente a determinar la va variable básica entrante en el problema dual. La
variable con el valor negativo más grande corresponde al coeficiente negativo
mayor en la ecuación (0) del problema dual (véase la tabla 6.3). La parte 2, que
determina la variable básica entrante, es equivalente a determinar la variable
básica que sale en el problema dual. El coeficiente de la ecuación (0) que llega
primero a cero corresponde a la primera variable que se hace cero en el problema
dual. También los dos criterios para detener el algo ritmo son complementarios.
Se ilustrará el método simplex dual aplicándolo al problema dual de la Wyndor.
Por lo general, este método se aplica directamente al problema en cuestión (un
problema primal). Se continuará denotando a las variables de decisión en el
problema que se va a resolver, como y i en lugar de x j . En forma de maximización,
el problema es

Maximizar Z=−4 y 1 – 12 y 2 – 18 y 3 ,

Iteració Variable Ec. Coeficiente de Lado

n básica Num. derecho
Z y1 y2 y3 y4 y5
Z 1 1 4 12 18 0 0 0

0 y4 0 0 -1 0 -3 1 0 -3

y5 2 0 0 -2 -2 0 1 -5
Z 0 1 4 0 6 0 6 -30

1 y4 1 0 -1 0 -3 1 0 -3

y2 2 0 0 1 1 0 −1 5
2 2
Z 0 1 2 0 0 0 6 -36

2 y3 1 0 1 0 1 −1 0 1
3 3
y2 2 0 −1 1 0 1 −1 3
3 3 2 2

Sujeta a

y 1 +3 y 3 ≥ 3

2 y 2+ 2 y 3 ≥5 ,

Y
 y 1 ≥ 0 , y 2 ≥ 0 , y 3 ≥0.

 Después de convertir las restricciones funcionales a la forma ≤ y de

introducir variables de holgura, el conjunto inicial de ecuaciones es el que
se muestra en la iteración 0 la tabla. Nótese que todos los coeficientes de
la ecuación (0) son no negativos, con lo que la solución es óptima si es
factible. La solución básica inicial es y 1=0 , y 2=0 , y 3=0 , y 4=−3 , y 5=−5 , con
Z=0 , que no es factible porque tiene valores negativos. La variable básica

12 18
que sale es y 5 (5 > 3), y la variable básica entrante es y 2 ( < ) lo que
2 2
conduce al segundo conjunto de ecuaciones que muestra en la iteración 1
de la tabla. La solución básica correspondiente es

5
y 1=0 , y 2= , y 3=0 , y 4=−3 , y 5=0 , con Z=−30 que no es factible. La
2

6 4
siguiente variable básica que sale es y 4 y la que entra es y 3 ( < ), lo que
3 4
da lugar al conjunto final de ecuaciones que se presenta en la tabla. La

3
solución básica correspondiente es y 1=0 , y 2= , y 3 =1, y 4 =0 , y 5=0 , con
2
Z=−36, que es tanto factible y por lo tanto óptima.
Conclusión

Hemos llegado a la conclusión de que el método dual-simplex es utilizado para

resolver modelos de programación lineal en su forma estándar, este ha
demostrado ser una eficiente herramienta en apoyo a la toma de decisiones
basada en resultados cuantitativos.

Sin embargo, algunos casos o problemas no siempre se presentan de tal manera

que puedan expresarse en la forma estándar y resolverse por el método dual-
simplex por lo que es necesario plantear una metodología para resolver estos
casos.