METODO SIMPLEX
DUAL
Método Simplex - Dual
QUE ES:
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.
Método Simplex - Dual
PARA QUE SE UTILIZA:
Como sabemos, el método simplex es un algoritmo iterativo que iniciando en
una solución básica factible pero no óptima, genera soluciones básicas
factibles cada vez mejores hasta encontrar la solución óptima (sí esta existe).
La base de su lógica es mantener la factibilidad, mientras busca la
optimalidad.
Pero surge la posibilidad de usar otro esquema igualmente iterativo, que
como contraparte del simplex, comienza en una solución básica óptima,
pero no factible y mantiene la inmejorabilidad mientras busca la factibilidad.
Con este procedimiento se llega igualmente a la solución óptima.
El nuevo algoritmo fue desarrollo en 1954 por C. E. Lemke y se conoce con el
nombre de Método Dual-Simplex.
Método Simplex - Dual
EN QUE CASOS SE UTILIZA:
Cada problema de programación lineal tiene un segundo problema
asociado con el. Uno se denomina primal y el otro dual. Los 2 poseen
propiedades muy relacionadas, de tal manera que la solución óptima
a un problema proporciona información completa sobre la solución
óptima para el otro.
Las relaciones entre el primal y el dual se utilizan para reducir el
esfuerzo de computo en ciertos problemas y para obtener información
adicional sobre las variaciones en la solución óptima debidas a ciertos
cambios en los coeficientes y en la formulación del problema. Esto se
conoce como análisis de sensibilidad o post-optimidad
EN QUE CASOS SE UTILIZA:
Otra de las ventajas que presenta es que dado a que el número de
restricciones y variables entre problema dual y primal es inverso, se
pueden resolver gráficamente problemas que presenten dos
restricciones sin importar el número de variables.
Obtendremos que los términos del lado
Si el modelo primal o dual tiene
derecho de las ecuaciones
solución óptima finita entonces su
multiplicadas por (-1) quedan con
respectivo dual o primal tendrán
signo negativo, lo cual hace que la
solución óptima finita.
solución inicial sea infactible.
Es importante destacar que este proceso es muy útil ya que en muchos
modelos evita la inclusión de variables artificiales en el momento de
transformar un modelo a formato estándar.
EN QUE CASOS SE UTILIZA:
Si el modelo primal o dual tiene Si el modelo primal o dual no tiene
solución óptima no acotada, entonces solución entonces su respectivo dual o
su respectivo dual o primal no tendrán primal no tendrán solución.
solución, será un modelo infactible.
Al hacer lo anterior se logra que
debajo de las variables básicas
aparezca una matriz identidad, que es
la que el simplex siempre toma como
base inicial.
Método Simplex - Dual
QUE IMPLICA RESOLVERLO CON OTRO METODO:
•Una de las ventajas de la existencia del programa dual es la posibilidad de reducir el
esfuerzo computacional al resolver ciertos modelos de programación lineal.
•Permite resolver problemas de programación lineal de forma más rápida y sencilla.
•Es otra vía para resolver un problema de programación lineal.
•Facilita profundizar en el contenido económico del problema original (primal).
•Puede ser utilizada para resolver el caso en que se debe considerar la introducción de una
nueva variable en el primal una vez que ha de sido obtenida la solución óptima, sin tener
que resolver completamente el problema.
•Otra de las ventajas que presenta es que dado a que el número de restricciones y variables
entre problema dual y primal es inverso, se pueden resolver gráficamente problemas que
presenten dos restricciones sin importar el número de variables.
Método Simplex - Dual
EJEMPLOS:
FUNCIÓN OPTIMA:
MIN Z=4X + 12X + 18X
1 2 3
SUJETA A :
X 1 + 18X >= 3 3
2X + 2X >= 5
2 3
X X X >= 0
1 2 3
Método Simplex - Dual
EJEMPLOS :
Paso 1: Convertir el problema de minimización en uno de
maximización . La función objetico se multiplica por -1
F.O. MIN Z= -4X - 12X - 18X 1 2 3
La restricciones se multiplican por -1
S.A. -X 1- 18X <= -3 3
-2X - 2X <= 5 2 3
X X X >= 0
1 2 3
Paso 2: Se convierten las inecuaciones en ecuaciones
F.O. Z + -4X - 12X - 18X = 0
1 2 3
S.A. -X1 - 18X3 + S1 >= -3
-2X2 - 2X3 + S2 >= 5
Método Simplex - Dual
EJEMPLOS :
Paso 3: Se determinan las variables básicas y no básicas.
Básicas: S yS
1 2
No Básicas: X1 X X
2 3
Paso 4: Se elabora la tabla inicial de simplex
Paso 5: Determinar la variable que sale (fila pivote)
El número mas negativo de la solución de las restricciones = fila de S2
Método Simplex - Dual
EJEMPLOS :
Paso 6: Determinar la variable que entra (columna pivoite).
Razón mayor = columna X2 (-12/2)
Paso 7: Elaborar la nueva tabla de simplex
a) Nueva fila pivote = fila pivote / elemento pivote
Método Simplex - Dual
EJEMPLOS :
b) Nuevas filas Fila anterior - coeficiente de la columna pivote *
nueva fila pivote
Método Simplex - Dual
Nueva tabla simplex EJEMPLOS :
Se realizan nuevamente los pasos del 5 al 7 obteniendo como
solución final:
Nota: No hay más iteraciones cuando no existan soluciones con
coeficientes negativos
El valor mínimo se alcanza para un X2 = 3/2 Y X3 = 1, para un Z=36
Conclusiones
⦿ El método Dual Simplex sirve y se aplica para resolver problemas que empiezan
con factibilidad dual, es decir, óptimos pero infactibles (No se puede realizar).
⦿ Comúnmente aquellos problemas de difícil solución son los de minimización.
⦿ El método simplex y el dual simplex se encuentran muy ligados, permitiendo que la
restricción de uno sean las variables del otro.
⦿ Las características básicas de una minimización para desarrollar el método dual
simplex es que tengan restricciones del mayor o igual que y donde las variables sean
mayores o iguales a cero
