Metodo Gomory

METODO DE GOMORY
Gomory fue el primer creador del algoritmo para resolver métodos de programación entera, el algoritmo de gomory consiste en resolver el problema sin considerar las restriccionesdel carácter entero de las variables y si la solución no es entera añade restricciones que reduce el conjunto de soluciones del problema lineal continuo asociado, sin excluir ninguna solución enteraEn matemática, y más en concreto en optimización, el método de los planos de corte es un procedimiento para encontrar soluciones enteras de un problema lineal. Fue introducido por Gomory.
Funcionaresolviendo un programa lineal no entero, después comprobando si la optimización encontrada es también una solución entera. Si no es así, es añadida una nueva restricción que corta la solución no enterapero no corta ningún otro punto de la región factible. Esto se repite hasta que se encuentra la solución entera óptima .
Interpretación geométrica, una restricción es equivalente a un hiperplano,permitiendo solo soluciones en uno de los lados del plano.

CORTES GOMORY
Tengo una solución x admisible y tengo una base B asociada a x tal que

  

Si tengo una solución fraccionaria entoncestengo un elemento enésimo de x fraccionario.

 

  

"MÉTODO FRACCIONAL DE GOMORY"
Este método solo resuelve modelos enteros puros y consta de los siguientes pasos:
1.- Resolver elmodelo 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 cortecomo 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...