Metodo Simplex
Metodo Simplex
Metodo Simplex
corresponda (mostrar/ocultar detalles)
Pasamos a construir la primera tabla de la Fase I del método de las Dos Fases.
Tabla
0 0 0 0 -1
1
P P
Base Cb P0 P1 P3 P5
2 4
P5 -1 2 -5 6 0 0 1
P3 0 12 0 12 1 0 0
P4 0 6 -3 2 0 1 0
Z -2 5 -6 0 0 0
Tabla
0 0 0 0 -1
2
P
Base Cb P0 P1 P2 P3 P5
4
P2 0 1/3 -5 / 1 0 0 1/6
6
P3 0 8 10 0 1 0 -2
-4 /
P4 0 16 / 3 0 0 1 -1 / 3
3
Z 0 0 0 0 0 1
Existe alguna solución posible para el problema, por lo que podemos pasar a la Fase II para calcularla.
Método Simplex
Tabla
-2 -6 0 0
1
Base Cb P0 P1 P2 P3 P4
-5 /
P2 -6 1/3 1 0 0
6
P3 0 8 10 0 1 0
-4 /
P4 0 16 / 3 0 0 1
3
Z -2 7 0 0 0
Método Gráfico
MINIMIZAR: 2 X1 + 6 X2
-5 X1 + 6 X2 = 2
0 X1 + 12 X2 ≤ 12
-3 X1 + 2 X2 ≤ 6
X1, X2 ≥ 0
NOTA:
En color verde los puntos en los que se encuentra la solución.
En color rojo los puntos que no pertenecen a la región factible.
Pasamos el problema a la forma estándar, añadiendo variables de exceso, holgura, y artificiales según
corresponda (mostrar/ocultar detalles)
Como la restricción 1 es del tipo '≥' se agrega la variable de exceso X3 y la variable artificial X6.
Como la restricción 2 es del tipo '≤' se agrega la variable de holgura X4.
Como la restricción 3 es del tipo '≤' se agrega la variable de holgura X5.
Pasamos a construir la primera tabla de la Fase I del método de las Dos Fases.
Tabla 0 0 0 0 0 -1
1
P P
Base Cb P0 P2 P4 P5 P6
1 3
P6 -1 4 4 4 -1 0 0 1
P4 0 12 0 3 0 1 0 0
P5 0 20 5 0 0 0 1 0
Z -4 -4 -4 1 0 0 0
Método Simplex
Tabla
4 5 0 0 0
1
P
Base Cb P0 P2 P3 P4 P5
1
P1 4 1 1 1 -1 / 4 0 0
P4 0 12 0 3 0 1 0
P5 0 15 0 -5 5/4 0 1
Z 4 0 -1 -1 0 0
Método Simplex
Operaciones intermedias (mostrar/ocultar detalles)
Tabla
4 5 0 0 0
2
P
Base Cb P0 P2 P3 P4 P5
1
P2 5 1 1 1 -1 / 4 0 0
P4 0 9 -3 0 3/4 1 0
P5 0 20 5 0 0 0 1
Z 5 1 0 -5 / 4 0 0
Método Simplex
Tabla
4 5 0 0 0
3
P
Base Cb P0 P2 P3 P4 P5
1
P2 5 4 0 1 0 1/3 0
P3 0 12 -4 0 1 4/3 0
P5 0 20 5 0 0 0 1
Z 20 -4 0 0 5/3 0
Método Simplex
Operaciones intermedias (mostrar/ocultar detalles)
Tabla
4 5 0 0 0
4
P
Base Cb P0 P1 P2 P4 P5
3
P2 5 4 0 1 0 1/3 0
P3 0 28 0 0 1 4/3 4/5
P1 4 4 1 0 0 0 1/5
Z 36 0 0 0 5/3 4/5
Método Gráfico
MAXIMIZAR: 4 X1 + 5 X2
4 X1 + 4 X2 ≥ 4
0 X1 + 3 X2 ≤ 12
5 X1 + 0 X2 ≤ 20
X1, X2 ≥ 0
O 0 0 0
A 0 1 5
B 1 0 4
C 0 4 20
D 4 4 36
E 4 0 16
NOTA:
En color verde los puntos en los que se encuentra la solución.
En color rojo los puntos que no pertenecen a la región factible.
PHPSimplex
Pasamos el problema a la forma estándar, añadiendo variables de exceso, holgura, y artificiales según
corresponda (mostrar/ocultar detalles)
Método Simplex
Tabla
10 8 0 0
1
P
Base Cb P0 P1 P3 P4
2
P3 0 20 5 4 1 0
P4 0 15 3 5 0 1
Z 0 -10 -8 0 0
Método Simplex
Tabla
10 8 0 0
2
Base Cb P0 P1 P2 P3 P4
P1 10 4 1 4/5 1/5 0
13 /
P4 0 3 0 -3 / 5 1
5
Z 40 0 0 2 0
Hay infinitos valores de X1, X2 para el valor óptimo Z = 40 , los cuales están contenidos en el segmento de la
recta 10 X1 + 8 X2 = 40 que cumple las restricciones del problema.
Una de ellas es:
X1 = 4
X2 = 0
Método Gráfico
MAXIMIZAR: 10 X1 + 8 X2
5 X1 + 4 X2 ≤ 20
3 X1 + 5 X2 ≤ 15
X1, X2 ≥ 0
O 0 0 0
A 0 5 40
B 4 0 40
C 3.0769230769231 1.1538461538462 40
D 0 3 24
E 5 0 50
NOTA:
En color verde los puntos en los que se encuentra la solución.
En color rojo los puntos que no pertenecen a la región factible.
Para la restriccion 1, dado que es = se agrega una variable de holgura rotulada como S0 con coeficiente 0 y
adicionalmente una variable artificial llamada 1 con coeficiente -M.
Para la restriccion 2 debido a que es <= se agrega una variable de holgura rotulada como S1 y se agrega en
la función objetivo con coeficiente 0
Para la restriccion 3 debido a que es <= se agrega una variable de holgura rotulada como S2 y se agrega en
la función objetivo con coeficiente 0
Inicio de Iteraciones
Entra la variable X2
Sale la variable: A1
- Ci -2 -6 0 0 -M
Cb Base X1 X2 S1 S2 A1 Bi Theta
-M A1 -5 6 0 0 1 2 0.33
0 S1 NaN 12 1 0 0 12 1
0 S2 -3 2 0 1 0 6 3
- Zj-Cj NaN 6 0 0 0 0
- Gran M 5 -6 0 0 0 -2
Solución Encontrada:
Z = -2
X1=0
X2=0.33
Nota: Los valores de las variables se pueden leer en la última tabla,
en la columna Bi para cada variable que este en la base. Si no esta, su valor es cero.
- Ci -2 -6 0 0 -M
Cb Base X1 X2 S1 S2 A1 Bi Theta
0 S1 NaN 0 1 0 -2 8 1
- Zj-Cj NaN 0 0 0 -1 -2
- Gran M 0 0 0 0 1 0
Max Z = 4X1+5X2
Sujeto a:
4X1+4X2>=4
+3X2<=12
5X1<=20
Para la restriccion 1, dado que es >= se agrega una variable de holgura rotulada como S1 con
coeficiente 0 y adicionalmente una variable artificial llamada 1 con coeficiente -M.
Para la restriccion 2 debido a que es <= se agrega una variable de holgura rotulada como S2 y se agrega en
la función objetivo con coeficiente 0
Para la restriccion 3 debido a que es <= se agrega una variable de holgura rotulada como S3 y se agrega en
la función objetivo con coeficiente 0
Inicio de Iteraciones
Entra la variable undefined
Max Z = 10X1+8X2
Sujeto a:
5X1+4X2<=20
3X1+5X2<=15
Para la restriccion 1 debido a que es <= se agrega una variable de holgura rotulada como S1 y se agrega en
la función objetivo con coeficiente 0
Para la restriccion 2 debido a que es <= se agrega una variable de holgura rotulada como S2 y se agrega en
la función objetivo con coeficiente 0
Inicio de Iteraciones
Entra la variable X1
Sale la variable: S1
- Ci 10 8 0 0
Cb Base X1 X2 S1 S2 Bi Theta
0 S1 5 4 1 0 20 4
0 S2 3 5 0 1 15 5
- Zj-Cj -10 -8 0 0 0
- Gran M 0 0 0 0 0
Solución Encontrada:
Z = 40
X1=4
X2=0
Nota: Los valores de las variables se pueden leer en la última tabla,
en la columna Bi para cada variable que este en la base. Si no esta, su valor es cero.
- Ci 10 8 0 0
Cb Base X1 X2 S1 S2 Bi Theta
10 X1 1 0.8 0.2 0 4 4
0 S2 0 2.6 -0.6 1 3 5
- Zj-Cj 0 0 2 0 40
- Gran M 0 0 0 0 0
Minimizar p = 2x + 6y sujeta a
-5x + 6y = 2
12y <= 12
-3x + 2y <= 6
Tabla #1
x y s1 s2 s3 s4 -p
-5 6 1 0 0 0 0 2
0 12 0 1 0 0 0 12
-3 2 0 0 1 0 0 6
-5 6 0 0 0 -1 0 2
2 6 0 0 0 0 1 0
Tabla #2
x y s1 s2 s3 s4 -p
0 0 1 0 0 1 0 0
10 0 0 1 0 2 0 8
7 0 0 0 0 1 1 -2
Maximizar p = 4x + 5y sujeta a
4x + 4y >= 4
3y <= 12
5x <= 20
Tabla #1
x y s1 s2 s3 p
4 4 -1 0 0 0 4
0 3 0 1 0 0 12
5 0 0 0 1 0 20
-4 -5 0 0 0 1 0
Tabla #2
x y s1 s2 s3 p
1 1 -0.25 0 0 0 1
0 3 0 1 0 0 12
0 -5 1.25 0 1 0 15
0 -1 -1 0 0 1 4
Tabla #3
x y s1 s2 s3 p
1 1 -0.25 0 0 0 1
-3 0 0.75 1 0 0 9
5 0 0 0 1 0 20
1 0 -1.25 0 0 1 5
Tabla #4
x y s1 s2 s3 p
0 1 0 0.333333 0 0 4
-4 0 1 1.33333 0 0 12
5 0 0 0 1 0 20
-4 0 0 1.66667 0 1 20
Tabla #5
x y s1 s2 s3 p
0 1 0 0.333333 0 0 4
0 0 1 1.33333 0.8 0 28
1 0 0 0 0.2 0 4
0 0 0 1.66667 0.8 1 36
5x + 4y <= 20
3x + 5y <= 15
Tabla #1
x y s1 s2 p
5 4 1 0 0 20
3 5 0 1 0 15
-10 -8 0 0 1 0
Tabla #2
x y s1 s2 p
1 0.8 0.2 0 0 4
0 2.6 -0.6 1 0 3
0 0 2 0 1 40