Metodo 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 restricciones del 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 entera
En 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.
Funciona resolviendo 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 …ver más…
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: