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 no es lexicográficamente mayor que Y

X - Y = 0, por tanto Y es lexicográficamente mayor que X.

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

Los pasos del método son:

1) Elige la XBi más negativa. Se designa a esa fila con r. Si el método dual simplex genera un pivote -1, aplicar el método dual simplex. Si no continuar con el método.

2) Elige aquella columna no-básica con arj<0 que sea lexicográficamente la menor. Se designa una columna por k. Al primer elemento distinto de cero de dicha columna se le designa por apk(>0) siendo su fila correspondiente la p.

3) Para la columna arj<0 se calcula el índice uij = [akj/apk] si es que apj es el primer elemento diferente de cero en la columna j. De otra manera uj=∞.

4) Se calcula λ=max [ !arj! / uj ]para arj<0 y uj≠∞.

5) Se deriva el corte:

6) Se anexa este a la tabla junto con su variable de holgura correspondiente y se aplica el método dual simplex sobre el entero. Si el resultado es XB≥0 entonces se tiene la solución óptima, si no ir al paso 1.

...