METODO DUAL SIMPLEX
Al hablar del mtodo dual simplex se nos viene a la mente la palabra dual, este
mtodo se basa en que todo problema de programacin lineal tiene
un problema
espejo, el cual se le llama DUAL. Este segundo problema genera un segundo algoritmo
de resolucin llamado METODO DUAL SIMPLEX. Este mtodo 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
bsica que tiene el valor ms negativo, si todas las variables bsicas son no negativas
el proceso termina y se alcanza la solucin factible - optima.
La CONDICION DE OPTIMIDAD se basa en que la variable que entra se escoge
calculando la razn entre los coeficientes del regln 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 razn ms pequea si el problema es de
minimizacin. Si llegara a ser el caso en que si todos los denominadores son
cero o positivos el problema no tendra solucin factible.
Si se tiene un problema principal de programacin lineal, existe otro problema, el Dual,
expresado como:
EL METODO DUAL SIMPLEX en el mtodo dual simplex se usa cuando se empieza
con una solucin infactible y adems optima, lo que se busca en este mtodo es la
factibilidad llevndonos a una solucin ptima y factible.
LA APLICACIN del mtodo dual-simplex es especialmente til para el tema de
ANLISIS DE SENSIBILIDAD, otra aplicacin del mtodo simplex dual es
la
resolucin de problemas con una FUNCIN OBJETIVO DE MINIMIZACIN, con
restricciones del tipo mayor o igual y donde las variables de decisin 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
SOLUCIN
PASO 1: Convertir el problema de minimizacin en uno de maximizacin. La
funcin 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 bsicas y no bsicas.
Bsicas: S1 y S2
No Bsicas: X1, X2 y X3
PASO 4: Elaborar la tabla inicial del simplex
Variable
bsica
Variables
x1
x2
x3
s1
s1
-1
0
-3
1
s2
0
-2
-2
0
Z
4
12
18
0
PASO 5: Determinar la variable que sale (fila pivote)
s2
0
1
0
SOLUCI
N
-3
-5
0
Es el nmero ms negativo de la solucin de las restricciones = fila de S2
PASO 6: Determinar la variable que entra (columna pivote)
Razn = Coeficiente de Z / coeficiente fila pivote.
Razn Mayor = Columna X2 (-12 / 2)
Variable
Variables
bsica
x1
x2
x3
s1
s2
s1
s2
Z
-1
0
4
0
-2
12
-3
-2
18
1
0
0
0
1
0
SOLUCI
N
-3
-5
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
bsica
s1
s2
Z
razn
Variables
x1
-1
0
4
-4
x2
0
1
0
-
x3
-3
1
6
-2
s1
1
0
0
0
s2
0
-1
6
-
SOLUCIN
-3
2,5
-30
Se realizan nuevamente los pasos del 5 al 7 obteniendo como solucin final:
Variables
VB
s1
s2
Z
x1
x2
x3
s1
s2
0,33
-0,33
2
0
1
0
1
0
0
-0,33
0,33
2
0
-0,5
6
SOLUCI
N
1
1,5
-36
NOTA: No hay ms iteraciones cuando no existan soluciones con coeficientes
negativos.
R\ El valor mnimo 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
SOLUCIN
PASO 1
Se lleva el modelo a forma estndar. 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 solucin inicial en las variables de exceso
S1, S2 y S3.esta solucin inicial es INFACTIBLE.
X1
-15
-7,5
-5
315
X2
-2
-3
-2
110
X3
-1
-1
-1
50
S1
1
0
0
0
S2
0
1
0
0
S3
0
0
1
0
-200
-150
-120
0
PASO 2
Se selecciona el lado derecho "ms negativo" lo cual indicar cul de las actuales
variables bsicas deber abandonar la base. En el ejemplo el lado derecho ms
negativo se encuentra en la primera fila, por tanto S1 deja la base. Para determinar
cul de las actuales variables no bsicas (A, B, C) entrar a la base se busca el mnimo
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 bsica y S1 como no bsica.
X1
X2
X3
S1
S2
S3
15-Feb
15-Jan
0.0666666
40/3
-2
-
-0.5
-
7
-0.5
-
-50
1.3333333
0.6666666
0.3333333
-53.33333
3
68
7
29
3
21
-4.2
PASO 4
Continuar las realizando el mismo proceso hasta lograr una solucin bsica factible,
nos adelantamos y la solucin fue factible fue de acuerdo a la tabla a continuacin.
X1
1
0
0
0
X2
0
1
0
0
X3
0
0
1
0
S1
-0.1
4-Jan
0
4
S2
0
-1
2
10
S3
10-Jan
4-Mar
-3
36
LA SOLUCION QUE NOS RESULTO OPTIMA ES X1=8, X2=10, X3=60
8
10
60
-6.62
