Algoritmos

"MÉTODO FRACCIONAL DE GOMORY"

Este método solo resuelve modelos enteros puros y consta de los siguientes pasos:

1.- Resolver el modelo relajado, es decir, que las variables sean continuas.

2.- Si el resultado es entero, entonces ya se tiene la solución optima, si no seguir con el método.

3.- Seleccionar el max ( XBi – [XBi] ) incluyendo al renglon Zj - Cj , fraccionario y generar un nuevo corte o nueva restricción:

∑ (aij – [aij])xj ≥ (xBi – [xBi])

añadir este corte como una nueva restricción y resolver utilizando el método Dual Simplex; ir al paso 2.

Nota: Z es entero si y solo si los coeficientes de la función objetivo son enteros y asi utilizar al renglon Zj - Cj en la tabla simplex.

"MÉTODO PURO DE GOMORY"

El algoritmo puro de Gomory es una variación del método fraccional de Gomory, al igual que este método la matriz A debe ser entera. Además debe cumplir las condiciones para aplicar el método dual simplex (optimalidad inicial y al menos un negativo en la solución):

1) Condición de optimalidad

2) Valor de variable básica < 0.

Definición: Un vector es lexicográficamente positivo si el primer componente diferente de cero es positivo. Cuando un vector X es lexicográficamente positivo se escribe X}0.

Ejemplo:

X= (0. 3, -2, 9) X = 0

X = (0,0,-3,12) X no es 0

Definición: un vector X es lexicográficamente mayor que otro vector Y si X - Y =0

Ejemplo:

X = (0, 3, -2)

Y = (1, 2, 2)

X – Y = (-1, 1, -4)

X

...