Facultad de Ingeniería y Arquitectura
Escuela de Ingeniería Industrial
Investigación de Operaciones 1
Prof: Dagoberto Peña
Lenny Jiménez
100484620
Hillary Quiñones Díaz
100520337
7.1 Método dual símplex
2022-02
El método dual símplex
Es una alternativa de solución que utiliza el modelo dual para simplificar el uso de sólo un algoritmo de
solución en lugar de dos. En ambos casos el algoritmo converge a la solución óptima del modelo, si es que
ésta existe, de otra manera nos indica que el problema no tiene solución.
Uno de los inconvenientes de estos métodos es que pueden ser muy sensibles a errores de redondeo,
debido a la gran cantidad de operaciones que deben realizarse, por este motivo programas como TORA,
LINDO, etc. utilizan algoritmos óptimos en el sentido computacional, es decir, algoritmos que son poco
sensibles a errores de redondeo.
A continuación, se resumen los detalles del método símplex dual:
1. Paso inicial: Después de convertir cualquier restricción funcional de la forma a la forma
mediante la multiplicación de ambos lados por –1—, se introducen las variables de holgura necesarias
para construir un conjunto de ecuaciones que describan el problema. Encuentre una solución básica
tal que los coefi cientes de la ecuación (0) sean ceros para el caso de las variables básicas y no negativos
para las variables no básicas (de manera que la solución es óptima si es factible). El método continúa
en la prueba de factibilidad.
2. Prueba de factibilidad: Se verifica si todas las variables básicas son no negativas. Si es así, esta solución
es factible y, por tanto, óptima, y el algoritmo se detiene. De otra manera, es necesario realizar una
iteración.
3. Iteración:
Paso 1 Se determina la variable básica que sale mediante la selección de la variable básica negativa
que tenga el mayor valor absoluto.
Paso 2 Se determina la variable básica entrante a través de la selección de aquella cuyo coeficiente en
la ecuación (0) llegue primero a cero al agregar a la ecuación (0) un múltiplo creciente de la ecuación
que contiene a la variable básica que sale. Para llevar a cabo esta elección se examinan las variables
no básicas con coeficientes negativos de esa ecuación —la que contiene la variable básica que sale—
y se elige la que tiene el menor valor absoluto del cociente dado por el coeficiente de la ecuación (0)
entre el coeficiente de esa ecuación.
Paso 3 Se determina la nueva solución básica a partir del 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 gaussiana.
Cuando las variables no básicas se hacen cero, cada variable básica (y Z) es igual al nuevo valor del lado
derecho de la ecuación en la que aparece (con coeficiente 1 1). Se repite la prueba de factibilidad.
Para comprender bien el método símplex dual se debe entender que hace lo mismo que haría el
método símplex si se aplicara a las soluciones básicas complementarias del problema dual (en realidad,
éste fue el motivo para construirlo así). El paso 1 de una iteración, que determina la variable básica
que sale, es equivalente a determinar la variable básica entrante en el problema dual. La variable
negativa con el valor absoluto más grande corresponde al coeficiente negativo con el mayor valor
absoluto de la ecuación (0) del problema dual (vea la tabla 6.3). El paso 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 algoritmo son complementarios.
Ejemplo:
Consideremos el siguiente problema para ilustrar sobre la aplicación del Método Simplex Dual:
Para llevar el problema anterior a la forma estándar se requiere agregar 2 variables de exceso no
negativas para la restricción 1 y 2, que llamaremos respectivamente X4 y X5. De esta forma el problema
en su formato estándar queda definido por:
Luego construimos la tabla inicial del Método Simplex:
En este contexto si quisiéramos usar X4 y X5 como variables básicas (y en
consecuencia X1, X2 y X3 como variables no básicas) se requiere que X4 y X5 sean mayores o iguales a
cero, sin embargo, sus coeficientes en las respectivas filas son negativos y por tanto no se dispone de la
identidad (matriz con «1» como diagonal y el resto de coeficientes igual a cero).
En consecuencia, para formar la identidad podemos multiplicar por «-1» la fila 1 y 2, obteniendo lo
siguiente:
Ahora X4 y X5 son variables básicas y adoptan los valores de -1 y -3/2, respectivamente, lo que
claramente no satisface las condiciones de no negatividad para las variables de decisión, es
decir, no corresponde a una solución básica factible.
Sin embargo, en esta instancia podemos aplicar el Método Simplex Dual como alternativa de resolución.
Para ello seleccionaremos una variable que deje la base y adoptaremos como criterio de selección aquella
variable básica asociada al lado derecho «más negativo» (con esto se busca favorecer la rapidez de
convergencia).
En el ejemplo dicha variable es X5. Luego para determinar que variable entra a la base realizamos un
mínimo cuociente entre el negativo del costo reducido de las variables no básicas y las entradas
estrictamente menores a cero para las variables no básicas en la fila 2 (fila asociada al lado derecho más
negativo).
Es decir: Min {-160/-2; -120/-2; -280/-2} =60 ==> el cuociente mínimo se alcanza en la segunda columna
asociada a la variable no básica X2, por tanto, dicha variable entra a la base.
Finalmente se realiza una iteración realizando las operaciones filas que sean necesarias, de modo de
ingresar X2 a la base al mismo tiempo que X5 deja la base. Los resultados serían:
Notar que ahora las variables básicas son X4 y X2 donde sólo X4=-1/4 lo que no satisface la condición de
ser una solución básica factible. Por lo tanto, realizamos una nueva iteración, en este caso sacando de la
base a la variable X4 y calculamos el mínimo cuociente: Min {-40/-1; -160/-3; -60/-1/2} =40 ==> el
cuociente mínimo está en la primera columna por tanto la variable X1 entra a la base.
En consecuencia, se actualiza la tabla quedando lo siguiente:
