tareas uch

"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 variablessean 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 yresolver 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 tablasimplex.












"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 matrizA 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 optimalidad2) 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áficamentepositivo 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 =0Ejemplo:



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...