Metodo Simplex, Investigation de operaciones
Emmanuel MoyaTutorial17 de Noviembre de 2021
5.500 Palabras (22 Páginas)131 Visitas
METODO SIMPLEX
- El método simplex analiza solo soluciones factibles de los vértices
- El método simplex es un algoritmo iterativo (un procedimiento de solución sistemática) que repite una serie de pasos, hasta que obtiene el resultado.
Iniciación
[pic 1]
Prueba de optimilidad [pic 2][pic 3]
[pic 4]
No
Iteración[pic 5]
Si
Termina
Ejemplo del Simplex ≤
Max Z = 3 X1 + 5 X2
Sujeto a X1 ≤ 4
X2 ≤ 12
3 X1 + 2 X2 ≤ 18
1º Paso: las restricciones factibles de desigualdad se convierten en igualdad.
Max Z = 3 X1 + 5 X2
Sujeto a X1 = 4
X2 = 12
3 X1 + 2 X2 = 18
2º paso: se introducen las variables de holguras (S), Al introducir las variables de holgura se dice que el modelo se ha aumentado
Max Z = 3 X1 + 5 X2
Sujeto a X1 + S1 = 4 Ec(1)
X2 + S2 = 12 Ec(2)
3 X1 + 2 X2 + S3 = 18 Ec(3)
S1 = S2 = S3 = 0, acompañadas del signo +, coeficiente 1
.3º Paso: se aumenta la función objetivo:
Max Z = 3 X1 + 5 X2 - 0 S1 - 0 S2 - 0 S3
Las variables de holgura están acompañadas del signo -, coeficiente 0
4º Paso: la función objetivo se hace cero:
Max Z - 3 X1 - 5 X2 + 0 S1 + 0 S2 + 0 S3 = 0 Ec(0)
5º paso: tabular: iteración 0
Variables iniciales: Variables decisión (X1, X2), Variables Básicas (Z, S1, S2, S3)
[pic 6]
[pic 7]
Variables básicas | Ecuación | Coeficientes | Lado derecho | |||||
Z | X1 | X2 | S1 | S2 | S3 | |||
Z | 0 | 1 | -3 | -5 | 0 | 0 | 0 | 0 |
S1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 4[pic 8][pic 9] |
S2[pic 10] | 2 | 0 | 0 | 2[pic 11] | 0 | 1 | 0 | 12 |
S3[pic 12] | 3 | 0 | 3[pic 13] | 2 | 0 | 0 | 1 | 18 |
[pic 14][pic 15]
- Hay que determinar la variable entrante, la que tiene el coeficiente negativo más alto (X2). Luego se coloca un recuadro debajo del coeficiente y se llama columna pivote.
b. La variable saliente se busca por el cociente mínimo. Se divide los coeficientes del lado derecho entre los coeficientes de la columna pivote (siempre debe ser mayor que cero) y se selecciona el mínimo valor, esa sería la variable saliente.
Iteración 1[pic 16]
[pic 17]
Variables básicas | Ecuación | Coeficientes | Lado derecho | |||||
Z | X1 | X2 | S1 | S2 | S3 | |||
Z | 0 | 1 | - 3 | 0 | 0 | 5/2 | 0 | 30 |
S1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 4 |
X2 | 2 | 0 | 0 | 1 | 0 | 1/2 | 0 | 6 |
S3[pic 18][pic 19] | 3 | 0 | 3 | 0 | 0 | - 1 | 1 | 6 |
- X2 sustituye a S2. Luego se divide el renglón pivote entre en número pivote, para obtener el valor se X2.
c. el valor de Z1, se calcula así: Z0 + 5 X2, 5, es el coeficiente de intercepción de Z y X2 siempre en el cálculo de Z se suma
- el valor se S1,1 = S1,0 - 0 X2, 0 es el coeficiente de intercepción de S1,0 , y X2
e. el valor de S3,1 = S3,0 - 2 X2, 2 es el coeficiente de intercepción de S3,0 , y X2
f. nueva variable entrante X1 , variable saliente S3
nota: cuando el valor en la columna pivote es positivo (+), para hallar el valor de la nueva variable se resta (-), sin embargo cuando el valor es negativo (-) se suma (+)
iteración 2
Variables básicas | Ecuación | Coeficientes | Lado derecho | |||||
Z | X1 | X2 | S1 | S2 | S3 | |||
Z | 0 | 1 | 0 | 0 | 0 | 3/2 | 1 | 36 |
S1 | 1 | 0 | 0 | 0 | 1 | 1/3 | -1/3 | 2 |
X2 | 2 | 0 | 0 | 1 | 0 | 1/2 | 0 | 6 |
X1 | 3 | 0 | 1 | 0 | 0 | -1/3 | 1/3 | 2 |
...