Algoritmos
Enviado por tefi23 • 30 de Diciembre de 2012 • 576 Palabras (3 Páginas) • 389 Visitas
"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]
...