Metodo Simplex Dual
Método Simplex Dual Las reglas para el método símplex dual son muy parecidas a las del método símplex. De hecho, una v
Views 141 Downloads 5 File size 334KB
Recommend stories
- Author / Uploaded
- Génesis Acosta
- Categories
- Algoritmos y Estructuras de Datos
- Programación de computadoras
- Análisis
- Algoritmos
- Áreas de informática
Citation preview
Método Simplex Dual
Las reglas para el método símplex dual son muy parecidas a las del método símplex. De hecho, una vez que se inician, la única diferencia entre ellos es el criterio para elegir las variables que entran y salen y la regla para detener el algoritmo.
Para dar inicio al método símplex dual todos los coeficientes en la ecuación (0) deben ser no negativos (de manera que la solución básica sea superóptima). El método continua haciendo que el valor de la función objetivo disminuya, y conserva siempre coeficientes no negativos en la ecuación (0), hasta que todas las variables sean no negativas.
Resumen del método símplex-dual
Paso inicial: Se introducen las variables de holgura necesarias para construir un conjunto de ecuaciones que describan el problema. Se encuentra una solución básica tal que los coeficientes de la ecuación (0) sean ceros para las variables básicas y no negativos para las variables no básicas. Se lleva acabo la prueba de optimalidad.
Paso Iterativo:
Parte 1 Se determina la variable básica que sale de la base, seleccionando aquella que tenga el valor negativo más grande en valor absoluto.
Parte 2 Se determina la variable básica que entra a la base: Se elige a aquella cuyo coeficiente en la ecuación (0) llegue primero a cero al agregar a la ecuación cero un múltiplo creciente de la ecuación que contiene a la variable básica que sale. Esta elección se hace examinando las variables no básicas con coeficientes negativos en esa ecuación (la que contiene la variable básica que sale) y escogiendo la que tiene el cociente más pequeño dado por el coeficiente de la ecuación (0) entre el valor absoluto del coeficiente en esa ecuación.
Parte 3 Se determina la nueva solución básica: se comienza con el conjunto actual de ecuaciones y se despejan las variables básicas en términos de las no básicas mediante el método de eliminación de Gauss–Jordan.
Método símplex dual aplicado al problema dual de la WG
Ejemplo 1 Maximizar Sujeta a:
– Z = – 4y1 – 12y2 – 18y3 y1
+ 3y3 3 2y2 + 2y3 5
y1 0 , y2 0 , y 3 0
Agregando variables de holgura – Z + 4y1 + 12y2 + 18y3 = 0 – y1 – 3y3 + y4 = –3 – 2y2 – 2y3 + y5 = – 5
Tabla Simplex-Dual
Coeficiente de Iteración Variable Número Básica Ecuación
Z
Y1
Y2
Y3
Y4
Y5
Lado Derecho
Z
0
-1
4
12
18
0
0
0
Y4
1
0
-1
0
-3
1
0
-3
Y5
2
0
0
-2
-2
0
1
-5
Z
0
-1
4
0
6
0
6
-30
Y4
1
0
-1
0
-3
1
0
-3
Y2
2
0
0
1
1
0
-0,5
2,5
Z
0
-1
2
0
0
2
6
-36
0
0,333 3
0
1
-0,333
0
1
0
0,333 3
-0,5
1,5
0
1
2
Y3 Y2
1 2
0
-0,333
1
Ejemplo 2 Resolver por el método simplex-dual el siguiente programa lineal. Mínimizar
Sujeto a
Z = 2X1 + X2 3X1 + X2
3
4X1 + 3X2
6
X1 + 2X2
3
X 1 0 , X2 0
Reescribiendo este programa Máximizar
– Z = – 2X1 – X2
Sujeto a – 3X1 – X2 + X3
= –3
– 4X1 – 3X2 + X4
= –6
– X1 – 2X2 + X5
= –3
X1 0 , X2 0 , X3 0 , X4 0 , X5 0
Tabla Simplex-Dual
Coeficiente de
Iteración
0
Variable Básica
Número Ecuación
Z
0
X3
1
X4
2
X5
3
Z
X1
X2
X3
X4
X5
Lado Derecho
-1
2
1
0
0
0
0
0
-3
-1
1
0
0
-3
0
-4
-3
0
1
0
-6
0
-1
-2
0
0
1
-3
Tabla Primera Iteración
Coeficiente de
Iteración Variable Número Básica Ecuación
Z
X1
X2
X3
X4
X5
Lado Derecho
Z
0
-1
2/3
0
0
1/3
0
-2
X3
1
0
-1 2/3
0
1
- 1/3
0
-1
X2
2
0
1 1/3
1
0
- 1/3
0
2
X5
3
0
1 2/3
0
0
- 2/3
1
1
1
Tabla Segunda Iteración
Coeficiente de
Iteración Variable Número Básica Ecuación
Z
X1
X2
X3
X4
X5
Lado Derecho
Z
0
-1
0
0
2/5
1/5
0
-2 2/5
X1
1
0
1
0
- 3/5
1/5
0
3/5
X4
2
0
0
1
4/5
- 3/5
0
1 1/5
X5
3
0
0
0
1
-1
1
0
2
Tabla Final Coeficiente de
Iteración
0
1
2
Variable Básica
Número Ecuación 0
Z -1
X1 2
X2 1
X3 0
X4 0
X5 0
Lado Derecho 0
Z X3
1
0
-3
-1
1
0
0
-3
X4
2
0
-4
-3
0
1
0
-6
X5
3
0
-1
-2
0
0
1
-3
Z
0
-1
2/3
0
0
1/3
0
-2
X3
1
0
-1 2/3
0
1
- 1/3
0
-1
X2
2
0
1 1/3
1
0
- 1/3
0
2
X5
3
0
1 2/3
0
0
- 2/3
1
1
Z
0
-1
0
0
2/5
1/5
0
-2 2/5
X1
1
0
1
0
- 3/5
1/5
0
3/5
X2
2
0
0
1
4/5
- 3/5
0
1 1/5
X5
3
0
0
0
1
-1
1
0