• Author / Uploaded
• Jesus Yano Hernandez

• Categories
• Análisis matemático
• Áreas de informática
• Conceptos matemáticos
• Matemáticas Aplicadas
• Algoritmos

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

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 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

Variables

básica

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 básica s1 s2 Z razón

Variables x1 -1 0 4 -4

x2 0 1 0 -

x3 -3 1 6 -2

s1 1 0 0 0

s2 0 -1 6 -

SOLUCIÓN -3 2,5 -30

Se realizan nuevamente los pasos del 5 al 7 obteniendo como solución 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 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 -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 "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

0

0

40/3

0

-2 -

-0.5 -

7 -0.5 -

1

0

-50

0

1.3333333

0.6666666

0.3333333

0

1

-53.33333

0

3 68

7 29

3 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 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