Download - Método Dual Simplex
Método Dual Simplex
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 optimalidad 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 infactibles
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.
Condiciones para aplicar el método
1. Se debe garantizar la optimalidad del problema.
2. Si se maximiza todos los Cj deben ser negativos y se minimiza todos los Cj deben
ser positivos.
3. Se empieza por una tabla donde todos los Zj−Cj ≥ 0 para todo j si se esta
maximizando o todos los Zj−Cj ≤ 0 para todo j si se está minimizando.
4. Se debe procurar que todas las restricciones sean del tipo ≤ (de ser necesario
multiplicar por -1 o sustituir una igualdad en dos restricciones).
5. El uso de las variables de exceso y holgura.
6. Las variables de decisión deben ser positivas.
NOTA: No se trabajan con variables artificiales.
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 forza las soluciones básicas hacia el espacio factible.
Integrantes:Ylianni Maita CI: 22724407Roselin Verdu CI:Rosangel Marin CI:María Arismendi CI:Elizbeth Alfonzo CI:
1. Condición de Factibilidad: Se aplica el Criterio de Factibilidad identificando el X B
más NEGATIVO. Esa es la variable que sale de la base X B<0. Esto es válido para
maximizar o minimizar. Si todas las variables básicas son positiva, es decir, X B>0,
se tiene la solución final, optima y factible.
2. Condición de Optimalidad: Se selecciona el vector entrante según el siguiente
criterio: Se divide el resultado obtenido de cada Zj−Cj para cada Xn, entre los
coeficientes correspondientes a la ecuación asociada con la variable que sale,
ignorando denominadores positivos o ceros. La variable entrante será aquella cuyo
cociente sea el menor, si el problema es de minimizar, ó el de menor valor
absoluto si es de maximizar. Si todos los denominadores son ceros o positivos el
problema no tiene solución factible.
MINIMIZAR= Min {|Zj−CjYij |} ; Yij<0; Si Yij ≥0. El problema no tiene solución factible.
MAXIMIZAR= Max {|Zj−CjYij |} ; Yij<0; Si Yij ≥0. El problema no tiene solución factible.
Yij : Vector Saliente
Tipos de solución: Los mismos que en el método simplex, excepto que Es Optima
única cuando nadie SALE de la base, y es Infinita o Ilimitada cuando nada ENTRA a
la base.
EJERCICIO #1.
Min Z = 3 X1+2 X2sa3 X1+X2≥34 X1+3 X2≥6X1+X2≤3
X1+X2≥0
Forma Canónica o Modelo Canónico
Min Z = 3 X1+2 X2+ 0 X3+0 X4 + 0 X5sa−3 X1−X2+X3=−3−4 X1−3 X 2+X4=−6X1+X2+X 5=3X1 , X2 , X3 , X4 , X5≥0
C j 3 2 0 0 0
CB V B X B X1 X2 X3 X 4 X5
0 X3 -3 -3 -1 1 0 0
0 X 4 -6 -4 -3 0 1 0
0 X5 3 1 1 0 0 1
Z j 0 0 0 0 0 0
Z j−C j -3 -2 0 0 0
0 X3 -1 −53
0 1 −13
0
2 X2 2 43
1 0 −13
0
0 X5 1 −13
0 0 13
1
Z j 4 83
2 0 −23
0
Z j−C j −13
0 0 −23
0
3 X1 35
1 0 −35
15
0
2 X2 65
0 1 45
−35
0
0 X5 65
0 0 −15
25
1
Z j 215
3 2 −15
−35
0
Z j−C j 0 0 −15
−35
0
Min {|−3−4|;|−2−3|} ; Yij<0 Entra X2
Min {|−13−53
|;|−23−13
|} ; Yij<0 Entra X2EJERCICIO #2.Max Z = −X1−5 X2
S.aX1+2 X2=−42 X1+7 X2≥83 X1−5 X2≤7X1 , X2≥0
Forma Canónica o Modelo Canónico
Max Z = −X1−5 X2+ 0 X3+0 X4 + 0 X5 +0 X6Sa−X1−2 X2+X3=4X1+2 X2+X 4=−4−2 X1−7 X2+X5=−83 X1+5 X2+X 6=−7X1 , X2 , X3 , X4 , X5 , X6≥0
C j -1 -5 0 0 0 0
CB V B X B X1 X2 X3 X 4 X5 X6
0 X3 4 -1 -2 1 0 0 0
0 X 4 -4 1 2 0 1 0 0
0 X5 -8 -2 -7 0 0 1 0
0 X6 -7 -3 5 0 0 0 1
Z j 0 0 0 0 0 0 0
Z j−C j 1 5 0 0 0 0
0 X3 8 0 32
1 0 −12
0
0 X 4 -8 0 −32
0 1 12
0
-1 X1 4 1 72
0 0 −12
0
0 X6 5 0 312
0 0 −32
1
Z j -4 -1 −72
0 0 12
0
Z j−C j 0 32
0 0 12
0
Min {| 1−2|;| 5−7|} ; Yij<0 Entra X1
Min {| 32−32
|;| 1212|} ; Yij<0 Entra X2