algoritmo gomory

Algoritmo fraccionario puro de Gomory
Max Z = 7x1 + 9x2

-x1 + 3x2 ≤ 6
7x1 + x2 ≤ 35
xi ∈ N , ∀i





7
9
0
0



X1
X2
X3
X4
0
X3
6
-1
3
1
0
0
X4
35
7
1
0
10
-7
-9
0
0




7
9
0
0



X1
X2
X3
X4
9
X2
2
-1/3
1
1/3
0
0
X4
33
22/3
0
-1/3
1


18
-10
0
3
0




7
9
0
0



X1
X2
X3
X4
9
X2
7/2
0
17/22
1/22
7
X1
9/2
1
0
-1/22
3/22


63
0
0
28/11
15/11

Llegamos a la conclusión de que es una solución no entera con:
X1 = 9/2 y x2 = 7/2
Ya que es una solución no entera, se generaun corte basándose en el renglón de la variable básica que contenga la mayor parte fraccionaria
Renglon
Bi – [bi]
1
½
2
1/2

(7/22 - [7/22])x3 + (1/22 - [1/22])x4 ≥ (7/2 - [7/2])
Por lo queel corte seria finalmente:
- 7/22 x3 - 1/22 x4 ≤ - ½
Ya por ultimo agregamos la última tabla optima, el corte generado en el paso anterior como una nueva restricción y se encuentra una nuevasolución óptima.



7
9
0
0
0



X1
X2
X3
X4
X5
9
X2
7/2
0
1
7/22
1/22
0
7
X1
9/2
1
0
-1/22
3/22
0
0
X5
-1/2
0
0
-7/22
-1/22
1


63
0
0
28/11
15/11
0

Deacuerdo con el procedimiento Dual-Simplex, sale x5 por ser negativa.
La variable de entrada se obtiene por





7
9
0
0
0



X1
X2
X3
X4
X5
9
X2
3
0
1
0
0
1
7
X1
32/7
10
0
1/7
-1/7
0
X3
11/7
0
0
1
1/7
-22/7


59
0
0
0
1
8




Como la solución del paso anterior no es entera, se genera un nuevo corte basándose en el renglón de la variablebásica que contenga la mayor parte fraccionaria
Renglon
bi - [bi]
2
4/7
3
4/7

Como son dos fracciones iguales: el corte se hace con cualquier de los dos renglones. En este caso se seleccionara elrenglón 2 .
(1/7 - [1/7])x4 + (- 1/7 - [- 1/7])x5 ≥ (32/7 - [32/7])
Por lo que el nuevo corte será: - 1/7 x4 - 6/7 x5 ≤ - 4/7
El siguiente paso es agregar la última tabla optima, el corte...