Upload
jesus-yano-hernandez
View
196
Download
13
Embed Size (px)
DESCRIPTION
metodo dual simplex
Citation preview
METODO DUAL SIMPLEX
Al hablar del método dual simplex se nos viene a la mente la palabra dual, este
método se basa en que todo problema de programación lineal tiene un problema
espejo, el cual se le llama DUAL. Este segundo problema genera un segundo algoritmo
de resolución llamado METODO DUAL SIMPLEX. Este método se aplica para resolver
problemas que empiezan con factibilidad dual (óptimos pero no son factibles).
La CONDICION DE FACTIBILIDAD consiste en que la variable que sale es la variable
básica que tiene el valor más negativo, si todas las variables básicas son no negativas
el proceso termina y se alcanza la solución factible - optima.
La CONDICION DE OPTIMIDAD se basa en que la variable que entra se escoge
calculando la razón entre los coeficientes del reglón “cero” y los coeficientes de la fila
asociada a la variable que sale (se ignoran los coeficientes positivos o ceros). La
variable que entra es aquella que posee la razón más pequeña si el problema es de
minimización. Si llegara a ser el caso en que si todos los denominadores son
cero o positivos el problema no tendría solución factible.
Si se tiene un problema principal de programación lineal, existe otro problema, el Dual,
expresado como:
EL METODO DUAL SIMPLEX en el método dual simplex se usa cuando se empieza
con una solución infactible y además optima, lo que se busca en este método es la
factibilidad llevándonos a una solución óptima y factible.
LA APLICACIÓN del método dual-simplex es especialmente útil para el tema de
ANÁLISIS DE SENSIBILIDAD, otra aplicación del método simplex dual es la
resolución de problemas con una FUNCIÓN OBJETIVO DE MINIMIZACIÓN, con
restricciones del tipo mayor o igual y donde las variables de decisión son mayores o
iguales a cero.
EJEMPLO #1
F.O.
Min. Z = 4X1 + 12X2 + 18X3
S.A.
X1 + 3X3 ≥ 3
2X2 + 2X3 ≥ 5
X1, X2, X3 ≥ 0
SOLUCIÓN
PASO 1: Convertir el problema de minimización en uno de maximización. La
función objetivo se multiplica por -1
F.O. Max. Z = - 4X1 - 12X2 - 18X3
Las restricciones se multiplican por -1
S.A. - X1 - 3X3 ≤ -3
- 2X2 - 2X3 ≤ -5
X1, X2, X3 ≥ 0
PASO 2: Se convierten las inecuaciones en ecuaciones.
F.O.
Z + 4X1 + 12X2 + 18X3 = 0
S.A.
- X1 - 3X3 + S1 = -3
– 2X2 - 2X3 + S2 = -5
PASO 3: Se determinan las variables básicas y no básicas.
·Básicas: S1 y S2 ·
No Básicas: X1, X2 y X3
PASO 4: Elaborar la tabla inicial del simplex
Variable
básica
Variables
x1 x2 x3 s1 s2SOLUCIÓ
N
s1 -1 0 -3 1 0 -3
s2 0 -2 -2 0 1 -5
Z 4 12 18 0 0 0
PASO 5: Determinar la variable que sale (fila pivote)
Es el número más negativo de la solución de las restricciones = fila de S2
PASO 6: Determinar la variable que entra (columna pivote)
Razón = Coeficiente de Z / coeficiente fila pivote.
Razón Mayor = Columna X2 (-12 / 2)
Variable
básica
Variables
x1 x2 x3 s1 s2SOLUCIÓ
N
s1 -1 0 -3 1 0 -3
s2 0 -2 -2 0 1 -5
Z 4 12 18 0 0 0
PASO 7: Elaborar la nueva tabla del simplex
a) Nueva fila pivote = Fila pivote / elemento pivote
b) Nuevas filas = fila anterior - coeficiente de la columna pivote x nueva fila pivote.
Nueva Tabla del Simplex:
Variable
básica
Variables
x1 x2 x3 s1 s2 SOLUCIÓN
s1 -1 0 -3 1 0 -3
s2 0 1 1 0 -1 2,5
Z 4 0 6 0 6 -30
razón -4 - -2 0 -
Se realizan nuevamente los pasos del 5 al 7 obteniendo como solución final:
VB
Variables
x1 x2 x3 s1 s2SOLUCIÓ
N
s1 0,33 0 1 -0,33 0 1
s2 -0,33 1 0 0,33 -0,5 1,5
Z 2 0 0 2 6 -36
NOTA: No hay más iteraciones cuando no existan soluciones con coeficientes
negativos.
R\ El valor mínimo se alcanza para un X2 = 3/2 y X3 = 1, para un Z = 36
---------------------------------------------------------------------------------------------------------------------
EJEMPLO #2
F.O.
Min. Z = 315X1 + 110X2 + 50X3
S.A.
15X1 + 2X2 + X3≥ 200
7,5X1 + 3X2 + 1X3≥ 150
5X1 + 2X2 + X3≥ 120
X1, X2, X3 ≥ 0
SOLUCIÓN
PASO 1
Se lleva el modelo a forma estándar. Se agregan 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 y así tener una solución inicial en las variables de exceso
S1, S2 y S3.esta solución inicial es INFACTIBLE.
X1 X2 X3 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
cuál de las actuales variables no básicas (A, B, C) entrará a la base se busca el mínimo
de {-Yj/aij}.
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 se deja a la variable A como básica y S1 como no básica.
X1 X2 X3 S1 S2 S3
1 15-Feb 15-Jan
-
0.0666666
7
0 0 40/3
0 -2 -0.5 -0.5 1 0 -50
0
-
1.3333333
3
-
0.66666667
-
0.3333333
3
0 1 -53.33333
0 68 29 21 0 0 -4.2
PASO 4
Continuar las realizando el mismo proceso hasta lograr una solución básica factible,
nos adelantamos y la solución fue factible fue de acuerdo a la tabla a continuación.
X1 X2 X3 S1 S2 S3
1 0 0 -0.1 0 10-Jan 8
0 1 0 4-Jan -1 4-Mar 10
0 0 1 0 2 -3 60
0 0 0 4 10 36 -6.62
LA SOLUCION QUE NOS RESULTO OPTIMA ES X1=8, X2=10, X3=60