INSTITUTO TECNOLÓGICO SUPERIOR

DE LA REGIÓN DE LOS LLANOS

Ingeniería Industrial

Investigación de las Operaciones I

Investigación: Método Dual Simplex

Unidad III
Alumnos:
Luis Enrique González Gonzalez
María Magdalena Gurrola Ibarra
Luis Fernando Flores de Casas

Docente:
Brenda Magali Castillo Escañuela

5“A”
Guadalupe Victoria, Dgo.
07/Noviembre/2019
Concepto Dual Simplex

El método dual-simplex se aplica para resolver problemas que empiezan

con factibilidad dual, es decir, óptimos, pero infectables.

El método simplex dual se basa en la teoría de la dualidad, se dice que ambas

soluciones son factibles primales si la solución básica primal es factible, y se llaman
factibles duales si la solución básica dual complementaria es factible para el
problema dual. Cada solución básica complementaria es óptima para su problema
sólo si es factible en el primal y en el dual. Se puede pensar en el método simplex
dual como un reflejo del método simplex.

Un problema se puede resolver por el método dual-simplex, cuando, después de

igualar acero la función objetivo y convertir las restricciones en ecuaciones,
agregando las variables de holgura necesarias, al menos uno, cualquiera de los
elementos del vector b (vector de disponibilidades) es negativo y la condición de
optimalidad se satisface.

Un comparativo entre el método simplex y el método dual-simplex:

El método dual-simplex requiere de la aplicación de dos criterios para su solución:

El criterio de optimalidad que asegura que la solución permanecerá óptima todo el
tiempo y el criterio de factibilidad que forzar las soluciones básicas hacia el espacio
factible.

Éste trata directamente con soluciones básicas del problema primal que son
factibles primales, pero no factibles duales. Después se mueve hacia la solución
óptima con el objetivo de lograr la factibilidad dual, la prueba de optimalidad del
método simplex. Por el contrario, el método simplex dual maneja soluciones básicas
del problema dual que son factibles duales, pero no factibles primales. Después se
mueve hacia la solución óptima con la meta de alcanzar la factibilidad en el primal.
Aún más, el método simplex dual trata un problema como si se aplicara el método
simplex a su problema dual de manera simultánea. Si sus soluciones básicas
iniciales se hacen complementarias, los dos métodos se mueven en una secuencia
completa y obtienen soluciones básicas complementarias en cada iteración.

Uno de los descubrimientos más importantes durante el desarrollo inicial de la

programación lineal fue el concepto de dualidad y sus importantes ramificaciones.
Este descubrimiento reveló que, asociado a todo problema de programación lineal,
existe otro problema lineal llamado dual. Desde distintos puntos de vista las
relaciones entre el problema dual y el original (llamado primal) son muy útiles. Por
ejemplo, se verá que, en realidad, la solución óptima del problema dual es la que
proporciona los precios sombra.

Dada nuestra forma estándar para el problema primal, que se presenta a la

izquierda (quizá después de hacer conversiones cuando provienen de otras
formas), su problema dual tiene la forma que se muestra a la derecha.
El problema dual se define sistemáticamente a partir del modelo de PL primal (u
original). Los dos problemas están estrechamente relacionados en el sentido de que
la solución óptima de uno proporciona automáticamente la solución óptima al otro.
En la mayoría de los tratamientos de PL, el dual se define para varias formas del
primal según el sentido de la optimización (maximización o minimización), los tipos
de restricciones (#,$ o =), y el signo de las variables (no negativas o irrestrictas).

Los cambios realizados en los datos de un modelo de PL pueden afectar la

optimalidad y/o factibilidad de la solución óptima actual. Las soluciones primal y dual
están estrechamente relacionadas en el sentido de que la solución óptima de uno u
otro problema da la solución óptima al otro. Así pues, en un modelo de PL en el que
la cantidad de variables es considerablemente menor que la de restricciones,
pueden ahorrarse cálculos resolviendo el dual porque la cantidad de cálculos
simplex depende en gran medida (aunque no totalmente) de la cantidad de
restricciones.
Teorema de la dualidad: Las siguientes son las únicas relaciones posibles entre los
problemas primal y dual.
1. Si un problema tiene soluciones factibles y una función objetivo acotada (y, por
ende, una solución óptima), entonces ocurre lo mismo con el otro problema, de
manera que se aplican tanto la propiedad de dualidad débil como la fuerte.
2. Si uno de los problemas tiene soluciones factibles y una función objetivo no
acotada (es decir, no tiene solución óptima), entonces el otro problema no tiene
soluciones factibles.
3. Si un problema no tiene soluciones factibles, entonces el otro problema no tiene
soluciones factibles o bien la función objetivo es no acotada. La principal razón de
que la programación lineal se utilice en forma tan amplia es la disponibilidad de un
algoritmo excepcionalmente eficiente ,el método simplex, que en forma rutinaria
resuelve problemas grandes que con frecuencia surgen en la práctica. Sin embargo,
el método simplex es sólo una parte del arsenal de algoritmos que se usan con
regularidad en la aplicación de la programación lineal.
Aplicaciones
Como acaba de establecerse, una aplicación importante de la teoría de la dualidad
es que puede resolverse el problema dual directamente con el método simplex, a
fin de identificar una solución óptima para el problema primal. 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 que sea factible que una que sea factible en el
dual. Sin embargo, en ocasiones es necesario introducir muchas variables
artificiales para construir una solución inicial BF de manera artificial. En esos casos
sería más sencillo comenzar con una solución básica factible dual y aplicar el
método simplex dual. Incluso, puede ser que ésta requiera menos iteraciones
cuando no se tiene que convertir en cero el valor de tantas variables artificiales.
Cuando se aborda un problema cuyas soluciones iniciales básicas (sin variables
artificiales) no son factibles primales ni factibles duales, también es posible combinar
las ideas de los métodos simplex y dual simplex en un algoritmo primal-dual que
trate de alcanzar la factibilidad tanto primal como dual.

Con el método dual simplex podemos resolver problemas relacionados con el

control de las organizaciones o sistemas (hombre – maquina). A fin de que se
produzcan soluciones que mejor sirvan a los objetivos de la organización. El método
simplex dual también puede ser útil para resolver problemas grandes de
programación lineal desde el principio debido a la eficiencia del algoritmo. La
experiencia computacional reciente con las últimas versiones de CPLEX indica que
el método simplex dual suele ser más eficiente que el método simplex para resolver
problemas particularmente grandes que se encuentran en la práctica. Las reglas del
método simplex dual son muy parecidas a las del método simplex. En realidad, una
vez que los métodos 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.
Ejemplo Simplex Dual
Considere el siguiente modelo de Programación Lineal:

Paso 1: Se lleva el modelo a su forma estándar. En nuestro ejemplo esto se logra

agregando variables de exceso en cada una de las restricciones (3 primeras: S1,
S2, S3, respectivamente). Luego, se multiplica cada fila de las restricciones por -1
de modo de disponer una solución básica inicial (infactible) en las variables de
exceso S1, S2 y S3. De esta forma se obtiene la siguiente tabla inicial.

A B C S1 S2 S3
-15 -2 -1 1 0 0 -200
-7,5 -3 -1 0 1 0 -150
-5 -2 -1 0 0 1 -120
315 110 50 0 0 0 0

Paso 2: Se selecciona el lado derecho "más negativo" lo cual indicará cuál de las
actuales variables básicas deberá abandonar la base. En el ejemplo el lado derecho
más negativo se encuentra en la primera fila, por tanto S1 deja la base. Para
determinar cual de las actuales variables no básicas (A, B, C) entrará a la base se
busca el mínimo de {-Yj / aij} donde aij es el coeficiente de la respectiva variable no
básica en la fija i (del lado derecho más negativo, marcado en verde) y donde Yj es
el costo reducido de la respectiva variable no básica. De esta forma se obtiene: Min
{-315/-15, -110/-2, -50/-1} = 21, donde el pivote (marcado en rojo) se encuentra al
hacer el primer cociente, por tanto A entra a la base.
Paso 3: Se actualiza la tabla anterior siguiendo un procedimiento similar al utilizado
en el Método Simplex. En el ejemplo se debe dejar a la variable A como básica y
S1 como no básica. La tabla que resulta es la siguiente:

A B C S1 S2 S3
1 2/15 1/15 -1/15 0 0 40/3
0 -2 -1/2 -1/2 1 0 -50
0 -4/3 -2/3 -1/3 0 1 -160/3
0 68 29 21 0 0 -4.200

Paso 4: Continuar las iteraciones y siguiendo el mismo procedimiento hasta

disponer de una solución básica factible. Luego de unas iteraciones se obtiene la
siguiente tabla final:

A B C S1 S2 S3
1 0 0 -1/10 0 1/10 8
0 1 0 1/4 -1 3/4 10
0 0 1 0 2 -3 60
0 0 0 4 10 36 -6.620

La solución óptima es A=8, B=10, C=60 (marcado en verde) con valor

óptimo V(P)=6.620 (marcado en azul - se obtiene con signo cambiado). También es
interesante notar que los costos reducidos de las variables artificiales S1, S2 y S3
(marcado en amarillo), corresponde a la solución óptima del modelo presentado en
el tutorial de resolver, esto dado que dicho modelo resulta ser el problema dual de
nuestro ejemplo.
Conclusiones

Para comprender el cómo funciona el método dual simplex, se debe de comprender

lo que es la teoría de la dualidad, una vez comprendiendo eso será de mayor
facilidad el comprender certeramente el funcionamiento del método. La diferencia
principal del método simplex y el método dual, es que el simplex se inicia con una
solución factible y la mantiene mientras busca conseguir la optimización. El método
dual inicia con una solución óptima pero no factible y busca la factibilidad
manteniendo la optimización.
Una vez que se comprende lo anterior, de acuerdo con lo leído en los diferentes
libros consultados, se sabe que mayormente se aplican en la resolución de
problemas con una función de minimizar, y con restricciones de tipo mayor o igual,
donde las variables de decisión deben de ser mayores o iguales acero.

Es un tema que se puede considerar que es de suma complicación si no se

comprende el método simplex normal, más sin embargo no tiene tanta complicación
como se ve. Para comprender bien el método simplex dual se debe entender que
hace lo mismo que haría el método simplex si se aplicara a las soluciones básicas
complementarias del problema dual (en realidad, éste fue el motivo para construirlo
así).

Bibliografía
Lieberman, F. S. (1997). Introduccion a la Investigacion de Operaciones. Mc Graw Hill.

Taha, H. A. (2012). Investigacion de Operaciones. Mexico: PEARSON.